Random Walk Planning: Theory, Practice, and Application

Doctoral dissertation
University of Alberta
Planning, Random Walk Planning, Random Walks, Arvand
Résumé :

Automated planning studies algorithms that, given a model of the world, generate a plan to achieve predefined goals. Success in automated planning not only facilitates the development of autonomous agents but also reduces the programming time and cost by providing off-the-shelf domain-independent solvers. In satisficing planning, which is the focus of this thesis, the problems are so hard that even good sub-optimal solutions are acceptable.

Most state-of-the-art planners use state-space search: the planner searches a state space in which each state corresponds to a state of the world and each state transition corresponds to an action. We introduce random walk (RW) planning as a new search paradigm for planning, by studying its theory, its practical relevance, and applications. Random walks, which are paths through a state space that follow successive randomized actions, are the building blocks of RW planning. We develop a theoretical framework that explains the strengths and weaknesses of RW as a tool for state-space search. The theory explains why and for which type of problems RW perform better than common search algorithms. Based on the theory, we propose a general framework for random walk search (RWS).

We identify and experimentally study the key components of RWS and for each component, design and test practical and adaptive algorithms. We study resource-constrained planning as an application of RWS. The need to economize limited resources, such as fuel or money, is a common feature of planning problems. Prudent consumption of resources becomes even more important if the resources are not replenishable and scarce. We show that RWS greatly outperforms the state of the art in solving resource-constrained tasks.

Compared with standard search algorithms, random walk search can solve much harder problems but may produce long plans. We introduce efficient postprocessing techniques that can significantly improve the results. We push the state of the art in planning by developing several RW planners that have strong performance in terms of both the number of problems solved and solution quality. One of these systems, ArvandHerd, won the multicore track of the 2011 international planning competition.