On the structural complexity of multi-agent robot formations

Abstract

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 show how the information flows depends on different protocols and that the broadcast protocol corresponds to the worst-case complexity for a given formation.