Steps Towards a Science of Heuristic Search

There are many algorithms designed to solve the shortest path problem. Each of the published algorithms has a demonstrated use; a situation in which it is the clear choice.  Unfortunately, if faced with a novel problem, there is no reliable robust way to figure out which algorithm should be used to solve the new problem. When classifying things, the first step is to identify relevant features for classifications.  In the context of heuristic search, it not clear what pieces of information should be used to predict search algorithm performance, and the question of algorithm selection for a novel domain is an open question. We first analyze which domain attributes common algorithms leverage, and discuss how to identify domains containing these attributes.  In addition to discussing how to classify domains, we also discuss why the classifications matter for various algorithms.  Ultimately, this will allow us to offer more accurate runtime predictions for various algorithms we analyze, allowing us to determine which algorithm will likely offer the best performance.