Inferring State Constraints for Domain-Independent Planning

Abstract

We describe some new preprocessing techniques that enable faster domain-independent planning. The first set of techniques is aimed at inferring state constraints from the structure of planning operators and the ini-tial state. Our methods consist of generating hy-pothetical state constraints by inspection of opera-tor effects and preconditions, and checking each hy-pothesis against all operators and the initial condi-tions. Another technique extracts (supersets of) pred-icate domains from sets of ground literals obtained by Graphplan-like forward propagation from the ini-tial state. Our various techniques are implemented in a package called DISCOPLAN. We show prelimi-nary results on the effectiveness of adding computed state constraints and predicate domains to the spec-ification of problems for SAT-based planners such as SATPLAN or MEDIC. The results suggest that large speedups in planning can be obtained by such au-tomated methods, potentially obviating the need for adding hand-coded state constraints.