A * algorithm

The A * algorithm ("A star" or English "a star", also A * search ) belongs to the class of informed search algorithms . In computer science, it is used to calculate the shortest path between two nodes in a graph with positive edge weights . It was first described in 1968 by Peter Hart , Nils J. Nilsson and Bertram Raphael . The algorithm is considered to be a generalization and extension of the Dijkstra algorithm , but in many cases conversely A * can also be reduced to Dijkstra.

In contrast to uninformed search algorithms, the A * algorithm uses an estimation function ( heuristic ) to search in a targeted manner and thus to reduce the runtime. The algorithm is complete and optimal. This means that an optimal solution is always found, if one exists.

Idea of the algorithm

The A * algorithm always examines the nodes first that are likely to lead quickly to the goal. In order to determine the most promising node, each known node is assigned a value which indicates an estimate of how long the path from the start to the destination is in the best case using the node under consideration. The node with the lowest value is examined next. ${\ displaystyle x}$ ${\ displaystyle f (x)}$ ${\ displaystyle f}$

${\ displaystyle f (x) = g (x) + h (x)}$

For a node denotes the previous costs from the starting node to reach. denotes the estimated cost from to the destination node. The heuristic used must never overestimate the costs. For example, the route search which is a straight line , a suitable estimate: The actual track is never shorter than the direct connection. ${\ displaystyle x}$ ${\ displaystyle g (x)}$ ${\ displaystyle x}$ ${\ displaystyle h (x)}$ ${\ displaystyle x}$

functionality

Illustration of finding the way around an obstacle using an A * search. Known nodes are outlined in light blue , nodes examined afterwards are filled in. The color of the latter marks the distance to the target; the greener, the closer it is to the goal. It can be observed that the A * first strives in a straight line towards the target until it hits the obstacle. When it reaches the target node, it first explores alternative nodes in the open list before terminating.

During the search, the nodes are divided into three different classes:

unknown nodes: These nodes were not yet found during the search. No way is yet known to them. Every node (except the starting node) is unknown at the beginning of the algorithm .

Known nodes: A (possibly suboptimal) path is known to this node. All known nodes are saved together with their value in the so-called Open List . The most promising node is always selected from this list and examined. The implementation of the Open List has a major impact on the runtime and is often implemented as a simple priority queue (e.g. binary heap ). At the beginning only the starting node is known . ${\ displaystyle f}$

Finally examined nodes: The shortest path to these nodes is known. The nodes that are finally examined are saved in the so-called closed list so that they are not examined more than once. In order to be able to efficiently decide whether an element is on the closed list , this is often implemented as a set . The closed list is initially empty.

Each known or finally visited node contains a pointer to its (best to date) predecessor node. With the help of these pointers, the path can be traced back to the start node.

If a node is finally examined (also expanded or relaxed ), its successor nodes are added to the open list and added to the closed list . For newly inserted successor nodes, the previous pointers are set to. If a successor node is already on the closed list , it is not added to the open list again and its predecessor pointer is not changed. If a successor node is already on the open list , the node is only updated ( value and previous pointer) if the new path to it is shorter than the previous one. ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle f}$

If the target node is finally examined, the algorithm terminates. The path found is reconstructed and output with the help of the previous pointer. If the Open List is empty, there are no more nodes that could be examined. In this case the algorithm terminates because there is no solution.

Due to the previous pointers, the path found is output from the destination backwards to the start. To get the route in the correct order, e.g. B. before the route search start and destination are swapped. Thus, the search is made from the actual destination to the start and the route output begins at the original start node.

Note: The closed list can also be implemented indirectly. For this purpose, the nodes finally examined also save their value. If a node that was finally examined is found again, its old value is lower than the new one, since the shortest path to this node has already been found. The node is therefore not added to the Open List again .

{\ displaystyle f}

{\ displaystyle f}

If no closed list is used, it must be ensured in some other way that nodes are not examined more than once. Otherwise the worst-case runtime is worse than the square. In addition, the algorithm no longer terminates if there is no solution. The nodes are then examined infinitely often because the open list is never empty.

declare openlist as PriorityQueue with Nodes // Prioritätenwarteschlange
declare closedlist as Set with Nodes

