Finding Optimal Solutions in HTN Planning - A SAT-based Approach

Gregor Behnke, Daniel Höller, Susanne BiundoIJCAI 2019 · DOI

TL;DR

This paper introduces the first SAT-based approach for finding optimal solutions in Hierarchical Task Network (HTN) planning. By reformulating the problem to bound solution length instead of decomposition depth, their novel approach significantly outperforms existing optimal HTN planners on a benchmark set.

What Problem Does This Paper Address?

Hierarchical Task Network (HTN) planning is a powerful AI planning paradigm that allows for complex task decomposition. While many recent advancements have focused on finding any solution quickly (satisficing planning), finding optimal solutions (e.g., shortest plans) in HTN planning remains a significant challenge. Existing optimal HTN planners struggle with the inherent complexity of HTN decompositions, where the search space depth doesn't directly correlate with plan length. This makes it difficult to guide search effectively towards optimal solutions. Furthermore, many practical applications, like logistics or human assistance, demand optimal plans to minimize costs or ensure user satisfaction.

Methods

The core contribution of this paper is a novel SAT-based approach to find optimal HTN plans. Unlike previous SAT-based HTN planners that bound the decomposition depth, this work focuses on bounding the solution length.

Here's a breakdown of their approach:

  • Reformulating the Problem: The key idea is to translate HTN planning problems into propositional logic formulas where the length of the plan is bounded, rather than the decomposition depth. This allows SAT solvers to directly search for shortest plans.
  • Computing Depth Bounds (K4): A crucial component is a new method for computing a bound, denoted as $K_4(A, l)$, which estimates the maximum decomposition depth required to achieve a plan of exactly $l$ primitive actions starting from an abstract task $A$. This computation is iterative and handles complex structures like Strongly Connected Components (SCCs) in the Task Schema Transition Graph (TSTG). They also address the challenge of "empty cycles" (decompositions that don't change the task network) to ensure completeness.
  • SAT Encoding: They leverage existing SAT encodings for HTN planning but modify them to incorporate the length bound derived from their $K_4$ computation. This allows them to search for plans up to a specific length.
  • Search Strategies: To efficiently find the optimal plan length, they employ strategies like incremental search (testing lengths $l=1, 2, \dots$) and binary search, similar to techniques used in classical planning.

Datasets

The evaluation was performed on the "144 instances from the most recent evaluations of satisficing HTN planners," which are standard benchmarks in the field. These instances are drawn from various domains, including UM-TRANSLOG, SATELLITE, WOODWORKING, SMARTPHONE, PCP, ROVER, and TRANSPORT.

Key Insights and Ideas

  • Length vs. Depth: The fundamental insight is that for optimal HTN planning, bounding the solution length is more effective than bounding the decomposition depth. This directly aligns the problem with the capabilities of SAT solvers.
  • Novel Depth Bound ($K_4$): The development of the $K_4$ bound is a significant technical contribution. It provides a tighter and more accurate estimate of the necessary decomposition depth for a given plan length, outperforming previous methods by up to three orders of magnitude.
  • Handling Empty Cycles: The paper effectively addresses the tricky issue of "empty cycles" in HTN decompositions, which can lead to infinite depth bounds. Their method ensures completeness by carefully excluding or accounting for these cycles.
  • SAT Solvers for Optimality: Demonstrating that SAT solvers, when properly constrained, can be highly effective for finding optimal solutions in HTN planning, a problem traditionally tackled with search-based methods.

Key Results

  • Outperforms Existing Planners: The proposed SAT-based approach significantly outperforms the previous state-of-the-art optimal HTN planner (PANDA) and a progression-based planner (Progr. LM-Cut) in terms of the number of optimally solved instances.
  • Improved Coverage: The SAT-based techniques solve between 19 and 26 more instances than the progression-based planner.
  • Efficient Bound Computation: The new $K_4$ bound computation is shown to be much tighter than previous methods ($K_1, K_2, K_3$), leading to significantly smaller propositional formulas and faster SAT solving. In 37 cases, $K_4$ returned $-\infty$, indicating that no plan of a shorter length could be derived, allowing them to prove optimality for satisficing plans.
  • Strategy Comparison: The paper found no significant difference between the incremental (INC), decremental (DEC), and binary search (BIN) strategies for SAT-based planning, though BIN solved a few more instances.

Limitations and Future Work

  • Computational Cost: While the approach is effective, the paper notes that the SAT-based encoding can still be computationally expensive, especially for instances with very long optimal plans.
  • Integration with Incremental SAT Solvers: The authors mention that they have not yet integrated their encoding with incremental SAT solvers, which could potentially speed up the search for optimal solutions.
  • Handling Parallelism: The current encoding does not explicitly handle parallelism in task execution, which could be a direction for future work.
  • Generalization: While the $K_4$ bound handles empty cycles, further research might explore even more efficient ways to compute or utilize these bounds.

Summary updated

BibTeX
@inproceedings{behnke2019finding,
  author = {Gregor Behnke and Daniel Höller and Susanne Biundo},
  title = {{Finding Optimal Solutions in HTN Planning - A SAT-based Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/764},
}
Figure