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

  • Computing Science
  • Heuristic Search
  • Artificial Intelligence

• Graduation date

  Fall 2014

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3SJ1B03G

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