program a-star
    // Initialisierung der Open List, die Closed List ist noch leer
    // (die Priorität bzw. der f-Wert des Startknotens ist unerheblich)
    openlist.enqueue(startknoten, 0)
    // diese Schleife wird durchlaufen bis entweder
    // - die optimale Lösung gefunden wurde oder
    // - feststeht, dass keine Lösung existiert
    repeat
        // Knoten mit dem geringsten f-Wert aus der Open List entfernen
        currentNode := openlist.removeMin()
        // Wurde das Ziel gefunden?
        if currentNode == zielknoten then
            return PathFound
        // Der aktuelle Knoten soll durch nachfolgende Funktionen
        // nicht weiter untersucht werden, damit keine Zyklen entstehen
        closedlist.add(currentNode)
        // Wenn das Ziel noch nicht gefunden wurde: Nachfolgeknoten
        // des aktuellen Knotens auf die Open List setzen
        expandNode(currentNode)
    until openlist.isEmpty()
    // die Open List ist leer, es existiert kein Pfad zum Ziel
    return NoPathFound
end

// überprüft alle Nachfolgeknoten und fügt sie der Open List hinzu, wenn entweder
// - der Nachfolgeknoten zum ersten Mal gefunden wird, oder
// - ein besserer Weg zu diesem Knoten gefunden wird
function expandNode(currentNode)
    foreach successor of currentNode
        // wenn der Nachfolgeknoten bereits auf der Closed List ist – tue nichts
        if closedlist.contains(successor) then
            continue
        // g-Wert für den neuen Weg berechnen: g-Wert des Vorgängers plus
        // die Kosten der gerade benutzten Kante
        tentative_g = g(currentNode) + c(currentNode, successor)
        // wenn der Nachfolgeknoten bereits auf der Open List ist,
        // aber der neue Weg nicht besser ist als der alte – tue nichts
        if openlist.contains(successor) and tentative_g >= g(successor) then
            continue
        // Vorgängerzeiger setzen und g Wert merken oder anpassen
        successor.predecessor := currentNode
        g(successor) = tentative_g
        // f-Wert des Knotens in der Open List aktualisieren
        // bzw. Knoten mit f-Wert in die Open List einfügen
        f := tentative_g + h(successor)
        if openlist.contains(successor) then
            openlist.updateKey(successor, f)
        else
            openlist.enqueue(successor, f)
    end
end

application areas

The A * algorithm generally finds an optimal path between two nodes in a graph. Optimal can mean shortest , fastest or also easiest , depending on the type of weighting function that assigns their length to the edges . Theoretically, the algorithm can solve all problems that can be represented by a graph and for which an estimate can be made of the remaining costs up to the goal. For the limitations of A * see the Disadvantages section .

A * is often used to search for routes in route planners or in computer games. The heuristic is usually the straight line distance to the target, because it is always optimistic because of the triangle inequality . Other areas of application are games such as the 15-puzzles or the ladies' problem , in which a given target state is to be achieved. The number of incorrectly placed stones can be used as a heuristic.

example

Map as a graph (information in kilometers)

In the example, the shortest route from Saarbrücken to Würzburg is to be found. The diagram shows a small selection of cities and routes. The edge lettering corresponds to the costs (here: distance in kilometers) to get from one city to the next. Each node contains the estimated distance to the target node (value of the function). The beeline is used here as the heuristic. ${\ displaystyle h}$

On the step-by-step images, the color of a node shows its status:

knows : not found yet
gray : found, is on the open list
black : examined, is on the closed list

As soon as a node has been reached, an edge points to the previous node. For all nodes on the Open List is value given. ${\ displaystyle f}$

Step 1: The starting point Saarbrücken was explored.

Step 1: All successor nodes from the starting node Saarbrücken are considered:

