A Stochastic Process Model of Classical Search
  Among classical search algorithms with the same heuristic information, with
sufficient memory A* is essentially as fast as possible in finding a proven
optimal solution. However, in many situations optimal solutions are simply
infeasible, and thus search algorithms that trade solution quality for speed
are desirable. In this paper, we formalize the process of classical search as a
metalevel decision problem, the Abstract Search MDP. For any given optimization
criterion, this establishes a well-defined notion of the best possible
behaviour for a search algorithm and offers a theoretical approach to the
design of algorithms for that criterion. We proceed to approximately solve a
version of the Abstract Search MDP for anytime algorithms and thus derive a
novel search algorithm, Search by Maximizing the Incremental Rate of
Improvement (SMIRI). SMIRI is shown to outperform current state-of-the-art
anytime search algorithms on a parametrized stochastic tree model for most of
the tested parameter values.
