Rigid Graph Theory for Vision-Based Formation Control in Heterogeneous Robot Networks

Tony Grubman

Formation control systems enable networks of robots to move together in a fixed geometric configuration. This allows the network to operate autonomously, with all robots working together to achieve a global objective. Rigid graph theory is a powerful mathematical tool that can be used to construct formation control systems with provable stability. The network of robots is modelled as a graph embedded in space, with the length of each edge actively controlled by the robots.

In order for the robots to control their position, they must first have some capability of sensing the distance to each of their neighbours. In many configurations, the identity of each neighbour is also essential to determine. A camera-based identification and tracking system that performs this necessary sensing was devised and implemented. The syste involves a circular sequence of colours around the perimeter of each robot. To maximise the number of possible robots while guaranteeing that they still can be identified, a combinatorial model of the colouring process was created. Interesting links were found to cycle decompositions of de Bruijn graphs, and several existence results were proved using a combination of Galois field algebra and combinatorics of words. The mathematical constructions that led to these results were developed.

[back to Ahmet's home] [back to ECSE home] [back to Monash home]

Department of Electrical and Computer Systems Engineering, Monash University, Melbourne, Australia
Last modified: Tue Oct 28 15:14:15 EST 2014 by Ahmet Sekercioglu