Download the full-sized PDF of Random Walk Planning: Theory, Practice, and ApplicationDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Random Walk Planning: Theory, Practice, and Application Open Access


Other title
Resource-constrained Planning
AI planning
Random Walk Theory
Random Walk Planning
Heuristic Search
Plan Improvement
Type of item
Degree grantor
University of Alberta
Author or creator
Nakhost, Hootan
Supervisor and department
Mueller, Martin (Computing Science)
Examining committee member and department
Helmert, Malte (Mathematics and Computer Science, University of Basel)
Hayward, Ryan (Computing Science)
Holte, Robert (Computing Science)
Schaeffer, Jonathan (Computing Science)
Department of Computing Science

Date accepted
Graduation date
Doctor of Philosophy
Degree level
This thesis introduces random walk (RW) planning as a new search paradigm for satisficing planning by studying its theory, its practical relevance, and applications. We develop a theoretical framework that explains the strengths and weaknesses of random walks as a tool for heuristic search. 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 and show that the developed techniques implemented on top of RWS greatly outperform the state of the art in solving resource-constrained tasks. While RWS alone can lead to inefficient 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 coverage and solution quality.
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication
Hootan Nakhost, and Martin Mueller. A Theoretical Framework to Study Random Walk Planning. Proceedings of the 3rd Annual Symposium on Combinatorial Search (SOCS'12), 2012Richard Valenzano, Hootan Nakhost, Martin Mueller, Jonathan Schaeffer, Nathan Sturtevant. ArvandHerd: Parallel Planning with a Portfolio. Proceedings of the 20st European Conference on AI (ECAI'12), 2012Hootan Nakhost, Joerg Hoffmann, and Martin Mueller. Resource-Constrained Planning: A Monte-Carlo Random Walk Approach. Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS'12), 2012.Fan Xie, Hootan Nakhost, and Martin Mueller. Planning via Random Walk-Driven Local Search. Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS'12), 2012Hootan Nakhost and Martin Mueller. Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement. Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10), pp. 137-144, 2010.Hootan Nakhost and Martin Mueller. Monte-Carlo Exploration for Deterministic Planning. Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), pp. 1766-1771, 2009.Hootan Nakhost and Martin Mueller. Towards a second generation random walk planner: an experimental exploration. Accepted for IJCAI 2013.

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 4732800
Last modified: 2015:10:12 13:38:40-06:00
Filename: Nakhost_Hootan_Spring 2013.pdf
Original checksum: ad0b671d1d725769c0251c42deba2553
Well formed: false
Valid: false
Status message: Lexical error offset=4709119
Page count: 124
Activity of users you follow
User Activity Date