Usage
  • 148 views
  • 104 downloads

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
  • Graduation date
    2013-11
  • 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.
  • Language
    English
  • Institution
    University of Alberta
  • Degree level
    Doctoral
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Mueller, Martin (Computing Science)
  • Examining committee members and their departments
    • Hayward, Ryan (Computing Science)
    • Holte, Robert (Computing Science)
    • Schaeffer, Jonathan (Computing Science)
    • Helmert, Malte (Mathematics and Computer Science, University of Basel)