User:Regnaron/Playground

A map of Germany used for this example with the distances between some cities annotated. The numbers denote the distance between the two connected cities.

If one applies the A* search algorithm on a node u, the first thing it does, is computing all the reacheable neighbors of u. Afterwards the heuristic estimates for every of this neighbors how costly it is to get from there to the goal. For every of these neighbors v the A* search algorithm adds the estimated cost getting from v to the goal to the costs getting from u to v. This approach can be described by the following equation:

f(v) = g(v) + h(v)

Whereas h(v) stands for the estimated cost of getting from vto the goal, g(v) stands for the cumulated cost getting from the start node to v, and f(v) stands for the expected costs if one follows the path from the start to the current position (u) to v, and from there somehow further to the goal. The node that has the lowest f-value will be the one to be explored in the next step.

[edit] Example

An example for the application of the A* search algorithm is searching for a shortest path on a map. In this example the A* search algorithm will be used to compute a shortest path between the german citys of Frankfurt and Munich.

First of all, one has to find a suitable heuristic for the problem, which gets very close to the actual distance between two cities, but never overestimates the distance between the two. For this example, the straight line distance between two cities is a very good choice for a heuristic. On the one hand, all road-connections between two cities are at least as long as the airline distance between the two cities, but on the other hand, most roads will be build quite directly, so that the straight line distance should not be too optimistic. Thus, estimating the straight line distances between all cities and the goal Munich, leads to the following table which will be used for the heuristic function h(v).

Augsburg <--> Munich: 43 km
Erfurt <--> Munich: 342 km
Frankfurt <--> Munich: 353 km
Karlsruhe <--> Munich: 260 km
Kassel <--> Munich: 446 km
Mannheim <--> Munich: 311 km
Munich <--> Munich: 0 km
Nürnberg <--> Munich: 151 km
Stuttgart <--> Munich: 199 km
Würzburg <--> Munich: 229 km

Furthermore one needs the costs for all paths between two cities for gradually computing how costly it is to get from the start to a city u. These values will later be used for the function g(u) and can be obtained from the map above used for this example.

Note: In the following example, the number written in brackets behind the name of the city is the already computed value f(v) for the corresponding city v, which itself is composed of the actual distance from Frankfurt to the City v and the estimated cost of getting from that city to Munich.

First Step: Frankfurt has been explored, the next city to explore is Mannheim. In the first step, one examines all cities reacheable from Frankfurt and estimates via the given heuristic how far it is from that city to Munich. To this estimated distance one adds the actual distance already traveled by getting from Frankfurt to this city. So, in regard to the current situation, the most promosing way seems to be to get from Frankfurt to Mannheim, since this route seems to be the shortest possible because it could be as short as 396 km.

Second Step: Mannheim has been explored, the next city to explore is Karlsruhe. In the second step one now examines all the cities reacheable from Mannheim, which are only two. The first choice would be getting back to Frankfurt, which – intuitively – would be a bad idea since we just came from there, and the second choice would be to travel from Mannheim to Karlsruhe, which – in the best case – would yield in a route between Frankfurt and Munich that is as short as 425 km. If one now regards all possibilities one could choose, this route emerges to be the most promising, since all other routes one could take would yield in a route that would be – even in the best case – 21 km longer than this route. So, in the next step, Karlsruhe is going to be explored.

Third Step: Karlsruhe has been explored, the next city to explore is Würzburg In the third step all citites reacheable from Karlsruhe are to be examined. These cities are Augsburg on the one hand, and Mannheim on the other, since, if there was a route going from Mannheim to Karlsruhe, one could also use that route, to travel back to Mannheim. But if one now examines all cities, one observes that the route going from Frankfurt via Mannheim to Karlsruhe and from there further on to Munich does not necessarily have to be the shortest, since this subroute would yield in a route that is at least 458 km. But if one has a closer look at the route from Frankfurt to Würzburg, this route to Munich could be as short as 446 km, and would thereby yield in a route that is 12 km shorter than the one via Karlsruhe. Hence in the next step, Würzburg is going to be explored.

