A Stochastic Process Model of Classical Search
This work addresses the need for efficient anytime search algorithms in domains where optimal solutions are computationally infeasible, representing an incremental advancement in search algorithm theory.
The paper tackles the problem of designing search algorithms that trade solution quality for speed when optimal solutions are infeasible, by formalizing classical search as a metalevel decision problem called the Abstract Search MDP and deriving a novel algorithm, SMIRI, which outperforms state-of-the-art anytime search algorithms on a parametrized stochastic tree model for most tested parameter values.
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.