Abstract
Search methods based on Monte-Carlo simulation have recently led to breakthrough performance improvements in difficult game-playing domains such as Go and General Game Playing. Monte-Carlo Random Walk (MRW) planning applies Monte-Carlo ideas to deterministic classical planning. In the forward chaining planner ARVAND, Monte-Carlo random walks are used to explore the local neighborhood of a search state for action selection. In contrast to the stochastic local search approach used in the recent planner Identidem, random walks yield a larger and unbiased sample of the search neighborhood, and require state evaluations only at the endpoints of each walk. On IPC-4 competition problems, the performance of ARVAND is competitive with state of the art systems.
Introduction
In AI planning, "satisficing" planners aim to find any valid solution quickly, rather than the absolute shortest one. Most successful planners use local search guided by heuristics—mathematical estimates of the distance to a goal state. However, these methods face two major hurdles: local minima (plateaus) where the heuristic provides no guidance, and the high computational cost of sophisticated heuristics like those used in Fast Forward (FF).
Traditional local search is "greedy," exploiting local knowledge immediately. If the heuristic is misleading, the planner can easily become trapped. This paper introduces ARVAND, a planner that utilizes Monte-Carlo Random Walks (MRW) to navigate complex search spaces. By favoring randomized exploration over greedy local search, ARVAND effectively escapes the traps that often hinder state-of-the-art systems.
Methodology: Monte-Carlo Random Walks
The core of ARVAND is the Monte-Carlo Random Walk (MRW) algorithm. Instead of evaluating every immediate neighbor, the planner performs multiple random walks of a specified length from the current state.
Key Features of MRW:
- Delayed Evaluation: The expensive heuristic is only computed at the end of each walk. This leverages the fact that applying actions is significantly faster than evaluating states.
- Iterative Deepening: If no better state is found, the walk length is increased, allowing the planner to take "bigger jumps" to escape larger plateaus.
- Acceptable Progress: To maintain efficiency, exploration stops as soon as a walk reaches a state deemed "good enough" based on a running average of recent progress.
Statistical Enhancements:
- Monte-Carlo Deadlock Avoidance (MDA): Uses Gibbs sampling to penalize actions that frequently lead to "dead ends" (walks that terminate prematurely).
- Monte-Carlo with Helpful Actions (MHA): Biases walks toward "helpful actions" identified by the heuristic at the end of successful walks.
Experimental Evaluation
ARVAND was evaluated using benchmarks from the IPC-4 (International Planning Competition), covering domains like logistics (Airport, Tankage), complex logic (Dining Philosophers), and large-scale problems (Satellite, PSR).
Performance and Robustness
ARVAND proved highly competitive with top-tier planners such as FF, Marvin, YAHSP, and SGPlan. It solved the highest percentage of tasks in several tested domains.
A notable success was in the "Philosophers" domain, which is notorious for local minima. While a base random walk solved only 21% of tasks, the addition of MDA boosted the success rate to 81% (and 94% over 10 runs), demonstrating the power of biased exploration in difficult search topologies.
Discussion and Future Work
ARVAND's success highlights the advantage of "cheap" action application over "expensive" heuristic evaluation. By performing thousands of steps for every evaluation, MRW provides a deeper, unbiased sample of the search space than traditional stochastic local search.
However, some limitations remain. Because walks are random, the resulting plans can be longer and less optimal than those from greedy planners, often requiring post-processing for pruning. Additionally, on "easy" problems where heuristics are highly accurate, the overhead of exploration can make ARVAND slower than simple greedy search.
Future research directions include integrating more advanced Monte-Carlo techniques, such as UCT (Monte-Carlo Tree Search) or Rapidly-exploring Random Trees (RRTs), to further refine search space sampling.
Summary updated