skip to main content
10.5555/1402298.1402313acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

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

Published: 12 May 2008 Publication History

Abstract

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.

References

[1]
S. Fitzpatrick and L. Meetrens. Distributed Sensor Networks A multiagent perspective, chapter Distributed Coordination through Anarchic Optimization, pages 257--293. Kluwer Academic, 2003.
[2]
D. MacKay. Good error-correcting codes based on very sparse matrices. IEEE Transactions on Information Theory, 45(2):399--431, 1999.
[3]
D. J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
[4]
R. Mailler and V. Lesser. Solving distributed constraint optimization problems using cooperative mediation. In Proceedings of 3rd International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS'04), pages 438--445, 2004.
[5]
A. Makarenko and H. Durrant-Whyte. Decentralized data fusion and control algorithms in active sensor networks. In Proceedings of 7th International Conference on Information Fusion (Fusion'04), pages 479--486, 2004.
[6]
M. Mezard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812--815, 2002.
[7]
P. Modi, S. Ali, W. Shen, and M. Tambe. Distributed constraint reasoning under unreliable communication. Proceedings of Distributed Constraint Reasoning Workshop at 2nd International Joint Conference on Autonomous Agents and MultiAgent Systems, 2003.
[8]
P. J. Modi, W. Shen, M. Tambe, and M. Yokoo. ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence Journal, (161):149--180, 2005.
[9]
K. P. Murphy, Y. Weiss, and M. I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI'99), pages 467--475, 1999.
[10]
P. Padhy, R. K. Dash, K. Martinez, and N. R. Jennings. A utility-based sensing and communication model for a glacial sensor network. In Proceeding of 5th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'06), pages 1353--1360, 2006.
[11]
A. Petcu and B. Faltings. DPOP: A scalable method for multiagent constraint optimization. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, (IJCAI'05), pages 266--271, 2005.
[12]
P. Rybski, S. Stoeter, M. Gini, D. Hougen, and N. Papanikolopoulos. Effects of limited bandwidth communications channels on the control of multiple robots. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 369--374, 2001.
[13]
Y. Weiss and W. Freeman. Correctness of belief propagation in gaussian graphical models of arbitrary topology. Neural Computation, 13(10):2173--2200, 2001.
[14]
W. Y. and F. W. T. On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory, 47(2):723--735, 2001.
[15]
W. Zhang, Z. Xing, G. Wang, and L. Wittenburg. An analysis and application of distributed constraint satisfaction and optimization algorithms in sensor networks. In Proceedings of the 2nd Int. Joint Conference on Autonomous Agent and Multiagent Systems (AAMAS'03), pages 185--192, 2003.

Cited By

View all
  • (2022)Deep attentive belief propagationProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602114(25436-25449)Online publication date: 28-Nov-2022
  • (2022)Beyond Uninformed Search: Improving Branch-and-bound Based Acceleration Algorithms for Belief Propagation via Heuristic StrategiesProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3536045(1592-1594)Online publication date: 9-May-2022
  • (2021)A Study on Applying Decentralized Constraint Optimization to Mobile Sensor Teams with Range SensorsProceedings of the 5th International Conference on Advances in Artificial Intelligence10.1145/3505711.3505737(183-188)Online publication date: 20-Nov-2021
  • Show More Cited By

Index Terms

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

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2
    May 2008
    673 pages
    ISBN:9780981738116

    Sponsors

    In-Cooperation

    Publisher

    International Foundation for Autonomous Agents and Multiagent Systems

    Richland, SC

    Publication History

    Published: 12 May 2008

    Check for updates

    Author Tags

    1. DCOP
    2. coordination
    3. sensor networks
    4. sum-product

    Qualifiers

    • Research-article

    Conference

    AAMAS08
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)13
    • Downloads (Last 6 weeks)9
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)Deep attentive belief propagationProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602114(25436-25449)Online publication date: 28-Nov-2022
    • (2022)Beyond Uninformed Search: Improving Branch-and-bound Based Acceleration Algorithms for Belief Propagation via Heuristic StrategiesProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3536045(1592-1594)Online publication date: 9-May-2022
    • (2021)A Study on Applying Decentralized Constraint Optimization to Mobile Sensor Teams with Range SensorsProceedings of the 5th International Conference on Advances in Artificial Intelligence10.1145/3505711.3505737(183-188)Online publication date: 20-Nov-2021
    • (2020)Distributed Wireless Network Optimization With Stochastic Local Search2020 IEEE 17th Annual Consumer Communications & Networking Conference (CCNC)10.1109/CCNC46108.2020.9045189(1-6)Online publication date: 10-Jan-2020
    • (2019)A privacy preserving collusion secure DCOP algorithmProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367471.3367707(4774-4780)Online publication date: 10-Aug-2019
    • (2019)Coordinated Multiagent Reinforcement Learning for Teams of Mobile Sensing RobotsProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3332090(2297-2299)Online publication date: 8-May-2019
    • (2019)Installing Resilience in Distributed Constraint Optimization Operated by Physical Multi-Agent SystemsProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3332049(2177-2179)Online publication date: 8-May-2019
    • (2019)PT-ISABBProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331864(1506-1514)Online publication date: 8-May-2019
    • (2019)Graph Based Optimization for Multiagent CooperationProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331863(1497-1505)Online publication date: 8-May-2019
    • (2019)Distributed gibbsJournal of Artificial Intelligence Research10.1613/jair.1.1140064:1(705-748)Online publication date: 1-Jan-2019
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media