When planning for tasks that feature both state-dependent action costs and conditional effects using relaxation heuristics, the following problem appears: handling costs and effects separately leads to worse-than-necessary heuristic values, since we may get the more useful effect at the lower cost by choosing different values of a relaxed variable when determining relaxed costs and relaxed active effects. In this paper, we show how this issue can be avoided by representing state-dependent costs and conditional effects uniformly, both as edge-valued multi-valued decision diagrams (EVMDDs) over different sets of edge values, and then working with their product diagram. We develop a theory of EVMDDs that is general enough to encompass state-dependent action costs, conditional effects, and even their combination.We define relaxed effect semantics in the presence of state-dependent action costs and conditional effects, and describe how this semantics can be efficiently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.

We adapt the relaxation heuristics h max , h add and h FF to interval based numeric relaxation frameworks, combining them with two different relaxation techniques and with two different search techniques. In contrast to previous approaches, the heuristics presented here are not limited to a subset of numeric planning and support action costs.

Similarly to classical planning, in MA-Strips multiagent planning, heuristics significantly improve efficiency of search-based planners. Heuristics based on solving a relaxation of the original planning problem are intensively studied and well understood. In particular, frequently used is the delete relaxation, where all delete effects of actions are omitted. In this paper, we present a unified view on distribution of delete relaxation heuristics for multiagent planning. Until recently, the most common approach to adaptation of heuristics for multiagent planning was to compute the heuristic estimate using only a projection of the problem for a single agent. In this paper, we place such approach in the context of techniques which allow sharing more information among the agents and thus improve the heuristic estimates. We thoroughly experimentally evaluate properties of our distribution of additive, max and Fast-Forward relaxation heuristics in a planner based on distributed Best-First Search. The best performing distributed relaxation heuristics favorably compares to a state-of-the-art MA-Strips planner in terms of benchmark problem coverage. Finally, we analyze impact of limited agent interactions by means of recursion depth of the heuristic estimates.

The currently dominant approach to domain-independent planning is planning as heuristic search, with most successful planning heuristics being based on solutions to delete-relaxed versions of planning problems, in which the negative effects of actions are ignored. We introduce a principled, flexible, and practical technique for augmenting delete-relaxed tasks with a limited amount of delete information, by introducing special fluents that explicitly represent conjunctions of fluents in the original planning task. Differently from previous work, conditional effects are used to limit the growth of the task to be linear in the number of such conjunctions, making its use for obtaining heuristic functions feasible. The resulting heuristics are empirically evaluated, and shown to be some- times much more informative than standard delete-relaxation heuristics.