Multi-robot formations: rule-based synthesis and stability analysis

Abstract

This thesis addresses three aspects of the multi-robot formation problem. Our contributions are: a novel bottom-up approach to formation assembly, a formal model for describing the assembly coordination based on a sequence of graph transformations, and a set of control policies that eliminate string instability within a formation. Specifically, we present a decentralized approach to assembling and maintaining robot formations. Starting with a collection of single robots, our approach assembles platoons, or line segments of robots, followed by larger, more complex formations. Formation growth occurs by negotiation when robots are in close proximity and is governed by a set of simple rules based on a graph grammar. We formally define robot formations as directed graphs and define a rule-based graph grammar that describes the assembly coordination. Using this formalism we state and validate three hypotheses: First, given a desired formation there exists a set of rules which cause the formation to be created, Second, given such a set of rules, a controller for each robot can be designed which when executed on a set of robots will cause the robots to assemble in the proper formation, and third, this controller has the necessary stability properties for disturbance rejection. Experimental validation for these hypotheses is provided in simulation and in limited tests on physical non-holonomic robots.