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.

One area of research in Multi-Agent Path Finding (MAPF) is to determine how re-planning can be efficiently achieved in the case of the delay of an agent. One option is to determine a new wait ordering to find the most optimal new solution that can be produced by re-ordering the wait order. We propose to use an Edge-Switchable Temporal Plan Graph and an augmented A* algorithm, called Switchable-Edge Search, to approach finding a new optimal wait order. While this is a work in progress still, we have discovered several optimizations for this algorithm, and the results show promising increases in efficiency for the algorithm. We have analyzed our present efficiency in a variety of conditions by measuring re-planning speed in different maps, with varying numbers of agents and randomized scenarios for agents' start and goal locations. We hope that, as we proceed with optimization, we can show that such an approach can be more efficient in practice and be used instead of re-running MAPF to perform cheap re-planning in such situations.