Abstract

Heuristic search is a central component of many important applications in AI including automated planning. While we can find optimal solutions to heuristic search problems, doing so may take hours or days. For practical app lications, this is unaccept-ably slow, and we must rely on algorithms which find solutions of high, but not optimal, quality or ones which bound the time used directly. In my dissertation, I present and analyze algorithms for the following settings : quality bounded h euristic search and time bounded heuristic search. The cen-tral theme of my doctoral work will be that taking advantage of additional information can improve the performance of heuristic search algorithms.