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, SAT heuristics for STRIPS planning have been introduced. In this work we show that the basic ideas in the heuristic can be gen-eralized to actions with conditional effects but without dis-junction, and that disjunction requires a more fundamental analysis of the STRIPS heuristic, which, despite complica-tions, will still lead to a natural heuristic which can be imple-mented efficiently. The experimental analysis shows substan-tial and systematic improvements over the state of the art in planning with SAT with ADL