Random Walk Planning: Theory, Practice, and Application

• Author / Creator

  Nakhost, Hootan

• 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.

• Subjects / Keywords

  • Plan Improvement
  • Heuristic Search
  • AI planning
  • Random Walk Planning
  • Random Walk Theory
  • Resource-constrained Planning

• Graduation date

  Fall 2013

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3896Q

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.