A-star

The $A^*$ (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 ${C}(x)$ denote the cost-to-come from ${x_{I}}$ to $x$, and let ${G}(x)$ denote the cost-to-go from $x$ to some state in ${X_{G}}$. It is convenient that $C^*(x)$ can be computed incrementally by dynamic programming; however, there is no way to know the true optimal cost-to-go, $G^*$, 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 $(i,j)$ and another has $(i',j')$, then $\vert i' - i\vert + \vert j' - j\vert$ 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 $\hat{G}^*(x)$ denote such an estimate.

The $A^*$ search algorithm works in exactly the same way as Dijkstra's algorithm. The only difference is the function used to sort ${Q}$. In the $A^*$ algorithm, the sum $C^*(x') + \hat{G}^*(x')$ is used, implying that the priority queue is sorted by estimates of the optimal cost from ${x_{I}}$ to ${X_{G}}$. If $\hat{G}^*(x)$ is an underestimate of the true optimal cost-to-go for all $x \in X$, the $A^*$ algorithm is guaranteed to find optimal plans [337,777]. As $\hat{G}^*$ becomes closer to $G^*$, 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 $\hat{G}^*(x)=0$ for all $x \in X$, then $A^*$ degenerates to Dijkstra's algorithm. In any case, the search will always be systematic.