Fourth Step: Würzburg has been explored, but turned out to be a bad choice, which is why the original path via Augsburg is the one going to be looked into further. In the fourth step, Würzburg is going to be explored, and all the possible cities to travel to from Würzburg are computed and estimates are made how far it is if one travels through these cities to Munich. These cities are Nürnberg and Frankfurt. But after this computation, one has to find out, that none of the two possibile choices one could use to follow the route via Würzburg are better than the already previously considered route from Frankfurt via Mannheim and Karlsruhe to Augsburg, why the A* search algorithm will examine Augsburg in the next step.

Fifth step: Augsburg has been explored, and a way to Munich was found. But this way has not yet to be a shortest one. If one explores Augsburg in the fifth step, one detects the goal Munich. So, the exact path costs travelling from Frankfurt via Mannheim, Karlsruhe and Augsburg to München are now known, but add up to a total distance of 499 km. If one compares this via the possible distance travelling from Frankfurt via Würzbug and Nürnberg, one recognizes that by travelling through Würzburg one could possibly find a route that is only 471 km. So, if one would stop the serch for a shortest path now, as one found a path from Frankfurt to Munich, one would perhaps use a suboptimal path, because there could be a path that is 27 km shorter than the one just discovered. This is why this route is not examined further until all other routes to Munich would be at least also 499 km long, since one could not be assured to actually having found a shortest path, and not overlooked some maybe shorter path, until this is true. Hence the next city to explore is Nürnberg, since this is the currently most promising city for finding a shortest path to Munich.

Six step:: Nürnberg has been expandet, and a shortest path to Munich has been found. Now, in the sixth step, Nürnberg is further expanded, and under all possible cities one could reach from Nürnberg, there also is the city Munich. Now the exact distance for the route from Frankfurt via Würzburg and Nürnberg and finally to München is known to be 487 km. This route is in particular shorter than the path already discovered in step five. Since now the city Munich is the one with the lowest costs, it will be explored in the next step, and thereby the algorithm will terminate and will sucessfully have found a shortest path from Frankfurt to Munich which is 487 km, and goes through the cities Frankfurt, Würzburg, Nürnberg and Munich. Besides the fact that actually a shortest path was found, one can see that the A* search algorithm explored very few nodes at all. Thanks to the good heuristic, it was unnecessary to explore many of the possible ways of getting from Frankfurt to Munich. For example, the route leading from Frankfurt to Kassel never has been examined, since Kassel is north of Frankfurt, while getting from Frankfurt to Munich, one has to travel south.

[edit] Algorithm

For finding a shortest path, the A* search algorithm needs six inputs: The graph (graph) it should run on, the node where the search should start (start), the goal node in which the shortest path should end (goal), a Priority Queue (S) that stores all the nodes already known by the algorithm (and whose f-values are thereby known), but have not yet been visited, a list (N) that stores all the nodes that already have been visited, and the heuristic h which estimates for every node the distance between that node and the goal.

In the first step, the starting node gets inserted into the Priority Queue. Afterwards a loop is being started which runs until either a shortest path to the goal is found, or a node that already had been explored should be explored once more, which only occurs when there is no path between the start and the goal.

Within the loop, the first node, which is – since the queue is a priority queue – the node with the lowest f-cost, is removed from the queue and added to the list of already visited nodes. Afterwards it is checked if the algorithm can already be terminated due to two reasons: First of all, the just visited node could already have been visited once, which could normally not happen due to the fact that a monotone heuristic was used. If the A* search algorithms tries to expand a node that has already been expanded earlier, there cannot exist a path from the start to the goal, since the algorithm would have found that path before exploring this node a for a second time. A more precise explanation for this can be found in the part Proof of optimality further down. If the algorithm terminated because it found the goal node, it calls the subfunction reconstruct_shortest_path which reconstructs the path from the goal node backwards to the starting node. Therefore the function gets the starting node, the goal node and the complete graph. Now it follows step by step, starting at the goal, the pointers to the predecessors until it reaches the starting node. These pointers have been created by the A* search algorithm within the graph while expanding the nodes, so that the function reconstruct_shortest_path for a node v simply need to lookup in the graph from which node u the node v was visited. After determine the predecessor of a nodem this predecessor will be stored in a Stack and reconstruct_shortest_path computes recursively the predecessor of that predecessor until it reaches the starting node. Now it can simply return the Stack which by now contains all the nodes on the shortest path in the correct order.

