doi: 10.17586/2226-1494-2022-22-6-1178-1186


УДК 004.8+ 65.011.56

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

Грибанов Т.А., Фильченков А.А., Азаров А.А., Шалыто А.А.


Читать статью полностью 
Язык статьи - русский

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


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

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

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

Список литературы
  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 multi-agent 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 and Distributed 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.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2023 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика