Decentralised Coordination of Low-Power Embedded Devices Using the Max-Sum Algorithm
Author(s)
Farinelli, Alessandro
Rogers, Alex
Petcu, Adrian
Jennings, NR
Type
Conference Paper
Abstract
This paper considers the problem of performing decentralised coordination of low-power embedded devices (as is required within many environmental sensing and surveillance applications). Specifically, we address the generic problem of maximising social welfare 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 communication cost (in terms of total messages size) that scales very well with the number of agents in the system (compared to the exponential increase of DPOP). Finally, we describe a hardware implementation of our algorithm operating on low-power Chipcon CC2431 System-on-Chip sensor nodes.
Date Issued
2008-05
Citation
2008, pp.639-646
Start Page
639
End Page
646
Identifier
http://eprints.soton.ac.uk/265159/
Source
Seventh International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-08)
Notes
Event Dates: 12-16 May 2008
Publication Status
Unpublished
OA Location
http://eprints.soton.ac.uk/265159/