D*

Template:Graph search algorithm In computer science and robotics, the D* algorithm (pronounced "D star") is a dynamic version of the backward variant of Dijkstra's algorithm and A* search algorithm. Also known as Stentz's Algorithm, it was first developed by Anthony Stentz in 1994. It is widely used in vehicle navigation applications.

The A* algorithm, while optimal and efficient for the "omniscient" case in which the entire graph is known prior to path calculation, does not cope well with partially or completely unknown initial graphs, or graphs whose arc costs change during pathfinding. In several navigation and exploration applications, the environment is not known prior to pathfinding. One approach to dealing with these issues is to recalculate the entire path using A*, from current location to destination, whenever new information about the environment is discovered. Though optimal, this brute force technique is inefficient.

The D* algorithm incorporates these dynamic changes to the search space in an efficient and optimal manner by recalculating less than the entire path in response to discovery of new information.

Procedure

Expansion

Like with A*, D* follows the path from start to finish. Unlike with A*, however, the sequence is turned around: from the finish to the start. This has the advantage that each expanded node refers to the next node leading to the target and knows the exact cost to the target (after expansion). The expansion is similar to A*. When the start node is the next to be expanded, the algorithm can be canceled. The OpenList must not be emptied.

A deadlock occurs

Once a deadlock occurs, all the points that are affected are added again into the OpenList. However, they are marked as Raise-marked points. Before a Raise-point increases in cost, however, the result points to its wider scope and it examines whether it can reduce its costs. Then, a Raise wave runs from all relevant points. This wave is pursued by a Lower wave, if it exists. Lower points are points which continue to spread a cost reduction. This is the heart of the D*. By this point, a whole series of other points are prevented from being "touched" by the waves. The algorithm has therefore only worked on the points which are affected by change of cost.

Another deadlock occurs

This time, the deadlock cannot be bypassed so elegantly. None of the points can find a new route via a neighbor to the destination. Therefore, they continue to propagate their cost increase. Only outside of the channel can points be found, which can lead to destination via a viable route. This is how two Lower waves develop, which expand as unattainably marked points with new route information.

The Algorithm in words

Expansion of points

First, decide whether to expand the current point in the Raise-state or not (and thus automatically in the Lower state). If a Lower condition is present, proceed similarly to A*. All neighbors are then investigated to see if the current point can be better achieved than previously. If this is the case, the current point is again computed to the predecessor of the neighbors, whose cost is recalculated and this added to the OpenList. If there is a raise before the state, the costs are immediately passed on to all neighbors that are used from the current point to reach the destination All other points are examined to see whether each could represent a cost decrease. If so, the minimal cost of the current point to its current cost is set (it will thus contribute to the lower state) and again in the OpenList so that in the next expansion, its cost optimization can propagate.

Decision (Lower/Raise)

The decision whether a Raise or Lower state exists is based on the current and minimum costs. If the current path costs are larger than the minimum, a Raise condition is present. Before these costs continue to be passed on, however, the algorithm checks whether there is any point in the neighborhood that could reduce the costs of the current point. If such a point exists, this is set as the new predecessor and the cost is again computed. Once all neighbors have been checked, the algorithm again verifies whether the minimal cost corresponds to the current cost. If this is the case, there is now a Lower state, otherwise it a Raise state remains and the cost is propagated.

Minimum Cost versus Current Cost

For D*, it is important to distinguish between current and minimum costs. The former is only important at the time of collection and the latter is critical because it sorts the OpenList. The function which returns the minimum cost is always the lowest cost to the current point since it is the first entry of the OpenList.

External links

• Anthony Stentz's original 1994 paper
• The updated 1995 paper describing the focussing extension
• Tony Stentz's paper entitled Real-Time Replanning in Dynamic and Unknown Environments