D* Lite

This repository contains a C++ implementation of D* Lite algorithm. D* Lite is an incremental heuristic search algorithm developed by Sven Koenig in his paper: D* Lite.

Being an incremental search algorithm, it speeds up search for dynamic environments by reusing the planning results of previous policies. Thus, outperforming repeated A* searches.

Below is an illustration of the real-time updates to the policy.

• White squares are free cells.
• Black squares are obstacles.
• Cyan square is the start cell.
• Green square is the goal cell.
• Orange squares are the optimal path to the goal.

Dependencies

• CMake >= 3.7
• GCC/G++
• SFML >= 2.5

Installation Instructions (Ubuntu)

1. Clone the repo.
2. Make sure all dependencies are installed:

   sudo apt install build-essential cmake libsfml-dev
   

3. Open a terminal in the repo directory.
4. Make a build directory in the top level directory:

   mkdir build && cd build
   

5. Compile:

   cmake .. && make
   

6. Run:

   ./DStarLiteVisualization
   

Controls

• Left Click: add obstacle
• Right Click: remove obstacle
• Key "R": remove all obstacles