ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2022-22-6-1187-1196ntv-353Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEСовместное обучение агентов и векторных представлений графов в задаче управления конвейерными лентамиJoint learning of agents and graph embeddings in a conveyor belt control problemhttps://orcid.org/0000-0003-0856-4276РыбкинК. Е.RybkinK. E.

Рыбкин Константин Евгеньевич – инженер

Санкт-Петербург, 197101

Konstantin E. Rybkin – Engineer

Saint Petersburg, 197101

matveich1903@gmail.comhttps://orcid.org/0000-0002-1133-8432ФильченковА. А.FilchenkovA. A.

Фильченков Андрей Александрович – кандидат физико-математических наук, инженер

Санкт-Петербург, 197101

sc 55507568200

Andrey A. Filchenkov – PhD (Physics & Mathematics), Engineer

Saint Petersburg, 197101

sc 55507568200

afilchenkov@itmo.ruhttps://orcid.org/0000-0003-3240-597XАзаровА. А.AzarovA. A.

Азаров Артур Александрович – кандидат технических наук, научный сотрудник; заместитель директора

Санкт-Петербург, 197101;

Санкт-Петербург, 199178

sc 56938354700

Artur A. Azarov – PhD, Scientific Researcher; Deputy Director

Saint Petersburg, 197101;

Saint Petersburg, 199178

sc 56938354700

artur-azarov@yandex.ruhttps://orcid.org/0000-0002-7494-4309ЗабаштаА. С.ZabashtaA. S.

Забашта Алексей Сергеевич – кандидат технических наук, доцент

Санкт-Петербург, 197101

sc 56902663900

Alexey S. Zabashta – PhD, Associate Professor

Saint Petersburg, 197101

sc 56902663900

azabashta@itmo.ruhttps://orcid.org/0000-0002-2723-2077ШалытоА. А.ShalytoA. A.

Шалыто Анатолий Абрамович – доктор технических наук, профессор, главный научный сотрудник

Санкт-Петербург, 197101

sc 56131789500

Anatoly A. Shalyto – D. Sc., Professor, Chief Reseacher

Saint Petersburg, 197101

sc 56131789500

shalyto@mail.ifmo.ruУниверситет ИТМОРоссияITMO UniversityRussian FederationУниверситет ИТМО; Северо-Западный институт управления – филиал РАНХиГСРоссияITMO University; North-West Institute of Management – branch of the Russian Presidential Academy of National Economy and Public AdministrationRussian Federation20221912202422611871196Copyright © Рыбкин К.Е., Фильченков А.А., Азаров А.А., Забашта А.С., Шалыто А.А., 20242024Рыбкин К.Е., Фильченков А.А., Азаров А.А., Забашта А.С., Шалыто А.А.Rybkin K.E., Filchenkov A.A., Azarov A.A., Zabashta A.S., Shalyto A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/353Предмет исследования

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

Метод

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

Практическая значимость

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

We focus on the problem of routing a conveyor belts system based on a multi-agent approach. Most of these airport baggage belt conveyor systems use routing algorithms based on manual simulation of conveyor behavior. This approach does not scale well, and new research in machine learning proposes to solve the routing problem using reinforcement learning. To solve this problem, we propose an approach to joint learning of agents and vector representations of a graph. Within this approach, we develop a QSDNE algorithm, which uses DQN agents and SDNE embeddings. A comparative analysis was carried out with multi-agent routing algorithms without joint learning. The results of the QSDNE algorithm showed its effectiveness in optimizing the delivery time and energy consumption in conveyor systems as it helped to reduce mean delivery time by 6 %. The proposed approach can be used to solve routing problems with complex path estimation functions and dynamically changing graph topologies, and the proposed algorithm can be used to control conveyor belts at airports and in manufacturing workshops.

