TL;DR
This paper introduces "external conditions" as a novel concept in Hierarchical Task Network (HTN) planning. By automatically identifying and prioritizing these conditions, their proposed ExCon strategy significantly boosts planning efficiency, especially in complex, multi-goal scenarios, without sacrificing soundness or completeness.
What Problem Does This Paper Address?
Hierarchical Task Network (HTN) planning is a powerful AI planning paradigm that breaks down complex tasks into smaller, manageable subtasks. While effective, practical HTN planners often incorporate constructs like high-level effects and unsupervised conditions to improve efficiency. However, these constructs can make it challenging to guarantee the soundness and completeness of the planning process. Existing theoretical work, while establishing soundness and completeness, often omits these efficiency-boosting practical constructs. This paper addresses the gap by proposing a way to leverage the benefits of these constructs—specifically, by identifying and utilizing "external conditions"—while maintaining theoretical guarantees. The core problem is how to make HTN planners more efficient in practice, especially when dealing with complex problems involving interleaved tasks and multiple goals, without compromising their correctness.
Methods
The paper introduces the concept of external conditions. An external condition of a method (a way to decompose a task) is a state constraint that cannot be established by any of the subtasks resulting from that method. If a method is to be used, this condition must be satisfied by something outside the method itself, such as the initial state or another task in the plan.
The authors propose the ExCon strategy to leverage these external conditions:
- Preprocessing: The planner's knowledge base is pre-processed to automatically identify external conditions for each decomposition method. This is done by analyzing which subtasks can and cannot establish certain constraints.
- Priority Stack: A stack is maintained for the applicability conditions of the current partial plan. When a method is instantiated, its external conditions are pushed onto this stack. The condition at the top of the stack becomes the planner's current priority.
- Task Selection: The planner prioritizes tasks that can potentially establish or threaten the current top external condition. This is a departure from standard strategies like "fewest alternatives first" (FAF), which might not consider the importance of establishing these critical conditions early.
The ExCon strategy's task selection algorithm is detailed, showing how it checks if the top condition is met, and if not, searches for tasks that can establish or threaten it.
Datasets
The authors evaluated their approach on two domains:
- Small Artificial Domain: A custom domain designed to test interleaving and predicate task handling. Problems were generated with varying numbers of goals (1-3), predicate tasks (1-3), and "overlap rates" (10%, 50%, 90%) to control the degree of task interleaving. 100 problems were generated for each combination, totaling 1800 problems.
- Translog Domain: A standard transportation logistics domain (Andrews et al., 1995) used to test the planner on more realistic delivery scenarios with different package types and itineraries. 50 problems were generated for various two-package delivery scenarios.
Key Insights and Ideas
- External conditions are a natural consequence of HTN structure: Unlike explicitly defined unsupervised conditions, external conditions arise directly from the decomposition methods themselves, making them easier to discover and manage.
- Early identification of external conditions is crucial for efficiency: By focusing on tasks that can satisfy or threaten external conditions, the planner avoids exploring large branches of the search space that would eventually lead to failure. This is particularly important in problems with many interleaved tasks.
- ExCon offers the benefits of high-level effects without the risks: The ability to establish conditions at a higher level of abstraction, similar to high-level effects, is achieved by prioritizing external conditions. However, ExCon does this in a way that preserves soundness and completeness.
- ExCon is a task-selection strategy, not a pruning heuristic: This means it guides the search order but doesn't eliminate possibilities, thus preserving the planner's theoretical guarantees.
Key Results
- Significant efficiency gains: In the artificial domain, ExCon consistently outperformed the FAF strategy, especially in problems with higher degrees of interleaving (lower overlap rates) and multiple predicates. For instance, in 3-goal problems with 10% overlap, FAF generated up to 2.64 times more search nodes than ExCon.
- Robustness to complexity: As the number of predicates and goals increased, ExCon's performance degraded much more gracefully than FAF's, indicating its better scalability.
- Translog domain performance: ExCon showed competitive or superior performance in the Translog domain, particularly in scenarios where task interleaving was possible but complex, outperforming FAF in scenarios with different package types or complex itinerary interactions.
Limitations and Future Work
- External condition extraction: The paper acknowledges that their method for automatically extracting external conditions is not perfect and is an area of ongoing research.
- Commitment strategies: The authors note that ExCon's performance can be affected by other commitment strategies within the planner, and suggest further study in this area.
- Further domain testing: While the artificial domain was designed to highlight ExCon's strengths, more extensive testing across a wider range of domains would be beneficial.
- Handling of other constructs: Future work could explore integrating ExCon with other practical HTN constructs like high-level effects in a sound and complete manner.
Summary updated