Английская Википедия: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.[1] 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.[3][4] 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*.[5] 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. [6] [7] Randomized Weighted A* (2021) introduced randomization into Anytime Weighted A* and demonstrated better empirical performance.[8]
Difference from A*
A* search algorithm can be presented by the function of Шаблон:Math, where Шаблон:Math is the last node on the path, Шаблон:Math is the cost of the path from the start node to Шаблон:Math, and Шаблон:Math is a heuristic that estimates the cost of the cheapest path from Шаблон:Math 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 Шаблон:Math, Шаблон:Math, and performs the A* search as usual, which eventually happens faster since fewer nodes are expanded.[1]
ATA* involves running weighted A* multiple times with Шаблон:Math gradually lowering each time until Шаблон:Math=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.[4] The initial value of Шаблон:Math determines the minimal (first-time) runtime of ATA*.
Anytime weighted A* turns weighted A* into an anytime algorithm as follows.[6][7] 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 Шаблон:Math minus the least f-value in the open list. The optimal solution is detected when no more nodes with Шаблон:Math remain open, and at that point the algorithm terminates with Шаблон:Math 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.[8]
References
