Leximin Multiple Objective DCOPs on Factor Graphs for Preferences of Agents

• Autorzy: Matsui T. , Silaghi M. , Okimoto T. , Hirayama K. , Yokoo M. , Matsuo H.

Identyfikatory

DOI

10.3233/FI-2018-1642

• Języki publikacji: EN

Abstrakty

EN

Distributed Constraint Optimization Problem (DCOP) has been studied as a fundamental component of multiagent systems. With DCOPs, various applications on multiagent systems are formalized as constraint optimization problems where variables and functions are distributed among agents. Leximin AMODCOP has been proposed as a class of Multiple Objective DCOPs, where multiple objectives for individual agents are optimized based on the leximin operator. This problem also relates to Asymmetric DCOPs based on its the criteria of fairness among agents. Previous studies explore only Leximin AMODCOPs on constraint graphs limited to functions with unary or binary scopes. We address the Leximin AMODCOPs on factor graphs that directly represent n-ary functions. A dynamic programming method on factor graphs is investigated as an exact solution method. In addition, for relatively dense problems, we also investigate several approximate/inexact algorithms.

Słowa kluczowe

EN

distributed constraint optimization; asymmetric; multiple objectives; leximin; egalitarian

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 158, nr 1/3
• Strony: 63--91
• Opis fizyczny: Bibliogr. 28 poz., rys., tab., wykr.

Twórcy

autor

Matsui T.

• Nagoya Institute of Technology, Gokiso-cho Showa-ku Nagoya 466-8555, Japan

autor

Silaghi M.

• Florida Institute of Technology, Melbourne FL 32901, United States of America

autor

Okimoto T.

• Kobe University, 5-1-1 Fukaeminami-machi Higashinada-ku Kobe, 658-0022, Japan

autor

Hirayama K.

• Kobe University, 5-1-1 Fukaeminami-machi Higashinada-ku Kobe, 658-0022, Japan

autor

Yokoo M.

• Kyushu University, 744 Motooka Nishi-ku Fukuoka 819-0395, Japan

autor

Matsuo H.

• Nagoya Institute of Technology, Gokiso-cho Showa-ku Nagoya 466-8555, Japan

Bibliografia

