CPlan: A Constraint Programming Approach to Planning

Abstract

Constraint programming, a methodology for solving diffi-cult combinatorial problems by representing them as con-straint satisfaction problems, has shown that a general pur-pose search algorithm based on constraint propagation com-bined with an emphasis on modeling can solve large, prac-tical scheduling problems. Given the success of constraint programming on scheduling problems and the similarity of scheduling to planning, the question arises, would a con-straint programming approach work as well in planning? In this paper, we present evidence that a constraint programming approach to planning does indeed work well and has the ad-vantage in terms of time and space efficiency over the current state-of-the-art planners.