Solving Classical AI Planning Problems Using Planning-Independent CP Modeling and Search


  • Behrouz Babaki Polytechnique Montréal
  • Gilles Pesant Polytechnique Montréal
  • Claude-Guy Quimper Laval University


The combinatorial problems that constraint programming typically solves belong to the class of NP-hard problems. The AI planning community focuses on even harder problems: for example, classical planning is PSPACE-hard. A natural and well-known constraint programming approach to classical planning solves a succession of fixed plan-length problems, but with limited success. We revisit this approach in light of recent progress on general-purpose branching heuristics. We conduct an empirical comparison of our proposal against state-of-the-art planners.