2021/07/01 by Stepan Dergachev, Dergachev, Stepan, Konstantin Yakovlev +1 · 4 citations
Computer Science · #FOS: Computer and information sciences #Multiagent Systems (cs.MA) #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2107.00246
openalex publication_date 2021/07/01 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Avoiding collisions is the core problem in multi-agent navigation. In\ndecentralized settings, when agents have limited communication and sensory\ncapabilities, collisions are typically avoided in a reactive fashion, relying\non local observations/communications. Prominent collision avoidance techniques,≠.g. ORCA, are computationally efficient and scale well to a large number of\nagents. However, in numerous scenarios, involving navigation through the tight\npassages or confined spaces, deadlocks are likely to occur due to the egoistic\nbehaviour of the agents and as a result, the latter can not achieve their\ngoals. To this end, we suggest an application of the locally confined\nmulti-agent path finding (MAPF) solvers that coordinate sub-groups of the\nagents that appear to be in a deadlock (to detect the latter we suggest a\nsimple, yet efficient ad-hoc routine). We present a way to build a grid-based\nMAPF instance, typically required by modern MAPF solvers. We evaluate two of\nthem in our experiments, i.e. Push and Rotate and a bounded-suboptimal version\nof Conflict Based Search (ECBS), and show that their inclusion into the\nnavigation pipeline significantly increases the success rate, from 15% to 99%\nin certain cases.\n