TL;DR
This paper delves into the computational complexity of automatically correcting AI planning models when a proposed plan fails to be a solution. The authors analyze how difficult it is to modify either the methods that decompose tasks or the actions' preconditions and effects to make a given plan valid, finding that most such modifications are NP-complete, though some specific cases are tractable.
What Problem Does This Paper Address?
In AI planning, especially in real-world applications, it's common for humans to be involved in the planning process. This is because not all constraints are known upfront, and the AI's model of the world might differ from a human's expectations. When a generated plan is rejected by a user or fails to meet certain criteria, it often indicates a mismatch between the AI's model and the desired outcome. This paper tackles the problem of understanding how computationally expensive it is to automatically adjust the planning model to make a given, but incorrect, plan a valid solution. This is crucial for building more robust mixed-initiative planning systems and for providing "counter-factual explanations" that help users identify and fix modeling mistakes.
Methods
The paper focuses on Hierarchical Task Network (HTN) planning and classical planning. They analyze two main types of model changes:
- Changing Decomposition Methods: This involves modifying the rules (methods) that dictate how compound tasks are broken down into simpler ones. The allowed changes are adding or deleting primitive tasks from a method's sequence. The authors define decision problems like
FIX-METHSxto ask if a sequence of such changes can make a given task network a solution. - Changing Action Definitions: This involves altering the preconditions (what must be true for an action to execute) and effects (what changes after an action) of primitive actions. The allowed changes are adding or deleting facts from these definitions. Decision problems like
FIX-ACTIONSxare defined to assess the complexity of making a task network executable by modifying actions.
The core methodology is to establish the computational complexity (NP-completeness, NP-hardness, or polynomial time solvability) of these decision problems. They achieve this through reductions from known NP-complete problems like the independent set and set cover problems.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Most Model Fixes are Hard: The paper's central finding is that automatically correcting planning models to satisfy a given plan is generally computationally hard. Specifically, changing decomposition methods is often NP-complete, and modifying action definitions becomes NP-complete as soon as "add" operations (adding facts to an action's effect) are allowed.
- Tractability in Specific Cases: While many scenarios are NP-complete, there are tractable cases. For instance, if the initial task network in HTN planning is empty (no primitive tasks) and each method refines a unique task, fixing methods becomes polynomial. Similarly, if only preconditions or delete lists of actions are modified (without adding effects), the problem is tractable.
- The Power of "Add" Operations: The complexity significantly increases when the ability to add facts to an action's effect list is introduced. This suggests that while fixing existing issues (deletions, precondition adjustments) might be manageable, introducing new capabilities or ensuring positive outcomes through adding effects is a much harder problem computationally.
- Formalizing "Fixing" Problems: The paper rigorously defines decision problems for various combinations of allowed changes, providing a formal framework for analyzing the complexity of model correction.
Key Results
- Fixing Methods:
FIX-METHSx(arbitrary additions/deletions of tasks in methods) is NP-complete.
FIX-METHSxwith a bounded number of changes (k) is also NP-complete.- Tractable (in P) if the initial HTN task network is empty and methods refine unique tasks.
- Fixing Actions:
FIX-ACTIONSPREC(only changing preconditions) is in P.
FIX-ACTIONSADD(only changing add lists) is NP-complete.FIX-ACTIONSDEL(only changing delete lists) is in P.- Combinations like
FIX-ACTIONSADD,DELandFIX-ACTIONSPREC,ADD,DELare NP-complete. FIX-ACTIONSPREC,DELis in P.
Limitations and Future Work
- Focus on Total-Order HTNs: The analysis of method changes is primarily for totally-ordered HTN planning. While results are stated to be lower bounds for partially ordered HTNs, a full analysis for the latter is left for future work.
- Specific Change Operations: The paper focuses on specific, atomic changes (adding/deleting a single fact or task). More complex or compound changes might have different complexity characteristics.
- Practical Implementation: The paper establishes theoretical complexity bounds. Future work could involve implementing these decision problems using efficient solvers (like SAT or ILP) to build practical tools for model correction and explanation.
- User Interaction: While motivated by mixed-initiative planning, the paper focuses on the computational complexity of the correction step itself, rather than the interactive dialogue between the user and the AI.
Summary updated