мультиагентное обучениеобучение с подкреплениемадаптивная маршрутизацияконвейерные лентыграфовое представлениеmulti-agent learningreinforcement learningadaptive routingconveyor beltgraph representationИсследование выполнено за счет гранта Российского научного фонда (проект № 20-19-00700).The study was supported by a grant from the Russian Science Foundation (project № 20-19-00700).ReferencesThe World of Air Transport in 2019. ICAO Annual Report, 2019 [Электронный ресурс]. URL: https://www.icao.int/annualreport-2019/Pages/the-world-of-air-transport-in-2019.aspx (дата обращения: 01.10.2022).The World of Air Transport in 2019. ICAO Annual Report, 2019. Available at: https://www.icao.int/annual-report-2019/Pages/theworld-of-air-transport-in-2019.aspx (accessed: 01.10.2022).COVID-19 Air Travel Recovery, OAG, 2022 [Электронный ресурс]. URL: https://www.oag.com/coronavirus-airline-schedules-data. (дата обращения: 01.10.2022).COVID-19 Air Travel Recovery, OAG, 2022. Available at: https://www.oag.com/coronavirus-airline-schedules-data. (sccessed: 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)2019 SITA Baggage IT Insights report, SITA, 2019. Available at: https://www.sita.aero/resources/surveys-reports/baggage-itinsights- 2019. (accessed: 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-190613Sørensen R.A., Nielsen M., Karstoft H. Routing in congested baggage handling systems using deep reinforcement learning. Integrated Computer-Aided Engineering, 2020, vol. 27, no. 2, pp. 139–152. https://doi.org/10.3233/ICA-190613Kang Y., Wang X., Lan Z. Q-adaptive: A multi-agent reinforcement learning based routing on dragonfly network // Proc. of the 30th International Symposium on High-Performance Parallel and Distributed Computing (HPDC). 2021. P. 189–200. https://doi.org/10.1145/3431379.3460650Kang Y., Wang X., Lan Z. Q-adaptive: A multi-agent reinforcement learning based routing on dragonfly network. Proc. of the 30th International Symposium on High-Performance Parallel and Distributed Computing (HPDC), 2021, pp. 189–200. https://doi.org/10.1145/3431379.3460650Choi 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.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, vol. 8, pp. 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.037Mukhutdinov 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, vol. 94, pp. 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).Mukhudinov D. Decentralized conveyor system control algorithm using multi-agent reinforcement learning methods. MSc Dissertation. St. Petersburg, ITMO University, 2019, 92 p. Available at: http://is.ifmo.ru/diploma-theses/2019/2_5458464771026191430.pdf (accessed: 01.10.2022). (in Russian).Dantzig G.B. Origins of the simplex method // A history of scientific computing. 1990. P. 141–151. https://doi.org/10.1145/87252.88081Dantzig G.B. Origins of the simplex method. A history of scientific computing, 1990, pp. 141–151. https://doi.org/10.1145/87252.88081Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. Минск: Вышэйшая школа, 1978. 256 с.Kuznetcov A.V., Kholod N.I., Kostevich L.S. Guide to Solving Mathematical Programming Problems. Minsk, Vyshjejshaja shkola Publ., 1978, 256 p. (in Russian).Vutukury S., Garcia-Luna-Aceves J.J. MDVA: A distance-vector multipath routing protocol // Proc. of the 20th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM). 2001. V. 1. P. 557–564. https://doi.org/10.1109/INFCOM.2001.916780Vutukury S., Garcia-Luna-Aceves J.J. MDVA: A distance-vector multipath routing protocol. Proc. of the 20th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM), 2001, vol. 1, pp. 557–564. https://doi.org/10.1109/INFCOM.2001.916780Albrightson R., Garcia-Luna-Aceves J.J., Boyle J. EIGRP — A fast routing protocol based on distance vectors. 1994.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.13Verma 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, vol. 9, no. 4, pp. 161–170. https://doi.org/10.14257/ijfgcn.2016.9.4.13Bang-Jensen J., Gutin G.Z. Digraphs: Theory, Algorithms and Applications. Springer Science & Business Media, 2009. 795 p.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/RFC3626Clausen T., Jacquet P. Optimized link state routing protocol (OLSR). 2003, no. RFC3626. https://doi.org/10.17487/RFC3626Jacquet 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.995315Jacquet 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, pp. 62–68. https://doi.org/10.1109/INMIC.2001.995315Noto 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.886462Noto 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, vol. 3, pp. 2316–2320. https://doi.org/10.1109/icsmc.2000.886462Mammeri 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.2913776Mammeri Z. Reinforcement learning based routing in networks: Review and classification of approaches. IEEE Access, 2019, vol. 7, pp. 55916–55950. https://doi.org/10.1109/ACCESS.2019.2913776Yao 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/1550147720935775Yao Z., Wang Y., Qiu X. DQN-based energy-efficient routing algorithm in software-defined data centers. International Journal of Distributed Sensor Networks, 2020, vol. 16, no. 6. https://doi.org/10.1177/1550147720935775Belkin M., Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering // Advances in Neural Information Processing Systems. 2002.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.00805Gao 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.00805Barros 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/3483595Barros C.D., Mendonça M.R., Vieira A.B., Ziviani A. A survey on embedding dynamic graphs. ACM Computing Surveys, 2021, vol. 55, no. 1, pp. 1–37. https://doi.org/10.1145/3483595Ou M., Cui P., Pei J., Zhang Z., Zhu W. Asymmetric transitivity preserving graph embedding // Proc. of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016. P. 1105–1114. https://doi.org/10.1145/2939672.2939751Ou M., Cui P., Pei J., Zhang Z., Zhu W. Asymmetric transitivity preserving graph embedding. Proc. of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 1105–1114. https://doi.org/10.1145/2939672.2939751Grover A., Leskovec J. Node2vec: Scalable feature learning for networks // Proc. of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016. P. 855–864. https://doi.org/10.1145/2939672.2939754Grover A., Leskovec J. Node2vec: Scalable feature learning for networks. Proc. of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 855–864. https://doi.org/10.1145/2939672.2939754Wang D., Cui P., Zhu W. Structural deep network embedding // Proc. of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016. P. 1225–1234. https://doi.org/10.1145/2939672.2939753Wang D., Cui P., Zhu W. Structural deep network embedding. Proc. of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 1225–1234. https://doi.org/10.1145/2939672.2939753Goyal 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.024Goyal P., Chhetri S.R., Canedo A. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Based Systems, 2020, vol. 187, pp. 104816. https://doi.org/10.1016/j.knosys.2019.06.024Ma Y., Guo Z., Ren Z., Tang J., Yin D. Streaming graph neural networks // Proc. of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. 2020. P. 719–728. https://doi.org/10.1145/3397271.3401092Ma Y., Guo Z., Ren Z., Tang J., Yin D. Streaming graph neural networks. Proc. of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, 2020, pp. 719–728. https://doi.org/10.1145/3397271.3401092Kool W., Van Hoof H., Welling M. Attention, learn to solve routing problems! // Proc. of the 7th International Conference on Learning Representations (ICLR). 2019.Kool W., Van Hoof H., Welling M. Attention, learn to solve routing problems! Proc. of the 7th 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_5Komer B., Bergstra J., Eliasmith C. Hyperopt-sklearn. Automated Machine Learning, 2019, pp. 97–111. https://doi.org/10.1007/978-3-030-05318-5_5

The authors declare that there are no conflicts of interest present.