A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution
This addresses real-time rescheduling for multi-robot systems, but it is incremental as it builds on existing A*-style methods for a specific bottleneck.
The paper tackles the problem of efficiently replanning for delayed agents in multi-agent path finding by proposing Switchable-Edge Search (SES), an A*-style algorithm that finds optimal passing orders, with results showing it runs in under 1 second for small- and medium-sized problems and up to 4 times faster than baselines for large-sized problems.
One area of research in multi-agent path finding is to determine how replanning can be efficiently achieved in the case of agents being delayed during execution. One option is to reschedule the passing order of agents, i.e., the sequence in which agents visit the same location. In response, we propose Switchable-Edge Search (SES), an A*-style algorithm designed to find optimal passing orders. We prove the optimality of SES and evaluate its efficiency via simulations. The best variant of SES takes less than 1 second for small- and medium-sized problems and runs up to 4 times faster than baselines for large-sized problems.