center for robotics and embedded systems University of Southern California Viterbi School of Engineering


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. Specically, 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 dene robot formations as directed graphs and dene 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.


Go Home
Maintained by webmaster