Makespan Investigations of Sequential, Parallel, PO, and POCL Plans

⭐ AAAI 2026 — Oral Presentation

Download

• Paper

Abstract

Modern planning systems utilize various plan representations — sequential, parallel, partially ordered (PO), and partial-order causal link (POCL) — each with different models for concurrency. These formalisms are often implicitly assumed to have the same base properties, particularly regarding makespan. We challenge this assumption, proving the relationship between them is fundamentally asymmetric. Our analysis shows conversions from plans with rigid concurrency layers (sequential, parallel) to those with flexible partial orders (PO, POCL) can preserve makespan. However, the reverse generally fails; the flexible orderings in PO/POCL plans can yield shorter makespans for solutions that cannot be represented in parallel plans without serialization. We prove that finding an optimal parallel representation for a given POCL plan is $\textsf{NP}–$complete, resolving a key question about their practical interchangeability. We also provide tight complexity bounds for makespan-bounded plan existence. Notably, our results disprove a claim in the literature that planning graph-based planners maximize concurrency by minimizing the critical path in derived PO plans.

Citation

Oates, H., and Bercher, P. 2026. “Makespan Investigations of Sequential, Parallel, PO, and POCL Plans” In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026). AAAI Press.

@InProceedings{Oates2025MakespanInvestigations,
  author     = {Harrison Oates and Pascal Bercher},
  booktitle  = {Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026)},
  title      = {Makespan Investigations of Sequential, Parallel, PO, and POCL Plans},
  year       = {2026},
  publisher  = {AAAI Press},
}