Back
to indexAnthony Stentz
Summary
The foundation of this paper directly comes from a previous paper, Optimal and Efficient Path Planning for Partially-Known Environments. This paper goes into the structural details of the D* algorithm, optimizing the results further and increasing the algorithm's efficiency. I recommend that whoever may be reading this start with my summary for the paper cited above, which talks about the D* algorithm in detail, first. My analysis in that summary holds true for this paper as well.
Focussed D* is the idea that you don't have to update all the states in the map: only the states between the current position of the robot and the goal state are relevant. Well, that's a brainstorm. It increases efficiency as the robot travels by reducing the number of states to update. The idea is to use a focussing heuristic g(X,R), which is the estimated path cost from the robot's location to R. A new function f(X, R) = h(X) + g(X,R) is introduced, which the result of which is fed into the sorting function for the LOWER states in the OPEN list. The trick is to select states which satisfy the monotone restriction: that each state in the path to the goal monotomically increases the cost. States which do not satisfy this restriction generally have some sort of backtracking involved, so they should be ignored.
The interesting thing about this algorithm is that its so darn common sense its amazing a whole paper was written about it. Its a great, clear optimization, with all the provably complete posits that the other paper had. There's value added, but a bit more complexity too.
Methods
Focussed D* is just like D* except LOWER states are only selected from the OPEN list if they satisfy the monotone restriction described above. The problem is that the robot moves to another location, which may require another recalculation step, when states may have been removed from the OPEN list. To minimize this problem (CLOSING states prematurely), a small constant is added to the cost measurement, preserving the ordering of the list. The cost is small and can be considered to be realistic, since the robot moves in small increments before the search is recalculated. Its a good approach, and should be considered if we do sensor fusion.
Keywords
path cost, efficiency, optimal, complete, intelligent search
Rating
8
Bibtex Entry
@inproceedings{ stentz95focussed,
author = "Anthony Stentz",
title = "The Focussed D* Algorithm for Real-Time Replanning",
booktitle = "{IJCAI}",
pages = "1652-1659",
year = "1995",
url = "citeseer.nj.nec.com/154664.html"
}