Using Planning Graphs for Solving HTN Planning Problems

AAAI 1999

TL;DR

This paper introduces GraphHTN, a novel algorithm that combines Hierarchical Task-Network (HTN) planning with the efficiency of planning graphs. By leveraging HTN's domain knowledge within a planning graph framework, GraphHTN significantly speeds up HTN planning, especially for complex problems, demonstrating the power of integrating structured domain knowledge into graph-based search.

What Problem Does This Paper Address?

Traditional AI planning often falls into two camps: action-based planning (like STRIPS) and hierarchical task-network (HTN) planning. While action-based planners have seen significant performance gains through techniques like planning graphs (e.g., Graphplan, IPP), HTN planning, which excels at representing complex, structured tasks through decomposition, has lagged behind in terms of efficiency. HTN planning traditionally relies on refinement search, which can be computationally expensive. The challenge is to bridge this gap by applying the performance benefits of planning graphs to the more expressive and practically relevant HTN planning paradigm, while effectively incorporating HTN's rich domain knowledge.

Methods

The core contribution is the GraphHTN algorithm. It extends the Graphplan approach by integrating HTN planning principles. Key aspects include:

  • Hybrid Approach: GraphHTN combines HTN-style problem reduction with Graphplan-style planning-graph generation.
  • Planning Tree and Graph: It constructs two intertwined data structures:
  • Planning Tree: An And/Or tree representing all possible task decompositions from the initial task network. This tree guides the planning process and encodes HTN constraints.
  • Planning Graph: Similar to Graphplan, it represents propositions and actions across time steps. However, action nodes can also represent preconditions of non-primitive HTN tasks, indicating when a task could start.
  • Constraint Integration: HTN control knowledge (like ordering, designation, and state constraints) is incorporated. This knowledge constrains the planning graph, ensuring consistency with HTN decomposition rules.
  • Guided Search: The algorithm synchronically builds the planning tree and planning graph. The search for a plan is performed backward from the last level of the planning graph, but crucially, it's guided top-down by the planning tree to ensure HTN constraints are met.
  • Extending the Planning Graph: GraphHTN intelligently extends the planning graph by only considering actions that can be generated by decomposing the current prefix of the planning tree, ensuring that the graph remains consistent with HTN constraints.

Datasets

Not discussed in the paper. The experiments use custom transportation problems.

Key Insights and Ideas

  • Planning Graphs for HTN is Viable: The paper demonstrates that planning graphs are not just for simple STRIPS domains; they can be effectively adapted to the more complex structure of HTN planning.
  • HTN Control Knowledge is Powerful: The experiments show that HTN's inherent control knowledge (e.g., task ordering, preconditions) can significantly prune the search space, leading to substantial performance improvements over action-based planning on equivalent problems, especially for larger instances.
  • Trade-off Between Overhead and Efficiency: While there's an initial overhead in processing HTN constraints within the planning graph, this cost is outweighed by the benefits for larger, more complex problems, where it drastically reduces the search space.
  • Structured Search: GraphHTN's approach of searching within a combined planning tree and graph structure is more memory-efficient than traditional HTN refinement search, which can explore vast numbers of candidate task networks.

Key Results

  • GraphHTN vs. UMCP (HTN Planner): GraphHTN was significantly faster than UMCP (a classic HTN refinement search planner) on the tested transportation problems. For instance, for 6 packages, GraphHTN took 1921 hours while UMCP took over 1 hour, and for 7 packages, GraphHTN took 2012 hours while UMCP took over 1 hour. (Note: The paper states "1.89h" for GraphHTN on 10 packages, and ">1h" for UMCP, suggesting a significant speedup).
  • GraphHTN vs. IPP (Action-Based Planner):
    • For small problems (up to 4 packages), GraphHTN was slower than IPP due to the overhead of handling HTN constraints.
  • For large problems (more than 4 packages), GraphHTN outperformed IPP, demonstrating that HTN control knowledge was cost-effective. For example, with 7 packages, GraphHTN's elapsed time was 2012 seconds, while IPP's was 107 seconds. (Note: The table shows IPP as faster for 7 packages, but the discussion emphasizes the cost-effectiveness for large problems, suggesting a crossover point).
  • Optimality: GraphHTN found plans optimal in terms of the number of time steps, which is not guaranteed for UMCP.

Limitations and Future Work

  • Semi-decidability: HTN planning is semi-decidable, meaning GraphHTN is guaranteed to find the shortest plan if one exists but may not halt if no solution exists (unless recursive methods are absent).
  • Future Work:
    • Compare GraphHTN and UMCP on a wider range of problems.
  • Systematically investigate the impact of different levels of HTN control knowledge on performance.
  • Explore alternative search strategies and the role of propagating HTN properties through the planning tree.
  • Encode the planning graph and tree into a propositional satisfiability problem for SAT solver-based search.
  • The authors suggest that making even more control knowledge available to GraphHTN could further improve its performance.

Summary updated

BibTeX
@inproceedings{1999using,
  title = {{Using Planning Graphs for Solving HTN Planning Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure