# A* search algorithm

A*A* algorithmA* searchA* graph search algorithmA-starheuristic searchTBA*
A* (pronounced "A-star") is a graph traversal and path search algorithm, which is often used in computer science due to its completeness, optimality, and optimal efficiency.wikipedia
102 Related Articles

### Pathfinding

Pathingpath findingpath search
A* (pronounced "A-star") is a graph traversal and path search algorithm, which is often used in computer science due to its completeness, optimality, and optimal efficiency.
Algorithms such as A* and Dijkstra's algorithm strategically eliminate paths, either through heuristics or through dynamic programming.

### Shakey the robot

Shakeye.g. Shakeythe Shakey project
A* was created as part of the Shakey project, which had the aim of building a mobile robot that could plan its own actions.
Some of the most notable results of the project include the A* search algorithm, the Hough transform, and the visibility graph method.

### Edsger W. Dijkstra

It can be seen as an extension of Edsger Dijkstra's 1959 algorithm.
One of the most used heuristic algorithms is the A* search algorithm (first described by Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute in 1968), the main goal is to reduce the run time by reducing the search space.

### Peter E. Hart

Peter HartHart
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968.
While at the SRI International Artificial Intelligence Center, Hart co-authored 20 papers, among them the initial exposition of the A* search algorithm and the variant of the Hough transform now widely used in computer vision for finding straight line segments in images.

### Heuristic (computer science)

heuristicheuristicsheuristic algorithm
A* achieves better performance by using heuristics to guide its search.
In the case of best-first search algorithms, such as A* search, the heuristic improves the algorithm's convergence while maintaining its correctness as long as the heuristic is admissible.

### Bertram Raphael

Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968.
While at SRI, he helped invent the A* search algorithm and develop Shakey the robot, which was one of the first projects sponsored by DARPA; Raphael directed work on Shakey from 1970 to 1971.

### Nils John Nilsson

Nils NilssonNils J. NilssonNilsson
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968.
Although the basic idea of using logical reasoning to decide on actions is due to John McCarthy, Nilsson's group was the first to embody it in a complete agent, along the way inventing the A* search algorithm and founding the field of automated temporal planning.

### Dijkstra's algorithm

Dijkstra algorithmDijkstraShortest Path First
It can be seen as an extension of Edsger Dijkstra's 1959 algorithm.
Further optimizations of Dijkstra's algorithm for the single-target case include bidirectional variants, goal-directed variants such as the A* algorithm (see ), graph pruning to determine which nodes are likely to form the middle segment of shortest paths (reach-based routing), and hierarchical decompositions of the input graph that reduce

If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal.
For example, in A* search the evaluation function (where

### Best-first search

best-firstBest firstGreedy best-first search
A* is an informed search algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.).
The A* search algorithm is an example of a best-first search algorithm, as is B*.

### Journey planner

public transport route plannerroute plannerroute planning
Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases.
Routing on such a graph can be accomplished effectively using any of a number of routing algorithms such as Dijkstra's, A*, Floyd-Warshall, or Johnson's algorithm.

### Iterative deepening A*

IDA*
In practice, this turns out to be the biggest drawback of A* search, leading to the development of memory-bounded heuristic searches, such as Iterative deepening A*, memory bounded A*, and SMA*.
It is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to evaluate the remaining cost to get to the goal from the A* search algorithm.

### Any-angle path planning

any-angleany-angle searchBlock A*
Other pathfinding algorithms such as A* constrain the paths to a grid, which produces jagged, indirect paths.

### Priority queue

priority queuingPriority queuesmin-priority queue
Typical implementations of A* use a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand.
Best-first search algorithms, like the A* search algorithm, find the shortest path between two vertices or nodes of a weighted graph, trying out the most promising routes first.

### Incremental heuristic search

incrementalFringe Saving A* (FSA*)incremental search algorithms
Heuristic search algorithms, often based on A*, use heuristic knowledge in the form of approximations of the goal distances to focus the search and solve search problems potentially much faster than uninformed search algorithms.

### Anytime A*

In computer science, anytime A*, also known as anytime repairing A* (ARA*), is a variant of the A* search algorithm.

### Consistent heuristic

monotone, or consistent
of the graph (where d denotes the length of that edge), then h is called monotone, or consistent.
In the A* search algorithm, using a consistent heuristic means that once a node is expanded, the cost by which it was reached is the lowest possible, under the same conditions that Dijkstra's algorithm requires in solving the shortest path problem (no negative cost cycles).

### Branch and bound

branch-and-boundbranch-and-bound algorithmPruning
A* itself is a special case of a generalization of branch and bound.
Examples of best-first search algorithms with this premise are Dijkstra's algorithm and its descendant A* search.

### Lifelong Planning A*

Lifelong Planning A* (LPA*)LPA*
LPA* or Lifelong Planning A* is an incremental heuristic search algorithm based on A*.

### SMA*

In practice, this turns out to be the biggest drawback of A* search, leading to the development of memory-bounded heuristic searches, such as Iterative deepening A*, memory bounded A*, and SMA*.
SMA* or Simplified Memory Bounded A* is a shortest path algorithm based on the A* algorithm.

### Fringe search

Fringe
In essence, fringe search is a middle ground between A* and the iterative deepening A* variant (IDA*).

### Bidirectional search

bidirectionalbidirectional versions
A* can also be adapted to a bidirectional search algorithm.
As in A* search, bi-directional search can be guided by a heuristic estimate of the remaining distance to the goal (in the forward tree) or from the start (in the backward tree).

### Greedy algorithm

greedygreedilygreedy heuristic
What sets A* apart from a greedy best-first search algorithm is that it takes the cost/distance already traveled,

### D*

D* LiteStentz's Algorithm

### Theta*

Theta* is an any-angle path planning algorithm that is based on the A* search algorithm.