On the Structural Complexity of Multi-Agent Robot Formations.
Egerstedt, Magnus B.
MetadataShow full item record
We present a complexity measure for studying the structural complexity of multi-agent robot formations. We base this measure on the total information flow in the system, which is due to sensory perception and communication among agents. We show that from an information theoretic point of view, perception and communication are fundamentally the same. We describe the information flows for different protocols and show that the broadcast protocol corresponds to the worst case complexity for a given formation. This upper bound is found to be remarkably similar to a complexity measure of graphs defined in the context of molecular chemistry.