Avoiding Unnecessary Calculations in Robot Navigation

Abstract

For solving problems of robot navigation over un- known and changing terrain, many algorithms have been in- vented. For example, D* Lite, which is a dynamic, incremen- tal search algorithm, is the most successful one. The improved performance of the D* Lite algorithm over other replanning al- gorithms is largely due to updating terrain cost estimates rather than recalculating them between robot movements. However, the D* Lite algorithm performs some recalculation every time a change in terrain is discovered. In this paper, it is shown that re- calculation is often not necessary, particularly when several opti- mal solutions (shortest paths) exist, and an efficient test for deter- mining this is presented. These ideas are packaged in a modified version of D* Lite which we call ID* Lite for Improved D* Lite. We present experimental results that show the speedups possible for a variety of benchmarks. Also, a novel realistic benchmark is described.