research-article

Bounded decentralised coordination over multiple objectives

Authors:

Francesco M. Delle Fave,

Ruben Stranders,

Nicholas R. JenningsAuthors Info & Claims

AAMAS '11: The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 1

Pages 371 - 378

Published: 02 May 2011 Publication History

Abstract

We propose the bounded multi-objective max-sum algorithm (B-MOMS), the first decentralised coordination algorithm for multi-objective optimisation problems. B-MOMS extends the max-sum message-passing algorithm for decentralised coordination to compute bounded approximate solutions to multi-objective decentralised constraint optimisation problems (MO-DCOPs). Specifically, we prove the optimality of B-MOMS in acyclic constraint graphs, and derive problem dependent bounds on its approximation ratio when these graphs contain cycles. Furthermore, we empirically evaluate its performance on a multi-objective extension of the canonical graph colouring problem. In so doing, we demonstrate that, for the settings we consider, the approximation ratio never exceeds 2, and is typically less than 1.5 for less-constrained graphs. Moreover, the runtime required by B-MOMS on the problem instances we considered never exceeds 30 minutes, even for maximally constrained graphs with 100 agents. Thus, B-MOMS brings the problem of multi-objective optimisation well within the boundaries of the limited capabilities of embedded agents.

References

[1]

S. M. Aji and R. J. McEliece. The Generalized Distributive Law. IEEE Transactions on Information Theory, 46(2):325--343, 2000.

Digital Library

[2]

E. Bowring, M. Tambe, and M. Yokoo. Multiply-constrained distributed constraint optimization. In Proc. of the 5th Int. Conf. on Autonomous Agents and Multiagent Systems, pages 1413--1420, 2006.

Digital Library

[3]

A. Farinelli, A. Rogers, and N. R. Jennings. Bounded approximate decentralised coordination using the max-sum algorithm. In IJCAI-09 Workshop on Distributed Constraint Reasoning, pages 46--59, 2009.

[4]

A. Farinelli, A. Rogers, A. Petcu, and N. R. Jennings. Decentralised coordination of low-power embedded devices using the max sum algorithm. In Proc. of the 7th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pages 639--646, 2008.

Digital Library

[5]

S. Fitzpatrick and L. Meertens. Distributed coordination through anarchic optimization. In Victor Lesser, Charles L. Ortiz, Jr., and Milind Tambe, editors, Distributed Sensor Networks, chapter 11, pages 257--295. Kluwer Academic Publishers, 2003.

[6]

R. G. Gallager, P. A. Humblet, and P. M. Spira. A distributed algorithm for minimum-weight spanning trees. In ACM Transactions on Programming Languages and Systems, volume 5, pages 66--77, 1983.

Digital Library

[7]

N. R. Jennings. An agent-based approach for building complex software systems. Communications of the ACM, 44(4):35--41, 2001.

Digital Library

[8]

A. Kumar, B. Faltings, and A. Petcu. Distributed constraint optimisation with structured resource constraints. In Proc. of the 8th Int. Conf. on Autonomous Agents and Multi-Agents Systems, pages 923--930, 2009.

Digital Library

[9]

V. Lesser, C. L. Ortiz, and M. Tambe. Distributed Sensor Networks, A Multiagent Perspective. Kluwer Academic Publishers, 2003.

Digital Library

[10]

R. J. Maheswaran, J. Pearce, and M. Tambe. A family of graphical-game-based algorithms for distributed constraint optimization problems. In Coordination of Large-Scale Multiagent Systems, pages 127--146. Springer-Verlag, Heidelberg Germany, 2005.

[11]

R. Marinescu. Exploiting problem decomposition in multi-objective constraint optimization. In Proc. of the 15th Int. Conf. on Principles and Practice of Constraint Programming, pages 592--607. 2009.

Digital Library

[12]

R. T. Marler and J. S. Arora. Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization, 26:369--395, 2004.

[13]

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.

Digital Library

[14]

A. Mouaddib, M. Boussard, and M. Bouzid. Towards a formal framework for multi-objective multi-agent planning. In Proc. of the 6th Int. Conf. on Autonomous Agents and Multiagent Systems, pages 801--808, 2007.

Digital Library

[15]

A. Petcu and B. Faltings. DPOP: A scalable method for multiagent constraint optimization. Proc. of the 19th Int. Joint Conf. on Artificial Intelligence, pages 266--271, 2005.

Digital Library

[16]

E. Rollón. Multi-Objective Optimization in Graphical Models. PhD thesis, Universitat Politecnicá de Catalunya, 2008.

[17]

A. Savikumar and C. Keng-Yan Tan. UAV swarm coordination using cooperative control for establishing a wireless communications backbone. In Proc. of the 9th Int. Conf. on Autonomous Agents and Multiagent Systems, pages 1157--1164, 2010.

Digital Library

[18]

D. A. Van Veldhuizen and G. B. Lamont. Multi-objective evolutionary algorithm research: A history and analysis. Technical report, Dept. Elec Comp. Eng. Graduate School of Eng., 1998.

