TL;DR
This paper delves into the computational complexity of automatically correcting Hierarchical Task Network (HTN) planning domains. The authors identify three key sources of difficulty that contribute to the problem being NP-hard, and they establish complexity bounds for various scenarios involving correcting flawed HTN models based on example plans.
What Problem Does This Paper Address?
AI planning holds immense promise for real-world applications, but its widespread adoption is hindered by the difficulty of modeling complex domains. While tools exist to assist in this process, they often lack intelligent guidance. This paper tackles the challenge of automatically correcting flawed HTN planning models. Specifically, it addresses the problem of modifying a domain so that a given set of "white list" plans become valid solutions, while a set of "black list" plans are rejected. This is crucial for building more robust and user-friendly AI planning systems.
Methods
The authors investigate the computational complexity of correcting HTN domains by introducing a framework for model change operations. These operations include adding/deleting actions (ACT⁺, ACT⁻) and adding/deleting ordering constraints (ORD⁺, ORD⁻) within methods. They systematically analyze the complexity of these correction problems under different combinations of allowed operations. A key methodological contribution is the formalization of "decomposition forests" to represent hierarchical task decomposition, which is more rigorous than previous approaches. They also introduce the concept of "modification functions" to capture the correspondence between plans and decomposition structures.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Three Sources of Hardness: The paper identifies three fundamental reasons why correcting HTN domains is computationally challenging:
- Finding Decomposition Hierarchies: Determining the correct hierarchical structure for tasks is inherently difficult, akin to solving a vertex cover problem.
- Mapping Plans to Decompositions: Establishing a correspondence between the actions in a plan and the tasks in a decomposition structure is complex, similar to subgraph isomorphism.
- Identifying Where to Add Missing Actions: Deciding which method should incorporate a newly added action is a significant hurdle, related to the independent set problem.
- VALIDSEQ is NP-complete: The problem of determining if an action sequence is a valid linearization of a primitive task network (VALIDSEQ) is proven to be NP-complete. This result is foundational and has implications for other areas like partial order causal link (POCL) planning.
- Complexity Varies with Operations: The complexity of correcting HTN domains depends heavily on the allowed modification operations. For instance, problems become easier if action insertions (ACT⁺) are disallowed.
- Formalizing Decomposition: The introduction of "decomposition forests" provides a more precise and powerful way to represent hierarchical task decomposition, enabling more accurate complexity analysis.
Key Results
- The problem of correcting HTN domains with only white list plans (CHANGEx) is shown to be NP-complete for various combinations of allowed operations.
- The problem of correcting HTN domains with both white list and black list plans (CHANGEWBx) is proven to be NP-hard and lies within the complexity class Σ (NPNP).
- The VALIDSEQ problem, crucial for verifying linearizations, is established as NP-complete.
- The paper provides theoretical bounds for the length of change sequences required for corrections, suggesting that efficient practical algorithms might be feasible.
Limitations and Future Work
- Method Preconditions Not Considered: The paper acknowledges that it does not consider method preconditions, as their semantics are not fully formalized in existing literature. Future work could explore this.
- Adding/Deleting Methods Not Studied: While adding or deleting methods is also NP-complete, the authors argue that these operations can be simulated by the studied operations and thus do not offer novel complexity insights.
- Practical Realizations: The paper suggests that encoding these problems into SAT solvers, leveraging existing work on SAT encodings for decomposition forests and subgraph isomorphism, is a promising direction for practical implementations.
- Exploiting ACT⁺: The insight that ACT⁺ (action insertion) is the most computationally expensive operation suggests that algorithms could prioritize handling deletions and then check feasibility of insertions in polynomial time.
Summary updated