Planning Via Random Walk-Driven Local Search - Xie, Fan; Nakhost, Hootan; Müller, Martin (Proceedings of the International Conference on Automated Planning and Scheduling, 2012)
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.