{"ID":2889437,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.22282","arxiv_id":"2507.22282","title":"Multi-Agent Path Finding Among Dynamic Uncontrollable Agents with Statistical Safety Guarantees","abstract":"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.","short_abstract":"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 pred...","url_abs":"https://arxiv.org/abs/2507.22282","url_pdf":"https://arxiv.org/pdf/2507.22282v1","authors":"[\"Kegan J. Strawn\",\"Thomy Phan\",\"Eric Wang\",\"Nora Ayanian\",\"Sven Koenig\",\"Lars Lindemann\"]","published":"2025-07-29T23:16:04Z","proceeding":"cs.MA","tasks":"[\"cs.MA\",\"cs.RO\"]","methods":"[]","has_code":false}