Article

Dynamic Continuous Distributed Constraint Optimization Problems

Authors:

William YeohAuthors Info & Claims

PRIMA 2022: Principles and Practice of Multi-Agent Systems: 24th International Conference, Valencia, Spain, November 16–18, 2022, Proceedings

Pages 475 - 491

https://doi.org/10.1007/978-3-031-21203-1_28

Published: 16 November 2022 Publication History

Abstract

The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool to model multi-agent coordination problems that are distributed by nature. While DCOPs assume that variables are discrete and the environment does not change over time, agents often interact in a more dynamic and complex environment. To address these limiting assumptions, researchers have proposed Dynamic DCOPs (D-DCOPs) to model how DCOPs dynamically change over time and Continuous DCOPs (C-DCOPs) to model DCOPs with continuous variables and constraints in functional form. However, these models address each limiting assumption of DCOPs in isolation, and it remains a challenge to model problems that both have continuous variables and are in dynamic environment. Therefore, in this paper, we propose Dynamic Continuous DCOPs (DC-DCOPs), a novel formulation that models both dynamic nature of the environment and continuous nature of the variables, which are inherent in many multi-agent problems. In addition, we introduce several greedy algorithms to solve DC-DCOPs and discuss their theoretical properties. Finally, we empirically evaluate the algorithms in random networks and in distributed sensor network application.

References

[1]

Bellifemine F, Bergenti F, Caire G, and Poggi A Bordini RH, Dastani M, Dix J, and El Fallah Seghrouchni A Jade — a java agent development framework Multi-Agent Programming 2005 Boston, MA Springer 125-147

[2]

Burke, D., Brown, K.: Efficiently handling complex local problems in distributed constraint optimisation. In: Proceedings of ECAI, pp. 701–702 (2006)

[3]

Choudhury, M., Mahmud, S., Khan, M.M.: A particle swarm based algorithm for functional distributed constraint optimization problems. In: Proceedings of AAAI (2020)

[4]

Deng, Y., An, B.: Speeding up incomplete GDL-based algorithms for multi-agent optimization with dense local utilities. In: Proceedings of IJCAI, pp. 31–38 (2020)

[5]

Fargier, H., Lang, J., Schiex, T.: Mixed constraint satisfaction: a framework for decision problems under incomplete knowledge. In: Proceedings of AAAI, pp. 175–180 (1996)

[6]

Farinelli, A., Rogers, A., Petcu, A., Jennings, N.: Decentralised coordination of low-power embedded devices using the max-sum algorithm. In: Proceedings of AAMAS, pp. 639–646 (2008)

[7]

Fioretto F, Pontelli E, and Yeoh W Distributed constraint optimization problems and applications: a survey J. Artif. Intell. Res. 2018 61 623-698

[8]

Fioretto, F., Yeoh, W., Pontelli, E.: Multi-variable agents decomposition for DCOPs. In: Proceedings of AAAI, pp. 2480–2486 (2016)

[9]

Fioretto, F., Yeoh, W., Pontelli, E.: A multiagent system approach to scheduling devices in smart homes. In: Proceedings of AAMAS, pp. 981–989 (2017)

[10]

Fioretto, F., Yeoh, W., Pontelli, E., Ma, Y., Ranade, S.: A DCOP approach to the economic dispatch with demand response. In: Proceedings of AAMAS, pp. 999–1007 (2017)

[11]

Fransman, J., Sijs, J., Dol, H., Theunissen, E., Schutter, B.D.: Bayesian-DPOP for continuous distributed constraint optimization problems. In: Proceedings of AAMAS, pp. 1961–1963 (2019)

[12]

Hoang KD, Fioretto F, Hou P, Yeoh W, Yokoo M, and Zivan R Proactive dynamic distributed constraint optimization problems J. Artif. Intell. Res. 2022 74 179-225

[13]

Hoang, K.D., Fioretto, F., Hou, P., Yokoo, M., Yeoh, W., Zivan, R.: Proactive dynamic distributed constraint optimization. In: Proceedings of AAMAS, pp. 597–605 (2016)

[14]

Hoang, K.D., Hou, P., Fioretto, F., Yeoh, W., Zivan, R., Yokoo, M.: Infinite-horizon proactive dynamic DCOPs. In: Proceedings of AAMAS, pp. 212–220 (2017)

[15]

Hoang, K.D., Yeoh, W., Yokoo, M., Rabinovich, Z.: New algorithms for continuous distributed constraint optimization problems. In: Proceedings of AAMAS, pp. 502–510 (2020)

[16]

Holland, A., O’Sullivan, B.: Weighted super solutions for constraint programs. In: Proceedings of AAAI, pp. 378–383 (2005)

[17]

Kim, Y., Krainin, M., Lesser, V.: Effective variants of the max-sum algorithm for radar coordination and scheduling. In: Proceedings of WI-IAT, pp. 357–364 (2011)

[18]

Kumar, A., Faltings, B., Petcu, A.: Distributed constraint optimization with structured resource constraints. In: Proceedings of AAMAS, pp. 923–930 (2009)

[19]

Lass, R., Sultanik, E., Regli, W.: Dynamic distributed constraint reasoning. In: Proceedings of AAAI, pp. 1466–1469 (2008)

[20]

Maheswaran, R., Tambe, M., Bowring, E., Pearce, J., Varakantham, P.: Taking DCOP to the real world: efficient complete solutions for distributed event scheduling. In: Proceedings of AAMAS, pp. 310–317 (2004)

[21]

Miller, S., Ramchurn, S., Rogers, A.: Optimal decentralised dispatch of embedded generation in the smart grid. In: Proceedings of AAMAS, pp. 281–288 (2012)

