Decentralised coordination of low-power embedded devices using the max-sum algorithm

By Alessandro Farinelli, Alex Rogers, Adrian Petcu, Nicholas R. Jennings. Adaptive Agents and Multi-Agent Systems, 2008

419 citations recorded by the source corpus.

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). 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.

View Paper: https://www.semanticscholar.org/paper/3f6b96090b5bde35290bdaf8fb562bb92ac8ee71

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games (2011, background): “ing algorithm described further in Sec. 3.4.2, can be applied to the interaction graph (Kok and Vlassis, 2005, 2006). In practice, MAX-PLUS is often much faster than NDP (Kok and Vlassis, 2005, 2006; Farinelli et al., 2008; Kim et al., 2010). However, when more than two agents participate in the sam”
Applying max-sum to teams of mobile sensing agents (2018, methodology): “The Max-Sum algorithm (Farinelli et al., 2008) is a Generalized Distributive Law (GDL) algorithm that operates on a factor graph: a bipartite graph where the nodes represent variables and constraint functions (Farinelli et al.”
Scalable Planning and Learning for Multiagent POMDPs (2014, methodology): “max~a ∑ eQe(~ae) can be performed efficiently via variable elimination (VE) (Guestrin, Koller, and Parr 2001), or maxsum (Kok and Vlassis 2006; Farinelli et al. 2008).”
Bounded approximate decentralised coordination via the max-sum algorithm (2009, background): “which each function depends (and this is typically much less than the total number of variables) [8].”