Мультиагентное моделирование в задачах формирования расписаний

В статье исследуется применение мультиагентных технологий для решения оптимизационных задач. Показано, как мультиагентные системы позволяют работать с ограничениями в распределенной вычислительной среде. Формализована задача составления расписания. Разработано программное обеспечение и проведены вычислительные эксперименты, показавшие эффективность предложенного подхода.

Рассмотрим проблему распределения множества задач на множество ресурсов (например, планирование лекций для аудиторий или пакета заданий для нескольких процессоров). Это распространенная и важная проблема, которую можно формализовать, используя мультиагентный подход.

1. 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.
2. Пантелеев А.В., Метлицкая Д.В., Алешина Е.А. Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы. М.: Вузовская книга, 2013. 244 c.
3. Сивакова Т.В., Судаков В.А. Метод нечетких областей предпочтении для оценки эффективности инноваций // XXVIII Международная научно-техническая конференция «Современные технологии в задачах управления, автоматики и обработки информации». Алушта, 14–20 сентября 2019 г. Сборник трудов. М.: Изд.-во Национальный исследовательский ядерный университет «МИФИ», 2019. С. 81–82.
4. R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.
5. Makoto Yokoo. Distributed constraint satisfaction: Foundations of cooperation in multiagent systems. Springer-Verlag, 2001.
6. P.J. Modi, W. Shen, M. Tambe, and M. Yokoo. ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artifi cial Intelligence Journal, (161):149–180, 2005.
7. A. Chechetka and K. Sycara. No-commitment branch and bound search for dis- tribute constraint optimization. In Proceedings of Fifth International Joint Confer- ence on Autonomous Agents and Multiagent Systems, pages 1427–1429, 2006.
8. Gershman, A. Meisels, and R. Zivan. Asynchronous forward bounding for dis- tribute COPs. Journal Artifi cial Intelligence Research, 34:61–88, 2009.
9. R. Dechter and R. Mateescu. And/or search spaces for graphical models. Artifi cial Intelligence, 171:73–106, 2007.
10. Katsutoshi Hirayama and Makoto Yokoo. Distributed partial constraint satisfaction problem. In Principles and Practice of Constraint Programming, pages 222–236, 1997.
11. A. Petcu and B. Faltings. DPOP: A scalable method for multiagent constraint optimization. In Proceedings of the Nineteenth International Joint Conference on Arti- fi cial Intelligence, pages 266–271, 2005.
12. 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.
13. Library for research on Distributed Constraints Optimization Problems. URL: https://github.com/Orange-OpenSource/pyDcop (датаобращения: 26.10.2019)
14. 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.
15. 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.

PlumX

Метрики публикации