But if the goal has not yet been found by the algorithm, all nodes that are reacheable from the current node are computed by expanding the current node. In this step, for all newly discovered nodes the algorithm also saves from which node they have been discovered. So, if such a node is expanded later on itself, this data can simply be saved within the graph, because due to the fact that a monotone heuristic is used, the first path used to get to a node always is a shortest one. Now, the algorithm computes the f-value for all the newly discovered nodes, while the computation uses the already given formula f(n) = g(n) + h(n) for a node n. The value of g(n) can directly be read from the graph and corresponds to the weight of the edge between the current node and the node just discovered plus the cost of getting from the start to the current node. Applying the function h(n) is easy since it is directly acessible to the algorithm. At last all newly detected nodes get inserted into the priority queue and the loop starts again with examining the node with the lowest f-value.

Note: In addition to the here used method of implementing the A* search algorithm with a monotone heuristic there is also a implementation which heavily uses a so called closed list of already visited nodes where it has to check in each step if the currently found route to a node is better or worse than the already computed one. This is necessary if one does not use a monotone heuristic, but just an admissable one. This is not necessary if one uses a monotone heuristic where it can be guaranteed that the first path computed to any node is in fact a shortest path to that node. A more-depth distinction between monotone and admissable heuristics can be found under heuristics further down in the article.

/*
 * Algorithm reconstructing a shortest path
 * ----------------------------------------
 * P: computed shortest path
 * start: starting node
 * node: goal node
 */
reconstruct_shortest_path (start, node, graph)
{
   if (node != start)
   {
      push(node, P);

      // Read the predecessor of the current node
      predecessor := getPredecessor(node, graph);

      reconstruct_shortest_path (start, predecessor, graph)
   }
   else
      return P;
}

/*
 * The main A* search algorithm
 * ----------------------------
 * graph: The graph being examined
 * start: starting node
 * goal: goal node
 * h: heuristic for estimating the distance between any node and the goal
 * S: priority queue of the nodes whose f-value is already known
 * N: list of all nodes already visited
 */
A-Star (graph, start, goal, h, S, N)
{
   insert (start,S);
   while not isEmpty(S)
   {
      current_node := pop(S);
      if current_node in N then
         // There exists no path between start and goal
         return fail;
      insert (current_node, N);
      if (current_node == goal) then
         return reconstruct_shortest_path(start,goal, graph);
      else
      {
         // Compute all nodes reacheable from the current node
         successors := expand(current_node, graph);

         // Save the predecessor of the current node
         save_predecessor_in_graph(current_node, graph)

         forall s in sucessors do
         {
            // Save the node from which s was discovered
            predecessor(s) := current_node;

            // Compute and save the f-values
            f(s) := g(s) + h(s);

            insert(s,S);
         }
      }
   }
   // No path could be found
   return fail;
}

[edit] Heuristics

When considering heuristics for the A* search algorithm, one distinguishes between two kinds of heuristics: On the one hand admissble heuristics, which never overestimate the total cost getting from a node to the goal, but which may overestimate the cost getting from one node to another, and on the other hand monotone heuristics that guarantee not just to never overestimate the total cost from any node to the goal, but that are also guarantee to never overestimate the total cost between any two nodes. Hence, if a heuristic is monotone, this is a stronger proposition than if the heuristic would just be admissable. Even though it is possible to construct heuristics that are admissable but not monotone, most heuristics are both. The straight line distance, a heuristic for estimating the distance between two points is not just admissable, but also monotone, since it is not possible to find any way getting from point A to point B that is shorter than the straight line distance between those two points.

The most important difference between those two heuristics emerges when trying to implement the A* search algorithm. If one only can use an admissable heuristic, it may happen that the actual distance between two nodes u and v is overestimated by the heuristic, and therefore the algorithm may get from u to v via another node w, which is obviously a detour, if one could directly get from u to v. This now entails in the fact that the computed distance between u and v is not optimal, since there certainly exists a shorter path from u to v which just omits the vertex w. This now leads to the problem that one has to check for each discovered node if the newly discovered path to that node is actually shorter or longer as the previously computed one. If the new path is shorter than the old one, the old path has to be replaced by the new one, and if the newly computed path is longer than the old one was, the new path has to be discarded. On the other hand, if one chooses a monotone heuristic, this is unnecessary, since every time a node gets expanded the first time, the path to this node found so far is assured to be a shortest one.