Kaiserslautern is added to the open list . (The cost to get from Saarbrücken to Saarbrücken is 0, the cost of the Saarbrücken - Kaiserslautern edge is 70, and the estimated remaining cost Kaiserslautern - Würzburg is 158. The cost of the edge between the nodes and .) ${\ displaystyle f_ {KL} = g (SB) + c (SB, KL) + h (KL) = 0 + 70 + 158 = 228}$ ${\ displaystyle c (k, k ')}$ ${\ displaystyle k}$ ${\ displaystyle k '}$

Karlsruhe is added to the open list . ${\ displaystyle f_ {KA} = g (SB) + c (SB, KA) + h (KA) = 0 + 145 + 140 = 285}$

Saarbrücken is entered as the previous node in both nodes. The Saarbrücken node has now been considered and is placed on the closed list . ( Intuitive: There is no point in driving around for a while, arriving at the start again, then arriving at some point and claiming that this is the best way to go.)

Step 2: Kaiserslautern has been explored.

Step 2: The Open List now contains two items. Since Kaiserslautern has the lower value, Kaiserslautern will now be examined next and its successor nodes considered. (The route via Kaiserslautern is at least 228 km long, the one via Karlsruhe at least 285 km. Therefore, it is best to check Kaiserslautern more closely first .) ${\ displaystyle f}$

Saarbrücken is already on the closed list and will not be considered any further.

Frankfurt is added to the open list . The costs to Frankfurt are calculated from the costs to Kaiserslautern plus the costs of the edge last used (Kaiserslautern - Frankfurt) . Kaiserslautern is saved as the previous node. ${\ displaystyle f_ {F} = g (KL) + c (KL, F) + h (F) = 70 + 103 + 96 = 269}$

Ludwigshafen is added to the open list . Kaiserslautern is saved as the previous node. ${\ displaystyle f_ {LU} = g (KL) + c (KL, LU) + h (LU) = 70 + 53 + 108 = 231}$

Kaiserslautern is placed on the closed list .

Step 3: Ludwigshafen was explored.

Step 3: The node with the lowest value is Ludwigshafen . (The actual costs from Ludwigshafen to Würzburg (183 km) deviate significantly from the estimate (108 km), since in this example only motorways are to be used.) ${\ displaystyle f}$

Kaiserslautern is already on the closed list and will not be considered any further.
The destination node Würzburg is found, but not yet issued as a solution, but first added to the Open List . Ludwigshafen is saved as the previous node.

Ludwigshafen is placed on the closed list .

Here an important difference between “Node is on the Open List ” and “Node is on the Closed List ” becomes clear: As long as a node has not been examined conclusively, the path to this node is only provisional. There may be a better path! By contrast, nodes on the closed list are considered conclusively. The shortest path there is known.

Step 4: Frankfurt was explored.

Step 4: Frankfurt is explored. The only successor node that is not on the Closed List is, will Wuerzburg found. The value 289 is calculated, which is lower than the previous value for Würzburg . This means that the route via Frankfurt is shorter than the route found first via Ludwigshafen . Therefore the value of Würzburg is changed. In addition, Frankfurt is now saved as the previous node. ${\ displaystyle f}$ ${\ displaystyle f}$ ${\ displaystyle f}$

Frankfurt is placed on the closed list .

Step 5: Karlsruhe was explored.

Step 5: Since Karlsruhe now has the smallest value, this node is examined next. Heilbronn is added to the Open List and Karlsruhe is placed on the Closed List . ${\ displaystyle f}$

Step 6: The destination node Würzburg has been explored.

Step 6: Now Würzburg has the lowest value and is examined: The destination has been found and the shortest route is: Saarbrücken – Kaiserslautern – Frankfurt – Würzburg . ${\ displaystyle f}$

This example is only intended to help you understand how the algorithm works. The peculiarity of the targeted search is not clear here, since all nodes are in the area of the direct connecting line Saarbrücken-Würzburg . Java applets can be found under web links , which better represent targeted searches.

Heuristics

There are two types of heuristics for the A * algorithm: legal and monotonic heuristics. Any monotonous heuristic is also allowed . So monotony is a stronger property than admissibility . In general, monotonous heuristics are used. For example, the heuristic used to estimate the distance between two cities - the straight line - is monotonic .

Permissible but not monotonous heuristics. A * algorithm with closed list after the third step. Each node has already been found and points to its previous node.

Allowed heuristic

A heuristic is permitted if the costs are never overestimated. This means that the estimated costs must always be in the interval when the actual costs are referred to. If the heuristic used is only permissible but not monotonic, then the shortest path to an expanded node is not necessarily known. It must therefore be possible to expand a node several times. So no closed list may be used. ${\ displaystyle [0; k]}$ ${\ displaystyle k}$

The diagram on the right shows an example graph and a permissible (but not monotonic) heuristic. The best route from start to finish has costs 40 and leads via nodes K1 and K2. The route via the detour node U has costs 45. The heuristic estimates costs of 40 for the starting node and costs of 30 for node K1, which in each case corresponds to the actual costs. Costs of 0 are estimated for nodes K2, U and target. Since a heuristic must not overestimate, costs of 0 are always estimated for a target node.

Example with closed list

In the first step, the start node is expanded. The two successor nodes K1 and U are found and entered in the open list with the values and . ${\ displaystyle f_ {K1} = 10 + 30 = 40}$ ${\ displaystyle f_ {U} = 25 + 0 = 25}$

In the second step, the node U is expanded because its value is the lowest. The successor node K2 is found and entered with the value in the open list. ${\ displaystyle f}$ ${\ displaystyle f_ {K2} = 35 + 0 = 35}$

In the third step, the Open List consists of node K2 with and node K1 with . So the node K2 is expanded. The two successor nodes K1 and target are found. The new value is greater than the old value. Therefore, the value for node K1 in the Open List is not updated. The target node is added to the Open List . ${\ displaystyle f_ {K2} = 35}$ ${\ displaystyle f_ {K1} = 40}$ ${\ displaystyle f_ {K1} '= 55 + 30 = 85}$ ${\ displaystyle f}$ ${\ displaystyle f_ {goal} = 45 + 0 = 45}$

In the fourth step, nodes K1 with and target with are in the open list . The expansion of K1 does not create any successor nodes, since both Start and K2 are already on the closed list . The use of the closed list prevents the optimal solution from being found here. ${\ displaystyle f_ {K1} = 40}$ ${\ displaystyle f_ {goal} = 45}$

In the fifth step, the only node on the Open List is expanded: the target node. The solution found is therefore the start – U – K2 – destination and with costs 45 not optimal.

Example without a closed list

In the first step, the start node is expanded. The two successor nodes K1 and U are found and entered in the open list with the values and . ${\ displaystyle f_ {K1} = 10 + 30 = 40}$ ${\ displaystyle f_ {U} = 25 + 0 = 25}$

In the second step, the node U is also expanded. The successor nodes K2 and Start are found and entered with the values and in the Open List . ${\ displaystyle f_ {U} = 25}$ ${\ displaystyle f_ {K2} = 35 + 0 = 35}$ ${\ displaystyle f_ {Start} = 50 + 40 = 90}$

In the third step, node K2 is expanded. The successor nodes K1 ( ), U ( ) and target ( ) are found.

{\ displaystyle f_ {K1} = 55 + 30 = 85}

{\ displaystyle f_ {U} = 45 + 0 = 45}

{\ displaystyle f_ {goal} = 45 + 0 = 45}

In the fourth step, the successor nodes of K1 ( ) are added to the Open List : Start with and K2 with . ${\ displaystyle f_ {K1} = 40}$ ${\ displaystyle f_ {Start} = 20 + 40 = 60}$ ${\ displaystyle f_ {K2} = 30 + 0 = 30}$

In the fifth step, K2 is expanded for the second time, now with . The nodes K1 ( ), U ( ) and target ( ) are found.

{\ displaystyle f_ {K2} = 30}

{\ displaystyle f_ {K1} = 50 + 30 = 80}

{\ displaystyle f_ {U} = 40 + 0 = 40}

{\ displaystyle f_ {goal} = 40 + 0 = 40}

In the sixth step has 8 nodes on the Open list ( , , , , , , , ). The two nodes U and target each have the lowest value of 40 . Which node is expanded depends on chance (more precisely: implementation details). However, this has no influence on the solution found. As soon as the destination node is expanded (either in this or in the next step), the optimal solution has been found with the path Start – K1 – K2 – Destination . ${\ displaystyle f_ {goal} = 40}$ ${\ displaystyle f_ {U} = 40}$ ${\ displaystyle f_ {U} = 45}$ ${\ displaystyle f_ {goal} = 45}$ ${\ displaystyle f_ {Start} = 60}$ ${\ displaystyle f_ {K1} = 80}$ ${\ displaystyle f_ {K1} = 85}$ ${\ displaystyle f_ {Start} = 90}$ ${\ displaystyle f}$

Monotonous heuristic

For a heuristic to be monotonic (or consistent), it must meet two conditions:

The costs must never be overestimated (condition for a permissible heuristic).
For every node and every successor node of must apply . Here refers to the actual cost of order to come. ${\ displaystyle k}$ ${\ displaystyle k '}$ ${\ displaystyle k}$ ${\ displaystyle h (k) \ leq c (k, k ') + h (k')}$ ${\ displaystyle c (k, k ')}$ ${\ displaystyle k}$ ${\ displaystyle k '}$

The second condition is a form of the triangle inequality : the estimated cost of a node can not be greater than the actual cost to a successor node plus the estimated cost of that node. ${\ displaystyle k}$ ${\ displaystyle k '}$

The permissible heuristic from the example violates this condition: The costs of node K1 are estimated at 30. If one now moves in the direction of the destination to node K2, suddenly no more costs are estimated. The following applies here . ${\ displaystyle 30 \ not \ leq 20 + 0}$

In many cases z. For example, the Euclidean distance (the air line) to the destination is a monotonous heuristic, for example for the distance traveled by a car.

If a heuristic is monotonic then it can be integrated into the cost function and the A * search becomes a Dijkstra algorithm .

properties

The A * algorithm is

complete : If a solution exists, it will be found.
optimal : The optimal solution is always found. If there are several optimal solutions, one of them is found (depending on the implementation details).
optimally efficient : There is no other algorithm that finds the solution faster using the same heuristic. (More precisely: A * expands a minimal number of nodes. )

Optimality

The A * algorithm is optimal if a monotonic heuristic is used. If no closed list is used, the optimality is retained even with a permissible heuristic. In the following, the optimality is proven using a monotonic heuristic.

Claim: The A * algorithm always finds an optimal solution.

Proof: Be an optimal solution with costs and a sub-optimal solution. Since the heuristic never overestimates the costs to the target, the following applies to each target node and in particular to : ${\ displaystyle L_ {1}}$ ${\ displaystyle K ^ {*}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {2}}$

{\ displaystyle h (L_ {2}) \! \, = 0}

Since this is a suboptimal solution, the following applies to the costs : ${\ displaystyle L_ {2}}$ ${\ displaystyle K_ {2}}$

{\ displaystyle K_ {2} \! \, = f (L_ {2}) = g (L_ {2}) + h (L_ {2}) = g (L_ {2})> K ^ {*}}

The heuristic estimates or underestimates the actual costs. So for any node on the shortest path to the optimal solution : ${\ displaystyle x}$ ${\ displaystyle L_ {1}}$

{\ displaystyle f (x) = g (x) + h (x) \ leq K ^ {*}}

The following applies:

{\ displaystyle f (x) \ leq K ^ {*} <f (L_ {2})}

This means that the A * algorithm does not choose the suboptimal solution as long as there are nodes of an optimal path in the open list (since the node with the minimum value is expanded at each step ). A sub-optimal solution would therefore only be chosen after the nodes of each optimal solution had been visited. This does not happen because the A * algorithm always outputs the first solution found and then terminates. ${\ displaystyle L_ {2}}$ ${\ displaystyle f}$

Time complexity

The time complexity (or asymptotic runtime ) described here is of little importance, since the strength of the A * algorithm lies in the targeted search and, compared to the total number of nodes, usually only a small part of it is examined. In the case of labyrinths, however, this is often not possible and the actual running time approaches the specified worst-case running time. The time complexity is estimated here only using simplifying assumptions. It depends very much on two factors:

Accuracy of the heuristic used : If the heuristic is not monotonic, the runtime becomes exponential because nodes are expanded several times. The more accurate the cost estimate, the fewer nodes are examined.
Implementation of the Open and Closed List : The costly operations in the A * algorithm are the methods to insert and remove elements in the lists, as well as to change elements in the Open List . These must be efficiently supported by the data structures used in order to enable a short runtime.

In the following, the set of nodes of the underlying graph is denoted by. It is assumed that all nodes and edges are known in advance. (This is usually the case with a route search.) The heuristic used is monotonic. The Open List is implemented as a binary heap , the Closed List as an array . (Each node has a flag indicating whether it is on the list or not.) The A * algorithm thus has a quadratic worst-case runtime: ${\ displaystyle V}$

{\ displaystyle {\ mathcal {O}} (\ vert V \ vert ^ {2})}

This runtime results as follows: The main loop of the algorithm is executed a maximum of once for each node. The functions openlist.removeMin , expandNode and closedlist.add are called a maximum of times. openlist.removeMin contains a maximum of nodes and requires a logarithmic runtime for a binary heap. closedlist.add only needs constant runtime for an array. This results in a preliminary term of: ${\ displaystyle \ vert V \ vert}$ ${\ displaystyle \ vert V \ vert}$

{\ displaystyle {\ mathcal {O}} {\ big (} \ vert V \ vert \ cdot (\ log \ vert V \ vert + {\ mathcal {O}} _ {\ textit {expandNode}}) {\ big )}}

The runtime of expandNode is made up of: closedlist.contains has a constant runtime. openlist.contains also has a constant runtime if an open list flag is also saved for each node . The call of openlist.find can be omitted if each node also saves its value. Either openlist.decreaseKey (requires linear runtime to find the corresponding element) or openlist.enqueue (requires logarithmic runtime) is called. The logarithmic run time is dominated by the linear run time. A loop run within expandNode therefore requires linear runtime. ${\ displaystyle f}$

All functions are called for each successor node. It is assumed that each node has only maximally outgoing edges. The number of loop passes within expandNode is therefore constant and can be neglected in the asymptotic run-time analysis. This assumption does not hold true for graphs in which every node is connected to almost every other node. ${\ displaystyle d}$

{\ displaystyle {\ mathcal {O}} _ {\ textit {expandNode}} = {\ mathcal {O}} (d \ cdot \ vert V \ vert) = {\ mathcal {O}} (\ vert V \ vert )}

The total term results as:

{\ displaystyle {\ mathcal {O}} {\ big (} \ vert V \ vert \ cdot (\ log \ vert V \ vert + \ vert V \ vert) {\ big)} = {\ mathcal {O}} (\ vert V \ vert \ cdot \ vert V \ vert)}

There is potential for optimization with regard to the worst-case runtime, especially with openlist.decreaseKey . There is no need for expensive searches in the heap if each node saves the position of its corresponding entry in the heap. This would reduce the running time of decreaseKey to logarithmic and the total running time to linear-logarithmic:

{\ displaystyle {\ mathcal {O}} (\ vert V \ vert \ cdot \ log \ vert V \ vert)}

disadvantage

The limiting factor for A * is often not the computing time, but the storage space. Since all known nodes are kept in memory ( open and closed list ), A * is not suitable for many problems. Even with the simple 15-puzzle , the complete graph already has nodes. If the solution is long enough, the available memory is insufficient and A * cannot find a solution. In the Related Algorithms section, there are similar algorithms that try to limit storage space consumption. ${\ displaystyle 16! = 20,922,789,888,000}$

Related algorithms

The A * algorithm is related to the Dijkstra algorithm and a Greedy algorithm . Dijkstra's algorithm does not use heuristics ( , therefore ) and only selects nodes based on previous costs. If the heuristic of the A * algorithm is monotonic, it can be included in the cost function (i.e. , ) and, equivalently, Dijkstra's algorithm can be used. A greedy algorithm, on the other hand, does not take the costs into account ( , therefore ) and only selects nodes based on the estimated remaining costs . For the route search example, the Dijkstra algorithm is more suitable if the destination is not already known before the route search (e.g. next petrol station) and therefore the use of a heuristic is not possible. ${\ displaystyle h = 0}$ ${\ displaystyle f = g}$ ${\ displaystyle g _ {\ text {new}} (x, y) = g (x, y) + h (y) -h (x)}$ ${\ displaystyle h _ {\ text {new}} = 0}$ ${\ displaystyle g = 0}$ ${\ displaystyle f = h}$

Many algorithms similar to A * try to solve the memory problem. These include:

IDA * (Iterative Deepening A *), a variant of iterative deep-first search
RBFS (Recursive Best-First Search) limits the storage space consumption linearly to the length of the solution
MA * (Memory-Bounded A *), SMA * (Simplified MA *) , each use a fixed amount of storage space

These algorithms limit storage space consumption at the expense of runtime. As a result, it may no longer be possible to keep all required nodes in memory. Bad nodes are then forgotten and may have to be regenerated later. If a monotonous heuristic is used and there is enough memory available, all of these algorithms are optimal. If the storage space limit is too restrictive, the optimal solution may be out of reach. In this case, a sub-optimal solution or no solution at all is found.

An extension of A * is the D * algorithm (dynamic A *). This algorithm is able to efficiently process new information about the environment. If, for example, a bridge is impassable, contrary to the initial assumption, the route is only partially re-planned instead of applying A * again to the slightly changed graph. Especially in dynamic or unfamiliar environments (robot moves through a disaster area), repeated planning of the path that has already been found may be necessary. Like A *, D * is optimal and optimally efficient.

Other graph-based algorithms are the Bellman-Ford algorithm (allows negative edge weights) or the Floyd and Warshall algorithm (calculates the shortest paths between all pairs of nodes).

literature

PE Hart, NJ Nilsson, B. Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths . IEEE Transactions on Systems Science and Cybernetics SSC4 (2), 1968, pp. 100-107.
PE Hart, NJ Nilsson, B. Raphael: Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" . SIGART Newsletter, 37, 1972, pp. 28-29.
Stuart Russell, Peter Norvig: Artificial Intelligence - A Modern Approach . 2004, Prentice Hall, ISBN 3-8273-7089-2 .
Anthony Stentz: Optimal and Efficient Path Planning for Partially-Known Environments . Original D * paper, ICRA International Conference on Robotics and Automation, 1994 (PDF; 239 kB).

Web links

This version was added to the list of articles worth reading on November 24, 2005 .