Conformant Planning for Domains with Constraints — A New Approach

Tran C. Son, Phan H. Tu, Michael Gelfond, Ricardo A. Morales

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 description 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 deterministic transition functions and can be computed efficiently. Moreover they are sound (and sometimes complete) with respect 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 planners 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 outperform KACMBP and CFF in the first domain while still working 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 in (Thiebaux, Hoffmann, & Nebel 2003).

Content Area: 16. Planning and Scheduling

Subjects: 1.11 Planning; 11. Knowledge Representation

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.