Date of Award
Spring 2011
Project Type
Thesis
Program or Major
Computer Science
Degree Name
Master of Science
First Advisor
Wheeler Ruml
Abstract
In many heuristic search problems of practical interest, insufficient time is available to find a provably optimal solution. The currently accepted methods of finding a best possible sub-optimal solution within a time deadline are the anytime methods which do not directly consider the time remaining in the search. My thesis is that a deadline-cognizant approach, one which attempts to expend all available search effort towards a single final solution, has the potential for outperforming these methods.
To support this thesis I introduce two new deadline-cognizant algorithms: Deadline Aware Search and Deadline Decision Theoretic Search. These approaches use on-line measurements of search behavior to guide the search towards the best possible solution reachable before the deadline. An empirical analysis illustrates that DAS is capable of outperforming the current incumbent methods across a wide variety of domains, the first deadline-cognizant heuristic search algorithm to do so.
Recommended Citation
Dionne, Austin, "Heuristic search under a deadline" (2011). Master's Theses and Capstones. 628.
https://scholars.unh.edu/thesis/628