A* search
In plain wordsA method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first.
A best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next. algorithm that ranks each frontier node n by f(n) = g(n) + h(n) — the cost already paid to reach n along the best route found so far, plus a heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. guess h(n) of the cost still to go — and always expands the node with the lowest f. If h is admissibleadmissible heuristic, n.: An estimate of the remaining distance to a goal that is never more than the real distance — an optimistic guess — which lets some search methods guarantee that they find the best route., A* returns an optimal path; if h is also consistent, no node is expanded twice, and no other optimal algorithm using the same heuristic expands fewer nodes, up to tie-breaking. With h = 0 it reduces to Dijkstra's algorithm. Its main limitation is memory, since it keeps every generated node; variants such as IDA*, SMA*, weighted A* (trading optimality for speed) and anytime A* address this. It is the standard pathfinding algorithm in video games, robot path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map. and route guidance.
With straight-line distance as the heuristic, A* expanded a tenth as many nodes as Dijkstra's algorithm.
Origin
Developed by Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute for navigation by the mobile robot ShakeyShakey the robot, prop. n.: A wheeled robot built at a California research institute between 1966 and 1972 that could look around, make a plan and carry it out: the first mobile robot to work out its own steps toward a goal., and published in 1968. The asterisk is usually explained as marking the optimal member of a family of 'A' algorithms, in keeping with the authors' use of starred symbols for optimal quantities.
Related
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- admissible heuristicadmissible heuristic, n.: An estimate of the remaining distance to a goal that is never more than the real distance — an optimistic guess — which lets some search methods guarantee that they find the best route.
- best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next.
- breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first.
- path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map.
- state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
- Shakey the robotShakey the robot, prop. n.: A wheeled robot built at a California research institute between 1966 and 1972 that could look around, make a plan and carry it out: the first mobile robot to work out its own steps toward a goal.
Sources
- Hart, P. E., Nilsson, N. J. & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics 4(2), 100–107.
Mentioned in
breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first., Dijkstra's algorithmDijkstra's algorithm, n.: A classic method for finding the shortest routes from one starting point to every other point on a map or network, by always settling the nearest not-yet-settled point next., heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do., path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map., state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal., admissible heuristicadmissible heuristic, n.: An estimate of the remaining distance to a goal that is never more than the real distance — an optimistic guess — which lets some search methods guarantee that they find the best route., best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next., branch and boundbranch and bound, n.: A method for finding the provably best answer to a hard puzzle: divide the possibilities into groups, quickly estimate the best any group could offer, and throw out every group that cannot beat the best answer already in hand., iterative deepening searchiterative deepening search, n.: A search strategy that explores one step deep, then starts over and explores two steps deep, then three, and so on. It repeats some work but needs very little memory and still finds the shortest answer., Nils NilssonNils Nilsson, prop. n.: An American computer scientist who co-created the A* search algorithm and the STRIPS planner for Shakey, the first robot to plan its own moves by reasoning, and wrote standard AI textbooks., probabilistic roadmapprobabilistic roadmap, n.: A planning method that scatters many random safe robot poses through a space and links nearby ones into a road network, so routes can later be looked up quickly, as on a map., Q*Q*, prop. n.: The code name of an internal OpenAI research project, reported in late 2023, said to let AI solve math problems it had never seen. Later reports linked it to OpenAI's first reasoning model, o1., Shakey the robotShakey the robot, prop. n.: A wheeled robot built at a California research institute between 1966 and 1972 that could look around, make a plan and carry it out: the first mobile robot to work out its own steps toward a goal., SRI InternationalSRI International, prop. n.: A nonprofit research institute in California, once part of Stanford University, where the Shakey robot was built and the technology behind Apple's Siri assistant began.