• [1] Modi PJ, Shen W, Tambe M, Yokoo M. Adopt: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 2005;161(1-2):149-180. https://doi.org/10.1016/j.artint.2004.09.003.
• [2] Petcu A, Faltings B. A Scalable Method for Multiagent Constraint Optimization. In: 19th International Joint Conference on Artificial Intelligence. 2005 pp. 266-271. http://dl.acm.org/citation.cfm?id=1642293.1642336.
• [3] Farinelli A, Rogers A, Petcu A, Jennings NR. Decentralised coordination of low-power embedded devices using the max-sum algorithm. In: 7th International Joint Conference on Autonomous Agents and Multiagent Systems. 2008 pp. 639-646. ISBN: 978-0-9817381-1-6.
• [4] Zhang W, Wang G, Xing Z, Wittenburg L. Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks. Artificial Intelligence, 2005;161(1-2):55-87. https://doi.org/10.1016/j.artint.2004.10.004.
• [5] Miller S, Ramchurn SD, Rogers A. Optimal decentralised dispatch of embedded generation in the smart grid. In: 11th International Conference on Autonomous Agents and Multiagent Systems, volume 1. 2012 pp. 281-288. ISBN: 0-9817381-1-7, 978-0-9817381-1-6.
• [6] Ramchurn SD, Farinelli A, Macarthur KS, Jennings NR. Decentralized Coordination in RoboCup Rescue. 2010;53(9):1447-1461. https://doi.org/10.1093/comjnl/bxq022.
• [7] Delle Fave FM, Stranders R, Rogers A, Jennings NR. Bounded decentralised coordination over multiple objectives. In: 10th International Conference on Autonomous Agents and Multiagent Systems, volume 1. 2011 pp. 371-378. ISBN: 0-9826571-5-3, 978-0-9826571-5-7.
• [8] Matsui T, Silaghi M, Hirayama K, Yokoo M, Matsuo H. Distributed Search Method with Bounded Cost Vectors on Multiple Objective DCOPs. In: Principles and Practice of Multi-Agent Systems - 15th International Conference. 2012 pp. 137-152. https://doi.org/10.1007/978-3-642-32729-2_10.
• [9] Grinshpoun T, Grubshtein A, Zivan R, Netzer A, Meisels A. Asymmetric Distributed Constraint Optimization Problems. Journal of Artificial Intelligence Research, 2013;47(1):613-647. http://dl.acm.org/citation.cfm?id=2566972.2566988.
• [10] Zivan R, Parash T, Naveh Y. Applying Max-sum to Asymmetric Distributed Constraint Optimization. In: 24th International Joint Conference on Artificial Intelligence. 2015 pp. 432-438. ISBN: 978-1-57735-738-4.
• [11] Netzer A, Meisels A. Distributed Envy Minimization for Resource Allocation. In: 5th International Conference on Agents and Artificial Intelligence, volume 1. 2013 pp. 15-24.
• [12] Netzer A, Meisels A. Distributed Local Search for Minimizing Envy. In: 2013 IEEE/WIC/ACM International Conference on Intelligent Agent Technology. 2013 pp. 53-58. doi:10.1109/WI-IAT.2013.90.
• [13] Netzer A, Meisels A. SOCIAL DCOP - Social Choice in Distributed Constraints Optimization. In: 5th International Symposium on Intelligent Distributed Computing. 2011 pp. 35-47. https://doi.org/10.1007/978-3-642-24013-3_5.
• [14] Matsui T, Matsuo H. Considering Equality on Distributed Constraint Optimization Problem for Resource Supply Network. In: 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology, volume 2. 2012 pp. 25-32. doi:10.1109/WI-IAT.2012.22.
• [15] Ueda S, Iwasaki A, Yokoo M, Silaghi MC, Hirayama K, Matsui T. Coalition Structure Generation Based on Distributed Constraint Optimization. In: 24th AAAI Conference on Artificial Intelligence. 2010 pp.197-203. http://dblp.uni-trier.de/db/conf/aaai/aaai2010.html#UedaIYSHM10.
• [16] Matsui T, Silaghi M, Hirayama K, Yokoo M, Matsuo H. Leximin Multiple Objective Optimization for Preferences of Agents. In: 17th International Conference on Principles and Practice of Multi-Agent Systems. 2014 pp. 423-438. https://doi.org/10.1007/978-3-319-13191-7_34.
• [17] Matsui T, Silaghi M, Okimoto T, Hirayama K, Yokoo M,Matsuo H. Leximin Asymmetric Multiple Objective DCOP on Factor Graph. In: 18th International Conference on Principles and Practice of Multi-Agent Systems. 2015 pp. 134-151. https://doi.org/10.1007/978-3-319-25524-8_9.
• [18] Matsui T, Matsuo H. Complete Distributed Search Algorithm for Cyclic Factor Graphs. In: 6th International Conference on Agents and Artificial Intelligence. 2014 pp. 184-192.
• [19] Rogers A, Farinelli A, Stranders R, Jennings NR. Bounded Approximate Decentralised Coordination via the Max-Sum Algorithm. Artificial Intelligence, 2011;175(2):730-759. doi:10.1016/j.artint.2010.11.001.
• [20] Sen AK. Choice, Welfare and Measurement. Harvard University Press, 1997.
• [21] Marler RT, Arora JS. Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization, 2004;26:369-395. https://doi.org/10.1007/s00158-003-0368-6.
• [22] Zivan R, Peled H. Max/Min-sum Distributed Constraint Optimization Through Value Propagation on an Alternating DAG. In: 11th International Conference on Autonomous Agents and Multiagent Systems. 2012 pp. 265-272. ISBN:0-9817381-1-7, 978-0-9817381-1-6.
• [23] Dechter R. Mini-buckets: A General Scheme for Generating Approximations in Automated Reasoning. In: 15th International Joint Conference on Artifical Intelligence, volume 2. 1997, pp. 1297-1302. ISBN: 1-555860-480-4.
• [24] de Weerdt M, Clement B. Introduction to Planning in Multiagent Systems. Multiagent and Grid Systems - Planning in multiagent systems. 2009;5(4): 345-355. http://dl.acm.org/citation.cfm?id=1735317.1735318.
• [25] Weiss G (ed.). Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. MIT Press, 1999.
• [26] Weiss G (ed.). Multiagent Systems, Second Edition. MIT Press, 2013. ISBN: 9780262018890.
• [27] Cox JS, Durfee EH, Bartold T. A Distributed Framework for Solving the Multiagent Plan Coordination Problem. In: rth International Joint Conference on Autonomous Agents and Multiagent Systems. 2005 pp. 821-827. ISBN: 1-59593-093-0.
• [28] Nissim R, Brafman RI, Domshlak C. A General, Fully Distributed Multi-agent Planning Algorithm. In: 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1 - Volume 1. 2010 pp. 1323-1330. ISBN: 978-0-9826571-1-9.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).