ID* Lite

Abstract

Robot navigation has been of great importance especially under unknown or keep-changing environment. In order to solve this kind of problems, many algorithms have been brought up. D* Lite is generally considered as one of the most functional ones. The better performance of D* Lite largely depends on relatively less updating rather than recalculating terrain cost from scratch between robot movements. However, D* Lite still needs updating, i.e. recalculation, every time a terrain change is discovered. In this paper, we give an efficient method to check out when such recalculation can be fully or partially avoided. Experimental results show that it speeds up to 5 times for a variety of benchmarks including a novel and realistic benchmark. Our idea results in an improved version of D* Lite which we call ID* Lite. Moreover, it can be easily embedded into D* Lite variants such as DD* Lite and anytime D* etc.