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

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

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

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

1. The 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).

2. COVID-19 Air Travel Recovery, OAG, 2022 [Электронный ресурс]. URL: https://www.oag.com/coronavirus-airline-schedules-data. (дата обращения: 01.10.2022).

3. 2019 SITA Baggage IT Insights report, SITA, 2019 [Электронный ресурс]. URL: https://www.sita.aero/resources/surveys-reports/baggage-it-insights-2019. (дата обращения: 06.09.2022)

4. 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

5. Kang 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.3460650

6. 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.

7. 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

8. Мухудинов Д. Децентрализованный алгоритм управления конвейерной системой с использованием методов мультиагентного обучения с подкреплением: магистерская диссертация. СПб.: Университет ИТМО, 2019, 92 с. [Электронный ресурс]. URL: http://is.ifmo.ru/diploma-theses/2019/2_5458464771026191430.pdf (дата обращения: 01.10.2022).

9. Dantzig G.B. Origins of the simplex method // A history of scientific computing. 1990. P. 141–151. https://doi.org/10.1145/87252.88081

10. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. Минск: Вышэйшая школа, 1978. 256 с.

11. 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.916780

12. Albrightson R., Garcia-Luna-Aceves J.J., Boyle J. EIGRP — A fast routing protocol based on distance vectors. 1994.

13. 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

14. Bang-Jensen J., Gutin G.Z. Digraphs: Theory, Algorithms and Applications. Springer Science & Business Media, 2009. 795 p.

15. Clausen T., Jacquet P. Optimized link state routing protocol (OLSR). 2003. N RFC3626. https://doi.org/10.17487/RFC3626

16. 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

17. 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

18. 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

19. 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

20. Belkin M., Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering // Advances in Neural Information Processing Systems. 2002.

21. 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

22. 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

23. Ou 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.2939751

24. Grover 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.2939754

25. Wang 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.2939753

26. 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

27. Ma 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.3401092

28. Kool W., Van Hoof H., Welling M. Attention, learn to solve routing problems! // Proc. of the 7th International Conference on Learning Representations (ICLR). 2019.

29. 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