Multi-Agent Path Finding Among Dynamic Uncontrollable Agents with Statistical Safety Guarantees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908472706072576 |
|---|---|
| author | Strawn, Kegan J. Phan, Thomy Wang, Eric Ayanian, Nora Koenig, Sven Lindemann, Lars |
| author_facet | Strawn, Kegan J. Phan, Thomy Wang, Eric Ayanian, Nora Koenig, Sven Lindemann, Lars |
| contents | Existing multi-agent path finding (MAPF) solvers do not account for uncertain behavior of uncontrollable agents. We present a novel variant of Enhanced Conflict-Based Search (ECBS), for both one-shot and lifelong MAPF in dynamic environments with uncontrollable agents. Our method consists of (1) training a learned predictor for the movement of uncontrollable agents, (2) quantifying the prediction error using conformal prediction (CP), a tool for statistical uncertainty quantification, and (3) integrating these uncertainty intervals into our modified ECBS solver. Our method can account for uncertain agent behavior, comes with statistical guarantees on collision-free paths for one-shot missions, and scales to lifelong missions with a receding horizon sequence of one-shot instances. We run our algorithm, CP-Solver, across warehouse and game maps, with competitive throughput and reduced collisions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_22282 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Agent Path Finding Among Dynamic Uncontrollable Agents with Statistical Safety Guarantees Strawn, Kegan J. Phan, Thomy Wang, Eric Ayanian, Nora Koenig, Sven Lindemann, Lars Multiagent Systems Robotics Existing multi-agent path finding (MAPF) solvers do not account for uncertain behavior of uncontrollable agents. We present a novel variant of Enhanced Conflict-Based Search (ECBS), for both one-shot and lifelong MAPF in dynamic environments with uncontrollable agents. Our method consists of (1) training a learned predictor for the movement of uncontrollable agents, (2) quantifying the prediction error using conformal prediction (CP), a tool for statistical uncertainty quantification, and (3) integrating these uncertainty intervals into our modified ECBS solver. Our method can account for uncertain agent behavior, comes with statistical guarantees on collision-free paths for one-shot missions, and scales to lifelong missions with a receding horizon sequence of one-shot instances. We run our algorithm, CP-Solver, across warehouse and game maps, with competitive throughput and reduced collisions. |
| title | Multi-Agent Path Finding Among Dynamic Uncontrollable Agents with Statistical Safety Guarantees |
| topic | Multiagent Systems Robotics |
| url | https://arxiv.org/abs/2507.22282 |