Implementation of D* Lite Algorithm for Dynamic Pathfinding in a Street Environment
Boxi Zhao · Applied and Computational Engineering · 2025
This project uses the D* Lite algorithm to do dynamic pathfinding in a simulated urban street environment, while also considering the movement limits of an autonomous vehicle. In the simulation, the vehicle is represented as a 2×3 car that moves forward on a narrow 10×100 grid. The environment contains both fixed obstacles and moving ones, like pedestrians crossing the street from time to time. To improve safety, a three-cell buffer is placed in front of the vehicle, which is roughly equal to one car length. This helps the vehicle react earlier when something suddenly appears ahead. During each step, the system updates both the planning mask and the safety mask, so the vehicle can either stop or replan its path when necessary. The safety buffer does help lower the chance of collisions, but D* Lite is still only a geometric planning algorithm, so it cannot predict future obstacle movement. Because of that, collisions may still happen in rare cases when an obstacle moves into the path after the vehicle has already sensed the environment. Even so, the results show that the algorithm can respond quickly and handle path planning well in a changing environment. Overall, this project shows that D* Lite is effective for a simplified autonomous driving simulation.