| Multiple-Agent Path Finding (MAPF) is a task involving the identification of collision-free paths for a group of agents navigating in a specific map with designated starting vertices and goals. While conventional MAPF focuses on path planning in static environments, real-world scenarios often involve dynamic surroundings, leading to potential blockages in agent paths. In this paper, we propose a multi-agent scheduler Dynamic Incremental Conflict-based Search (DI-CBS) capable of concurrently generating paths satisfying both temporal and spatial constraints in response to environmental changes. A binary Environment Conflict Tree (ECT) is designed for high-level schedule in dynamic environments, effectively addressing determined conflicts and potential conflicts with other agents. Additionally, an incremental search-based planner Spatiotemporal Lifelong Planning A* (SLPA*) is proposed as the low-level module, enabling swift replanning in response to environmental changes.We compare our method with two baseline algorithms on the MAPF benchmark containing 2000 instances. The experiment results verified that our algorithm performs well to a highly dynamic environment. |
*** Title, author list and abstract as seen in the Camera-Ready version of the paper that was provided to Conference Committee. Small changes that may have occurred during processing by Springer may not appear in this window.