10.14489/vkit.2021.11.pp.013-026

DOI: 10.14489/vkit.2021.11.pp.013-026

Дубенко Ю. В., Дышкант Е. Е., Тимченко Н. Н., Рудешко Н. А.
ГИБРИДНЫЙ АЛГОРИТМ ФОРМИРОВАНИЯ КРАТЧАЙШЕЙ ТРАЕКТОРИИ, ОСНОВАННЫЙ НА ПРИМЕНЕНИИ МНОГОАГЕНТНОГО ОБУЧЕНИЯ С ПОДКРЕПЛЕНИЕМ И ОБМЕНА ОПЫТОМ
(с. 13-26)

Аннотация. Приведены гибридный алгоритм формирования кратчайшей траектории для интеллектуальных агентов многоагентной системы, основанный на синтезе методов парадигмы обучения с подкреплением, и эвристический поисковый алгоритм А*, обладающий функциями обмена опытом, а также автоматического формирования подгрупп агентов на основании их областей видимости. Экспериментальная оценка разработанного алгоритма осуществлялась путем моделирования задачи поиска целевого состояния в лабиринте в среде Microsoft Unity. Результаты эксперимента показали, что применение разработанного гибридного алгоритма позволило снизить время решения задачи в среднем на 12,7 % по сравнению с аналогами. Отличие предложенного нового «гибридного алгоритма формирования кратчайшей траектории, основанного на применении многоагентного обучения с подкреплением, поискового алгоритма A* и обмена опытом» от аналогов заключается, во-первых, в применении алгоритма формирования подгрупп агентов-подчиненных на основании «области видимости» агента-лидера для реализации многоуровневой иерархической системы управления группой агентов и, во-вторых, в объединении принципов обучения с подкреплением и поискового алгоритма А*.

Ключевые слова: интеллектуальный агент; многоагентное обучение с подкреплением; эвристический алгоритм А*; область видимости агента; обмен опытом; формирование кратчайшей траектории; агент-менеджер; агент-подчиненный.

Dubenko Yu. V., Dyshkant E. E., Timchenko N. N., Rudeshko N. A.
A HYBRID ALGORITHM FOR FORMING THE SHORTEST TRAJECTORY BASED ON THE APPLICATION OF MULTI-AGENT LEARNING WITH REINFORCEMENT, THE SEARCH ALGORITHM A* AND EXCHANGE OF EXPERIENCE
(pp. 13-26)

Abstract. The article presents a hybrid algorithm for the formation of the shortest trajectory for intelligent agents of a multi-agent system, based on the synthesis of methods of the reinforcement learning paradigm, the heuristic search algorithm A*, which has the functions of exchange of experience, as well as the automatic formation of subgroups of agents based on their visibility areas. The experimental evaluation of the developed algorithm was carried out by simulating the task of finding the target state in the maze in the Microsoft Unity environment. The results of the experiment showed that the use of the developed hybrid algorithm made it possible to reduce the time for solving the problem by an average of 12.7 % in comparison with analogs. The differences between the proposed new “hybrid algorithm for the formation of the shortest trajectory based on the use of multi-agent reinforcement learning, search algorithm A* and exchange of experience” from analogs are as follows: – application of the algorithm for the formation of subgroups of subordinate agents based on the “scope” of the leader agent for the implementation of a multi-level hierarchical system for managing a group of agents; – combining the principles of reinforcement learning and the search algorithm A*.

