<div>
	Совместное обучение агентов и векторных представлений графов в задаче управления конвейерными лентами</div>

Рыбкин Константин Евгеньевич, Фильченков Андрей Александрович, Азаров Артур Александрович, Забашта Алексей  Сергеевич, Шалыто Анатолий Абрамович

doi:10.17586/2226-1494-2022-22-6-1187-1196

2022 , ТОМ 22, НОМЕР 6 ( ноябрь-декабрь )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

doi: 10.17586/2226-1494-2022-22-6-1187-1196

УДК 004.8+ 65.011.56

Совместное обучение агентов и векторных представлений графов в задаче управления конвейерными лентами

Рыбкин К.Е., Фильченков А.А., Азаров А.А., Забашта А.С., Шалыто А.А.

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования:

Рыбкин К.Е., Фильченков А.А., Азаров А.А., Забашта А.С., Шалыто А.А. Совместное обучение агентов и векторных представлений графов в задаче управления конвейерными лентами // Научно- технический вестник информационных технологий, механики и оптики. 2022. Т. 22, № 6. С. 1187–1196. doi:10.17586/2226-1494-2022-22-6-1187-1196

Аннотация

Предмет исследования. Рассмотрена задача маршрутизации системы конвейерных лент на основе мультиагентного подхода. В большинстве данных конвейерных систем багажных лент в аэропортах используются алгоритмы маршрутизации, основанные на ручном моделировании поведения конвейеров. Такой подход плохо масштабируем. Новые исследования в области машинного обучения предлагают решать задачу маршрутизации с помощью обучения с подкреплением. Метод. Сформулирован подход к совместному обучению агентов и векторных представлений графа. В рамках подхода предложен алгоритм QSDNE, использующий агентов DQN и векторные представления SDNE. Основные результаты. Выполнен сравнительный анализ разработанного алгоритма c алгоритмами мультиагентной маршрутизации без совместного обучения. На основании результатов работы алгоритма QSDNE сделан вывод о его эффективности для оптимизации времени доставки и энергопотребления в конвейерных системах. Алгоритм позволил сократить среднее время доставки на 6 % по сравнению с лучшим аналогом. Практическая значимость. Разработанный подход может быть использован для решения задач маршрутизации со сложными функциями оценки пути и динамически меняющимися топологиями графов, а предложенный алгоритм — для управления конвейерными лентами в аэропортах и в цеховых производствах.

Ключевые слова: мультиагентное обучение, обучение с подкреплением, адаптивная маршрутизация, конвейерные ленты, графовое представление

Благодарности. Исследование выполнено за счет гранта Российского научного фонда (проект № 20-19-00700).

Список литературы