Furthermore the chosen heuristic also has great influences on the running time of the A* search algorithm. On the one hand, there is the perfect heuristic, which will in each step just estimate the exact cost of getting from u to the goal, but this is useless, as it is the solution to the problem that should be solved by the A* search algorithm. On the other hand the trivial heuristic that estimates a value of 0 for getting from any node to the goal is obviously monotone, but is as useless as the perfect heuristic, as this "heuristic" does not help at all deciding which way to go, so that the algorithm has to search blindly for the goal, which it can just find by coincidence. This version of the A* search algorithm, where the heuristic estimates a distance of 0 between any node and the goal is better known as Dijkstra's algorithm. So a good heuristic is a tradeoff between accuracy and the cost it takes to compute it.

[edit] Proof of optimality

As already mentioned, a good heuristic is one of the key requirements for the A* search algorithm to work efficently. If one assumes that the used heuristic is a monotone one, which means that it never overestimates the distance between any two nodes, and if one furthermore assumes that the graph on which the algorithm runs has no negative edge weights, one can proof that the A* search algorithm will always find a shortest path, if one exists. If one examines how the algorithm works, one observes, that every time a node is picked, it is the one with the lowest f-value. But since a monotone heuristic was chosen, and therefore by assumption the estimated distance between any two nodes is never overestimated by the algorithm, and the costs for getting to the node u that currently has to be estimated, are known (because the algorithm has already found a path leading to u), also, the final f-value for that node u is a optimistic estimate, which will definately not be more than the actual cost. If there exists a node a with f(a) = 450, this node will not be expanded until all other nodes x with f(x) < 450) got expanded. So the algorithm cannot omit any nodes that possibly could lead cheaper to the goal. However, if one would allow negative edge weights, there could exists nodes – due to the edges with negative weights leading to them – with f-cost lower than 450. If one writes down these considerations, the optiality of the A* search algorithm can formally proven as follows:

To be proofed: Every path to the goal computed by the A* search algorithm is a shortest path and thereby an optimal solution.

Assumption: The A* search algorithm finds a suboptimal solution G₂, while the optimal solution is G₁ and has costs of C₁.

Since for all Goal nodes the estimated distance from the goal to the goal is 0, the following equation holds:

h(G2) = 0

Since G₂ is a suboptimal solution after the made assumption the following equation holds:

f(G2) = g(G2) + h(G2) = g(G2) > C1

If one now considers an arbitrary node n on the shortes path to the optimal goal G₁ and the fact that the heuristic never overestimates the actual costs, it is true that:

f(n) = g(n) + h(n) ≤ C1

By combining the two equations, one obtains:

f(n) ≤ C1 < f(G2)

But this now means that the A* search algorithm never explores the node G₂ before exploring the node G₁ which is the optimal solution. So the Algorithm first discovers the solution G₁ and thereby in fact computes a shortest path.

[edit] Field of application

The A* search algorithm is applied when computing a shortest path between two poins, as for example the route planner in a car or a route planner in the Internet. Another field of application is Artificial Intelligence as in computer games, where the algorithm is heavily used when some unit has to find its way to a special point on the map. This example can be generalized for robots or software agents, which autonomously should find a route in some specified world.

[edit] See also

• Bellman-Ford algorithm
• Dijkstra's algorithm
• Floyd-Warshall algorithm

[edit] References

• Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach, 2. Auflage, 2002, Prentice Hall.
• P. E. Hart, N. J. Nilsson, B. Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100-107, 1968.
• P. E. Hart, N. J. Nilsson, B. Raphael: Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", SIGART Newsletter, 37, pp. 28-29, 1972.
• N. J. Nilsson, Principles of Artificial Intelligence, Tioga Publishing Company, Palo Alto, California, 1980.

[edit] External links

• Justin Heyes-Jones' A* algorithm tutorial
• Another A* Pathfinding for Beginners
• Amit's Thoughts on Path-Finding and A*
• Sven Koenig's Demonstration of Lifelong Planning A* and A*
• Remko Tronçon and Joost Vennekens's JSearch demo: demonstrates various search algorithms, including A*.