Anytime A*

Running the optimal A* algorithm to completion is too expensive for many purposes. A*'s optimality can be sacrificed in order to gain a quicker execution time by inflating the heuristic, as in weighted A* from 1970. Iteratively reducing the degree the heuristic is "inflated" provides a naive anytime algorithm (ATA*, 2002), but this repeats previous work.[2] A more efficient and error-bounded version that reuses results, Anytime Repairing A* (ARA*), was reported in 2003.[1][3] A dynamic (in the sense of D*) modification of ARA*, Anytime Dynamic A* (ADA*) was published in 2005. It combines aspects of D* Lite and ARA*.[4] Anytime Weighted A* (1997, 2007) is similar to weighted A*, except that it continues the search after finding the first solution. It finds successively better solutions (and ultimately the optimal solution) without repeating previous work and also provides error bounds throughout the search. [5] [6]

A* algorithm can be presented by the function of f(n) = g(n) + h(n), where n is the last node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic that estimates the cost of the cheapest path from n to the goal. Different than the A* algorithm, the most important function of Anytime A* algorithm is that, they can be stopped and then can be restarted at any time.[1]

ATA* involves running A* multiple times each with a heuristic that gradually lowers to optimal the more times it is run. This is done by replacing the h(n) term with a weight ε × h(n) where ε gradually lowers to 1, when the search just becomes plain A*. Although this could work by calling A* repeatedly, discarding all previous memory as in old ATA*, ARA* does this by introducing a way of updating the path.[7] The initial, maximum weight of heuristic used determines the minimal (first-time) runtime of ATA*.

The Anytime A* algorithm proves to be useful as it usually finds a first, possibly highly sub-optimal, solution very quickly and then continually works on improving the solution until the allocated time expires. Unfortunately, it can rarely provide bounds on the sub-optimality of its solutions unless the cost of an optimal solution is already known. ARA* improves on this issue and is able to control the sub-optimality bound.[7]