Decentralised Coordination of Robotic Agents Using the Max-Sum Algorithm

Decentralised coordination of robotic agents is required within many emerging applications (e.g., rescue and emergency operations, environmental monitoring, etc.). In this talk we discuss the main issues related to the problem of decentralised coordination when physical devices are involved.

We focus on a novel recent technique for decentralised coordination based on the Max-Sum algorithm. We propose a novel representation of the coordination problem, as a cyclic bipartite factor graph, and show that such representation allows us to use an extension of the Max-Sum algorithm to generate approximate solutions through local decentralised message passing.

We present an empirical evaluation of the Max-Sum approach on a canonical coordination problem (graph colouring), comparing it against state of the art approximate and complete algorithms. We describe a hardware deployment of the Max-Sum operating on low-power Chipcon CC2431 System-on-Chip sensor nodes. Finally, we show the application of the Max-Sum algorithm for coordinating the sense/sleep schedules of energy constrained sensors, involved in a wide area surveillance application.