Abstract
The CPT planner bridges the gap between the flexible branching of Partial Order Causal Link (POCL) planning and the aggressive pruning power of modern SAT/CSP-based planners. By formulating planning as a Constraint Programming (CP) problem that reasons about actions before they are even added to a plan, it achieves state-of-the-art performance in finding optimal temporal plans.
Introduction
In automated planning, two classic paradigms have long dominated. State-space planners navigate through world states, utilizing strong heuristics to prune search trees but often struggling with complex temporal constraints and parallel action execution. Conversely, Partial Order Causal Link (POCL) planners build plans by identifying and resolving "flaws" (e.g., unsatisfied preconditions). While POCL is naturally suited for temporal planning, it has historically been plagued by search space explosions due to a lack of early pruning mechanisms.
CPT addresses this efficiency gap by integrating the flexibility of POCL with the robust pruning power of modern optimal planners like Graphplan or Blackbox. The result is a domain-independent optimal temporal planner that leverages Constraint Programming to navigate the search space more effectively.
Methodology
CPT introduces several core innovations to the POCL framework:
- Reasoning about the Unseen: Traditional POCL planners only reason about actions already present in a partial plan. CPT, however, creates variables for all possible actions in a domain. It uses constraints to determine if an action must be included in the plan ($InPlan(a)$) and its corresponding start time ($T(a)$).
- Constraint Propagation: CPT employs pruning rules based on temporal distances and "structural mutexes"—actions that cannot occur simultaneously. If the solver determines an action's required start time exceeds the plan's time bound, it can prune that action or the entire search branch immediately.
- Canonical Plan Assumption: To manage complexity, CPT focuses on "canonical plans" where each ground action is executed at most once. This assumption holds for most standard benchmarks and simplifies the mapping between actions and plan occurrences.
- Heuristic Lower Bounds: The planner integrates $h^2_T$ heuristics, providing admissible lower bounds on the time required to reach goals, which further constrains the search space.
- Mutex Sets: Interfering actions are grouped into sets. If the cumulative time required for actions in a set exceeds the available time window, the current partial plan is identified as a dead-end.
Experimental Evaluation
The planner was evaluated using standard benchmarks from the 3rd International Planning Competition (IPC) and other classic domains, including Logistics, Blocks World (bw-large), ZenoTravel, DriverLog, and Satellite.
Key Insights
A significant finding is the power of CPT's inference engine. In specific "stress test" domains like TOWER-n, the planner can often find optimal plans through pure inference, expanding zero search nodes. Furthermore, by "lifting" causal link constraints—reasoning about the set of possible supporters for a precondition—CPT can prune impossible supporters much earlier than traditional methods. The branching heuristic also utilizes "slack" (the difference between latest and earliest start times), focusing on the most constrained parts of the problem first.
Results
CPT demonstrates substantial performance gains over previous optimal temporal planners like TP4. As shown in the temporal problem benchmarks, TP4 frequently times out while CPT solves the same instances in seconds.
In parallel planning scenarios where actions have unit duration, CPT remains highly competitive with top-tier planners like Blackbox and IPP. Notably, CPT successfully scales to larger instances of the bw-large and satellite domains that other optimal planners fail to solve within a one-hour time limit.
Conclusion and Future Work
While CPT represents a significant advancement, it currently assumes actions occur at most once. Future work involves implementing a "cloning" mechanism to handle complex temporal problems requiring repeated actions. Additionally, the authors aim to further align CPT's semantics with the PDDL 2.1 standard regarding overlapping interfering actions. As an optimal planner, CPT prioritizes finding the shortest possible plan, which may introduce overhead compared to satisficing planners on extremely large-scale problems; however, its current performance sets a new benchmark for optimal temporal planning.
Summary updated