Anytime A* is a family of variants of the A* search algorithm built so that a search can be interrupted at any moment and still hand back a valid, if imperfect, path. Plain A* must run to completion to be optimal, which is too slow for many purposes, so the anytime variants first find a quick non-optimal solution by inflating the heuristic, as weighted A* does, and then improve it step by step. The family includes ATA* from 2002, Anytime Repairing A* from 2003 that reuses earlier work, Anytime Dynamic A* from 2005, Anytime Weighted A* and Randomized Weighted A* from 2021. Anytime weighted A* tests for a goal when a node is generated, keeps the best goal so far, and reports an error bound until the optimal solution is proven.
Facts
Problem Solvedpathfinding or graph traversal 1 Connections
In Field
Source Anytime A* (Wikipedia)
Uses Design Technique
Source Anytime A* (Wikipedia)
Sources
1. Anytime A* (Wikipedia)
Lead, problem solved
can return a valid solution to a pathfinding or graph traversal problem even if it is interrupted before it ends
In Group: Heuristic Graph Search and Pathfinding Algorithms, Lead
anytime A* is a family of variants of the A* search algorithm
In Field: Artificial Intelligence, Lead
This ability to quickly generate solutions has made it attractive to Search-base sites and AI designs.
Uses Design Technique: Heuristics, Background and history
A*'s optimality can be sacrificed in order to reduce the execution time by inflating the heuristic, as in weighted A* from 1970.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.