Topology and Complexity of Formations

Presented at the Workshop on the Mathematics and Algorithms of Social Insects, Atlanta, GA, Dec. 2003.Biological multi-agent systems such as animal herds, insect colonies and fish schools provide a lot of insight into the study and design of artificial multi-agent systems such as teams of autonomous mobile robots. Similarly, a lot can be learned about biological systems by borrowing design and analysis tools from multi-agent robotics. In this paper some recent work in the area of multi-agent robotics by the authors has been summarized, which addresses some basic issues in the modelling of formations with limited sensory and communication capabilities. The basic idea is to model spatial relationships between agents as connectivity graphs. An information theoretic complexity measure of multi-agent formations is suggested, which is based on the complexity of connectivity graphs. The complexity measure helps find graphs and formations of the highest and the lowest complexities