A Grid-Based Approach to Formation Reconfiguration for a Class of Robots with Non-Holonomic Constraints

In this paper, we propose an architecture for safe, collision-free formation reconfiguration of a team of autonomous agents. Our approach is based on abstracting the agent formation by a rectangular grid. We develop a discrete-event coordination strategy that plans collisionfree transitions between arbitrarily defined formations. The coordination strategy implementation is based on a well-established control design methodology for manufacturing systems. Agent dynamics are modeled taking into account realistic, non-holonomic constraints. Using the concept of leader-to-formation stability, we propose controller tuning guidelines to ensure that the actual multiagent system behavior conforms to the discrete-event motion plan. Group navigation is achieved by integrating a way point controller with this novel grid-based formation reconfiguration scheme. The proposed hybrid architecture is capable of driving a group of agents through a cluttered environment, while maintaining specified formation constraints. We present simulated and experimental results verifying the validity of our methodology.