The World of Air Transport in 2019. ICAOAnnualReport, 2019 [Электронный ресурс]. URL: https://www.icao.int/annual-report-2019/Pages/the-world-of-air-transport-in-2019.aspx(дата обращения: 01.10.2022).
COVID-19 Air Travel Recovery, OAG, 2022 [Электронный ресурс]. URL: https://www.oag.com/coronavirus-airline-schedules-data. (дата обращения:01.10.2022).
2019 SITA Baggage IT Insights report, SITA, 2019 [Электронный ресурс]. URL: https://www.sita.aero/resources/surveys-reports/baggage-it-insights-2019. (дата обращения: 06.09.2022)
Sørensen R.A., Nielsen M., Karstoft H. Routing in congested baggage handling systems using deep reinforcement learning // Integrated Computer-Aided Engineering. 2020. V. 27. N 2. P. 139–152. https://doi.org/10.3233/ICA-190613
Kang Y., Wang X., Lan Z. Q-adaptive: A multi-agent reinforcement learning based routing on dragonfly network // Proc. of the 30^th International Symposium on High-Performance Parallel and Distributed Computing (HPDC). 2021. P. 189–200. https://doi.org/10.1145/3431379.3460650
Choi S., Yeung D.Y. Predictive Q-routing: A memory-based reinforcement learning approach to adaptive traffic control// Advances in Neural Information Processing Systems.1995.V. 8.P. 945–951.
Mukhutdinov D., Filchenkov A., Shalyto A., Vyatkin V. Multi-agent deep learning for simultaneous optimization for time and energy in distributed routing system // Future Generation Computer Systems. 2019. V. 94. P. 587–600. https://doi.org/10.1016/j.future.2018.12.037
Мухудинов Д. Децентрализованный алгоритм управления конвейерной системой с использованием методов мультиагентного обучения с подкреплением: магистерская диссертация. СПб.: Университет ИТМО, 2019, 92 с.[Электронный ресурс].URL: http://is.ifmo.ru/diploma-theses/2019/2_5458464771026191430.pdf (дата обращения: 01.10.2022).
Dantzig G.B. Origins of the simplex method // A history of scientific computing. 1990. P. 141–151. https://doi.org/10.1145/87252.88081
Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. Минск: Вышэйшая школа, 1978. 256 с.
Vutukury S., Garcia-Luna-Aceves J.J. MDVA: A distance-vector multipath routing protocol // Proc. of the 20^th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM). 2001. V. 1. P. 557–564. https://doi.org/10.1109/INFCOM.2001.916780
Albrightson R., Garcia-Luna-Aceves J.J., Boyle J. EIGRP – A fast routing protocol based on distance vectors. 1994.
Verma A., Bhardwaj N. A review on routing information protocol (RIP) and open shortest path first (OSPF) routing protocol // International Journal of Future Generation Communication and Networking. 2016. V. 9. N 4. P. 161–170. https://doi.org/10.14257/ijfgcn.2016.9.4.13
Bang-Jensen J., Gutin G.Z. Digraphs: Theory, Algorithms and Applications. Springer Science & Business Media, 2009. 795 p.
Clausen T., Jacquet P. Optimized link state routing protocol (OLSR). 2003. N RFC3626. https://doi.org/10.17487/RFC3626
Jacquet P., Muhlethaler P., Clausen T., Laouiti A., Qayyum A., Viennot L. Optimized link state routing protocol for ad hoc networks // Proceedings. IEEE International Multi Topic Conference, 2001. IEEE INMIC 2001. Technology for the 21st Century. 2001. P. 62–68. https://doi.org/10.1109/INMIC.2001.995315
Noto M., Sato H. A method for the shortest path search by extended Dijkstra algorithm // Smc 2000 conference proceedings. 2000 IEEE International Conference on Systems, Man and Cybernetics. 2000. V. 3. P. 2316–2320. https://doi.org/10.1109/icsmc.2000.886462
Mammeri Z. Reinforcement learning based routing in networks: Review and classification of approaches // IEEE Access. 2019. V. 7. P. 55916–55950. https://doi.org/10.1109/ACCESS.2019.2913776
Yao Z., Wang Y., Qiu X. DQN-based energy-efficient routing algorithm in software-defined data centers//International Journal of Distributed Sensor Networks.2020.V. 16. N 6.https://doi.org/10.1177/1550147720935775
Belkin M., Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering // Advances in Neural Information Processing Systems. 2002.
Gao B., Pavel L. On the properties of the softmax function with application in game theory and reinforcement learning // arXiv.2017. arXiv:1704.00805.https://doi.org/10.48550/arXiv.1704.00805
Barros C.D., Mendonça M.R., Vieira A.B., Ziviani A. A survey on embedding dynamic graphs // ACM Computing Surveys. 2021. V. 55. N 1. P. 1–37. https://doi.org/10.1145/3483595
Ou M., Cui P., Pei J., Zhang Z., Zhu W. Asymmetric transitivity preserving graph embedding // Proc. of the 22^nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016. P. 1105–1114. https://doi.org/10.1145/2939672.2939751
Grover A., Leskovec J. Node2vec: Scalable feature learning for networks // Proc. of the 22^nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016. P. 855–864. https://doi.org/10.1145/2939672.2939754
Wang D., Cui P., Zhu W. Structural deep network embedding // Proc. of the 22^nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016. P. 1225–1234. https://doi.org/10.1145/2939672.2939753
Goyal P., Chhetri S.R., Canedo A. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning // Knowledge-Based Systems. 2020. V. 187. P. 104816. https://doi.org/10.1016/j.knosys.2019.06.024
Ma Y., Guo Z., Ren Z., Tang J., Yin D. Streaming graph neural networks // Proc. of the 43^rd International ACM SIGIR Conference on Research and Development in Information Retrieval. 2020. P. 719–728. https://doi.org/10.1145/3397271.3401092
Kool W., Van Hoof H., Welling M. Attention, learn to solve routing problems! // Proc. of the 7^th International Conference on Learning Representations (ICLR). 2019.
Komer B., Bergstra J., Eliasmith C. Hyperopt-sklearn // Automated Machine Learning.2019. P. 97–111. https://doi.org/10.1007/978-3-030-05318-5_5

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License