This is a joint work with Héctor Geffner.

CPT (which stands for "Constraint Programming Temporal planner") is a planning system for optimal temporal STRIPS planning. It combines a branching scheme based on Partial Order Causal Link (POCL) Planning with powerful and sound pruning rules implemented as constraints.

The development of CPT is motivated by the limitation of heuristic state approaches to parallel and temporal planning that suffer from a high branching factor (cf. HSP* family of planners) and thus have difficulties matching the performance of planners built on SAT techniques such as SATPLAN. In CPT, all branching decisions (resolution of open supports, support threats, and mutex threats), generate binary splits, and nodes in the search correspond to "partial plans" very much as in POCL planning.

The CPT planner is implemented using the Choco CP library that operates on top of Claire, a high-level programming language that compiles into C++. Further details can be found in the AAAI-2004 paper that is concerned mostly with the computation of optimal canonical plans; plans where no ground action is done more than once. The version of CPT on this page removes this restriction, and computes optimal temporal plans, whether canonical or not. Currently, the semantics of these plans follows the one in (Smith and Weld, IJCAI-99) where interfering actions are not allowed to overlap in time. This condition has been relaxed in PDDL 2.1 where interfering actions may overlap sometimes (e.g., when preconditions do not have to be preserved throughout the execution of the action).


This work has been published at the AAAI-2004 conference, at the Workshop on "Integrating Planning Into Scheduling" WIPIS-2004 held in conjunction with ICAPS-2004 [ps] [ps.gz] [pdf] and in the Artificial Intelligence Journal [ps] [ps.gz] [pdf]. It is also published in the french conference JNPC-2004 [ps] [ps.gz] [pdf].



You can find here the source code and some binary versions of our planning system. The source package also contains the original source code of Claire required for the compilation of CPT, plus the tailored version of Choco that we use. It should compile on any platform where Claire can be compiled, that is at least Linux, Windows, Solaris...