Abstract
Planning in nondeterministic domains presents a significant computational challenge due to the exponential growth of state spaces. Traditional approaches have relied either on compact state representations (like Binary Decision Diagrams) without search control, or on sophisticated search control (like Hierarchical Task Networks) using explicit state representations. This paper introduces YoYo, a novel planner that synthesizes these two paradigms. By performing HTN task decompositions over sets of states represented as BDDs, YoYo achieves significant improvements in both speed and scalability, often outperforming existing state-of-the-art planners by multiple orders of magnitude.
Introduction
In automated planning, nondeterministic environments—where actions have multiple possible outcomes—require planners to account for every potential execution path. This leads to a combinatorial explosion. Historically, two strategies have dominated: Planning as Model Checking (e.g., the MBP planner), which uses Binary Decision Diagrams (BDDs) for memory-efficient state representation but lacks search guidance; and Planning with Search Control (e.g., the ND-SHOP2 planner), which uses Hierarchical Task Networks (HTNs) to prune the search space but relies on memory-intensive explicit state representations.
The YoYo planner bridges this gap by integrating HTN task decomposition directly with BDD-based state representations, allowing for "controlled search over compact representations."
Methodology
The core innovation of YoYo is its ability to perform task decomposition over an entire set of states simultaneously. In traditional HTN planning, a task is decomposed for a single state. YoYo, however, takes a task $t$ and a BDD representing a set of states $S$. It identifies the subset $S' \subseteq S$ where a specific decomposition is applicable. The algorithm then splits the BDD: the decomposition proceeds for $S'$, while other possible decompositions are explored for the remaining states $S \setminus S'$. This approach allows the planner to reason about classes of states at once, effectively compressing the search process.
Experimental Evaluation
The researchers evaluated YoYo using a pursuit-evasion (hunter-prey) game in a grid world. The hunter must capture one or more prey that move nondeterministically. Two primary scaling factors were tested:
- Complexity Scaling: Increasing the number of prey (from 2 to 6) in a fixed 4x4 grid.
- State Space Scaling: Increasing the grid size (from 5x5 to 10x10) with a single prey.
Results and Discussion
The experimental results demonstrate that the synergy between BDDs and HTNs acts as a force multiplier. As shown in Figure 1, the MBP planner, which lacks search control, fails to scale as the number of prey increases, exceeding time limits quickly. Conversely, Figure 2 illustrates that ND-SHOP2, while possessing search control, struggles with memory overhead as the physical state space (grid size) expands.
YoYo bypassed both hurdles. It used HTNs to ignore irrelevant state transitions (addressing MBP's weakness) and BDDs to handle large state spaces (addressing ND-SHOP2's weakness). In all tests, YoYo was frequently 2 to 3 orders of magnitude faster than its predecessors and solved all instances that caused the other planners to crash or time out.
Conclusion
YoYo demonstrates that combining compact state representations with high-level search control provides a robust solution for nondeterministic planning. While the system currently requires human-authored domain knowledge and assumes full observability, its performance gains are substantial. Future work aims to extend this logic to Markov Decision Processes (MDPs) and partially observable environments, potentially revolutionizing fields such as Semantic Web Service composition and hybrid system control.
Summary updated