Multi-Agent Modeling in Schedule Problems

The article explores the use of multi-agent technologies for solving optimization problems. It is shown how multi-agent systems allow working with restrictions in a distributed computing environment. The task of scheduling is formalized. Software was developed and computational experiments were carried out, which showed the effectiveness of the proposed approach.

Keywords: multiagent systems, agent preferences, optimization, distributed systems

Column: Optimization Methods

DOI: https://doi.org/10.17759/mda.2019090408

For Reference

Sivakova T.V., Sudakov V.A. Multi-Agent Modeling in Schedule Problems. Modelirovanie i analiz dannikh [Modelling and Data Analysis], 2019. Vol. 09, no. 4, pp. 100–111. doi:10.17759/mda.2019090408. (In Russ., аbstr. in Engl.)

This work was supported by grant RFBR No 18–00–00012 (18–00–00011) KOMFI.

A. Farinelli, M. Vinyals, A. Rogers, and N. Jennings. “Distributed Constraint Handling and Optimization”, in G. Weiss (ed.), “Multiagent Systems” (second edition), MIT Press, p. 547–584, 2013.
Panteleev A.V., Metlitskaya D.V., Aleshina E.A. Metody global’noi optimizatsii. Metaevristicheskie strategii i algoritmy [Global optimization methods, Metaheuristic strategies and algorithms]. Moscow, Vuzovskayakniga, 2013. 244 p. (in Russian)
Sivakova T.V., Sudakov V.A. Metod nechetkih oblastej predpochtenii dlya ocenki effektivnosti innovacij [Fuzzy preference method for evaluating innovation performance] // XXVIII Mezhdunarodnaya nauchno-tekhnicheskaya konferenciya «Sovremennye tekhnologii v zadachah upravleniya, avtomatiki i obrabotki informacii». Alushta, 14–20 sentyabrya 2019 g. Sbornik trudov. M.: Izd.-vo Nacional’nyj issledovatel’skij yadernyj universitet “MIFI”, 2019. 81–82. (in Russian)
R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.
Makoto Yokoo. Distributed constraint satisfaction: Foundations of cooperation in multiagent systems. Springer-Verlag, 2001.
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.
A. Chechetka and K. Sycara. No-commitment branch and bound search for distributed constraint optimization. In Proceedings of Fifth International Joint Confer- ence on Autonomous Agents and Multiagent Systems, pages 1427–1429, 2006.
Gershman, A. Meisels, and R. Zivan. Asynchronous forward bounding for dis- tribute COPs. Journal Artifi cial Intelligence Research, 34:61–88, 2009.
R. Dechter and R. Mateescu. And/or search spaces for graphical models. Artificial Intelligence, 171:73–106, 2007.
Katsutoshi Hirayama and Makoto Yokoo. Distributed partial constraint satisfaction problem. In Principles and Practice of Constraint Programming, pages 222–236, 1997.
A. Petcu and B. Faltings. DPOP: A scalable method for multiagent constraint optimization. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, pages 266–271, 2005.
R.Maillerand, V.Lesser. Solving distributed constraint optimization problems using cooperative mediation. In Proceedings of Third International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 438–445, 2004.
Library for research on Distributed Constraints Optimization Problems. URL: https://github.com/Orange-OpenSource/pyDcop (26.10.2019)
W. Yeoh, A. Felner, and S. Koenig. BnB-ADOPT: An asynchronous branch-and- bound DCOP algorithm. In Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, pages 591–598, 2008.
S.M. Ali, S. Koenig, and M. Tambe. Preprocessing techniques for accelerating the DCOP algorithm ADOPT. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, pages 1041–1048, 2005.

comments powered by Disqus

PlumX