On Total-Order HTN Plan Verification with Method Preconditions - An Extension of the CYK Parsing Algorithm

Songtuan Lin, Gregor Behnke, Simona Ondrcková, Roman Barták, Pascal BercherAAAI 2023 · DOI

TL;DR

This paper introduces a novel algorithm for verifying "totally-ordered Hierarchical Task Network" (TOHTN) plans, a crucial task in ensuring AI agents behave as intended. By extending the classic CYK parsing algorithm, the authors achieve a more efficient verification process, particularly for plans with complex method preconditions, outperforming existing specialized methods.

What Problem Does This Paper Address?

Ensuring that AI planning systems generate correct and reliable plans is paramount, especially in safety-critical applications or when AI interacts with humans. Plan verification is the process of checking if a given plan is a valid solution to a planning problem. Hierarchical Task Network (HTN) planning is a powerful AI planning paradigm that breaks down complex tasks into simpler subtasks, often using methods that define how to decompose tasks. A specific type, "totally-ordered HTN" (TOHTN) planning, is widely used due to its prevalence in benchmarks.

However, verifying TOHTN plans, especially those with "method preconditions" (conditions that must be met for a decomposition method to be applicable), is computationally challenging. Existing verification methods often treat TOHTN plans as general HTN plans, missing opportunities for optimization. While one method attempts TOHTN optimization, it relies on exhaustive search. This paper addresses the need for a more efficient and specialized approach to TOHTN plan verification that effectively handles method preconditions.

Methods

The core contribution of this paper is an extension of the CYK parsing algorithm for TOHTN plan verification. The CYK algorithm is a well-established method for determining if a string belongs to a context-free grammar (CFG). The authors establish an analogy between TOHTN planning problems and CFGs, where primitive tasks correspond to terminal symbols, compound tasks to non-terminal symbols, and methods to production rules.

The standard CYK algorithm, however, doesn't account for method preconditions. The authors adapt the algorithm by incorporating checks for these preconditions during the parsing process. Specifically, when considering a method to decompose a task, they verify if the method's preconditions are satisfied by the current state of the plan.

To further optimize the process, especially when dealing with a large number of methods, the authors introduce two mappings. These mappings allow for quick retrieval of methods that decompose a compound task into specific subtasks, avoiding a brute-force search through all available methods. This optimization is crucial because, in practice, the number of methods can far exceed the length of the plan.

The paper also discusses how to handle TOHTN planning problems that are not in Chomsky Normal Form (CNF) by transforming them into a "2-Normal Form" (2NF), where methods have at most two subtasks. This binarization step simplifies the problem without the quadratic explosion in grammar size that full CNF conversion can cause.

Datasets

The experiments were conducted on benchmark sets from the IPC 2020 on HTN Planning. These benchmarks include instances both with and without method preconditions. The set with method preconditions contains 12367 plan instances (10961 valid, 1406 invalid), while the set without method preconditions has 12367 instances (11304 valid, 1063 invalid).

Key Insights and Ideas

  • CYK for HTN Verification: The paper elegantly demonstrates how a classic parsing algorithm can be adapted for a complex AI planning verification problem, highlighting the underlying structural similarities between formal grammars and planning decomposition.
  • Efficient Precondition Handling: The key innovation is the seamless integration of method precondition checks within the CYK framework, making the verification process more robust and accurate for practical HTN problems.
  • Optimization for Large Method Sets: The use of precomputed mappings to quickly find relevant decomposition methods is a critical optimization that significantly improves performance when dealing with domains that have many methods.
  • 2NF as a Practical Compromise: By using 2NF instead of full CNF, the authors strike a balance between simplifying the planning problem for efficient parsing and avoiding the computational blow-up associated with full CNF conversion.

Key Results

The proposed CYK-based approach was compared against existing state-of-the-art methods: a parsing-based verifier and a planning-based verifier.

  • With Method Preconditions:
    • The CYK-based approach solved 10917 out of 10961 valid instances (99.60%) and all 1406 invalid instances (100%).
  • It significantly outperformed the parsing-based verifier, solving 9158 valid (83.55%) and 1301 invalid (92.53%) instances.
  • It slightly underperformed the planning-based verifier on valid instances (10925 solved, 99.67%) but was much better on invalid instances.
  • Without Method Preconditions:
    • The CYK-based approach solved 9946 valid (87.99%) and 981 invalid (92.29%) instances.
  • It outperformed the planning-based verifier (9679 valid, 85.62%; 898 invalid, 84.48%) and the parsing-based verifier (7889 valid, 69.79%; 915 invalid, 86.08%). The SAT-based verifier performed poorly in this setting.

The paper also shows that the CYK-based approach is significantly faster than the planning-based approach in many domains, particularly when dealing with method preconditions.

Limitations and Future Work

  • Limitations: The paper acknowledges that their approach slightly underperformed the planning-based verifier on valid instances with method preconditions. They hypothesize this is due to the planning-based verifier's heuristics being more effective for solvable problems.
  • Future Work: The authors suggest extending their work by exploring more sophisticated charting parsing algorithms, such as the Earley parsing algorithm, to develop even more efficient plan verification approaches for TOHTN planning. They also propose adapting their ideas to other HTN formalisms that support advanced features like prevail conditions and using preprocessing techniques to make general HTN verification more systematic.

Summary updated

BibTeX
@inproceedings{lin2023total,
  author = {Songtuan Lin and Gregor Behnke and Simona Ondrcková and Roman Barták and Pascal Bercher},
  title = {{On Total-Order HTN Plan Verification with Method Preconditions - An Extension of the CYK Parsing Algorithm}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26420},
}
Figure