Multi-Robot Navigation among Movable Obstacles: Implicit Coordination to Deal with Conflicts and Deadlocks

How to coordinate multiple robots moving in modifiable cluttered environments? In this paper, we introduce the multi-robot version of the NAMO problem (Navigation Among Movable Obstacles). In MR-NAMO, robots must not only plan for the possibility of displacing obstacles as needed to facilitate their navigation, but also solve conflicts that may arise when trying to simultaneously access a location or obstacle. After identifying all different types of conflicts, we define and compare variants of an implicit coordination strategy allowing the use of existing NAMO algorithms [1] in a Multi-Robot context. We also show how our previously introduced social occupation cost model [2] can improve the efficiency of multi- robot plans with better obstacle placement choices, and how it can be applied in a novel way to find relevant robot placement choices to solve deadlock situations.