Heuristic search is one of the most successful approaches to classical planning, finding solution paths in large state spaces. A major focus has been the development of domain-independent heuristic functions. One recent method are partial delete relaxation heuristics, improving over the standard delete relaxation heuristic through imposing a set C of conjunctions to be treated as atomic. Practical methods for selecting C are based on counter-example guided abstraction refinement, where iteratively a relaxed plan is checked for conflicts and new atomic conjunctions are introduced to address these. However, in each refinement step, the choice of possible new conjunctions is huge. The literature so far offers merely one simple strategy to make that choice. Here we fill that gap, considering a sizable space of basic ranking strategies as well as combinations thereof. We furthermore devise ranking strategies for conjunction-forgetting, where the ranking pertains to the current conjunctions and thus statistics over their usefulness can be maintained. Our experiments show that ranking strategies do make a large difference in performance, and that our new strategies can be useful.

Heuristic search is one of the most successful approaches to classical planning, finding solution paths in large state spaces. A major focus has been the development of domain-independent heuristic functions. One recent method are partial delete relaxation heuristics, improving over the standard delete relaxation heuristic through imposing a set C of conjunctions to be treated as atomic. Practical methods for selecting C are based on counter-example guided abstraction refinement, where iteratively a relaxed plan is checked for conflicts and new atomic conjunctions are introduced to address these. However, in each refinement step, the choice of possible new conjunctions is huge. The literature so far offers merely one simple strategy to make that choice. Here we fill that gap, considering a sizable space of basic ranking strategies as well as combinations thereof. We furthermore devise ranking strategies for conjunction-forgetting, where the ranking pertains to the current conjunctions and thus statistics over their usefulness can be maintained. Our experiments show that ranking strategies do make a large difference in performance, and that our new strategies can be useful.

Heuristic functions based on the delete relaxation compute upper and lower bounds on the optimal delete-relaxation heuristic h+, and are of paramount importance in both optimal and satisficing planning. Here we introduce a principled and flexible technique for improving h+, by augmenting delete-relaxed planning tasks with a limited amount of delete information. This is done by introducing special fluents that explicitly represent conjunctions of fluents in the original planning task, rendering h+ the perfect heuristic h* in the limit. Previous work has introduced a method in which the growth of the task is potentially exponential in the number of conjunctions introduced. We formulate an alternative technique relying on conditional effects, limiting the growth of the task to be linear in this number. We show that this method still renders h+ the perfect heuristic h* in the limit. We propose techniques to find an informative set of conjunctions to be introduced in different settings, and analyze and extend existing methods for lower-bounding and upper-bounding h+ in the presence of conditional effects. We evaluate the resulting heuristic functions empirically on a set of IPC benchmarks, and show that they are sometimes much more informative than standard delete-relaxation heuristics.

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.