A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution


  • Ying Feng Carnegie Mellon University, USA
  • Adittyo Paul Carnegie Mellon University, USA
  • Zhe Chen Monash University, Australia
  • Jiaoyang Li Carnegie Mellon University, USA




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.




How to Cite

Feng, Y., Paul, A., Chen, Z., & Li, J. (2024). A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 201-209. https://doi.org/10.1609/icaps.v34i1.31477