Conflict-Based Search for Multi-Agent Path Planning Using D*Lite for Dynamic Re-planning: Analysis and Verification

Abdel-Rahman, Ahmed S.; Nafea, Sherif F; Elnaghi, Basem E.; El‑Badawy, Ayman A.

doi:10.21608/sceee.2025.375386.1074

Conflict-Based Search for Multi-Agent Path Planning Using D*Lite for Dynamic Re-planning: Analysis and Verification

Document Type : Original Article

Authors

¹ Electrical Engineering Department, Faculty of Engineering, Suez Canal University, Ismailia, Egypt

² Electrical Engineering Department, Faculty of Engineering Suez Canal University, Ismailia, Egypt

³ Mechatronics Engineering Department, Faculty of Engineering, German University in Cairo, Cairo, Egypt

10.21608/sceee.2025.375386.1074

Abstract

Conflict-Based Search (CBS) is a widely used approach in multi-agent pathfinding due to its flexibility and effective conflict resolution capabilities. However, CBS encounters challenges in terms of path optimality and computational cost, especially in dynamic environments where obstacles frequently move and change. This study gives an analysis for integrating the D* Lite algorithm as a replacement for A*. D* Lite introduces incremental replanning, allowing the algorithm to efficiently update paths without recalculating them entirely. This analysis shows the enhancement of CBS’s adaptability to real-time dynamic environments, significantly reducing computational costs and improving responsiveness. By leveraging the ability of D* Lite to reuse portions of existing paths, CBS can resolve conflicts faster and maintain path optimality even as obstacles and agents move unpredictably. Simulations demonstrate that the optimized CBS with D* Lite achieves significantly reduced computation times than traditional CBS. This enhancement makes it more suitable for large-scale multi-agent systems operating in dynamic settings, such as autonomous vehicle coordination, swarm robotics, and warehouse automation, where real-time path adjustments are crucial.

Keywords

Main Subjects