A New Way to Reduce Computing in Navigation Algorithm

For solving problems of robot navigation over unknown and changing terrain, many algorithms have been invented. For example, D* Lite, which is a dynamic, incremental search algorithm, is one of the most successful. The improved performance of the D* Lite algorithm over other replanning algorithms 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 recalculation is often not necessary, particularly when several optimal solutions (shortest paths) exist, or only a partial recalculation is needed and an efficient test for determining these 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. Besides, a novel realistic benchmark is described.