Conflict-Based Search for Multi-Agent Path Planning Using D*Lite for Dynamic Re-planning: Analysis and Verification | ||
| Suez Canal Engineering, Energy and Environmental Science | ||
| Volume 3, Issue 4, October 2025, Pages 20-29 PDF (961.17 K) | ||
| Document Type: Original Article | ||
| DOI: 10.21608/sceee.2025.375386.1074 | ||
| Authors | ||
| Ahmed S. Abdel-Rahman* 1; Sherif F Nafea1; Basem E. Elnaghi2; Ayman A. El‑Badawy3 | ||
| 1Electrical Engineering Department, Faculty of Engineering, Suez Canal University, Ismailia, Egypt | ||
| 2Electrical Engineering Department, Faculty of Engineering Suez Canal University, Ismailia, Egypt | ||
| 3Mechatronics Engineering Department, Faculty of Engineering, German University in Cairo, Cairo, Egypt | ||
| 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 | ||
| Conflict-Based Search (CBS); Multi-Agent Path Planning; D* Lite Algorithm; Real-Time Pathfinding | ||
|
Statistics Article View: 10 PDF Download: 4 |
||
