D*Lite is an incremental heuristic search algorithm that is used by agents (game ai, or robots) where the surrounding terrain is not completely known. The algorithm makes assumptions about the unknown terrain. D*Lite finds the shortest route from the start to the goal position, and as it encounters new obstacles these are taken into account and only part of the path is modified. Alternatively, pathfinding algorithms like A* typically have to replan the entire path when the environment changes.

D*Lite was developed by Sven Koenig in 2002 is based on the LPA* algorithm. I needed a suitable, computationally efficient algorithm for pathfinding in my current project and couldn’t find any java versions of the D*Lite algorithm that would have suited my purpose. My version is a standalone java version of D*Lite based on an existing C++ implementation.

This implementation is based on the original research paper http://idm-lab.org/bib/abstracts/Koen02e.html and also based on the c++ version located here: http://code.google.com/p/dstarlite/

For further reading check out the wikipedia article: Here Sven Koenig’s personal page: Here There is also an applet to help understand the algorithm: Here 

You can find my DStarLiteJava project on GitHub: Here