Traditional Multi-Agent Path Finding (MAPF) operates under a convenient but unrealistic assumption: a fleet of robots starts at designated positions, plans collision-free paths to a static set of destinations, and stops once those goals are reached. In real-world logistics—such as automated fulfillment centers handling thousands of orders—tasks arrive continuously and asynchronously. Robots cannot simply sit idle after a single delivery; they must immediately transition to new assignments.
Shifting from "one-shot" planning to Lifelong Multi-Agent Path Finding (LMAPF) introduces a fundamental computational challenge. Because the environment's state is perpetually evolving without a defined end state, a naive centralized planner would need to re-compute global paths every time a new task enters the system. This creates an intractable computational bottleneck. To maintain high system throughput without gridlock, researchers have developed mechanisms that decouple planning across time, space, and agent identities.
Breaking the Infinite Horizon: Rolling-Horizon Planning
If a system attempts to plan optimal, collision-free paths for hundreds of robots over an infinite timeline, the search space explodes. However, resolving a collision between two robots five minutes into the future is often a waste of compute, as subsequent task assignments will likely alter their trajectories anyway.
To exploit this intuition, Jiaoyang Li et al. introduced Rolling-Horizon Collision Resolution (RHCR) in [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses]. Instead of solving the global pathfinding problem all at once, RHCR decomposes lifelong coordination into a sequence of finite-horizon planning instances.
Timeline: |---- Window W (Resolve Collisions) ----|--- Plan to Goal (No Collision Checks) --->
^ ^
Current Time Horizon Limit
Agents plan full paths to their targets, but the algorithm only checks for and resolves collisions within a specific short-term temporal window ($W$). As time progresses, the window slides forward, and the system replans. This windowed approach ensures that agents can adapt dynamically to new goals while keeping real-time computation bounded. Building on this concept, He Jiang et al. demonstrated in their Windowed Parallelized Local Search (WPPL) framework [Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities] that combining windowed planning with parallelized local search allows systems to scale to 10,000 agents in high-density environments.
Decentralization via Local Coordination Rules
While rolling horizons reduce the temporal complexity, centralized planners can still struggle to distribute paths to massive fleets in real time. An alternative strategy shifts the coordination burden to the agents themselves, using decentralized rules or learned behaviors to maintain continuous flow.
One prominent algorithmic mechanism is Priority Inheritance with Backtracking (PIBT), proposed by Keisuke Okumura et al. in [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding]. PIBT requires agents to plan only one step ahead. When a higher-priority agent wants to move into a space occupied by a lower-priority agent, the lower-priority agent "inherits" the priority to clear the way, recursively backtracking if it hits a dead end. This localized negotiation prevents deadlocks reactively without requiring global path re-computation.
Complementing these algorithmic rules are learning-based frameworks like PRIMAL$_2$, developed by Mehul Damani et al. [PRIMAL$_2$: Pathfinding Via Reinforcement and Imitation Multi-Agent Learning - Lifelong]. By training agents using a combination of reinforcement learning and imitation learning, the authors enabled robots to learn implicit "social conventions"—such as favoring right-hand sides in narrow corridors. Because agents make decisions based purely on local observations, the computational cost remains constant regardless of the total fleet size, allowing thousands of robots to navigate dense layouts without explicit communication.
Trading Identity for Flow: Dynamic Target Swapping
In many industrial applications, robots are anonymous carriers; it does not matter which specific robot picks up a given item, as long as some robot does. This insight allows researchers to bypass spatial collision resolution entirely by transforming it into a logical task assignment problem.
In [Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution], Keisuke Okumura et al. formalized this via the TSWAP algorithm. When two agents moving in opposite directions encounter a potential collision or deadlock in a narrow passageway, they do not spend compute calculating complex bypasses. Instead, they instantly swap their target assignments.
Before Swap: (Agent A) ----> [Collision Point] <---- (Agent B)
Target: 1 Target: 2
After Swap: (Agent A) <---- [Collision Point] ----> (Agent B)
Target: 2 Target: 1
By dynamically reassignment goals on the fly, TSWAP eliminates the physical bottlenecks that cause gridlock. Similarly, the Token Passing with Task Swaps (TPTS) algorithm by Jiaoyang Li et al. [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks] uses task swapping to maintain continuous, online streams of pickup-and-delivery operations, ensuring that the closest available robot always takes over a task to maximize system efficiency.
From Path Cost to Sustained Throughput
As the research direction solidifies around lifelong operations, the metrics used to evaluate these systems have fundamentally shifted. As Nathan R. Sturtevant et al. emphasize in [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks], traditional metrics like "sum-of-costs" (the total time taken for all agents to reach their initial goals) are insufficient for lifelong scenarios.
Instead, the community evaluates algorithms based on sustained throughput—the number of tasks completed per unit of time over indefinite horizons. Single-author works in this space have explored alternative paradigms to maximize this throughput. For instance, Alexey Skrynnik [Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding] investigated decentralized search mechanisms to maintain long-term traffic flow under partial observability, while Kazumi Kasaura [Periodic Multi-Agent Path Planning] proposed optimizing repeatable, periodic schedules to handle continuous streams of agents without requiring real-time communication.
By focusing on long-term traffic management rather than one-time path completion, these combined approaches ensure that large-scale robotic fleets can operate continuously without succumbing to gridlock or computational exhaustion.
Key Foundational Work
Process-Oriented Planning and Average-Reward Opumalirv (1995) — contributed 1 concept elements to this direction.
Learning to Take Concurrent Actions (2002) — contributed 1 concept elements to this direction.