  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.
