Coordinated navigation of multi-robot systems with binary constraints

In this paper we present a method for navigating a multi-robot system through an environment while additionally maintaining a predefined set of constraints. Possible constraints are the requirement to keep up the direct line-of-sight between robots or to ensure that robots stay within a certain distance. Our approach is based on graph structures that model movements and constraints separately, in order to cover different robots and a large class of possible constraints. Additionally, the partition of movement and constraint graph allows us to use known graph algorithms like Steiner trees to solve the problem of finding a target configuration for the robots. We construct so called separated distance graphs from the Steiner tree and the underlying roadmap graph, which allow assembling valid navigation plans fast.