CPT

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).