Conflict Mitigation in Shared Environments Using Flow-Aware Multi-Agent Path Finding
Lukas Heuer, Yufei Zhu, Luigi Palmieri, Anna Mannucci, Andrey Rudenko, Sven Koenig, Martin Magnusson
AI summary
Problem
Multi-robot systems struggle with unpredictable delays and conflicts when operating in environments shared with dynamic, uncontrollable agents like humans. Current MAPF methods largely ignore environmental motion patterns to proactively avoid these conflicts.
Approach
FA-MAPF incorporates learned spatio-temporal motion patterns of dynamic agents into centralized path planning by adjusting edge costs to penalize trajectories that align with predicted flows.
Key results
- Reduces conflicts with uncontrollable agents by up to 55%
- Maintains task throughput and efficiency in lifelong planning
- Preserves completeness and bounded sub-optimality guarantees
- Validated on synthetic benchmarks and real-world human trajectory datasets
Why it matters
Enables reliable and safe deployment of large multi-robot fleets in dynamic, human-populated environments like warehouses and public spaces.
Abstract
Deploying multi-robot systems in environments shared with dynamic and uncontrollable agents presents sig- nificant challenges, especially for large robot fleets. In such environments, individual robot operations can be delayed due to unforeseen conflicts with uncontrollable agents. While existing research primarily focuses on preserving the completeness of Multi-Agent Path Finding (MAPF) solutions considering delays, there is limited emphasis on utilizing additional environmental information to enhance solution quality in the presence of other dynamic agents. To this end, we propose Flow-Aware Multi-Agent Path Finding (FA-MAPF), a novel framework that integrates learned motion patterns of uncontrollable agents into centralized MAPF algorithms. Our evaluation, conducted on a diverse set of benchmark maps with simulated uncontrollable agents and on a real-world map with recorded human trajecto- ries, demonstrates the effectiveness of FA-MAPF compared to state-of-the-art baselines. The experimental results show that FA-MAPF can consistently reduce conflicts with uncontrollable agents, up to 55%, without compromising task efficiency.