Fast Rescheduling for Multi-Agent Plan Execution in Dynamic Urban Environments: A Machine Scheduling Perspective

The Multi-Agent Path Finding (MAPF) problem is crucial for sidewalk delivery robots operating in dynamic urban environments. These robots frequently encounter unforeseen obstacles and delays, causing deviations from precomputed routes and schedules, necessitating rapid real-time replanning to maintain efficient operations. However, traditional MAPF approaches can be computationally intensive, particularly when recalculating both routes and schedules. We present a novel replanning approach that addresses this challenge by retaining the original routes and only adjusting the schedules. This constrained MAPF variant is closely related to the Blocking Job Shop (BJS) problem, allowing us to leverage existing BJS local search techniques to develop an anytime replanning procedure. We evaluated our method on various maps, including a real-world deployment site, demonstrating its efficiency in computing high-quality schedules essential for seamless operations.