On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence

Songtuan Lin, Conny Olz, Malte Helmert, Pascal BercherAAAI 2024 · DOI

Abstract This paper provides a comprehensive complexity analysis of four fundamental reasoning tasks in automated planning: plan verification, bounded plan existence, plan optimality verification, and bounded plan optimality verification. The study covers both classical and Hierarchical Task Network (HTN) planning, distinguishing between grounded and lifted representations. Key findings include the significant complexity jump in lifted HTN planning, reaching classes as high as 2NEXPTIME, and the impact of numerical encoding on problem hardness. This work fills critical gaps in the planning literature, providing a rigorous map of the computational landscape.

Introduction

In the field of automated planning, determining if a sequence of actions can achieve a goal is only the first step. Often, it is equally important to verify if a plan is optimal—meaning it achieves the goal in the fewest possible steps—or if a plan of a specific length exists. While these problems are well-understood for grounded classical planning, where every action is explicitly defined, they have remained largely unexplored for more complex formalisms like Hierarchical Task Network (HTN) planning and lifted representations.

This paper addresses the computational "hardness" of four key questions: plan verification, bounded plan existence, plan optimality verification, and bounded plan optimality verification. By distinguishing between grounded representations (explicit actions) and lifted representations (using variables and schemas), the authors reveal how the abstraction of planning problems dramatically increases their computational difficulty.

Methods

The researchers employed complexity reductions to establish the hardness of various planning tasks. To analyze lifted HTN planning, they constructed "gadgets"—mathematical structures that encode known hard problems into planning verification tasks. For example, they designed specific method schemas that simulate state transitions and action effects within the task decomposition process to prove PSPACE-hardness for lifted HTN verification.

Figure 4: Gadget construction for complexity reductions in lifted HTN planning.

Additionally, the study analyzed the impact of numerical encoding. The researchers examined how representing the plan length bound $k$ in binary (compact) versus unary (long strings) affects complexity. They demonstrated that for many tasks, the compact binary encoding pushes the problem into significantly higher complexity classes, such as NEXPTIME.

Key Insights and Ideas

  • The "Lifted" Penalty: In classical planning, moving from grounded to lifted representations does not change the complexity of plan verification (it remains in P). However, in HTN planning, it jumps from NP-complete to at least PSPACE-hard. This is because the lifted representation allows for a massive number of possible groundings that the verifier must implicitly navigate.
  • Encoding Sensitivity: The complexity of finding a plan of length $k$ depends heavily on its representation. In binary, the problem is often NEXPTIME-complete for HTN, whereas in unary, it drops to NP-complete. This highlights that the magnitude of the bound itself is a major source of difficulty.
  • Optimality as a Complement: The authors show that verifying if a plan is optimal is essentially the complement of the bounded plan existence problem. If no plan shorter than $n$ exists, then a plan of length $n$ is optimal. This allows for the transfer of complexity results between existence and optimality tasks (e.g., moving from NP to coNP).

Results

The primary contribution of this work is a comprehensive map of complexity results, filling in critical gaps for both classical and HTN planning. These results are summarized in the table below.

Figure 6: Comprehensive complexity landscape for plan verification and optimality.

Highlights include proving that lifted HTN plan verification is PSPACE-hard (and in NEXPTIME), while $k$-length plan existence for lifted HTN (with binary $k$) is NEXPTIME-hard and potentially in 2NEXPTIME. For context, 2NEXPTIME represents problems requiring doubly-exponential time to solve on a non-deterministic machine, marking a significant peak in planning complexity.

Conclusion and Future Work

While this paper provides a much-needed map of the planning complexity landscape, several results for lifted HTN planning are not yet "tight." For instance, lifted HTN plan verification is proven to be PSPACE-hard and in NEXPTIME, but the exact complexity between these two classes remains an open question. Future research may also focus on formalizing complexity for solutions defined as primitive task networks (including ordering constraints) rather than simple action sequences, further refining our understanding of hierarchical planning systems.

Summary updated

BibTeX
@inproceedings{lin2024computational,
  author = {Songtuan Lin and Conny Olz and Malte Helmert and Pascal Bercher},
  title = {{On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.30000},
}
Figure