Lifelong MAPF (LMAPF)

Unlike classical MAPF, which solves a single instance from start to goal, LMAPF operates continuously. Agents receive new goal assignments as soon as they complete their current task, creating an online planning problem. The system must maintain a persistent planner that can handle these dynamic arrivals without restarting the entire solution process. This is analogous to a real-world warehouse where robots are constantly given new pick locations.

LMAPF is inherently coupled with a task allocation system. The planner must interface with a dispatcher that assigns new goals (e.g., fetching inventory, delivering a package) to idle or soon-to-be-idle agents. Key considerations include:

• Matching efficiency: Assigning tasks to minimize travel distance or time.
• Load balancing: Distributing work evenly across the fleet.
• Temporal constraints: Some tasks may have deadlines or time windows for completion.

LMAPF systems must be reactive to changes in the environment and plan failures. This necessitates:

• Fast replanning engines: Algorithms that can quickly adjust paths for a subset of agents when a new task is added or an obstacle appears.
• Incremental techniques: Reusing previous computation (e.g., existing path segments, conflict data) to speed up new planning episodes.
• Execution robustness: Incorporating k-robustness or buffers to handle minor timing deviations without causing cascading collisions.

A core guarantee in LMAPF is liveness—ensuring every agent can eventually complete its assigned tasks and that the system does not enter a permanent deadlock. This is more challenging than in one-shot MAPF because of infinite horizons. Strategies include:

• Deadlock detection algorithms: Proactively identifying gridlock situations (e.g., cyclic waiting).
• Priority-based protocols: Using dynamic priorities or reservation rules to break symmetries.
• Task swapping: Allowing agents to exchange goals to resolve mutual blockages.

The primary performance metric shifts from makespan or sum-of-costs (relevant for a fixed set of goals) to system throughput. The goal is to maximize the number of tasks completed per unit time. Optimization focuses on:

• Minimizing agent idle time: Keeping agents productively moving.
• Reducing congestion: Planning paths that avoid creating bottlenecks in high-traffic areas.
• Efficient charging integration: For electric agents, scheduling docking/charging as a task to minimize fleet downtime.

LMAPF is not a standalone algorithm but a critical component within a larger heterogeneous fleet orchestration platform. It must seamlessly interact with:

• State estimation services: For real-time agent localization.
• Health monitoring: To account for agent failures or maintenance needs.
• Zone management: To respect dynamic no-go zones or speed limits.
• Human-in-the-loop interfaces: To allow for operator overrides or priority task insertion.

In modern distribution centers, LMAPF algorithms coordinate fleets of Autonomous Mobile Robots (AMRs) that continuously receive new pick-and-place or transport orders. Key characteristics include:

• Dynamic order injection: New tasks arrive in real-time as customer orders are placed.
• Persistent agent activity: Robots are never "done"; upon delivering one item to a packing station, they are immediately assigned a new pod to retrieve.
• Integration with WMS: The LMAPF solver acts as the real-time execution layer below a Warehouse Management System's task allocator. This application demands high throughput and low latency replanning to adapt to congestion and changing priorities.

LMAPF provides the continuous routing core for systems that autonomously park and retrieve customer vehicles or manage storage robots in dense automotive facilities.

• Continuous task stream: As cars arrive at a drop-off zone, they become new agents requiring paths to parking spots. Upon request, parked cars become agents needing paths to a pickup zone.
• High-density, dynamic obstacles: The environment changes as cars are moved by the system itself, requiring constant map updates and conflict resolution.
• Battery-aware scheduling: For robotic carriers, the LMAPF system must schedule charging cycles as a new type of lifelong task without disrupting overall flow.

In flexible smart factories, LMAPF orchestrates material transport robots (like Autonomous Guided Vehicles or free-ranging AMRs) that supply parts to assembly stations in a just-in-time manner.

• Uninterrupted material flow: Stations have continuous demand, creating a non-ending stream of fetch-and-deliver tasks for robots.
• Multi-modal stations: Robots may interact with stationary robots, conveyor belts, and human workers, requiring sophisticated spatio-temporal coordination.
• Exception handling: The LMAPF engine must seamlessly reroute around station downtime or robot failures, reassigning tasks dynamically to maintain production line uptime.

LMAPF systems manage fleets of robots performing endless delivery loops for linens, meals, lab samples, and pharmaceuticals within large facilities.

• Priority-based interruptions: A stat lab sample may require immediate transport, forcing the online replanning of all other robot paths to clear a high-priority corridor.
• Human-shared environments: Paths must be planned with extra caution (e.g., larger buffers or k-robust plans) around unpredictable human movement.
• Multi-depot operation: Robots may need to periodically return to central sterilization or charging depots, which are integrated as recurring tasks within the lifelong problem.

At automated port yards, LMAPF coordinates the movement of straddle carriers, automated guided vehicles, and stacking cranes to transfer containers between ships, storage blocks, and trucks.

