Skip to content
Open access

Path Passing Sequence Search for Lifelong Multi-Agent Pathfinding With Uncertain Delays

Nov 2026 · IEEE Robotics and Automation Letters · Vol 11, pp. 12440-12447 · 0 citations · 27 references
Computer Science

TL;DR

A Path-Passing-Sequence Search (PPSS) framework is proposed that constructs robust passing sequences directly during the planning phase without strict reliance on time steps and a novel collision prediction strategy is introduced to evaluate potential conflicts and deadlock cycles.

Abstract

The Lifelong Multi-Agent Path Finding (LMAPF) problem in practice faces significant challenges due to uncertain delays and the interleaving of planning and execution. Traditional solvers often rely on precise time-step reservations, which are prone to failure when agents deviate from their schedules, leading to inaccurate collision predictions between planning and executing agents. To address this limitation, this letter proposes a Path-Passing-Sequence Search (PPSS) framework that constructs robust passing sequences directly during the planning phase without strict reliance on time steps. PPSS extends the A* algorithm by expanding the search state space to determine spatial routes and valid insertion positions within existing passing orders simultaneously. Furthermore, a novel collision prediction strategy is introduced to evaluate potential conflicts and deadlock cycles by analyzing the relative passing ranks of Anchor-Anchor Movement Units (AAMUs). Extensive experiments in discrete-time settings and a preliminary real-world deployment in a continuous-time setting demonstrate that PPSS effectively generates collision-free paths and maintains safe passing orders even under practical uncertain delays.

Read PDF

Similar papers

Open access Sep 2026

Solving the Multi-Agent Path Finding Problem Using a Hierarchical Multi-Resolution Planner

A hierarchical, reservation-based, multi-resolution planner for discrete-time grid environments, including deadline-aware priority guidelines to resolve reservation contention, boundary-based validation of abstract connectivity to avoid phantom links, and a wait-and-retry fallback when planning temporarily fails are pr...

Gicu Rata, Liviu Octavian Mafteiu-Scai · 0 citations
#artificial intelligence Preprint Oct 2026

MeshSIPP: Efficient Lattice Planning in Dynamic Environment

Autonomous navigation in dynamic environments requires computing spatiotemporal trajectories that satisfy non-holonomic motion constraints. When the trajectories of the moving obstacles are predictable or known, a promising approach is to rely on the combination of state lattices constructed from precomputed feasible m...

Marat Agranovskiy, K. Yakovlev · 0 citations
#artificial intelligence Open access Jul 2025

LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions (Extended Abstract)

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all...

Da-Chuan Liu, Shuai Zhou, Shi-Zhe Zhao et al. · 3 citations
Preprint Oct 2026

The Cost of Classical Multi-Agent Path Finding

Insight is provided on when classical MAPF is a reasonable simplification, and when MAPF$_R$ unlocks significantly higher-quality solutions.

Alvin Combrink, S. Roselli, Martin Fabian · 0 citations
Open access Sep 2026

Path Planning with Motion Primitives in Dynamic Environments: SIPP on Lattices

Autonomous navigation in dynamic environments is a critical challenge, particularly when spaces are shared with other mobile agents whose future trajectories are known. While traditional grid-based planners efficiently find collision-free paths, their reliance on stop-and-turn mechanics over $2^k$-connected grids produ...

Marat Agranovskiy · 1 citation
Open access Sep 2026

Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels

The efficiency and stability of path planning algorithms are important factors in the autonomous navigation of Unmanned Surface Vehicles (USVs), particularly in maritime environments where obstacle avoidance, control smoothness, and computational workload must be considered together. Classical deterministic planners su...

Eren Deniz, E. Sezer · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.