Keywords: Intelligent agent; Multiagent reinforcement learning; Heuristic algorithm A*; Agent visibility; Exchange of experience; Formation of the shortest trajectory; Agent-manager; Agent-subordinate.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Ю. В. Дубенко, Е. Е. Дышкант, Н. Н. Тимченко, Н. А. Рудешко (Кубанский государственный технологический университет, Краснодар, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

Yu. V. Dubenko, E. E. Dyshkant, N. N. Timchenko, N. A. Rudeshko (Kuban State Technological University, Krasnodar, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Дубенко Ю. В. Аналитический обзор проблем многоагентного обучения с подкреплением // Вестник компьютерных и информационных технологий. 2020. Т. 17, № 6(192). С. 48 – 56.
2. Дубенко Ю. В., Дышкант Е. Е., Гура Д. А. Анализ иерархического обучения с подкреплением для реализации поведенческих стратегий интеллектуальных агентов // Вестник компьютерных и информационных технологий. 2020. Т. 17, № 9(195). С. 35 – 45.
3. Симанков В. С., Дубенко Ю. В. Системный анализ в иерархических интеллектуальных многоагентных системах // Вестник компьютерных и информационных технологий. 2021. Т. 18, № 3(201). С. 33 – 46.
4. Foerster J. N. Deep Multi-Agent Reinforcement Learning. (2018). University of Oxford. URL:https://ora.ox. ac.uk/objects/uuid:a55621b3-53c0-4e1b-ad1c-92438b57ffa4 (дата обращения: 07.11.2021).
5. Тарасов В. Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: Эдиториал УРСС, 2002. 352 с.
6. Саттон Р. С., Барто Э. Дж. Обучение с подкреплением: Введение. 2-е изд. / пер. с англ. А. А. Слинкина. М.: ДМК Пресс, 2020. 552 с.
7. Евстигнеев В. А. Применение теории графов в программировании / под ред. А. П. Ершова. М.: Наука. Главная редакция физико-математической литературы, 1985. 352 с.
8. Ahilan S., Dayan P. Feudal Multi-Agent Hierarchies for Cooperative Reinforcement Learning // arxiv:1901.08492v1[cs.MA]24Jan.2019.

Eng

1. Dubenko Yu. V. (2020). Analytical overview of the problems of multi-agent reinforcement learning. Vestnik komp'yuternyh i informatsionnyh tekhnologiy, Vol. 17, 192(6), pp. 48 – 56. [in Russian language] DOI 10.14489/ vkit.2020.06.pp.048-056
2. Dubenko Yu. V., Dyshkant E. E., Gura D. A. (2020). Analysis of hierarchical reinforcement learning for the implementation of behavioral strategies of intelligent agents. Vestnik komp'yuternyh i informatsionnyh tekhnologiy, Vol. 17, 195(9), pp. 35 – 45. [in Russian language] DOI 10.14489/vkit.2020.09.pp.035-045
3. Simankov V. S., Dubenko Yu. V. (2021). System analysis in hierarchical intelligent multi-agent systems. Vestnik komp'yuternyh i informatsionnyh tekhnologiy, Vol. 18, 201(3), pp. 33 – 46. [in Russian language] DOI 10.14489/ vkit.2021.03.pp.033-046
4. Foerster J. N. (2018). Deep Multi-Agent Rein-forcement Learning [PhD Thesis]. University of Oxford. Available at: https://ora.ox.ac.uk/objects/uuid:a55621b3-53c0-4e1b-ad1c-92438b57ffa4 (Accessed: 07.11.2021).
5. Tarasov V. B. (2002). From multiagent systems to intelligent organizations: philosophy, psychology, computer science. Moscow: Editorial URSS. [in Russian language]
6. Satton R. S., Barto E. Dzh. (2020). Reinforcement Learning: An Introduction. 2nd ed. Moscow: DMK Press. [in Russian language]
7. Ershov A. P. (Ed.), Evstigneev V. A. (1985). Application of graph theory in programming. Moscow: Nauka. Glavnaya redaktsiya fiziko-matematicheskoy literatury. [in Russian language]
8. Sanjeevan Ahilan, Peter Dayan (2019). Feudal Multi-Agent Hierarchies for Cooperative Reinforcement Learning. Proceedings of the Workshop on “Structure & Priors in Rein-forcement Learning” at ICLR 2019.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 450 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2021.11.pp.013-026

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 450 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2021.11.pp.013-026

and fill out the form