 |
This article may require cleanup to meet Wikipedia's quality standards. Please improve this article if you can. (March 2009) |
D* refers to any one of the following three related incremental search algorithms:
- The original D*[1] (pronounced: D star) is an uninformed incremental search algorithm by Anthony Stentz.
- Focussed D*[2] is an informed incremental heuristic search algorithm by Anthony Stentz that combines ideas of A*[3] and the original D*. Focussed D* resulted from a further development of the original D*.
- D* Lite[4] is an incremental heuristic search algorithm by Sven Koenig and Maxim Likhachev that builds on LPA*[5], an incremental heuristic search algorithm that combines ideas of A* and Dynamic SWSF-FP[6]. D* Lite is not based on the original D* and Focussed D* and is simpler to understand than them, which explains its name.
All three search algorithms solve the same assumption-based path planning problems, including planning with the freespace assumption[7], where a robot has to navigate to given goal coordinates in unknown terrain. It makes assumptions about the unknown part of the terrain (for example: that it contains no obstacles) and finds a shortest path from its current coordinates to the goal coordinates under these assumptions. It then follows the path. When it observes new map information (such as previously unknown obstacles), it adds the information to its map and, if necessary, replans a shortest path from its current coordinates to the given goal coordinates. It repeats the process until it reaches the goal coordinates or determines that the goal coordinates cannot be reached. Thus, replanning needs to be fast. Incremental (heuristic) search algorithms speed up searches for sequences of such similar search problems by using experience with the previous search problems to speed up the search for the current one. If the goal coordinates do not change, then all three search algorithms are more efficient than repeated A* searches.
D* and its variants have been widely used for mobile robot and autonomous vehicle navigation. Current systems are typically based on D* Lite rather than the original D* or Focussed D*. In fact, it's said that Stentz's lab even uses D* Lite.[8] Such navigation systems include a prototype system tested on the Mars rovers Opportunity and Spirit on Mars and the navigation system of the winning entry in the DARPA Urban Challenge, both developed at Carnegie Mellon University.
Contents |
Procedure
The following text describes Focussed D*.
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.
References
- ^ A. Stentz, Optimal and Efficient Path Planning for Partially-Known Environments, Proceedings of the International Conference on Robotics and Automation, 1994,3310–3317.
- ^ A. Stentz. The Focussed D* Algorithm for Real-Time Replanning. Proceedings of the International Joint Conference on Artificial Intelligence, 1652–1659, 1995.
- ^ P. Hart, N. Nilsson and B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Trans. Syst. Science and Cybernetics, SSC-4(2), 100-107, 1968.
- ^ S. Koenig and M. Likhachev. Fast Replanning for Navigation in Unknown Terrain. Transactions on Robotics, 21, (3), 354-363, 2005.
- ^ S. Koenig, M. Likhachev and D. Furcy. Lifelong Planning A*. Artificial Intelligence Journal, 155, (1-2), 93-146, 2004.
- ^ G. Ramalingam, T. Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms 21 (1996) 267–305.
- ^ S. Koenig, Y. Smirnov and C. Tovey. Performance Bounds for Planning in Unknown Terrain. Artificial Intelligence Journal, 147, (1-2), 253-279, 2003.
- ^ D. Wooden, Graph-based Path Planning for Mobile Robots, Dissertation, Georgia Institute of Technology, 2006.
External links
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