[22]

Modi P, Shen WM, Tambe M, and Yokoo M ADOPT: asynchronous distributed constraint optimization with quality guarantees Artif. Intell. 2005 161 1–2 149-180

[23]

Paulos, A., et al.: A framework for self-adaptive dispersal of computing services. In: IEEE Self-Adaptive and Self-Organizing Systems Workshops (2019)

[24]

Petcu, A., Faltings, B.: A scalable method for multiagent constraint optimization. In: Proceedings of IJCAI, pp. 1413–1420 (2005)

[25]

Petcu, A., Faltings, B.: Superstabilizing, fault-containing multiagent combinatorial optimization. In: Proceedings of AAAI, pp. 449–454 (2005)

[26]

Petcu, A., Faltings, B.: Optimal solution stability in dynamic, distributed constraint optimization. In: Proceedings of IAT, pp. 321–327 (2007)

[27]

Rust, P., Picard, G., Ramparany, F.: Using message-passing DCOP algorithms to solve energy-efficient smart environment configuration problems. In: Proceedings of IJCAI, pp. 468–474 (2016)

[28]

Sarker, A., Choudhury, M., Khan, M.M.: A local search based approach to solve Continuous DCOPs. In: Proceedings of AAMAS, pp. 1127–1135 (2021)

[29]

Stranders, R., Farinelli, A., Rogers, A., Jennings, N.: Decentralised coordination of continuously valued control parameters using the Max-Sum algorithm. In: Proceedings of AAMAS, pp. 601–608 (2009)

[30]

Sultanik, E., Lass, R., Regli, W.: DCOPolis: a framework for simulating and deploying distributed constraint reasoning algorithms. In: Proceedings of AAMAS, pp. 1667–1668 (2008)

[31]

Tarim SA, Manandhar S, and Walsh T Stochastic constraint programming: a scenario-based approach Constraints 2006 11 1 53-80

[32]

Voice, T., Stranders, R., Rogers, A., Jennings, N.: A hybrid continuous max-sum algorithm for decentralised coordination. In: Proceedings of ECAI, pp. 61–66 (2010)

[33]

Wallace, R., Freuder, E.: Stable solutions for dynamic constraint satisfaction problems. In: Proceedings of CP, pp. 447–461 (1998)

[34]

Walsh, T.: Stochastic constraint programming. In: Proceedings of ECAI, pp. 111–115 (2002)

[35]

Yeoh W, Felner A, and Koenig S BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm J. Artif. Intell. Res. 2010 38 85-133

[36]

Yeoh, W., Varakantham, P., Sun, X., Koenig, S.: Incremental DCOP search algorithms for solving dynamic DCOPs. In: Proceedings of IAT, pp. 257–264 (2015)

[37]

Yeoh W and Yokoo M Distributed problem solving AI Mag. 2012 33 3 53-65

[38]

Yokoo, M. (ed.): Distributed Constraint Satisfaction: Foundation of Cooperation in Multi-agent Systems. Springer, Cham (2001).

[39]

Zink, M., et al.: Meteorological command and control: an end-to-end architecture for a hazardous weather detection sensor network. In: Workshop on End-to-End, Sense-and-Respond Systems, Applications, and Services. USENIX Association (2005)

[40]

Zivan R, Yedidsion H, Okamoto S, Glinton R, and Sycara K Distributed constraint optimization for teams of mobile sensing agents J. Auton. Agents Multi-Agent Syst. 2015 29 3 495-536

Cited By

Pouvreau QGeorgé JBernon CMaignan S(2023)Optimization of Complex Systems in Photonics by Multi-agent Robotic ControlAdvances in Practical Applications of Agents, Multi-Agent Systems, and Cognitive Mimetics. The PAAMS Collection10.1007/978-3-031-37616-0_23(272-283)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-37616-0_23

Index Terms

Dynamic Continuous Distributed Constraint Optimization Problems
1. Mathematics of computing
  1. Mathematical analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

Dynamic Continuous Distributed Constraint Optimization Problems
Solving dynamic constraint optimization problems using ICHEA
ICONIP'12: Proceedings of the 19th international conference on Neural Information Processing - Volume Part III

Many real-world constrained problems have a set of predefined static constraints that can be solved by evolutionary algorithms (EAs) whereas some problems have dynamic constraints that may change over time or may be received by the problem solver at run ...
Incomplete Distributed Constraint Optimization Problems: Model, Algorithms, and Heuristics
Distributed Artificial Intelligence
Abstract
The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool to model cooperative multi-agent problems, especially when they are sparsely constrained with one another. A key assumption in this model is that all constraints ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

PRIMA 2022: Principles and Practice of Multi-Agent Systems: 24th International Conference, Valencia, Spain, November 16–18, 2022, Proceedings

Nov 2022

713 pages

ISBN:978-3-031-21202-4

DOI:10.1007/978-3-031-21203-1

Editors:
Reyhan Aydoğan
Özyeğin University, Istanbul, Turkey
,
Natalia Criado
Universitat Politècnica de València, Valencia, Spain
,
Jérôme Lang
Université Paris-Dauphine, Paris, France
,
Victor Sanchez-Anguix
Universitat Politècnica de València, Valencia, Spain
,
Marc Serramia
King's College London, London, UK

© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 16 November 2022

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pouvreau QGeorgé JBernon CMaignan S(2023)Optimization of Complex Systems in Photonics by Multi-agent Robotic ControlAdvances in Practical Applications of Agents, Multi-Agent Systems, and Cognitive Mimetics. The PAAMS Collection10.1007/978-3-031-37616-0_23(272-283)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-37616-0_23

View Options

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

Media

Figures

Other

Tables

View Table of Contents