Download
Abstract
Non-sequential plan representations, especially partial-order causal link (POCL) plans, are central to automated planning for modelling concurrency, enabling flexible execution, and optimising plan quality. This report provides a foundational investigation into the fundamental computational properties of these representations, focusing primarily on makespan, the minimum time required to execute a plan under parallelism.
The first part of this report presents a systematic investigation into the makespan-preserving convertibility among four prominent plan types: sequential, parallel, partial order, and POCL. We establish that while conversions to `higher’ representations can preserve makespan, the reverse is not generally possible due to action interference that necessitates serialization. We further show that the problem of finding parallel plan with minimal makespan for a given POCL plan is an $\textsf{NP}–$complete problem. We complement this analysis by proving that the problem of finding a plan with a bounded makespan is $\textsf{PSPACE}–$complete for all non-sequential representations when the bound is encoded in binary, and $\textsf{NP}–$complete when it is encoded in unary. Notably, our results disprove an assumption, made both explicitly and implicitly in several works, that planning graph-based planners maximise concurrency for partial order plans. This impacts the validity of makespan-optimality claims for planners which rely upon this principle.
Building on this foundation, the second part of the report performs a deep-dive complexity analysis of POCL planning in the lifted setting, where actions are represented as parameterized schemas. Reasoning over lifted plans is crucial for avoiding the prohibitive cost of grounding, yet its complexity has been under-explored. We first prove that deciding the existence of a solution for a lifted POCL plan is $\textsf{EXPSPACE}–$complete. The primary focus, however, is on the impact of delete relaxation on problem complexity. We formalise a suite of delete-relaxation semantics and, in a key finding that contrasts sharply with the grounded case, demonstrate that plan existence remains $\textsf{EXPTIME}–$complete across most variants. To provide a direct counterpart to our ground-level analysis and a complete picture, we then extend our investigation to bounded planning in the lifted setting, showing that both makespan- and length-bounded plan refinement for POCL plans are $\textsf{NEXPTIME}–$complete.