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 situationin which it is the clear choice.  Unfortunately, if faced with a novelproblem, there is no reliable robust way to figure out which algorithmshould be used to solve the new problem.When classifying things, the first step is to identify relevantfeatures for classifications.  In the context of heuristic search, itnot clear what pieces of information should be used to predict searchalgorithm performance, and the question of algorithm selection for anovel domain is an open question.We first analyze which domain attributes common algorithms leverage,and discuss how to identify domains containing these attributes.  Inaddition to discussing how to classify domains, we also discuss whythe classifications matter for various algorithms.  Ultimately, thiswill allow us to offer more accurate runtime predictions for variousalgorithms we analyze, allowing us to determine which algorithm willlikely offer the best performance.