Steps Towards a Science of Heuristic Search

Abstract

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.