Monte-Carlo Exploration for Deterministic Planning

Hootan Nakhost, Martin MüllerIJCAI 2009 · OpenReview

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:

  1. Monte-Carlo Deadlock Avoidance (MDA): Uses Gibbs sampling to penalize actions that frequently lead to "dead ends" (walks that terminate prematurely).
  2. 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).

Runtime comparison between ARVAND and FF on IPC-4 problems.

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.

Comparison of ARVAND coverage with state-of-the-art planners across IPC-4 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

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.
BibTeX
@inproceedings{nakhost2009monte,
  author = {Hootan Nakhost and Martin Müller},
  title = {{Monte-Carlo Exploration for Deterministic Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=B1V5tmG_-S},
}
Figure