Should I Replan? Learning to Spot the Right Time in Robust MAPF Execution
David Zahr ́adka,, David Woller, Denisa Muˇz ́ıkov ́a,, Miroslav Kulich and Libor Pˇreuˇcil
AI summary
Problem
Robust MAPF execution prevents collisions during unexpected delays but often forces agents to wait, increasing execution cost. Deciding when to replan is computationally costly and frequently unnecessary, yet doing it too often accumulates overhead without guaranteeing savings.
Approach
The authors augment the Action Dependency Graph with real-time execution metrics to train a feed-forward neural network that estimates the expected cost savings of replanning at any given moment.
Key results
- Augmented ADG with novel real-time metrics capturing execution state and delay impact
- Generated a labeled dataset of 12,000 experiments for supervised neural network training
- Identified the most informative features and analyzed dynamic obstacle impact on execution cost
- Demonstrated the method recovers 94.6% of available cost savings
Why it matters
Enables autonomous fleets and warehouse robots to minimize execution delays and operational costs by intelligently triggering replanning only when beneficial.
Abstract
During the execution of Multi-Agent Path Find- ing (MAPF) plans in real-life applications, the MAPF assump- tion that the fleet’s movement is perfectly synchronized does not apply. Since some of the agents may become delayed due to internal or external factors, it is often necessary to use a robust execution method to avoid collisions caused by desynchronization. Robust execution methods – such as the Action Dependency Graph (ADG) – synchronize the execution of risky actions, but often at the expense of increased plan execution cost, because it may require some agents to wait for the delayed agents. In such cases, the execution’s cost can be reduced while still preserving safety by finding a new plan either by rescheduling (reordering the agents at crossroads) or the more general replanning capable of finding new paths. However, these operations may be costly, and the new plan may not even lead to lower execution cost than the original plan: for example, the two plans may be the exact same, as some losses may not be recoverable at all. Therefore, we estimate the benefit that can be achieved by single replanning in scenarios with delayed agents given an immediate state of the execution with a fully connected feed-forward neural network. The input to the neural network is a set of newly designed ADG-based features describing the execution’s state and the impact of potential delays, and the output is an estimated benefit achievable by replanning. We train and test the network on a new labeled dataset containing 12, 000 experiments and show that our proposed method is capable of significantly reducing the impact of recoverable delays.