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

arXiv: https://arxiv.org/abs/2403.18145 · HTML: https://mlsanity.com/paper/2403.18145/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 26 Mar 2024.

## Builds on (most cited first, 6 of 6)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)
- [Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers](https://mlsanity.com/paper/1912.00253/) (2019)
- [A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph](https://mlsanity.com/paper/2010.05254/) (2020)
- [Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution](https://mlsanity.com/paper/2401.00315/) (2023)
- [Symmetry Breaking for k-Robust Multi-Agent Path Finding](https://mlsanity.com/paper/2102.08689/) (2021)

## Built on by (most cited first, 4 of 4)

- [Advancing MAPF Toward the Real World: A Scalable Multi-Agent Realistic Testbed (SMART)](https://mlsanity.com/paper/2503.04798/) (2025)
- [WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning](https://mlsanity.com/paper/2508.01495/) (2025)
- [Lifelong Scalable Multi-Agent Realistic Testbed and A Comprehensive Study on Design Choices in Lifelong AGV Fleet Management Systems](https://mlsanity.com/paper/2602.15721/) (2026)
- [From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding](https://mlsanity.com/paper/2511.21886/) (2025)

## Abstract (arXiv)

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.