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

Abstract

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.