Graphs, Simplicial Complexes, and Beyond: Topological Tools for Multi-agent Coordination

The increasing pervasiveness and accuracy of sensors, unprecedented automation of data collection, extremely cheap storage and rapid dissemination of data by communication networks have enabled researchers to think about deploying swarms of cooperating robotic agents for various applications. However, the conception of such large-scale systems is contigent on efficient methods to deal with an explosion of data. Thus the main challenge in this field has shifted from difficulties in manufacturing to the lack of theoretical foundations for provably correct design and deployment. This monograph, appearing originally as a doctoral thesis, offers a unique perspective on the solution of such problems. It introduces some novel methods for dealing with the spatial complexities in robotic networks. At the same time, it makes connections to several emerging disciplines in engineering and mathematical sciences, most notably computational algebraic topology, graph drawing, networked control, sensor networks and distributed optimization. This work received the Georgia Tech Sigma Xi Best doctoral dissertation award in 2006.