When Agents Break Down in Multiagent Path Finding

Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos, Michal Opler · 2025

Read When Agents Break Down in Multiagent Path Finding by Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos, Michal Opler (2025) 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-2508-03777.txt.

Introduction

Foivos Fioravantes and three co-authors wrote a 2025 paper on keeping multi-robot path plans working when some robots break down. In multi-agent path finding, many agents cross a network without collisions, minimizing total completion time. A malfunctioning agent can wreck a carefully optimized schedule, and replanning from scratch is often too slow.

The authors propose protocols for local adaptation instead. Agents coordinate with neighbors and adjust paths on the fly. Their main protocol provably bounds the damage: after k malfunctions, completion takes at most k extra turns. A second protocol moves the computing onto the network's nodes, for agents with weak processors. The results offer a scalable route to resilient navigation. Fleets of warehouse robots are the natural audience.

Catalog record

CREATORFoivos Fioravantes, Dušan Knop, Nikolaos Melissinos, Michal Opler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-03777

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

When Agents Break Down in Multiagent Path Finding Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos, Michal Opler Abstract In Multiagent Path Finding ( MAPF ), the goal is to compute efficient, collision-free paths for multiple agents navigating a network from their sources to targets, minimizing the schedule’s makespan-the total time until all agents reach their destinations. We introduce a new variant that formally models scenarios where some agents may experience delays due to malfunctions, posing significant challenges for maintaining optimal schedules. Recomputing an entirely new schedule from scratch after each malfunction is often computationally infeasible. To address this, we propose a framework for dynamic schedule adaptation that does not rely on full replanning. Instead, we develop protocols enabling agents to locally coordinate and adjust their paths “on the fly.” We prove that following our primary communication protocol, the increase in makespan after k k malfunctions is bounded by k k additional turns, effectively limiting the impact of malfunctions on overall efficiency. Moreover, recognizing that agents may have limited computational capabilities, we also present a secondary protocol that shifts the necessary computations onto the network’s nodes, ensuring robustness without requiring enhanced agent processing power. Our results demonstrate that these protocols provide a practical, scalable approach to resilient multiagent navigation in the face of agent failures. 1 Introduction The classical Multiagent Path Finding ( MAPF ) problem focuses on computing non-colliding paths for a set of k agents. Finding an optimal schedule—minimizing either the makespan or the total energy (i.e., the total distance traveled by all agents) – is known to be computationally hard ma2022graph ; FKKMO24 ; FKKMOV25 . Even heuristic approaches struggle with scalability and performance SharonSFS15 . In this work, we initiate the study of Multiagent Path Finding in the presence of faulty agents. Specifically, we consider scenarios where a scheduled agent may unexpectedly pause its movement, incurring a delay of up to d\in\mathbb{N} time steps. Such interruptions can invalidate the original schedule by introducing collisions. Two obvious remedies are: (1) recomputing the entire schedule from the agents’ current positions, or (2) pausing the execution of all agents until the delayed one can resume. While both approaches resolve conflicts, they come with significant drawbacks: recomputation may be computationally infeasible in real time, and global pausing requires coordinated communication among all agents. Our goal is to analyze the effects of such malfunctions and propose decentralized recovery strategies that preserve as much of the original schedule as possible. Traditional MAPF algorithms assume perfectly reliable agents that follow their assigned schedules without deviation. However, in real-world deployments – such as warehouse robotics, autonomous drones, or multi-robot exploration – agents may experience delays due to hardware faults, temporary obstacles, or energy constraints. In such settings, requiring all agents to pause or triggering a global replanning procedure is often impractical due to latency, communication limitations, or computational overhead (think of, e.g., traffic control). This motivates the need for local recovery mechanisms that allow the system to tolerate occasional agent delays with minimal disruption. We propose a framework for decentralized schedule repair, where only agents directly affected by a delay participate in resolving potential conflicts. Our approach leverages the structure of the original schedule and local interactions to avoid global rescheduling, enabling more resilient and scalable multi-agent coordination. To this end, we propose the Multiagent Path Finding with Malfunctioning Agents problem, where agents may pause for one or more turns. We observe that even with a single turn delay, conflicts can arise if other agents stick to the original schedule, especially under worst-case, adversarial conflict resolution—potentially leading to scenarios with no feasible solutions (see Example 1 ). In this work, we analyze protocols to propagate information about delays. The most straightforward approach is to broadcast delay information and to suspend all agents until the malfunctioning agent resumes. Although this guarantees a conflict-free schedule, it introduces a uniform delay for all agents, which is often inefficient in practice. Furthermore, broadcasting may not be feasible in all settings, and such a protocol can unnecessarily delay unaffected agents. 1.1 Our Results We begin by observing that adapting a given schedule in a centralized way is infeasible. In particular, we show deciding in a centralized way how to adapt the initial schedule so that its makespan is unaffected, is computationally hard (see Theorem 1 ). We then focus on the case of a single delay (i.e., a delay of exactly one turn), we propose the Check Before Moving protocol, a natural and intuitive approach that prioritizes agents that have already experienced a delay. Specifically, this protocol grants the delayed agent priority access to the next vertex, ensuring conflict resolution without requiring global coordination. Surprisingly, as we show in Theorem 2 , this simple strategy guarantees a conflict-free schedule and increases the overall makespan by only one turn, which is clearly necessary (e.g., if the delayed agent is at distance equal to the original makespan from its target). Moreover, this protocol is highly localized: before entering a vertex, an agent inspects its immediate neighborhood. If a delayed agent is detected in the vicinity, the agent pauses its own movement and signals the delay in the following turn. This localized mechanism minimizes communication overhead and leverages only local interactions to resolve conflicts. Extending this protocol to delays of k turns introduces further complexity. In such cases, the delay signal must propagate up to k hops, and agents may need to scan a neighborhood of radius k to respond appropriately. Although conceptually simple, this requirement implies that agents must be explicitly designed to handle delays up to k . Unexpected longer delays (e.g. k+1 ) can break the protocol guarantees, leading to potential deadlocks or unsafe behaviors. To address such robustness concerns, we introduce a second protocol inspired by the “Hansel and Gretel” paradigm. Here, agents leave markers (such as pebbles or stickers) on vertices they visit. Each agent knows how many agents are expected to traverse each vertex on its planned path, and it scans only its adjacent vertex to determine when it may safely proceed. This lightweight marking system encodes minimal but sufficient information along the path and is based solely on local observations. Despite its simplicity, the second protocol ensures a makespan increase of at most k , in the presence of k faulty agents, as we show in Theorem 3 . Moreover, we believe that it offers a practical balance between robustness and minimal local sensing, making it suitable for real-world multiagent systems. 1.2 Related Work Multiagent Path Finding ( MAPF ) is a fundamental and practically motivated problem with a wide variety of algorithmic frameworks and real-world applications ma2022graph ; see also surveys stern2019 ; amigoni2022 . The idea of reusing previously computed solutions has been a subject of interest across planning domains. In fact, early work in general planning showed that reusing a plan can, paradoxically, be more complex than computing a new one from scratch NebelK95 . Motivated by real-world uncertainty, several variants of MAPF have been proposed to handle malfunctions or execution delays. One notable model is k - Robust MAPF , where the solution must tolerate up to k delays at arbitrary times and agents AtzmonSFWBZ20 . Another related model assumes that agents occupy

Read the complete text