ERA

Download the full-sized PDF of Design Decisions in Suboptimal Heuristic Search-Based SystemsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3SJ1B03G

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Design Decisions in Suboptimal Heuristic Search-Based Systems Open Access

Descriptions

Other title
Subject/Keyword
Computing Science
Heuristic Search
Artificial Intelligence
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Valenzano, Richard Anthony
Supervisor and department
Sturtevant, Nathan (Computer Science, University of Denver)
Schaeffer, Jonathan (Computing Science)
Examining committee member and department
Vadim Bulitko (Computing Science)
Wheeler Ruml (Computer Science, University of New Hampshire)
Michael Buro (Computing Science)
Martin Müller (Computing Science)
Department
Department of Computing Science
Specialization

Date accepted
2014-09-26T17:09:04Z
Graduation date
2014-11
Degree
Doctor of Philosophy
Degree level
Doctoral
Abstract
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.
Language
English
DOI
doi:10.7939/R3SJ1B03G
Rights
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
Richard Anthony Valenzano, Shahab Jabbari Arfaee, Jordan Tyler Thayer, and Roni Stern. Alternative Forms of Bounded Suboptimal Search. In Proceedings of the Fifth Annual Symposium on Combinatorial Search, pages 175–176, 2012.Richard Anthony Valenzano, Shahab Jabbari Arfaee, Jordan Tyler Thayer, Roni Stern, and Nathan R. Sturtevant. Using Alternative Suboptimality Bounds in Heuristic Search. In Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, pages 233–241, 2013.Richard Anthony Valenzano, Hootan Nakhost, Martin M¨uller, Jonathan Schaeffer, and Nathan R. Sturtevant. ArvandHerd: Parallel Planning with a Portfolio. In 20th European Conference on Artificial Intelligence, pages 786–791, 2012.Richard Anthony Valenzano, Hootan Nakhost, Martin M¨uller, Nathan R. Sturtevant, and Jonathan Schaeffer. ArvandHerd: Parallel Planning with a Portfolio. In The 2011 International Planning Competition [26], pages 113– 116.  http://hdl.handle.net/10016/11710.Richard
Anthony Valenzano, Nathan R. Sturtevant, and Jonathan Schaeffer. Adding Exploration to Greedy Best-First Search. Technical Report TR13-06, University of Alberta, 2013.Richard Anthony Valenzano, Nathan R. Sturtevant, and Jonathan Schaeffer. Worst-Case Solution Quality Analysis When Not Re-Expanding Nodes in Best-First Search. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.Richard Anthony Valenzano, Nathan R. Sturtevant, Jonathan Schaeffer, and Fan Xie. A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration. In Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, pages 375–379, 2014.

File Details

Date Uploaded
Date Modified
2014-11-15T08:21:36.548+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 1167236
Last modified: 2015:10:12 14:28:32-06:00
Filename: Valenzano_Richard_A_201409_PhD.pdf
Original checksum: 3a7e6308ac2740fce7053229c6b5ac2e
Well formed: true
Valid: true
Status message: Too many fonts to report; some fonts omitted. Total fonts = 1853
Page count: 251
Activity of users you follow
User Activity Date