Heuristics for Planning with SAT and Expressive Action Definitions
We present the first effective SAT heuristics for planning with expressive planning languages such as ADL. Recently, first SAT heuristics for STRIPS planning have been introduced. These heuristics seem to -- at least at a superficial level -- rely on the simple properties of STRIPS actions, most notably the lack of disjunctions and conditional effects. In this work we show that the basic ideas in the STRIPS heuristic can be generalized to actions with conditional effects but without disjunction, and that disjunction requires a more fundamental analysis of the STRIPS heuristic, which, despite complications, will still lead to a natural heuristic which can be implemented efficiently. The experimental analysis shows substantial and systematic improvements over the state of the art in planning with SAT with ADL.