Anytime A*

In computer science, anytime A* (ATA*) 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.[1] This ability to spit out quick 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 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 (original 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]

Difference from A*

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* with a gradually lowering heuristic to optimal. 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.[5] The initial, maximum weight of heuristic used determines the minimal (first-time) runtime of ATA*.

Limitation

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.[5]

References
  1. Likhachebv, Maxim; Gordon, Geoff; Thrun, Sebastian. "ARA*: formal analysis" (PDF). School of Computer Science, Carnegie Mellon University. Retrieved 24 July 2018. Cite journal requires |journal= (help)
  2. R. Zhou and E. A. Hansen. Multiple sequence alignment using A*. In Proc. of the National Conference on Artificial Intelligence (AAAI), 2002.
  3. Likhachev, M.; Gordon, G.; and Thrun, S. 2003. ARA*: Anytime A* with provable bounds on sub-optimality. In Advances in Neural Information Processing Systems. MIT Press.
  4. Krause, Alex (2005). "Anytime Dynamic A*: An Anytime, Replanning Algorithm". Proceedings of the Fifteenth International Conference on International Conference on Automated Planning and Scheduling.
  5. Likhachebv, Maxim; Gordon, Geoff; Thrun, Sebastian. "ARA*: Anytime A* with Provable Bounds on Sub-Optimality" (PDF). School of Computer Science, Carnegie Mellon University. Retrieved 24 April 2018. Cite journal requires |journal= (help)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.