Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends the PIE concurrent planning-and-execution framework to lifelong MAPF with random execution delays, combining a dummy simulation step, delay-aware execution policies (MCP, PIBT-D) and replanners, and showing up to 3x throughput gains over delay-handling baselines.
Problem
Lifelong multi-agent path finding where agents may be delayed stochastically during execution, causing the committed and uncommitted plans to become desynchronised from actual agent positions.
Approach
Combine concurrent planning and execution (PIE) with a dummy simulation that predicts agents' actual positions after delays, plus reactive execution policies (MCP, PIBT-D) and a replanner that warm-starts LaCAM* with the previous uncommitted paths as a guidance heuristic.
Key results
- PIE-D with Replan All (guidance heuristic) and PIBT-D or MCP execution achieves up to 3x throughput over the PIE+MCP baseline (Hönig et al. 2019) in lifelong MAPF with delays.
- Replan All with partial-solution guidance has 100% success rate across 200-1400 agents in Warehouse with p=0.01, while Replan Affect drops to 0.68% success at 1400 agents.
- Restoring feasibility via concurrent replanning is consistently better than conventional reactive execution policies in the reported experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PIE-D with Replan All and partial-solution guidance instead of the delay-handling baselines | Lifelong MAPF · Random, Warehouse, Game, and City maps | throughput: up to a factor 3 | Helped |
| Add the previous uncommitted paths as guidance for LaCAM* replanning (ablation) | Replan All · Warehouse, p = 0.01, 600 agents | average solution cost (×1000): 4.733±0.376 -> 3.667±0.282 | Helped |
| Use Replan All with partial-solution guidance instead of Replan Affect | PIE-D with MCP · Warehouse, p = 0.01, 1400 agents | success rate (%): 0.68 -> 100 | Helped |
| Use Replan All with partial-solution guidance instead of Simulate then Replan | PIE-D with MCP · Warehouse, p = 0.01, 1400 agents | success rate (%): 11.11 -> 100 | Helped |
| Use PIBT-D rather than MCP as the execution policy (ablation) | PIE-D · Dense environments or large delay probabilities | throughput | Helped |
| Use MCP rather than PIBT-D as the execution policy (ablation) | PIE-D · Larger maps and Warehouse with p = 0.001 | throughput | Helped |
| Increase delay probability | PIE-D with MCP · LMAPF experiments | throughput | Hurt |
| Increase commit length from k = 3 to k = 10 (ablation) | PIE-D · LMAPF experiments | throughput | Mixed |
Surprising findings
- Smaller commit windows generally yield higher throughput, since they give more frequent feedback, except for the fully-execute baseline.
- Simply having the planner fully execute to commit cuts (PIE with MCP) performs worse than instant-feedback PIBT, because it introduces waiting for delayed agents.
Limitations
- Delay model is a synthetic MAPF-DP-style random delay model with uniform durations in [1,10].
- Replan Affect and Simulate then Replan time out at large team sizes under the 3s replanning limit.
- Replan All degrades in very large maps (City with 5000 agents) and can time out, reducing gains.
Experimental setup
Datasets: random-32-32-10 MAPF benchmark warehouse-10-20-10-2-1 MAPF benchmark ht_mansion_n MAPF benchmark Paris_1_256 MAPF benchmark
Benchmarks: random-32-32-10 warehouse-10-20-10-2-1 ht_mansion_n Paris_1_256
Metrics: throughput success rate average runtime solution cost
Baselines: PIBT with instant delay feedback PIE with MCP execution (Hönig et al. 2019) Replan All (LaCAM*) Replan Affect Simulate then Replan
Builds on: PIE MAPF-DP MCP PIBT LaCAM* MAPF-LNS
Closest papers by meaning
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.92)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.90)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.90)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.90)
- Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI 2024 · similarity 0.88)
- Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic (AAAI 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.