Introduction
In automated planning, the goal is often to generate plans that can be executed efficiently. While sequential plans are straightforward, partially ordered plans allow independent actions to run in parallel, thereby reducing the total execution time, or makespan. Historically, the research community has oscillated between two formalisms: Partial Order (PO) plans, which define simple ordering constraints, and Partial Order Causal Link (POCL) plans, which explicitly map how one action's effects satisfy another's preconditions.
For years, it was widely assumed these two were interchangeable. This research investigates whether they are truly equivalent regarding makespan and examines the computational complexity of optimizing these plans by removing unnecessary constraints (deordering).
Structural Differences vs. Makespan Equivalence
The authors first demonstrate that PO and POCL plans are not structurally identical. POCL plans are more restrictive because every precondition must be explicitly linked to a specific producer. This requirement can eliminate "white knight" scenarios—flexible arrangements where one action deletes a condition but another restores it before it is needed.
Despite this structural gap, the paper provides a significant positive result: makespan equivalence. The authors introduce a polynomial-time algorithm that converts any PO plan into a POCL plan without increasing the total execution time. This proves that while POCL plans are more "explained," they do not inherently sacrifice parallel efficiency.
The Complexity of Deordering
While converting between formats is easy, optimizing them is not. The authors define the Minimum-Makespan Deordering problem—the task of removing as many ordering constraints as possible to achieve a target makespan. They prove that this problem is NP-complete for both PO and POCL plans.
The source of this complexity lies in negative side effects (deletes). As shown in the reduction from 3-SAT (see the action table above), the combinatorial challenge arises when deciding which action should produce a condition when multiple candidates exist, all while ensuring no other action deletes that condition at a critical moment. If actions only had additive effects (no deletes), the optimization problem would become polynomial.
Key Results and Tractability
The research establishes several landmark complexity results:
- Theorem 1: Any PO plan with makespan $k$ can be transformed into a POCL plan with makespan $k$ in polynomial time.
- Theorem 2: Finding a deordering to reach a specific makespan is NP-complete.
- Tractable Cases: Optimization becomes polynomial if delete lists are empty or if the causal links in a POCL plan are "fixed" (meaning the producer-consumer relationships cannot be changed).
Conclusion
This work settles the debate on the relationship between PO and POCL plans: they are equivalent in terms of parallel execution potential, even if they differ in structural flexibility. However, the NP-completeness of makespan minimization highlights that the "thinning out" of plans remains a significant hurdle for automated planners, primarily due to the complex management of action deletes. Future work may extend these results to plans with non-unit action durations or complex resource constraints.
Summary updated