POP ≡ POCL, Right? Complexity Results for Partial Order (Causal Link) Makespan Minimization

Pascal Bercher, Conny OlzAAAI 2020 · DOI

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.

A POCL plan structure illustrating causal links (arrows) that connect action effects to the preconditions of subsequent actions.

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 action schema used in the reduction from 3-SAT to prove that finding an optimal deordering is NP-complete. Note the role of the 'del' (delete) column.

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

BibTeX
@inproceedings{bercher2020pop,
  author = {Pascal Bercher and Conny Olz},
  title = {{POP ≡ POCL, Right? Complexity Results for Partial Order (Causal Link) Makespan Minimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6530},
}
Figure