ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2022-22-6-1178-1186ntv-352Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEМультиагентная адаптивная маршрутизация агентами-клонами на основе многоголового внутреннего внимания с использованием обучения с подкреплениемMulti-agent adaptive routing by multi-head-attention-based twin agents using reinforcement learninghttps://orcid.org/0000-0002-1151-3405ГрибановТ. А.GribanovT. A.

Грибанов Тимофей Александрович – студент

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

Timofey A. Gribanov – Student

Saint Petersburg, 197101

t.hrybanau@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-2723-2077ШалытоА. А.ShalytoA. A.

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

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

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 Federation20221912202422611781186Copyright © Грибанов Т.А., Фильченков А.А., Азаров А.А., Шалыто А.А., 20242024Грибанов Т.А., Фильченков А.А., Азаров А.А., Шалыто А.А.Gribanov T.A., Filchenkov A.A., Azarov A.A., 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/352Предмет исследования

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

Метод

Метод. Предложен новый метод, основанный на мультиагентном моделировании с агентами-клонами, с использованием новой архитектуры нейронной сети с многоголовым внутренним вниманием, которая предобучена в рамках парадигмы обучения с нескольких взглядов. Агент в такой парадигме использует вершину как вход, а его клоны помещены в вершины графа и осуществляют выбор соседа, которому следует передать объект. Основные результаты. Выполнен сравнительный анализ с существующим алгоритмом мультиагентной маршрутизации DQN-LE-routing по следующим этапам: предобучение и симуляция. Для каждого этапа рассмотрены запуски с помощью изменения топологии в процессе тестирования или симуляции. Эксперименты показали, что предложенный метод повышения адаптивности обеспечивает глобальную адаптивность, увеличивая время доставки при глобальных изменениях не более чем на 14,5 % от оптимального.

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

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

A regular condition, typical for packet routing, for the problem of cargo transportation, and for the problem of flow control, is the variability of the graph. Reinforcement learning based adaptive routing algorithms are designed to solve the routing problem with this condition. However, with significant changes in the graph, the existing routing algorithms require complete retraining. To handle this challenge, we propose a novel method based on multi-agent modeling with twin-agents for which new neural network architecture with multi-headed internal attention is proposed, pre-trained within the framework of the multi-view learning paradigm. An agent in such a paradigm uses a vertex as an input, twins of the main agent are placed at the vertices of the graph and select a neighbor to which the object should be transferred. We carried out a comparative analysis with the existing DQN-LE-routing multi-agent routing algorithm on two stages: pre-training and simulation. In both cases, launches were considered by changing the topology during testing or simulation. Experiments have shown that the proposed adaptability enhancement method provides global adaptability by increasing delivery time only by 14.5 % after global changes occur. The proposed method can be used to solve routing problems with complex path evaluation functions and dynamically changing graph topologies, for example, in transport logistics and for managing conveyor belts in production.

