Abstract
Much recent work in satisficing planning has aimed at striking a balance between coverage—solving as many problems as possible—and plan quality. Current planners achieve near-perfect coverage on the latest IPC benchmarks. It is therefore natural to investigate their scaling behavior on more difficult instances. Among state-of-the-art planners, LAMA is able to generate high-quality plans, but its coverage drops off rapidly with increasing problem complexity. The Arvand planner scales to much harder instances but generates lower-quality plans. This paper introduces a new algorithm, Monte Carlo Random Walk-based Local Tree Search (MRW-LTS), which uses random walks to selectively build local search trees. Experiments demonstrate that MRW-LTS combines a scaling behavior that is better than LAMA's with a plan quality that is better than Arvand's.
Introduction
In deterministic planning, the search for a valid sequence of actions often encounters a fundamental trade-off between systematic exploration and stochastic sampling. Systematic planners like LAMA provide high-quality solutions but often struggle with the state-space explosion inherent in massive problem instances. Conversely, planners based on Monte Carlo Random Walks (MRW), such as Arvand, excel at navigating large search spaces and bypassing plateaus but frequently produce suboptimal, "noisy" plans.
Presented at AAAI 2011, this research introduces MRW-LTS, a hybrid approach designed to bridge this gap. By embedding local tree search within a random walk framework, the algorithm provides a mechanism to guide exploration more effectively, ensuring that the scaling benefits of stochastic search do not come at the expense of plan efficiency.
The Coverage-Quality Dilemma
In the context of "satisficing" planning—where the priority is finding any valid plan within a time limit—two primary methodologies have dominated:
- Systematic Search (e.g., LAMA): These planners use heuristic-driven search to find high-quality plans. However, their coverage (the number of problems solved) tends to drop sharply as problem complexity increases because the search space becomes too large to manage systematically.
- Monte Carlo Random Walks (e.g., Arvand): These planners use random walks to explore the state space. While they can solve much larger problems by "leaping" over search plateaus, the resulting plans are often unnecessarily long and inefficient.
MRW-LTS was developed to address Arvand’s quality issues while maintaining its robust scaling capabilities.
Methodology: MRW-LTS
The core innovation of MRW-LTS is the use of a selective, unbalanced local search tree to determine the next "jump" in the planning process. Instead of moving blindly based on a single random walk, the algorithm builds a local structure to evaluate potential paths.
Key Algorithmic Components
- Local Tree Search (LTS): Before committing to a move, the algorithm grows a tree from the current state. It employs an $ε$-greedy strategy, where it typically exploits the most promising child node based on heuristic values but occasionally explores random nodes to maintain diversity.
- Lazy Expansion: To optimize memory and computational overhead, nodes are only expanded (generating their children) upon their second visit. This ensures that resources are focused on paths that show initial promise.
- Heuristic Backpropagation: Upon the completion of a random walk, the heuristic value of the final state—representing the estimated distance to the goal—is propagated back up the local tree. This updates the parent nodes and informs future selection within that local search.
- Strict Jump and Restart Policies: MRW-LTS is more conservative than its predecessors. It allows the local tree to mature before making a move, ensuring the next step is well-vetted. If a search step fails to find an improvement, the algorithm restarts to avoid becoming trapped in local minima.
Experimental Evaluation
The authors evaluated MRW-LTS (referred to in some results as Arvand-LTS) against the state-of-the-art using the IPC-2008 benchmarks and a set of "Scaled Hard Problems" designed to test limits in domains like Elevators, Openstacks, Transport, and Woodworking.
Scaling and Performance
- Scaling Behavior: In the Elevator domain, MRW-LTS demonstrated superior scaling. As the number of passengers and complexity increased, MRW-LTS maintained high coverage while LAMA’s performance declined.
- Benchmark Success: On the standard IPC-2008 suite, MRW-LTS achieved a total score of 234.2, outperforming the original Arvand (228.4) and matching the competitive performance of LAMA (233.96).
- Quality Improvements: The integration of local tree search successfully mitigated the "veering" problem—where pure random walks drift away from optimal paths—resulting in significantly shorter and higher-quality plans than those produced by Arvand.
Discussion and Insights
The success of MRW-LTS stems from its treatment of heuristics as a "compass" rather than a "map." By acknowledging that heuristic signals can be noisy, the algorithm uses local exploration to refine those signals. The "selective unbalance" of the local tree allows the planner to pour its computational budget into the most promising branches, effectively tethering random walks to high-quality areas of the search space.
However, this quality comes with a trade-off in raw speed. MRW-LTS performs more computation before each move compared to pure random walk methods. Additionally, the current selection function does not fully account for varying action costs, which remains an area for future refinement.
Conclusion
MRW-LTS represents a significant step forward in deterministic planning by successfully combining the scaling power of Monte Carlo methods with the plan quality of systematic search. By using local trees to guide stochastic exploration, the algorithm provides a robust solution for increasingly complex planning problems where traditional methods fail to scale.
Summary updated