Мультиагентная адаптивная маршрутизация агентами-клонами на основе многоголового внутреннего внимания с использованием обучения с подкреплением

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

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

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

1. Toth 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.ch1

2. Vutukury 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.916780

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

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

5. Puthal 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.6081616

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

7. Ibrahim 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/app112210870

8. Bono 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.3009289

9. 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 andDistributed Computing. 2021. P. 189–200. https://doi.org/10.1145/3431379.3460650

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

11. Watkins C.J., Dayan P. Q-learning // Machine Learning. 1992. V. 8. N 3. P. 279–292. https://doi.org/10.1023/A:1022676722315

12. Mnih 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.5602

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

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

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

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

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

18. Wang 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/3386252

19. Liu 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/524

20. Sola 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.589532

21. Baldi P., Sadowski P.J. Understanding dropout // Advances in Neural Information Processing Systems. 2013. V. 26. P. 26–35.