Conflict Mitigation in Shared Environments using Flow-Aware Multi-Agent Path Finding
Authors: Lukas Heuer, Yufei Zhu, Luigi Palmieri, Andrey Rudenko, Anna Mannucci, Sven Koenig, Martin Magnusson
Organizations: L. Heuer, Y. Zhu and M. Magnusson - Örebro University · L. Palmieri, A. Rudenko and A. Mannucci - Bosch Research · A. Rudenko - Technical University of Munich · S. Koenig - University of California, Irvine
Deploying multi-robot systems in environments shared with dynamic and uncontrollable agents presents significant 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 trajectories, 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.
Figures & tables
Fig. 1: The cost for an edge transition for every location in the den312d -map, for each move action respectively. It is computed using the MoD in Figure 3 and shows how FA-MAPF translates motion patterns into a semantic cost-landscape for the MAPF algorithm.
Fig. 2: Left: A visualization of an SWGMM, obtained from an MoD, that represents the likelihood of UA movement for a specific location in a map. The colored arrows represent the set of possible actions of a MAPF agent. Right: Flow cost calculated using Eq. 4 representing the distance from an action to the SWGMM.
Fig. 3: Left: It shows the areas from which the start and goal points are sampled for directed UA movement. The numbers indicate the corresponding areas. Right: The corresponding CLiFF-map of dynamics, with the arrows representing the means of the SWGMM mixture components, and color indicates their direction in radians.
Fig. 4: Result of one-shot EECBS on the different benchmark maps (see Table I for the map names), for different UA movement types (as described in Section IV ). x-axis is the number of MAPF agents. y-axis shows either the percentage ( top ) of instances solved (out of 25) or the average runtime ( bottom ). The runtime cutoff is 5 seconds.
TABLE I: Results from running (FA-)RHCR on different benchmark maps for a specific number of MAPF agents. The results compare the relevant metrics for RHCR with and without flow-awareness. Mean and standard deviation are computed across the different RHCR iterations. .
Fig. 5: Results of running RHCR on the den312d -map. x-axis is the number of MAPF agents, y-axis the respective metric value. UA movement type is directed .
Fig. 6: Results of running RHCR with 200 agents on the den312d -map. x-axis is the replanning window size of RHCR, y-axis the respective metric value. UA movement type is directed .
Fig. 7: Results of running RHCR on the ATC-map. x-axis is the number of steps, y-axis the respective metric value. RHCR runs for 33000 timesteps with 40 MAPF agents.
Fig. 8: Results of running RHCR on the warehouse-10-20-10-2-1 -map. x-axis is the number of agents, y-axis the respective metric value. UA movement type is directed .
Fig. 9: Results of running RHCR on the warehouse-10-20-10-2-1 -map. x-axis is the number of agents, y-axis the respective metric value. UA movement type is directed but enforces highway patters [ 32 ] .