Enhanced Symmetry Breaking in Cost-Optimal Planning as Forward Search


  • Carmel Domshlak Technion
  • Michael Katz Saarland University
  • Alexander Shleyfman Technion




symmetry, heuristic search


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

Domshlak, C., Katz, M., & Shleyfman, A. (2012). Enhanced Symmetry Breaking in Cost-Optimal Planning as Forward Search. Proceedings of the International Conference on Automated Planning and Scheduling, 22(1), 343-347. https://doi.org/10.1609/icaps.v22i1.13531