Indoor navigation path planning method based on improved D*Lite algorithm for complex environments
Jiaqi Ye, Lie Niu, Xinyuan Xu, Yunfei Wang · IET conference proceedings. · 2025
The D*Lite algorithm is widely used for dynamic path planning in indoor environments, but it faces limitations in complex scenarios due to low efficiency and unsmooth paths. This paper proposes an improved D*Lite algorithm to address these issues. First, Delaunay triangulation is used to construct an abstract map and extract key navigation nodes, reducing the search space. Second, a dynamic guidance corridor is introduced by combining a rough A*-based path with a dual-modal heuristic to guide exploration toward optimal paths. Finally, cubic B-spline curves smooth the resulting paths for improved continuity. Experiments on virtual indoor maps (50×50 to 500×500 pixels) and the Stanford campus dataset (666×367 pixels) compare the proposed method with traditional D*Lite and JD*Lite across varying scales and obstacle densities. Results show that the improved algorithm significantly concentrates the search area, reduces invalid node visits, and enhances path smoothness. In high obstacle density environments, it reduces search time by 19.0% compared to D*Lite and 57.0% compared to JD*Lite. By reducing complexity from O(n²) to approximately O(n log n) while preserving topological features, the proposed method improves both efficiency and path quality. It offers robust support for intelligent indoor navigation, robot path planning, and emergency evacuation in large, complex environments.