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 applications, this is unacceptably 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 heuristic search and time bounded heuristic search. The central theme of my doctoral work will be that taking advantage of additional information can improve the performance of heuristic search algorithms.