A graph theoretic approach for modeling mobile robot team formations

This paper addresses a new approach for modeling and control of multiple teams of mobile robots navigating in a terrain with obstacles, while maintaining a desired formation and changing formations when required. We model each team as a triple, (g,r,H), consisting of a group element, g is an element of SE(2), that describes the gross position of the lead robot, a set of shape variables, r, that describe the relative positions of robots, and a control graph, H, that describes the behaviors of the robots in the formation. We assume that all the robots are equipped with the appropriate sensors to detect and avoid other robots and obstacles in the environment. Our framework enables the representation and enumeration of possible control graphs, and the coordination of transitions between any two control graphs. Further, we describe an algorithm that allows each 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 examples to illustrate the control graphs and the algorithm for transitioning between them in the presence and absence of sensor noise. (C) 2002 Wiley Periodicals, Inc.