Back
to indexAnthony Stentz
Summary
This is the foundational paper on the D* algorithm. The D* algorithm stems from the A* algorithm, by choosing the optimal path based on the cost to traverse between grid locations. D stands for "dynamic", which is its improvement over A* by updating the map representation in real time as sensors pick up obstacles, so a path can be recomputed during a traverse. Its benefits are its efficiency, optimality, and completeness. The key to the D* algorithm, as well as the A* algorithm, is to choose an appropriate cost function representing the traversal between grid locations. Cost may be distance traveled, energy expended, time exposed to danger, etc. The algorithm is provably optimal, given there exists accurate cost functions. Empirical results clock the algorithm in significantly faster than the "replanner" algorithm, which is also complete.
Its a good algorithm - simple to implement and pretty efficient. I'm just concerned about choosing the right cost function for our problem of off road map path selection - how can we prove that we are choosing the right path? What is the criteria to evaluate correctness? Unfortunately, the paper deals with these questions on the abstract level - proving the algorithm, not the application.
D* includes dynamic updates - which I'm also not sure we will be using. The mapping data from the MySQL database will be static, precalculated grid squares. At this point, there is no design to include sensor fusion to take advantage of D* over A*. Since D* could be added without problems on top of A*, my recommendation is to currently continue to implement A* and use D* if time and sensor fusion necessitates it.
Methods
The D* algorithm maintains a grid of states, where the current location and the goal location is noted. Each state is connected by a directional arc, which includes the cost to traverse that arc. Each state maintains the "backpointer" indicating its best path toward the goal node. A list of OPEN, CLOSED, or NEW states are maintained. The algorithm works by sorting the OPEN list by the key function value of the state. The key function is the minimum of the estimated cost to the goal. Each state on the list is also classified into either a RAISE or LOWER state, denoting if the estimated path cost, h(G,X) is greater than or less than the minimum estimated path cost. LOWER states are propagated first, which expands all the neighbors leading to the goal, continuing until the total path cost reaches or exceeds the key function that the state began with.
Keywords
path cost, optimal, complete, intelligent search
Rating
9
Bibtex Entry
@inproceedings{ stentzoptimal,
author = "A. Stentz",
title = "Optimal and Efficient Path Planning for Partially-Known Environments",
booktitle = "Proceedings of the IEEE International Conference on Robotics and Automation",
year = 1994,
pages = "3310--3317",
}