Design Decisions in Suboptimal Heuristic Search-Based Systems

  • Author / Creator
    Valenzano, Richard Anthony
  • Heuristic search has been shown to be an effective way to solve state-space problems. While many heuristic search techniques are guaranteed to find the best solution, these are often not feasible given practical resource requirements. In such cases, it is necessary to sacrifice solution optimality in exchange for a faster search. When a system designer is building a suboptimal heuristic search system to solve a set of given state-space problems, there are many decisions to be made that can greatly impact system performance. These include the need to select an appropriate algorithm from the many that have been proposed in the suboptimal heuristic search literature, selecting values for the parameters in these algorithms, and deciding on which search enhancements to employ. The goal of this dissertation is to aid a system designer in this endeavour by increasing our understanding of what choices need to be considered and how these choices impact algorithm performance. In particular, we show that this large design space can be handled effectively through the use of an algorithm portfolio by building the state-of-the-art multi-core planner, ArvandHerd. Next we isolate the impact of inducing random exploration into greedy algorithms, and demonstrate that this option can often add useful variation into search. We then identify what choices are available to a system designer when there are given requirements on the quality of solutions found — even non-traditional ones — by showing that many existing algorithm frameworks can be modified accordingly to be guaranteed to satisfy a large range of possible requirements. Finally, we will examine the technique of “not re-expanding nodes” to better understand how the choice of whether or not to use this technique can impact the quality of solutions found.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Doctor of Philosophy
  • DOI
  • 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
  • Institution
    University of Alberta
  • Degree level
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Sturtevant, Nathan (Computer Science, University of Denver)
    • Schaeffer, Jonathan (Computing Science)
  • Examining committee members and their departments
    • Wheeler Ruml (Computer Science, University of New Hampshire)
    • Vadim Bulitko (Computing Science)
    • Martin Müller (Computing Science)
    • Michael Buro (Computing Science)