TL;DR
This paper investigates how different strategies for making decisions (commitments) during Hierarchical Task Network (HTN) planning affect performance. They introduce a novel "dynamic" strategy that adapts its commitment approach on the fly, outperforming static "eager" and "reluctant" strategies across a range of planning domains. This suggests that flexible commitment is key to efficient HTN planning.
What Problem Does This Paper Address?
Planning, especially in complex domains, involves making numerous decisions. Two critical types of decisions are: 1) the order in which to execute sub-tasks, and 2) the specific values to assign to variables within those tasks. The "commitment strategy" dictates when and how these decisions are made. In Hierarchical Task Network (HTN) planning, where tasks are decomposed into sub-tasks, this choice significantly impacts the efficiency of finding a valid plan. Previous work has shown commitment strategies are crucial in STRIPS-style planning, but their impact on HTN planning, particularly with different approaches to variable instantiation and task expansion, was less understood. This paper aims to compare and contrast three distinct commitment strategies within the UMCP HTN planner to determine which performs best across various planning problems.
Methods
The authors compare three commitment strategies for HTN planning, implemented within the UMCP planner:
- Eager Variable Instantiation Strategy (EVIS): This strategy prioritizes committing to variable bindings. It avoids expanding non-primitive tasks until all their associated variable constraints are resolved. Variables are instantiated with concrete values as soon as possible.
- Reluctant Variable Binding Strategy (RVBS): This is the opposite of EVIS. It delays variable instantiation as much as possible, expanding tasks first and only binding variables when absolutely necessary.
- Dynamic Variable Commitment Strategy (DVCS): This is the novel contribution. DVCS attempts to minimize the branching factor in the search tree. At each decision point, it compares the number of possible values for variables with the number of available methods for expanding tasks. If there are fewer variable options (V) than task expansion methods (M), it prioritizes instantiating a variable. If there are more task expansion methods, it prioritizes expanding a task. This allows it to dynamically switch between eager and reluctant approaches based on the current state of the planning problem.
Datasets
The authors evaluated their strategies on three custom-designed planning domains:
- Domain A: A relatively simple domain designed to test variable instantiation and method selection.
- Domain B: Based on the arc-consistency problem, this domain features methods that increase the branching factor, testing how strategies handle this.
- Domain C: A more complex domain that combines aspects of Domains A and B, requiring careful sequencing of methods depending on the specific goal.
For each domain, they generated a suite of randomly selected problems (100 for A and C, 50 for B).
Key Insights and Ideas
- Static vs. Dynamic Commitment: The core insight is that a single static commitment strategy (like always being eager or always reluctant) might perform well in some domains but poorly in others. A dynamic strategy that can adapt its approach based on the specific task and its constraints offers a more robust solution.
- Branching Factor Matters: The paper reinforces the intuition that minimizing the branching factor in the search tree, especially early on, leads to more efficient planning. DVCS directly targets this by making informed decisions about whether to instantiate variables or expand tasks.
- Domain-Specific Performance: While DVCS generally performs best, the paper acknowledges that specific domains might favor one strategy over another. However, DVCS's ability to adapt makes it a strong contender across a broader range of problems.
Key Results
The experiments consistently showed DVCS outperforming both EVIS and RVBS in terms of CPU time and the number of nodes generated in the search tree.
- Domain A: DVCS and RVBS performed similarly and significantly better than EVIS. DVCS averaged 0.66 seconds, RVBS 0.71 seconds, and EVIS 2.88 seconds.
- Domain B: EVIS and DVCS performed comparably and much better than RVBS. EVIS and DVCS averaged around 1.10 seconds, while RVBS averaged 2.54 seconds.
- Domain C: DVCS achieved the best performance, with an average CPU time of 1.38 seconds, compared to RVBS at 1.83 seconds and EVIS at 2.15 seconds. Statistical tests confirmed these differences were significant.
Limitations and Future Work
- Domain Specificity: The authors acknowledge that highly domain-specific commitment strategies could potentially outperform their general DVCS. However, developing such strategies requires significant domain knowledge.
- Heuristics for Instantiation: The current DVCS implementation uses a simple heuristic for choosing which variable to instantiate (the one with the fewest possible values). Future work could explore more sophisticated heuristics, such as prioritizing variables involved in the most pending constraints.
- Ordering Constraints: The paper focuses on variable commitment. Future research will explore extending the dynamic commitment approach to handle step-ordering constraints as well.
- Learning Commitment Strategies: The authors are interested in using AI learning techniques (like case-based reasoning and explanation-based learning) to automatically learn domain-specific commitment strategies. They also plan to investigate adjusting dynamic heuristics like DVCS based on experience.
- Broader Testing: They intend to test DVCS on a wider range of planning problems and domains, including Blocks World and the UCPOP test suites.
Summary updated