Cited By

Clement MOkimoto TInoue KAndre EKoenig SDastani MSukthankar G(2018)Multi-Objective Distributed Pseudo-Tree OptimizationProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3238018(1903-1905)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3238018
Fioretto FYeoh W(2018)AI buzzwords explainedAI Matters10.1145/3175502.31755063:4(8-13)Online publication date: 16-Feb-2018
https://dl.acm.org/doi/10.1145/3175502.3175506
Amigoni FCastelletti AGiuliani MWeiss GYolum PBordini RElkind E(2015)Modeling the Management of Water Resources Systems Using Multi-Objective DCOPsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773258(821-829)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773258
Show More Cited By

Index Terms

Bounded decentralised coordination over multiple objectives
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

Handling multiple objectives with biogeography-based optimization

Biogeography-based optimization (BBO) is a new evolutionary optimization method inspired by biogeography. In this paper, BBO is extended to a multi-objective optimization, and a biogeography-based multi-objective optimization (BBMO) is introduced, which ...
Timed Games with Bounded Window Parity Objectives
Formal Modeling and Analysis of Timed Systems
Abstract
The window mechanism, introduced by Chatterjee et al. [19] for mean-payoff and total-payoff objectives in two-player turn-based games on graphs, refines long-term objectives with time bounds. This mechanism has proven useful in a variety of ...
Genetic algorithm for the personnel assignment problem with multiple objectives

The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

AAMAS '11: The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 1

May 2011

444 pages

ISBN:0982657153

General Chairs:
Liz Sonenberg
The University of Melbourne, Australia
,
Peter Stone
The University of Texas at Austin
,
Program Chairs:
Kagan Tumer
Oregon State University
,
Pinar Yolum
Bogazici University, Turkey

Sponsors

IFAAMAS

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 02 May 2011

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS'11

Sponsor:

AAMAS'11: The Tenth International Conference on Autonomous Agents and Multiagent Systems

May 2 - 6, 2011

Taipei, Taiwan

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
94
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Clement MOkimoto TInoue KAndre EKoenig SDastani MSukthankar G(2018)Multi-Objective Distributed Pseudo-Tree OptimizationProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3238018(1903-1905)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3238018
Fioretto FYeoh W(2018)AI buzzwords explainedAI Matters10.1145/3175502.31755063:4(8-13)Online publication date: 16-Feb-2018
https://dl.acm.org/doi/10.1145/3175502.3175506
Amigoni FCastelletti AGiuliani MWeiss GYolum PBordini RElkind E(2015)Modeling the Management of Water Resources Systems Using Multi-Objective DCOPsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773258(821-829)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773258
Okimoto TSchwind NClement MInoue KBazzan AHuhns MLomuscio AScerri P(2014)Lp-Norm based algorithm for multi-objective distributed constraint optimizationProceedings of the 2014 international conference on Autonomous agents and multi-agent systems10.5555/2615731.2617506(1427-1428)Online publication date: 5-May-2014
https://dl.acm.org/doi/10.5555/2615731.2617506
Roijers DWhiteson SOliehoek FBazzan AHuhns MLomuscio AScerri P(2014)Linear support for multi-objective coordination graphsProceedings of the 2014 international conference on Autonomous agents and multi-agent systems10.5555/2615731.2617454(1297-1304)Online publication date: 5-May-2014
https://dl.acm.org/doi/10.5555/2615731.2617454
Roijers DWhiteson SOliehoek FGini MShehory OIto TJonker C(2013)Multi-objective variable elimination for collaborative graphical gamesProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485146(1209-1210)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2485146
Okimoto TClement MInoue K(2013)AOF-Based Algorithm for Dynamic Multi-Objective Distributed Constraint OptimizationProceedings of the 7th International Workshop on Multi-disciplinary Trends in Artificial Intelligence - Volume 827110.1007/978-3-642-44949-9_17(175-186)Online publication date: 9-Dec-2013
https://dl.acm.org/doi/10.1007/978-3-642-44949-9_17
Okimoto TJoe YIwasaki AMatsui THirayama KYokoo M(2012)Interactive Algorithm for Multi-Objective Constraint OptimizationProceedings of the 18th International Conference on Principles and Practice of Constraint Programming - Volume 751410.5555/2969951.2969997(561-576)Online publication date: 8-Oct-2012
https://dl.acm.org/doi/10.5555/2969951.2969997
Nguyen DYeoh WLau Hvan der Hoek WPadgham LConitzer VWinikoff M(2012)Stochastic dominance in stochastic DCOPs for risk-sensitive applicationsProceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/2343576.2343613(257-264)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.5555/2343576.2343613
Matsui TMatsuo H(2012)Considering Equality on Distributed Constraint Optimization Problem for Resource Supply NetworkProceedings of the The 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology - Volume 0210.1109/WI-IAT.2012.22(25-32)Online publication date: 4-Dec-2012
https://dl.acm.org/doi/10.1109/WI-IAT.2012.22

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents