Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Multi-Agent Motion Planning for Differential Drive Robots Through Stationary State Search
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.
Proposes MASS, a three-level multi-agent motion planner for kinodynamically feasible differential-drive robot plans (PBS/PP at Level 1, stationary-state SSIPP at Level 2, speed profile solvers at Level 3), extended with an adaptive window for lifelong warehouse MAMP.
Problem
Multi-agent motion planning for differential drive robots under kinodynamic constraints (speed/acceleration limits, in-place rotation, orientation), where MAPF-based methods use simplified motion models and produce unrealistic or slow plans.
Approach
Searches only over stationary states (zero-speed transitions between rotation and movement) with an A*-style safe-interval search (SSIPP), uses partial stationary expansion to limit branching, and calls an optimization-based speed profile solver for each action; lifelong extension uses an adaptive replanning window with f_win = max(t_w, g) + h.
Key results
- Lifelong warehouse experiments: MASS(BAS) achieves throughput of 0.262 to 0.380 goals/s versus 0.065 to 0.152 for PP w/ ADG across Sparse and Congest settings, with the abstract claiming up to 400% improvement.
- Partial stationary expansion improves MASS(BCS) success rate on all maps and MASS(BAS) success rate on large maps.
- BAS achieves solution cost similar to the complete BCS on instances where both solve, while having higher success rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MASS(BAS) instead of PP w/ ADG | Lifelong MAMP_D · Sparse warehouse | throughput: 0.142$\pm$8.4\% -> 0.262$\pm$2.9\%; 0.152$\pm$8.3\% -> 0.264$\pm$4.3\%; 0.149$\pm$6.8\% -> 0.259$\pm$4.5\%; 0.148$\pm$7. | Helped |
| Use MASS(BAS) instead of PP w/ ADG | Lifelong MAMP_D · Congest warehouse | throughput: 0.065$\pm$2.5\% -> 0.373$\pm$1.4\%; 0.075$\pm$4.0\% -> 0.380$\pm$3.4\%; 0.090$\pm$3.4\% -> 0.371$\pm$4.1\%; 0.095$\pm$2. | Helped |
| Use MASS(BCS) instead of PP w/ ADG | Lifelong MAMP_D · Sparse warehouse | throughput: 0.142$\pm$8.4\% -> 0.215$\pm$6.4\%; 0.152$\pm$8.3\% -> 0.215$\pm$7.0\%; 0.149$\pm$6.8\% -> 0.215$\pm$1.9\%; 0.148$\pm$7. | Helped |
| Use MASS(BCS) instead of PP w/ ADG | Lifelong MAMP_D · Congest warehouse | throughput: 0.065$\pm$2.5\% -> 0.294$\pm$4.4\%; 0.075$\pm$4.0\% -> 0.300$\pm$3.4\%; 0.090$\pm$3.4\% -> 0.294$\pm$13.4\%; 0.095$\pm$2 | Helped |
| Use BAS instead of BCS as the speed profile solver | MASS · Sparse and Congest warehouses | throughput: 0.215$\pm$6.4\% -> 0.262$\pm$2.9\%; 0.215$\pm$7.0\% -> 0.264$\pm$4.3\%; 0.215$\pm$1.9\% -> 0.259$\pm$4.5\%; 0.218$\pm$3. | Helped |
| Add partial expansion (PE) (ablation) | MASS(BCS) · Single-shot grid maps | success rate | Helped |
| Add partial expansion (PE) (ablation) | MASS(BAS) · Single-shot large-scale maps | success rate | Helped |
| Add partial expansion (PE) (ablation) | MASS(BAS) · Single-shot small-scale maps | success rate | No clear effect |
| Use BAS instead of BCS as the speed profile solver | MASS · Single-shot grid maps | solution cost | No clear effect |
| Replace MASS with SIPP-IP | Single-shot MAMP_D · Obstacle-rich maps | success rate | Hurt |
| Use MASS instead of SIPP-IP | Single-shot MAMP_D · Some grid-map cases | solution quality | Helped |
| Use BCS as the speed profile solver rather than BAS | MASS · Single-shot large-agent scenarios | scalability | Hurt |
Surprising findings
- The incomplete Binary Acceleration Solver achieves higher success rate than the complete Bezier-curve Solver, attributed to BCS scalability limits.
- MASS(BAS) gains slightly more throughput than MASS(BCS) because its shorter runtime lets it explore more priority orderings.
Limitations
- BAS is incomplete and can miss feasible speed profiles (e.g., agent must wait at a vertex).
- BCS does not scale beyond less congested instances (fails with 150 agents on warehouse-small).
- Speed profile solver and planner are heuristic-driven; completeness depends on Level 3 being complete and optimal.
Experimental setup
Datasets: MovingAI grid benchmark maps LMAPF Competition sortation-center map
Benchmarks: MovingAI grid maps (empty, random, room, den520d, Boston, warehouse-small, warehouse-large) sortation-center map Amazon HARMONIES Kiva warehouse simulator (Congest, Sparse)
Metrics: success rate runtime relative sum of costs throughput
Baselines: SIPP-IP PP w/ ADG PSB MAPF+ADG
Builds on: Priority-Based Search Safe Interval Path Planning SIPP-IP RHCR Action Dependency Graph
Closest papers by meaning
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.88)
- Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models (ICML 2025 · similarity 0.85)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.85)
- LNS2+RL: Combining Multi-agent Reinforcement Learning with Large Neighborhood Search in Multi-agent Path Finding (AAAI 2025 · similarity 0.85)
- Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities (AAAI 2025 · similarity 0.85)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.85)
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.