Tight Bounds for HTN Planning with Task Insertion

Ron Alford, Pascal Bercher, David W. AhaIJCAI 2015

Abstract

Hierarchical Task Network (HTN) planning is a powerful paradigm for automated planning that leverages domain-specific knowledge. However, standard HTN planning often suffers from high computational complexity and undecidability. This paper investigates Task Insertion (TIHTN), a hybrid approach that allows for the insertion of actions outside the predefined hierarchy. We provide the first tight complexity bounds for TIHTN planning, demonstrating that it ranges from PSPACE-complete to 2-NEXPTIME-complete, depending on task ordering and the use of variables.

Introduction

In automated planning, researchers typically choose between classical planning—finding a sequence of actions to reach a goal—and HTN planning, which decomposes high-level tasks into sub-tasks. While HTN planning captures expert knowledge, it is often "brittle" and computationally expensive, frequently reaching undecidability.

Task Insertion (TIHTN) addresses these limitations by allowing the planner to "insert" actions from outside the hierarchy when necessary. Although this flexibility is favored in practice, its theoretical complexity remained largely unknown, previously estimated only as being within EXPSPACE. This research maps the exact complexity of TIHTN across various configurations, revealing that task insertion often makes the planning problem more computationally manageable.

Methodology

The authors establish these tight bounds through two primary theoretical contributions:

Acyclic Progression

A novel planning technique called acyclic progression is introduced. This method interleaves task decomposition with state-based progression while tracking the "ancestry" of tasks to prevent infinite recursive loops. The authors prove that if a TIHTN solution exists, an acyclic version of that solution must also exist, effectively bounding the search space.

Complexity Mapping

The study analyzes TIHTN along two primary axes:

  1. Ordering: Whether tasks within a method are totally ordered (sequential) or partially ordered (flexible).
  2. Variables: Whether the problem is propositional (fixed objects) or lifted (utilizing variables).

To establish lower bounds, the authors utilize a "Bottles of Beer on the Wall" construction, employing a binary counter to simulate complex Turing machines and force exponential step counts.

Key Insights

The research yields several counter-intuitive findings regarding the nature of task insertion:

  • Insertion as a Complexity Lowerer: Paradoxically, the ability to insert arbitrary tasks makes the problem easier to solve than standard HTN by breaking strict adherence to potentially infinite hierarchies.
  • The Total Order Shortcut: When tasks are totally ordered, TIHTN planning is no more complex than classical planning (PSPACE-complete). This allows developers to use HTN guidance without a computational penalty.
  • The Cost of Flexibility: The transition from total to partial ordering significantly increases complexity, shifting the problem to NEXPTIME or 2-NEXPTIME.
  • Impact of Recursion: Unlike standard HTN, where recursion type (e.g., tail-recursive vs. arbitrary) drastically alters complexity, TIHTN's complexity is primarily driven by task ordering rather than recursive structure.
Comprehensive comparison of HTN and TIHTN complexity across various parameters including recursion types.

Results

The paper provides definitive completeness results for TIHTN planning across different configurations. These "tight bounds" offer a roadmap for algorithm designers to understand worst-case performance.

Summary of tight complexity bounds for TIHTN planning based on ordering and variables.

The results confirm that TIHTN is decidable in all analyzed cases, providing a significant theoretical advancement over standard HTN models.

Conclusion and Future Work

While this work establishes the theoretical "ceiling" for TIHTN planning, several avenues for future research remain. The current analysis focuses on plan existence rather than plan quality or optimality; in practice, a plan with excessive insertions may be suboptimal. Additionally, the authors suggest that further syntactic restrictions, such as "constant-free methods," could further reduce complexity for lifted problems. Finally, the "acyclic progression" technique serves as a promising foundation for developing efficient heuristics for practical TIHTN planners.

Summary updated

BibTeX
@inproceedings{alford2015tight,
  author = {Ron Alford and Pascal Bercher and David W. Aha},
  title = {{Tight Bounds for HTN Planning with Task Insertion}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure