On Computing Conformant Plans Using Classical Planners: A Generate-And-Complete Approach


  • Khoi Nguyen New Mexico State University
  • Vien Tran New Mexico State University
  • Tran Son New Mexico State University
  • Enrico Pontelli New Mexico State University




generate and complete, combining oneof


The paper illustrates a novel approach to conformant planning using classical planners. The approach relies on two core ideas developed to deal with incomplete information in the initial situation: the use of a classical planner to solve non-classical planning problems, and the reduction of the size of the initial belief state. Differently from previous uses of classical planners to solve non-classical planning problems, the approach proposed in this paper creates a valid plan from a possible plan---by inserting actions into the possible plan and maintaining only one level of non-deterministic choice (i.e., the initial plan being modified). The algorithm can be instantiated with different classical planners---the paper presents the GC[LAMA] implementation, whose classical planner is LAMA. We investigate properties of the approach, including conditions for completeness. GC[LAMA] is empirically evaluated against state-of-the-art conformant planners, using benchmarks from the literature. The experimental results show that GC[LAMA] is superior to other planners, in both performance and scalability. GC[LAMA] is the only planner that can solve the largest instances from several domains. The paper investigates the reasons behind the good performance and the challenges encountered in GC[LAMA].




How to Cite

Nguyen, K., Tran, V., Son, T., & Pontelli, E. (2012). On Computing Conformant Plans Using Classical Planners: A Generate-And-Complete Approach. Proceedings of the International Conference on Automated Planning and Scheduling, 22(1), 190-198. https://doi.org/10.1609/icaps.v22i1.13498