Меню
Публикации
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
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).
Список литературы
Благодарности. Исследование выполнено за счет гранта Российского научного фонда (проект № 20-19-00700).
Список литературы
- 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
- 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
- Clausen T., Jacquet P. Optimized link state routing protocol (OLSR). 2003. N RFC3626. https://doi.org/10.17487/RFC3626
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- Watkins C.J., Dayan P. Q-learning // Machine Learning. 1992. V. 8. N 3. P. 279–292. https://doi.org/10.1023/A:1022676722315
- 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
- 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
- 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
- Мухудинов Д. Децентрализованный алгоритм управления конвейерной системой с использованием методов мультиагентного обучения с подкреплением: магистерская диссертация. СПб.: Университет ИТМО, 2019.92 с. [Электронный ресурс].URL: http://is.ifmo.ru/diploma-theses/2019/2_5458464771026191430.pdf (дата обращения: 01.10.2022)
- 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
- 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
- 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
- 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
- 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
- Baldi P., Sadowski P.J. Understanding dropout // Advances in Neural Information Processing Systems. 2013. V. 26. P. 26–35.