Distributed Multi-agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined Multi-agent Path Finding

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,\ne.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