{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T20:43:54Z","timestamp":1715028234171},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Hum-Cent Intell Syst"],"abstract":"Abstract<\/jats:title>Coordinating multiple agents to optimize an objective has several real-world applications. In areas such as disaster rescue, environment monitoring and the like, mobile agents may be deployed to work as a team to achieve a joint goal. Recently, multi-agent problems involving mobile sensor teams have been formalized in the literature as DCOP_MSTs. Under this class of problems, DCOP algorithms are applied to enable agents to coordinate the assignment of their physical locations as they jointly optimize the team objective. In DCOP_MSTs, the environment is dynamic, and agents may leave or join the environment at random times. As a result, a predefined interaction topology or graph may not be useful over the problem horizon. Therefore, there is a need to study methods that could facilitate agent-to-agent interaction in such open and dynamic environments. Existing methods require reconstructing the entire graph upon detecting changes in the environment or assume a predefined interaction graph. In this study, we propose a dynamic multi-agent hierarchy construction algorithm that can be used by DCOP_MST algorithms that require a pseudo-tree for execution. We evaluate our proposed method in a simulated target detection case study to show the effectiveness of the proposed approach in large agent teams.<\/jats:p>","DOI":"10.1007\/s44230-023-00044-0","type":"journal-article","created":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T03:28:21Z","timestamp":1694489301000},"page":"473-486","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Distributed Multi-Agent Hierarchy Construction for Dynamic DCOPs in Mobile Sensor Teams"],"prefix":"10.1007","volume":"3","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-5050-8916","authenticated-orcid":false,"given":"Brighter","family":"Agyemang","sequence":"first","affiliation":[]},{"given":"Fenghui","family":"Ren","sequence":"additional","affiliation":[]},{"given":"Jun","family":"Yan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,12]]},"reference":[{"key":"44_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.engappai.2018.02.017","volume":"71","author":"H Yedidsion","year":"2018","unstructured":"Yedidsion H, Zivan R, Farinelli A. Applying max-sum to teams of mobile sensing agents. Eng Appl Artif Intell. 2018;71:87\u201399. https:\/\/doi.org\/10.1016\/j.engappai.2018.02.017.","journal-title":"Eng Appl Artif Intell"},{"key":"44_CR2","doi-asserted-by":"publisher","unstructured":"Rybski PE, Stoeter SA, Gini M, Hougen DF, Papanikolopoulos N. Effects of limited bandwidth communications channels on the control of multiple robots. In: Proceedings 2001 IEEE\/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180), 2001;1:369\u20133741. https:\/\/doi.org\/10.1109\/IROS.2001.973385","DOI":"10.1109\/IROS.2001.973385"},{"key":"44_CR3","doi-asserted-by":"publisher","unstructured":"Padhy P, Dash RK, Martinez K, Jennings NR. A utility-based sensing and communication model for a glacial sensor network. In: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems. AAMAS \u201906, pp. 1353\u20131360. Association for Computing Machinery New York, NY, USA 2006. https:\/\/doi.org\/10.1145\/1160633.1160885 .","DOI":"10.1145\/1160633.1160885"},{"key":"44_CR4","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-3-642-40643-0_21","volume-title":"Advances in artificial intelligence","author":"M Pujol-Gonzalez","year":"2013","unstructured":"Pujol-Gonzalez M, Cerquides J, Meseguer P, Rodr\u00edguez-Aguilar JA, Tambe M. Engineering the decentralized coordination of uavs with limited communication range. In: Bielza C, Salmer\u00f3n A, Alonso-Betanzos A, Hidalgo JI, Mart\u00ednez L, Troncoso A, Corchado E, Corchado JM, editors. Advances in artificial intelligence. Berlin: Springer; 2013. p. 199\u2013208."},{"key":"44_CR5","unstructured":"Junges R, Bazzan ALC. Evaluating the performance of dcop algorithms in a real world, dynamic problem. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2. AAMAS \u201908, pp. 599\u2013606. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC. 2008."},{"key":"44_CR6","doi-asserted-by":"publisher","unstructured":"Lezama F, Munoz de Cote E, Farinelli A, Soares J, Pinto T, Vale Z. Distributed constrained optimization towards effective agent-based microgrid energy resource management. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11804 LNAI(July 2017), 2019;438\u2013449. https:\/\/doi.org\/10.1007\/978-3-030-30241-2_37","DOI":"10.1007\/978-3-030-30241-2_37"},{"issue":"3","key":"44_CR7","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s10458-014-9255-3","volume":"29","author":"R Zivan","year":"2015","unstructured":"Zivan R, Yedidsion H, Okamoto S, Glinton R, Sycara K. Distributed constraint optimization for teams of mobile sensing agents. Auton Agent Multi-Agent Syst. 2015;29(3):495\u2013536. https:\/\/doi.org\/10.1007\/s10458-014-9255-3.","journal-title":"Auton Agent Multi-Agent Syst"},{"key":"44_CR8","doi-asserted-by":"publisher","unstructured":"Fioretto F, Pontelli E, Yeoh W. Distributed constraint optimization problems and applications: a survey. J Artif Intell Res 2018;61:623\u2013698 https:\/\/doi.org\/10.1613\/jair.5565arXiv:1602.06347","DOI":"10.1613\/jair.5565"},{"key":"44_CR9","unstructured":"Federal Aviation Agency: UTM Concept of Operations Version 2.0. Technical report 2020. https:\/\/www.faa.gov\/sites\/faa.gov\/files\/2022-08\/UTM_ConOps_v2.pdf"},{"key":"44_CR10","doi-asserted-by":"publisher","first-page":"9","DOI":"10.3390\/app11093995","volume":"11","author":"C Capit\u00e1n","year":"2021","unstructured":"Capit\u00e1n C, P\u00e9rez-Le\u00f3n H, Capit\u00e1n J, Casta\u00f1o \u00c1, Ollero A. Unmanned aerial traffic management system architecture for U-space in-flight services. Appl Sci. 2021;11:9. https:\/\/doi.org\/10.3390\/app11093995.","journal-title":"Appl Sci"},{"key":"44_CR11","first-page":"1065","volume":"9","author":"G Picard","year":"2022","unstructured":"Picard G. Trajectory coordination based on distributed con-straint optimization techniques in unmanned air traffic management. Ifaamas. 2022;9:1065\u201373.","journal-title":"Ifaamas"},{"key":"44_CR12","first-page":"449","volume":"1","author":"A Petcu","year":"2005","unstructured":"Petcu A, Faltings B. Superstabilizing, fault-containing distributed combinatorial optimization. Proc Natl Conf Artif Intell. 2005;1:449\u201354.","journal-title":"Proc Natl Conf Artif Intell"},{"key":"44_CR13","doi-asserted-by":"publisher","unstructured":"Petcu A, Faltings B. Optimal solution stability in dynamic, distributed constraint optimization. Proceedings of the IEEE\/WIC\/ACM International Conference on Intelligent Agent Technology, IAT. 2007;2007:321\u20137. https:\/\/doi.org\/10.1109\/IAT.2007.11.","DOI":"10.1109\/IAT.2007.11"},{"key":"44_CR14","unstructured":"Sultanik EA, Lass RN, Regli WC. Dynamic configuration of agent organizations. IJCAI International Joint Conference on Artificial Intelligence, 2009;305\u2013311"},{"key":"44_CR15","unstructured":"Youssef Hamadi Christian Bessiere JQ. Backtracking in distributed constraint networks. ECAI, 1998;219\u2013223"},{"issue":"6","key":"44_CR16","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(94)90103-1","volume":"49","author":"Z Collin","year":"1994","unstructured":"Collin Z, Dolev S. Self-stabilizing depth-first search. Inf Process Lett. 1994;49(6):297\u2013301. https:\/\/doi.org\/10.1016\/0020-0190(94)90103-1.","journal-title":"Inf Process Lett"},{"key":"44_CR17","doi-asserted-by":"publisher","unstructured":"Yeoh W, Varakantham P, Sun X, Koenig S. Incremental DCOP search algorithms for solving dynamic DCOP problems. Proceedings - 2015 IEEE\/WIC\/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, WI-IAT 2015 2015;2:257\u2013264. https:\/\/doi.org\/10.1109\/WI-IAT.2015.114","DOI":"10.1109\/WI-IAT.2015.114"},{"key":"44_CR18","unstructured":"Yeoh W, Varakantham P, Sun X, Koenig S. Incremental DCOP Search Algorithms for Solving Dynamic DCOPs ( Extended Abstract ). Artificial Intelligence (Aamas), 2011;1069\u20131070"},{"key":"44_CR19","doi-asserted-by":"publisher","unstructured":"Agyemang B, Ren F, Yan J. Distributed interaction graph construction for dynamic DCOPs in cooperative multi-agent systems. arXiv 2022. https:\/\/doi.org\/10.48550\/ARXIV.2212.03461 . https:\/\/arxiv.org\/abs\/2212.03461","DOI":"10.48550\/ARXIV.2212.03461"},{"issue":"1\u20132","key":"44_CR20","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.artint.2004.09.003","volume":"161","author":"PJ Modi","year":"2005","unstructured":"Modi PJ, Shen WM, Tambe M, Yokoo M. Adopt: Asynchronous distributed constraint optimization with quality guarantees. Artif Intell. 2005;161(1\u20132):149\u201380. https:\/\/doi.org\/10.1016\/j.artint.2004.09.003.","journal-title":"Artif Intell"},{"key":"44_CR21","unstructured":"Hoang K.D, Fioretto F, Hou P, Yokoo M, Yeoh W, Zivan R. Proactive dynamic distributed constraint optimization. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 597\u2013605 (2016)"},{"key":"44_CR22","unstructured":"Hoang KD, Hou P, Fioretto F, Yeoh W, Zivan R, Yokoo M. Infinite-horizon proactive dynamic DCOPs. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS. 2017;1:212\u201320."},{"key":"44_CR23","doi-asserted-by":"publisher","unstructured":"Chechetka A, Sycara K. A decentralized variable ordering method for distributed constraint optimization. Proceedings of the International Conference on Autonomous Agents, 2005;1385\u20131386. https:\/\/doi.org\/10.1145\/1082473.1082746","DOI":"10.1145\/1082473.1082746"},{"key":"44_CR24","doi-asserted-by":"publisher","first-page":"507","DOI":"10.4018\/978-1-59904-849-9.ch077","volume":"2","author":"MC Silaghi","year":"2011","unstructured":"Silaghi MC, Yokoo M. Distributed constraint reasoning. Encycl Artif Intell. 2011;2:507\u201313. https:\/\/doi.org\/10.4018\/978-1-59904-849-9.ch077.","journal-title":"Encycl Artif Intell"},{"key":"44_CR25","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/11564751_6","volume-title":"Principles and practice of constraint programming - CP 2005","author":"R Zivan","year":"2005","unstructured":"Zivan R, Meisels A. Dynamic ordering for asynchronous backtracking on DisCSPs. In: Beek P, editor. Principles and practice of constraint programming - CP 2005. Berlin: Springer; 2005. p. 32\u201346."},{"key":"44_CR26","unstructured":"Stranders R, Farinelli A, Rogers A, Jennings NR. Decentralised coordination of mobile sensors using the max-sum algorithm. IJCAI International Joint Conference on Artificial Intelligence, 299\u2013304 (2009)"},{"key":"44_CR27","doi-asserted-by":"publisher","unstructured":"Darko J, Park H. Proactive distributed constraint optimization of heterogeneous incident vehicle teams. CoRR abs\/2207.11132 2022. https:\/\/doi.org\/10.48550\/arXiv.2207.11132arXiv:2207.11132","DOI":"10.48550\/arXiv.2207.11132"},{"key":"44_CR28","unstructured":"Sarker A, Choudhury M, Khan MM. A local search based approach to solve continuous DCOPs. Aamas 21, 2021;1127\u20131135."},{"key":"44_CR29","doi-asserted-by":"publisher","unstructured":"Van Leeuwen CJ, Pawe\u0142czak P. CoCoA: A non-iterative approach to a local search (A)DCOP Solver. 31st AAAI Conference on Artificial Intelligence, AAAI 2017, 3944\u20133950 (2017) https:\/\/doi.org\/10.1609\/aaai.v31i1.11125","DOI":"10.1609\/aaai.v31i1.11125"},{"key":"44_CR30","unstructured":"Hoang K.D, Yeoh W, Yokoo M, Rabinovich Z. New algorithms for continuous distributed constraint optimization problems. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020-May(Aamas), 2020;502\u2013510."},{"key":"44_CR31","doi-asserted-by":"publisher","first-page":"11","DOI":"10.3390\/s21113807","volume":"21","author":"J Barambones","year":"2021","unstructured":"Barambones J, Imbert R, Moral C. Applicability of multi-agent systems and constrained reasoning for sensor-based distributed scenarios: a systematic mapping study on dynamic DCOPs. Sensors. 2021;21:11. https:\/\/doi.org\/10.3390\/s21113807.","journal-title":"Sensors"},{"key":"44_CR32","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1613\/jair.1.13499","volume":"74","author":"KD Hoang","year":"2022","unstructured":"Hoang KD, Fioretto F, Hou P, Yeoh W, Yokoo M, Zivan R. Proactive dynamic distributed constraint optimization problems. J Artif Intell Res. 2022;74:179\u2013225. https:\/\/doi.org\/10.1613\/jair.1.13499.","journal-title":"J Artif Intell Res"}],"container-title":["Human-Centric Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44230-023-00044-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s44230-023-00044-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44230-023-00044-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T15:08:22Z","timestamp":1703171302000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s44230-023-00044-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,12]]},"references-count":32,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["44"],"URL":"https:\/\/doi.org\/10.1007\/s44230-023-00044-0","relation":{},"ISSN":["2667-1336"],"issn-type":[{"value":"2667-1336","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,12]]},"assertion":[{"value":"8 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The authors hereby consent to publication of the work.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}