A-star

The (pronounced ``ay star'') search algorithm is an extension of Dijkstra's algorithm that tries to reduce the total number of states explored by incorporating a heuristic estimate of the cost to get to the goal from a given state. Let denote the cost-to-come from to , and let denote the cost-to-go from to some state in . It is convenient that can be computed incrementally by dynamic programming; however, there is no way to know the true optimal cost-to-go, , in advance. Fortunately, in many applications it is possible to construct a reasonable underestimate of this cost. As an example of a typical underestimate, consider planning in the labyrinth depicted in Figure 2.2. Suppose that the cost is the total number of steps in the plan. If one state has coordinates and another has , then is an underestimate because this is the length of a straightforward plan that ignores obstacles. Once obstacles are included, the cost can only increase as the robot tries to get around them (which may not even be possible). Of course, zero could also serve as an underestimate, but that would not provide any helpful information to the algorithm. The aim is to compute an estimate that is as close as possible to the optimal cost-to-go and is also guaranteed to be no greater. Let denote such an estimate.

The search algorithm works in exactly the same way as Dijkstra's algorithm. The only difference is the function used to sort . In the algorithm, the sum is used, implying that the priority queue is sorted by estimates of the optimal cost from to . If is an underestimate of the true optimal cost-to-go for all , the algorithm is guaranteed to find optimal plans [337,777]. As becomes closer to , fewer vertices tend to be explored in comparison with Dijkstra's algorithm. This would always seem advantageous, but in some problems it is difficult or impossible to find a heuristic that is both efficient to evaluate and provides good search guidance. Note that when for all , then degenerates to Dijkstra's algorithm. In any case, the search will always be systematic.

Steven M LaValle 2012-04-20