期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2007
卷号：28
页码：267-297
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：We describe how to convert the heuristic search algorithm A* into an anytime
algorithm that finds a sequence of improved solutions and eventually converges
to an optimal solution. The approach we adopt uses weighted heuristic search to
find an approximate solution quickly, and then continues the weighted search to
find improved solutions as well as to improve a bound on the suboptimality of
the current solution. When the time available to solve a search problem is
limited or uncertain, this creates an anytime heuristic search algorithm that
allows a flexible tradeoff between search time and solution quality. We analyze
the properties of the resulting Anytime A* algorithm, and consider its
performance in three domains; sliding-tile puzzles, STRIPS planning, and
multiple sequence alignment. To illustrate the generality of this approach, we
also describe how to transform the memory-efficient search algorithm Recursive
Best-First Search (RBFS) into an anytime algorithm.
