Implementation of the D* lite algorithm in Python for "Improved Fast Replanning for Robot Navigation in Unknown Terrain"
MIT License
This software is an implementation of the D*-Lite algorithm as explained in Koenig, 2002. The D* Lite algorithm was developed by Sven Koenig and Maxim Likhachev for a faster more lightweight alternative to the D* algorithm (developed by Anthony Stentz in 1995).
you can use pipenv or poetry to active virtual env.
$ pip install poetry
$ cd /d-star-lite/python
$ poetry install
$ poetry shell
$ python main.py
The version of D* Lite that I implemented works by bascially running A* search in reverse starting from the goal and attempting to work back to the start. The solver then gives out the current solution and waits for some kind of change in the weights or obstacles that it is presented with. As opposed to repeated A* search, the D* Lite algorithm avoids replanning from scratch and incrementally repair path keeping its modifications local around robot pose.
This is the optimized version as explained in Figure 4 of the paper.
Improved Fast Replanning for Robot Navigation in Unknown Terrain Sven Koenig, Maxim Likhachev Technical Report GIT-COGSCI-2002/3, Georgia Institute of Technology, 2002.