Precomputing Multi-Agent Path Replanning using Temporal Flexibility: A Case Study on the Dutch Railway Network
- URL: http://arxiv.org/abs/2601.04884v1
- Date: Thu, 08 Jan 2026 12:30:36 GMT
- Title: Precomputing Multi-Agent Path Replanning using Temporal Flexibility: A Case Study on the Dutch Railway Network
- Authors: Issa Hanou, Eric Kemmeren, Devin Wild Thomas, Mathijs de Weerdt,
- Abstract summary: We show how to efficiently replan by tracking and using the temporal flexibility of other agents while avoiding cascading delays.<n>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.<n>We demonstrate our method in a real-world case study of replanning trains in the densely-used Dutch railway network.
- Score: 4.217343824099138
- License: http://creativecommons.org/licenses/by/4.0/
- 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.
Related papers
- DLLM Agent: See Farther, Run Faster [94.74432470237817]
Diffusion large language models (DLLMs) have emerged as an alternative to autoregressive (AR) decoding with appealing efficiency and modeling properties.<n>We study this in a controlled setting by instantiatingDLLM and AR backbones within the same agent workflow.<n>We find thatDLLM Agents are on average over 30% faster end to end than AR agents, with some cases exceeding 8x speedup.
arXiv Detail & Related papers (2026-02-07T09:01:18Z) - When Agents Break Down in Multiagent Path Finding [0.0]
We introduce a new variant that formally models scenarios where some agents may experience delays due to malfunctions.<n>We propose a framework for dynamic schedule adaptation that does not rely on full replanning.<n>We prove that following our primary communication protocol, the increase in makespan after k malfunctions is bounded by k additional turns.
arXiv Detail & Related papers (2025-08-05T12:59:30Z) - Adaptive Reinforcement Learning for Unobservable Random Delays [46.04329493317009]
We introduce a general framework that enables agents to adaptively handle unobservable and time-varying delays.<n>Specifically, the agent generates a matrix of possible future actions to handle both unpredictable delays and lost action packets sent over networks.<n>Our method significantly outperforms state-of-the-art approaches across a wide range of benchmark environments.
arXiv Detail & Related papers (2025-06-17T11:11:37Z) - Agent-Oriented Planning in Multi-Agent Systems [54.429028104022066]
We propose AOP, a novel framework for agent-oriented planning in multi-agent systems.<n>In this study, we identify three critical design principles of agent-oriented planning, including solvability, completeness, and non-redundancy.<n> Extensive experiments demonstrate the advancement of AOP in solving real-world problems compared to both single-agent systems and existing planning strategies for multi-agent systems.
arXiv Detail & Related papers (2024-10-03T04:07:51Z) - KnowAgent: Knowledge-Augmented Planning for LLM-Based Agents [52.34892973785117]
Large Language Models (LLMs) have demonstrated great potential in complex reasoning tasks, yet they fall short when tackling more sophisticated challenges.<n>This inadequacy primarily stems from the lack of built-in action knowledge in language agents.<n>We introduce KnowAgent, a novel approach designed to enhance the planning capabilities of LLMs by incorporating explicit action knowledge.
arXiv Detail & Related papers (2024-03-05T16:39:12Z) - Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
Multi-Agent Pickup and Delivery (MAPD) is the problem of computing collision-free paths for a group of agents.
Current algorithms for MAPD do not consider many of the practical issues encountered in real applications.
We present two solution approaches that provide robustness guarantees by planning paths that limit the effects of imperfect execution.
arXiv Detail & Related papers (2023-03-30T14:42:41Z) - Fault-Tolerant Offline Multi-Agent Path Planning [5.025654873456756]
We study a novel graph path planning problem for multiple agents that may crash at runtime, and block part of the workspace.
In our setting, agents can detect neighboring crashed agents, and change followed paths at runtime. The objective is then to prepare a set of paths and switching rules for each agent, ensuring that all correct agents reach their destinations without collisions or deadlocks.
arXiv Detail & Related papers (2022-11-25T05:58:32Z) - Coach-assisted Multi-Agent Reinforcement Learning Framework for
Unexpected Crashed Agents [120.91291581594773]
We present a formal formulation of a cooperative multi-agent reinforcement learning system with unexpected crashes.
We propose a coach-assisted multi-agent reinforcement learning framework, which introduces a virtual coach agent to adjust the crash rate during training.
To the best of our knowledge, this work is the first to study the unexpected crashes in the multi-agent system.
arXiv Detail & Related papers (2022-03-16T08:22:45Z) - Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity,
and Optimism [33.116006446428756]
We study multi-agent online learning problems in the presence of delays and asynchronicities.
We derive adaptive learning strategies with optimal regret bounds, at both the agent and network levels.
arXiv Detail & Related papers (2020-12-21T18:55:55Z) - A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by
Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks.
One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes.
If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays.
We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
arXiv Detail & Related papers (2020-10-11T14:39:50Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.