tributed Artificial Intelligence General Terms Algorithms, Experimentation

This paper considers the problem of performing decentralised co-ordination of low-power embedded devices (as is required within many environmental sensing and surveillance applications). Specif-ically, we address the generic problem of maximising social wel-fare within a group of interacting agents. We propose a novel representation of the problem, as a cyclic bipartite factor graph, composed of variable and function nodes (representing the agents’ states and utilities respectively). We show that such representation allows us to use an extension of the max-sum algorithm to generate approximate solutions to this global optimisation problem through local decentralised message passing. We empirically evaluate this approach on a canonical coordination problem (graph colouring), and benchmark it against state of the art approximate and complete algorithms (DSA and DPOP). We show that our approach is robust to lossy communication, that it generates solutions closer to those of DPOP than DSA is able to, and that it does so with a commu-nication cost (in terms of total messages size) that scales very well with the number of agents in the system (compared to the exponen-tial increase of DPOP). Finally, we describe a hardware implemen-tation of our algorithm operating on low-power Chipcon CC2431 System-on-Chip sensor nodes