Incremental CBS: Adaptive Multi-Agent Pathfinding in Dynamic Environments
Xichen Xing, Buyun Wang, Jun Sheng Cheng · 2024
In Multi-Agent Pathfinding (MAPF), traditional Conflict-Based Search (CBS) algorithms excel in static environments but struggle with efficiency and responsiveness in dynamic settings. This study introduces the Incremental Conflict-Based Search (ICBS) algorithm, which enhances response efficiency through incremental updates, only adjusting paths for agents affected by environmental changes. By constructing a dependency graph between agent paths and the environment, ICBS quickly identifies necessary path adjustments. A dynamic monitoring module ensures timely responses to obstacle changes. Experimental results show that ICBS outperforms traditional CBS in dynamic scenarios, making it ideal for applications like automated warehouse management and robotic soccer.