• Extreme scale and density: Hundreds of agents operate simultaneously in a tightly structured but highly dynamic grid.
• Temporal synchronization: An AGV's path must be precisely timed to arrive at a crane's pickup location exactly when the crane is ready, requiring tightly coupled scheduling.
• Weather and delay resilience: The system must absorb delays (e.g., a slowed AGV) and continuously re-optimize the plan for the entire fleet to minimize vessel turnaround time, a classic makespan optimization under uncertainty.

In security or agricultural monitoring, a swarm of UAVs must maintain continuous coverage of a large area, with individual drones cycling to charging stations.

• Task as persistent area coverage: The "goal" for a drone is a region to monitor; upon completion, its new task is another region. This is modeled as a continuous sequence of area-coverage tasks.
• Energy as a fundamental constraint: The LMAPF solver must schedule return-to-base charging as a highest-priority task, seamlessly reallocating coverage areas among the remaining drones.
• Dynamic threat response: The system must be able to interrupt the persistent coverage plan to vector multiple drones to a newly detected event, showcasing dynamic task re-prioritization within the lifelong framework.

Multi-Agent Path Finding (MAPF) is the foundational computational problem of finding collision-free paths for multiple agents from their start locations to their goal locations in a shared, typically discrete, environment. It is a one-shot planning problem. LMAPF is a direct extension where, instead of a single set of goals, agents are continuously assigned new tasks, making it an online, persistent variant of MAPF.

• Centralized vs. Decoupled: Algorithms can be centralized (planning in the joint state space) or decoupled (planning per agent with coordination).
• Optimality Criteria: Solutions are evaluated by metrics like Makespan (total completion time) and Sum of Costs (SOC) (total distance traveled).

Conflict-Based Search (CBS) is a leading optimal, centralized algorithm for classical MAPF. It operates on two levels: a high-level constraint tree and low-level single-agent path planners (typically A*).

• Constraint Resolution: When a vertex conflict (two agents in same location at same time) or edge conflict (swapping positions) is found, CBS branches by imposing constraints (e.g., Agent 1 cannot be at vertex V at time T) and replans for the affected agent.
• Relevance to LMAPF: CBS provides the foundational conflict resolution logic. In LMAPF, algorithms often use CBS-based replanners that are invoked online when new tasks arrive or when execution deviates from plan, managing a continuously evolving constraint tree.

A Real-Time Replanning Engine is the core software component in an LMAPF system that dynamically adjusts agent plans in response to environmental changes, new task insertions, or agent failures. Unlike one-shot MAPF solvers, these engines must operate under strict latency constraints to maintain fleet fluidity.

• Trigger Events: Replanning can be triggered by sensor updates (new obstacles), task dispatcher commands, or predictive deadlock detection.
• Algorithmic Strategies: Engines may use windowed planning (like WHCA*), lazy replanning (only replan affected agents), or anytime algorithms that improve solutions within a time budget.
• System Integration: This engine sits within the broader orchestration middleware, interfacing with the fleet state estimator and task allocator.

Dynamic Task Allocation is the real-time process of assigning newly arriving tasks (e.g., transport jobs in a warehouse) to agents within a heterogeneous fleet. In LMAPF, this is intrinsically coupled with path planning, as a task's cost depends on the agent's current location and the planned paths of other agents.

• Market-Based Approaches: Tasks are auctioned to agents, which bid based on estimated path cost including conflicts.
• Centralized Optimizers: Use combinatorial optimization (e.g., Hungarian algorithm) to match tasks to agents, often incorporating predicted path costs from the MAPF solver.
• Objective Functions: Allocation aims to minimize total travel cost, maximum agent workload, or task completion time.

Sum of Costs (SOC), also called Flowtime, is the primary performance metric for evaluating LMAPF solutions over a finite horizon. It is defined as the sum of the travel times (or distances) for all agents from their current states to their assigned goal locations. In the lifelong setting, this is measured over a rolling window of completed tasks.

• Minimization Objective: The core optimization goal for most LMAPF algorithms is to minimize the ongoing SOC, which directly correlates with system throughput and fleet efficiency.
• Contrast with Makespan: Makespan measures the time until the last agent finishes its current task. SOC is often more relevant in continuous operation as it accounts for the performance of all agents across all tasks.

Windowed Hierarchical Cooperative A (WHCA)** is a scalable, suboptimal algorithm designed for real-time multi-agent planning, making it highly relevant for LMAPF systems. It breaks the infinite-horizon problem into manageable, repeating planning windows.

• Mechanism: Within a short planning window (e.g., 10 timesteps), agents plan paths using A* while respecting a shared reservation table (a type of Conflict Avoidance Table). Paths are executed only for the duration of the window, after which the process repeats.
• Hierarchy: A high-level planner can assign coarse goals, while the low-level WHCA* handles fine-grained collision avoidance.
• Trade-off: Sacrifices global optimality for computational tractability and reactivity, which is essential for large-scale, lifelong operations.