Predicting and Improving the Performance of Heuristic Search

Heuristic search algorithms are used to find optimal solutions to problems for which as far as we know there exist no polynomial time algorithms to find optimal solutions. These algorithms can also be used to find suboptimal solutions, but in this work we focus only on optimal solutions. The main intent of this work is to better predict the performance of heuristic search algorithms. My main contributions in this area are twofold: The first set of contributions is on Iterative-Deepening-A* (IDA*). I present the first results analyzing the performance of additive heuristics, and of disjoint additive pattern databases as a special case. In particular, independent additive heuristics reduce search multiplicatively. I also study the relationship between the size of a pattern database and number of nodes expanded. Furthermore, I give an exact derivation of what is called the equilibrium heuristic distribution. The second set of contributions is on A*. I present the first results accurately predicting the actual number of node expansions for A*. Furthermore, I propose a technique to estimate the number of states in a search graph. In the last part of this dissertation, I turn from predicting to improving performance, in particular to compression methods for pattern databases. I introduce a new compression method that can store a consistent heuristic in as few as 1.6 bits per entry.