AAAI Publications, Twenty-Second International Conference on Automated Planning and Scheduling

Font Size: 
Planning Via Random Walk-Driven Local Search
Fan Xie, Hootan Nakhost, Martin Müller

Last modified: 2012-05-14


The ideas of local search and random walks have been used successfully in several recent satisficing planners. Random Walk-Driven Local Search (RW-LS) is a strong new addition to this family of planning algorithms. The method uses a greedy best-first search driven by a combination of random walks and direct node evaluation. In this way, RW-LS balances between exploration and exploitation. The algorithm has been implemented in the system Arvand-LS. Its performance is evaluated against other state of the art planners on problems from IPC-2011, as well as on scaled up instances from several IPC domains. The results show significant improvements in both coverage and plan quality.


satisficing planning; local search; random walk

Full Text: PDF