AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Monte-Carlo Exploration for Deterministic Planning
Hootan Nakhost, Martin Müller

Last modified: 2009-06-26


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.


Artificial Intelligence Planning; Monte-Carlo Search; Heuristic Search

Full Text: PDF