Precomputing Multi-Agent Path Replanning using Temporal Flexibility: A Case Study on the Dutch Railway Network
Issa Hanou, Eric Kemmeren, Devin Wild Thomas, Mathijs de Weerdt · 2026
Read Precomputing Multi-Agent Path Replanning using Temporal Flexibility: A Case Study on the Dutch Railway Network by Issa Hanou, Eric Kemmeren, Devin Wild Thomas, Mathijs de Weerdt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04884.txt.
Introduction
Issa Hanou and 3 co-authors precompute help for multi-agent path replanning in a 2026 paper. When one agent in a coordinated plan is delayed, conflicts with other agents follow, and a new safe plan is needed fast. Replanning only the delayed agent can be inefficient or even infeasible, while replanning everyone risks cascading changes and heavy computation.
The authors track the temporal flexibility of other agents: how long each can be delayed without causing new conflicts. Using that slack, they replan a single delayed agent efficiently while avoiding cascades. The approach suits warehouses and traffic systems, where one stalled robot or vehicle should not force a costly rethink of every other agent's route.
Catalog record
| CREATOR | Issa Hanou, Eric Kemmeren, Devin Wild Thomas, Mathijs de Weerdt |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-04884
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Precomputing Multi-Agent Path Replanning using Temporal Flexibility: A Case Study on the Dutch Railway Network Issa Hanou, Eric Kemmeren, Devin Wild Thomas, Mathijs de Weerdt 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 result in an efficient plan, and sometimes cannot even yield a feasible plan. On the other hand, replanning other agents may lead to a cascade of changes and delays. We show how to efficiently replan by tracking and using the temporal flexibility of other agents while avoiding cascading delays. This flexibility is the maximum delay an agent can take without changing the order of or further delaying more agents. Our algorithm, FlexSIPP, precomputes all possible plans for the delayed agent, also returning the changes for the other agents, for any single-agent delay within the given scenario. We demonstrate our method in a real-world case study of replanning trains in the densely-used Dutch railway network. Our experiments show that FlexSIPP provides effective solutions, relevant to real-world adjustments, and within a reasonable timeframe. \DeclareCaptionType equ[Equation][] Introduction When executing in a multi-agent environment, delays frequently occur, which can result in conflicts and disrupt the previously safe execution of the plan. Resolving these execution conflicts often requires deciding which agents will have their plans disrupted and by how much. As conflicts compromise the safe execution, a decision must be made swiftly, while replanning takes time. In this paper, we address the multi-agent path replanning problem, where a single agent needs to be replanned (e.g., because of a delay), and our objective is to recover a safe plan as quickly as possible. Full replanning of all agents can be computationally expensive, so we consider the subset of these problems where other agents may only be delayed, not rerouted, and this delay must not introduce additional conflicts. These constraints are inspired by the application of railway networks. We quantify an agent’s ability to absorb a delay as its temporal flexibility , which is the maximum delay that it can take without changing the order in which agents use a resource, and without further delaying more agents. The temporal flexibility is easily precomputed from a given plan. With this, we can identify the set of tipping points for the delayed agent, which are the extent of the delays causing a conflict with another agent at which the ordering should change (i.e., when the other agent should go first). Example 1 . Consider a corridor with two agents who must use it in opposite directions (see Figure 1 ). In the original plan, agent a_{1} goes first, and then agent a_{2} uses the corridor from the other side. Now suppose agent a_{1} is delayed. If we do not want agent a_{2} to be affected, we say that agent a_{1} must wait for agent a_{2} to cross the corridor, thereby delaying agent a_{1} even further. However, if we let agent a_{2} wait a little bit until agent a_{1} is able to cross the corridor, then both agents a_{1} and a_{2} are delayed slightly, but the overall makespan (or sum of costs) including wait time is not considerably increased. Still, if agent a_{1} does suffer a significant delay, then it would be better to let agent a_{2} go first, and have agent a_{1} wait until agent a_{2} has crossed the corridor. In this case, the tipping point is when the delay of agent a_{1} is large enough such that it is better to let agent a_{2} go first. u v \overline{v} \overline{u} w \overline{w} a_{1} Start at t=2 a_{2} Start at t=10 Arrive at t=10 Arrive at t=18 Figure 1: Example of a corridor MAPF problem. This work is most closely related to Multi-Agent Execution Delay Replanning (MAEDeR) ( Hanou et al. 2024 ) , which addresses a stricter subset of delay replanning problems, where the originally delayed agent must recover without affecting the plans of any other agents. Like MAEDeR, our approach uses the Safe Interval Path Planning (SIPP) ( Phillips and Likhachev 2011 ) state space to encode when resources are not used by other agents. With this problem representation, optimal single-agent plans for all start times can be efficiently computed ( Thomas et al. 2023 ) , by treating other agents as moving obstacles. Hanou et al. 2024 use this to shift replanning to be ‘in advance’, and recover from some execution conflicts instantly by looking up a new plan for the delayed agent in its any-start-time plan. While the resulting multi-agent plan is safe, MAEDeR does not necessarily provide an optimal solution, as it is based on the assumption that the plans of agents other than the delayed agent cannot be modified. In comparison to MAEDeR, because we allow for the delay of other agents, we can reduce the overall delay. This method, called FlexSIPP, still provides near-instant delay replanning, and the required precomputation runs in polynomial time. FlexSIPP was originally described by Kemmeren 2025 as a railway-specific approach. In this paper, we formalize FlexSIPP and generalize it to include the multi-agent path replanning setting with continuous time, demonstrating that we can efficiently replan a single agent, either because it is delayed or because its initial plan fails for other reasons. To evaluate the effectiveness of FlexSIPP, we analyze a real-world case study of a defective high-speed line and the process of rerouting the affected trains in the regular network in the Netherlands. We identify the tipping points in relation to the regular trains in the network so that we can plan the rerouted train in between them. As the Dutch railway network is densely used, we show the need for using agents’ temporal flexibility to find a feasible solution. Our main contribution is the FlexSIPP algorithm for quickly replanning a delayed agent in a multi-agent pathfinding context. We present a method for determining the flexibility of agents and use tipping points to illustrate the replanning trade-off between delaying other agents or further delaying or rerouting a delayed agent. A case study of the railway network in the Netherlands is used to demonstrate the benefits of automatically identifying tipping points and using these in real-world situations. Background We begin by describing the state space representation of Safe Interval Path Planning (SIPP); Any-Start-Time Planning, which is the single-agent optimal search used by our precomputation; and Multi-Agent Execution Delay Replanning (MAEDeR), which is the most closely related formulation of the multi-agent delay replanning problem. Safe Interval Path Planning SIPP ( Phillips and Likhachev 2011 ) is a single-agent state-space search problem defined by a tuple \langle S,E,\delta,x_{o},t_{o},x_{g}\rangle , where each state s=\langle x,i\rangle\in S is a configuration x (e.g., agent location) and a safe interval i=\langle t_{s},t_{e}\rangle , which is a continuous timespan from t_{s} to t_{e} when it is safe for the agent to be in configuration x . An edge e=\langle s_{1},s_{2},i\rangle~\in~E for states s_{1},s_{2}\in S denotes the safe interval i when the edge (s_{1},s_{2}) can be used by the agent, and the cost of this edge is defined by \delta(s_{1},s_{2}) , which is the minimum time it takes an agent to