Precomputing Multi-Agent Path Replanning Using Temporal Flexibility

Issa Hanou; Eric Kemmeren; Devin Wild Thomas; Mathijs de Weerdt

cs.AIJan 8, 2026

Precomputing Multi-Agent Path Replanning Using Temporal Flexibility

Authors: Issa Hanou, Eric Kemmeren, Devin Wild Thomas, Mathijs de Weerdt

Organizations: Delft University of Technology · University of New Hampshire

Abstract

Executing a multi-agent plan can be challenging when an agent is delayed, because this typically creates conflicts with other agents. So, we need to quickly find a new safe plan. Replanning only the delayed agent often does not yield an efficient plan, and sometimes cannot even yield a feasible one. On the other hand, replanning other agents may lead to a cascade of changes and delays, and it is computationally expensive. We show how to efficiently replan a single delayed agent by tracking and using the temporal flexibility of other agents while avoiding cascading delays. This flexibility is the maximum delay that the agent can take without changing the order with agents other than the initially delayed agent, or further delaying other agents. Our algorithm, FlexSIPP, precomputes all possible plans for the delayed agent and returns the changes to the other agents within the given scenario. We demonstrate our method in a real-world case study of replanning trains in the densely-used Dutch railway network and in the MovingAI MAPF benchmark set. Our experiments show that FlexSIPP provides effective solutions relevant to real-world adjustments, and within a reasonable timeframe.

Figures & tables

Panel of Figure 1 — Figure 1: Example Multi-Agent Pathfinding warehouse problem. Each corridor has a width of one.

Panel of Figure 2 — Figure 2: An ATF with parameters $\zeta,\alpha,\beta$ , and $\Delta$ .

Panel of Figure 3 — Figure 3: Results on warehouse example from Figure 1 .

Tipping Point	Train	Location	Delay
13:42	77	Delft	01:12
22:20	58	The Hague	01:08

Table 1: Tipping points found by FlexSIPP for Scenario 1(93 trains over a 237-minute timespan). Times in mm:ss .

		FlexSIPP		@MAEDeR
Scen	$\alpha$	# Paths	$\beta$	# Paths	$\beta$
1	2741	14	1507.80	11	1507.80
	2799	1	2000.60	—	-
	2934	—	-	1	2000.60
2	2698	6	1244.30	3	1106.10
2	2743	1	2228.80	1	2228.80

Table 2: Any-start-time plans for Eurostar, showing the number of paths found for different starting times

\alpha

, with the associated latest start time: the max

\beta

of those path ATFs.

maze	20	0	93.4%	0.96	0.55	66%	64%
			Delay	Time (s)		Path Found
Map	$k$	f	F / M	F	M	F	M
		3	93.9%	1.51	0.81	66%	60%
		5	93.8%	1.06	0.57	73%	70%
		8	59.9%	2.02	0.80	64%	57%
	50	0	91.8%	2.74	1.51	68%	64%

Table 3: Total delay comparison for maze scenarios with 20 and 50 (

k

) agents and warehouse scenarios with 50 agents, where one agent is delayed, and extra flexibility ( f ) is added in the initial paths. Shows the average delay difference in percentage (FlexSIPP / @MAEDeR) and the percentage of runs when a path was found, along with the average search time over those for FlexSIPP (F) and @MAEDeR (M).

Figure 4: Total delay progression over sequential updates. The input delay is the agents’ cumulative imposed delay, showing the delays in resulting arrival times. $\times$ marks runs where no path was found (and @SIPP graph not updated).

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Railway Network in the Netherlands showing the maximum speed on each segment. Zoom-in of the area between Rotterdam and Amsterdam, both the regular track over Leiden in yellow, as well as the high-speed section between Rotterdam and Schiphol in red ( ProRail 2022 ) [p.199].

Panel of Figure 6 — Figure 6: Two blocking time staircases of two trains along the same track. The rightmost block is the critical block. Adapted from Pachl (2021) .

Time Components	S1	S2	S3	S4
Creation Routes $N$	47.08	48.65	46.14	46.18
Conflict gen.	58532	49014	47730	48806
Flexibility gen.	0.18	0.19	0.16	0.16
Interval gen.	5.92	8.94	6.35	7.64
Search FlexSIPP	129.68	146.62	143.15	77.76
Search @MAEDeR	86.67	97.18	41.81	50.88

Appendix

Table 4: Table reporting the components of the runtime in seconds of the two algorithms for four different scenarios of replanning the Eurostar.

Safe Interval Path Planning

See all 8 papers

Should I Replan? Learning to Spot the Right Time in Robust MAPF Execution
Apr 28, 2026David Zahrádka, David Woller, Denisa Mužíková +2Robust MAPF Multi-Agent Path Finding
Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague · Faculty of Electrical Engineering, Czech Technical University in Prague · Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Czechia. +1
Planning over MAPF Agent Dependencies via Multi-Dependency PIBT
Mar 24, 2026Zixiang Jiang, Yulun Zhang, Rishi Veerapaneni +1Kinodynamic Motion Planning Motion Planning
University Of Melbourne · Robotics Institute, Carnegie Mellon University
Optimal Planning in a Dynamic World
Oct 2, 2026Devin Wild Thomas, Solomon Eyal Shimony, Wheeler Ruml +3Safe Interval Path Planning Motion Planning
University of New Hampshire, USA · Ben-Gurion University of the Negev, Israel · Technion - Israel Institute of Technology, Israel +3

Apr 28, 2026J/K move · Enter open · S save

Should I Replan? Learning to Spot the Right Time in Robust MAPF Execution

David Zahrádka, David Woller, Denisa Mužíková, Miroslav Kulich+1

Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague · Faculty of Electrical Engineering, Czech Technical University in Prague · Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Czechia.+1

Robust MAPF Multi-Agent Path Finding Dynamic Replanning

Open paper AskPDF arXiv

During the execution of Multi-Agent Path Finding (MAPF) plans in real-life applications, the MAPF assumption that the fleet's movement is perfectly synchronized does not apply. Since one or more 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. 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 robust 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 we show that our proposed method is capable of reducing the impact of delays by up to 94.6% of the achievable reduction.

Abstract

Safe Interval Path Planning

Explore similar work

Should I Replan? Learning to Spot the Right Time in Robust MAPF Execution

Planning over MAPF Agent Dependencies via Multi-Dependency PIBT

Optimal Planning in a Dynamic World