Spatially constrained coordinated navigation for a multi-robot system

In this paper we present a method for navigating a multi-robot system through an environment while additionally maintaining a predefined set of constraints. Examples for constraints are the requirement to maintain a direct line-of-sight between robots or to ensure that the multi-robot system maintains communication. Our approach is based on graph structures that model movements and constraints separately, in order to cover different kind of robots and a large class of possible constraints. Additionally, the separation of movement and constraint graph allows us to use known graph algorithms like Steiner tree heuristics or the multi-point relay algorithm to solve the problem of finding a target configuration for the robots. To connect the movements of the robots with the given constraints, we introduce separated connection graphs which allow assembling valid navigation plans fast. This paper presents some theoretical insight into the problem of coordinated navigation for multi-robot systems with spatial constraints as well as a practical solution. Experiments in simulation and with real robots show the feasibility of the approach.