Anytime A*

In computer science, anytime A* is a family of variants of the A* search algorithm. Like other anytime algorithms, it has a flexible time cost, can return a valid solution to a pathfinding or graph traversal problem even if it is interrupted before it ends, by generating a fast, non-optimal solution before progressively optimizing it. This ability to quickly generate solutions has made it attractive to Search-base sites and AI designs.

Background and history

Running the optimal A* algorithm to completion is too expensive for many purposes. A*'s optimality can be sacrificed in order to reduce the 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. A more efficient and error-bounded version that reuses results, Anytime Repairing A* (ARA*), was reported in 2003. 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*. Anytime Weighted A* (1997, 2007) is similar to weighted A*, except that it continues the search after finding the first solution. It finds better solutions iteratively and ultimately finds the optimal solution without repeating previous work and also provides error bounds throughout the search. Randomized Weighted A* (2021) introduced randomization into Anytime Weighted A* and demonstrated better empirical performance.

Difference from A*

Weighted A* search that uses a heuristic that is w = 5.0 times a consistent heuristic and obtains a suboptimal path.

A* search 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. Anytime A* family of algorithms typically build upon the weighted version of the A* search: where one uses f_w(n) = g(n) + w × h(n), w > 1, and performs the A* search as usual, which eventually happens faster since fewer nodes are expanded.

ATA* involves running weighted A* multiple times with w gradually lowering each time until w=1 when the search just becomes plain A*. Although this could work by calling A* repeatedly and discarding all previous memory, ARA* does this by introducing a way of updating the path. The initial value of w determines the minimal (first-time) runtime of ATA*.

Anytime weighted A* turns weighted A* into an anytime algorithm as follows. Each goal test is done at node generation instead of node expansion, and the current solution becomes the best goal node so far. Unless the algorithm is interrupted, the search continues until the optimal solution is found. During the search, the error bound is the cost of the current solution c minus the least f-value in the open list. The optimal solution is detected when no more nodes with f(n) ≤ c remain open, and at that point the algorithm terminates with c as the cost of optimal solution. In 2021, it was discovered that given a search time-limit, Anytime weighted A* yields better solutions on average by simply switching the weight randomly after each node expansion than by using a fine-tuned static weight or by gradually lowering the weight after each solution.