Modeling multiple teams of mobile robots: a graph theoretic approach

Addresses the control of a team of robots navigating in a terrain with obstacles, while maintaining a desired formation and changing formations when required using an underlying graph theoretic framework. We state and prove the mathematical results relating to multi-robot teams moving in a formation. We model each team as a triple, (g, r, ℋ), consisting of a group element, g, that describes the gross position of the lead robot, a set of shape variables, r, that describes the relative positions of robots and a control graph, ℋ that describes the behaviors of the robots in the formation. Our framework enables the representation and enumeration of all possible control graphs, and the coordination of transitions between any two control graphs. Further, we describe an algorithm that allows the team of robots to move between any two formations, while avoiding obstacles. As the number of robots increases, the number of possible control graphs increases. However, because the control computations are decentralized, the algorithms scale with the number of robots. We present an example to illustrate the control graphs and the algorithm for transitioning. between them in the presence and absence of sensor noise