маршрутизациямультиагентное обучениеобучение с подкреплениемадаптивная маршрутизацияroutingmulti-agent learningreinforcement learningadaptive routingИсследование выполнено за счет гранта Российского научного фонда (проект № 20-19-00700).The study was supported by the grant from the Russian Science Foundation (project № 20-19-00700).ReferencesToth P., Vigo D. An overview of vehicle routing problems // The Vehicle Routing Problem. SIAM, 2002. P. 1–26. https://doi.org/10.1137/1.9780898718515.ch1Toth P., Vigo D. An overview of vehicle routing problems. The Vehicle Routing Problem. SIAM, 2002, pp. 1–26. https://doi.org/10.1137/1.9780898718515.ch1Vutukury S., Garcia-Luna-Aceves J.J. MDVA: A distance-vector multipath routing protocol // Proc. 20th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM). 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. 20th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM), vol. 1, pp. 557–564. https://doi.org/10.1109/INFCOM.2001.916780Clausen 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/RFC3626Sweda T.M., Dolinskaya I.S., Klabjan D. Adaptive routing and recharging policies for electric vehicles // Transportation Science. 2017. V. 51. N 4. P. 1326–1348. https://doi.org/10.1287/trsc.2016.0724Sweda T.M., Dolinskaya I.S., Klabjan D. Adaptive routing and recharging policies for electric vehicles. Transportation Science, 2017, vol. 51, no. 4, pp. 1326–1348. https://doi.org/10.1287/trsc.2016.0724Puthal M.K., Singh V., Gaur M.S., Laxmi V. C-Routing: An adaptive hierarchical NoC routing methodology // Proc. of the 2011 IEEE/IFIP 19th International Conference on VLSI and System-on-Chip. 2011. P. 392–397. https://doi.org/10.1109/VLSISoC.2011.6081616Puthal M.K., Singh V., Gaur M.S., Laxmi V. C-Routing: An adaptive hierarchical NoC routing methodology. Proc. of the 2011 IEEE/IFIP 19th International Conference on VLSI and System-on-Chip, 2011, pp. 392–397. https://doi.org/10.1109/VLSISoC.2011.6081616Zeng S., Xu X., Chen Y. Multi-agent reinforcement learning for adaptive routing: A hybrid method using eligibility traces // Proc. of the 16th IEEE International Conference on Control & Automation (ICCA’20). 2020. P. 1332–1339. https://doi.org/10.1109/ICCA51439.2020.9264518Zeng S., Xu X., Chen Y. Multi-agent reinforcement learning for adaptive routing: A hybrid method using eligibility traces. Proc. of the 16th IEEE International Conference on Control & Automation (ICCA’20), 2020, pp. 1332–1339. https://doi.org/10.1109/ICCA51439.2020.9264518Ibrahim A.M., Yau K.L.A., Chong Y.W., Wu C. Applications of multiagent deep reinforcement learning: models and algorithms // Applied Sciences. 2021. V. 11. N 22. P. 10870. https://doi.org/10.3390/app112210870Ibrahim A.M., Yau K.L.A., Chong Y.W., Wu C. Applications of multiagent deep reinforcement learning: models and algorithms. Applied Sciences, 2021, vol. 11, no. 22, pp. 10870. https://doi.org/10.3390/app112210870Bono G., Dibangoye J.S., Simonin O., Matignon L., Pereyron F. Solving multi-agent routing problems using deep attention mechanisms // IEEE Transactions on Intelligent Transportation Systems. 2021. V. 22. N 12. P. 7804–7813. https://doi.org/10.1109/TITS.2020.3009289Bono G., Dibangoye J.S., Simonin O., Matignon L., Pereyron F. Solving multi-agent routing problems using deep attention mechanisms. IEEE Transactions on Intelligent Transportation Systems, 2021, vol. 22, no. 12, pp. 7804–7813. https://doi.org/10.1109/TITS.2020.3009289Kang 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 andDistributed Computing. 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 andDistributed Computing, 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.Watkins C.J., Dayan P. Q-learning // Machine Learning. 1992. V. 8. N 3. P. 279–292. https://doi.org/10.1023/A:1022676722315Watkins C.J., Dayan P. Q-learning. Machine Learning, 1992, vol. 8, no. 3, pp. 279–292. https://doi.org/10.1023/A:1022676722315Mnih V., Kavukcuoglu K., Silver D., Graves A., Antonoglou I., Wierstra D., Riedmiller M. Playing atari with deep reinforcement learning // arXiv. 2013. arXiv:1312.5602. https://doi.org/10.48550/arXiv.1312.5602Mnih V., Kavukcuoglu K., Silver D., Graves A., Antonoglou I., Wierstra D., Riedmiller M. Playing atari with deep reinforcement learning. arXiv, 2013, arXiv:1312.5602. https://doi.org/10.48550/arXiv.1312.5602Mukhutdinov 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.037Gao 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.00805Мухудинов Д. Децентрализованный алгоритм управления конвейерной системой с использованием методов мультиагентного обучения с подкреплением: магистерская диссертация. СПб.: Университет ИТМО, 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)Belkin M., Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering // Advances in Neural Information Processing Systems. 2001. P. 585–591. https://doi.org/10.7551/mitpress/1120.003.0080Belkin M., Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in Neural Information Processing Systems, 2001, pp. 585–591. https://doi.org/10.7551/mitpress/1120.003.0080Benea M.T., Florea A.M., Seghrouchni A.E.F. CAmI: An agent oriented-language for the collective development of AmI environments // Proc. of the 20th International Conference on Control Systems and Computer Science (CSCS). 2015. P. 749–756. https://doi.org/10.1109/CSCS.2015.136Benea M.T., Florea A.M., Seghrouchni A.E.F. CAmI: An agent oriented-language for the collective development of AmI environments. Proc. of the 20th International Conference on Control Systems and Computer Science (CSCS), 2015, pp. 749–756. https://doi.org/10.1109/CSCS.2015.136Wang Y., Yao Q., Kwok J.T., Ni L.M. Generalizing from a few examples: A survey on few-shot learning // ACM Computing Surveys. 2020. V. 53. N 3. P. 63. https://doi.org/10.1145/3386252Wang Y., Yao Q., Kwok J.T., Ni L.M. Generalizing from a few examples: A survey on few-shot learning. ACM Computing Surveys, 2020, vol. 53, no. 3, pp. 63. https://doi.org/10.1145/3386252Liu J., Chen S., Wang B., Zhang J., Li N., Xu T. Attention as relation: learning supervised multi-head self-attention for relation extraction // Proc. of the 19th International Joint Conferences on Artificial Intelligence (IJCAI). 2020. P. 3787–3793. https://doi.org/10.24963/ijcai.2020/524Liu J., Chen S., Wang B., Zhang J., Li N., Xu T. Attention as relation: learning supervised multi-head self-attention for relation extraction. Proc. of the 19th International Joint Conferences on Artificial Intelligence (IJCAI), 2020, pp. 3787–3793. https://doi.org/10.24963/ijcai.2020/524Sola J., Sevilla J. Importance of input data normalization for the application of neural networks to complex industrial problems // IEEE Transactions on Nuclear Science. 1997. V. 44. N 3. P. 1464–1468. https://doi.org/10.1109/23.589532Sola J., Sevilla J. Importance of input data normalization for the application of neural networks to complex industrial problems. IEEE Transactions on Nuclear Science, 1997, vol. 44, no. 3, pp. 1464–1468. https://doi.org/10.1109/23.589532Baldi P., Sadowski P.J. Understanding dropout // Advances in Neural Information Processing Systems. 2013. V. 26. P. 26–35.Baldi P., Sadowski P.J. Understanding dropout. Advances in Neural Information Processing Systems, 2013, vol. 26, pp. 26–35.

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