Date of Award

Spring 2011

Project Type


Program or Major

Computer Science

Degree Name

Master of Science

First Advisor

Wheeler Ruml


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.