Conformant Planning for Domains with Constraints-a New Approach

Abstract

The paper presents a pair of new conformant planners, CPApc and CPAph, based on recent developments in theory of action and change. As an input the planners take a domain descrip-tion D in action language AL which allows state constraints (non-stratified axioms), together with a set of CNF formulae describing the initial state, and a set of literals representing the goal. We propose two approximations of the transition diagram T defined by D. Both approximations are deter-ministic transition functions and can be computed efficiently. Moreover they are sound (and sometimes complete) with re-spect to T. In its search for a plan, an approximation based planner analyses paths of an approximation instead of that of T. CPApc and CPAph are forward, best first search plan-ners based on this idea. We compare them with two state-of-the-art conformant planners, KACMBP and Conformant-FF (CFF), over benchmarks in the literature, and over two new domains. One has large number of state constraints and another has a high degree of incompleteness. Our planners perform reasonably well in benchmark domains and outper-form KACMBP and CFF in the first domain while still work-ing well with the second one. Our experimental result shows that having an integral part of a conformant planner to deal with state constraints directly can significantly improve its performance, extending a similar claim for classical planners