Исследование и разработка системы поиска наилучшего маршрута посредством технологий машинного обучения
Введение
Задача данной работы заключается в исследовании и разработки системы поиска наилучшего маршрута при помощи средств машинного обучения.
С каждым днем все повышается объем больших данных реальных карт и местности, в связи с чем возникает большинство трудностей с нахождением оптимального пути. Самым простым способом является метод перебора путей. Но он неприменим из-за чрезмерных накладных расходов, так как требуется полное исследование всей местности и хранение ее в памяти.
Области машинного обучения, обучения с подкреплением привлеки многих ученых способностью решать широкий круг разнообразных задач, используя простую архитектуру и без необходимости изучения динамики проблемы для процесса решения. Обучение с подкреплением нашло применение во многих областях человеческой деятельности, начиная с финансов и робототехники, заканчивая обработкой естественного языка и телекоммуникациями. Ведущей частью системы обучения с подкреплением является агент, который принимает действия в среде, которая моделирует задачу, которая должны быть выполнена. Во всех приложениях, агенты взаимодействуют со средой, принимая пробные и ошибочные суждения о её состояниях, получая при этом вознаграждения. Мультиагентные системы могут быть использованы во многих областях, например, контроль трафика, маршрутизация сетевых пакетов, распределение энергии, системы роботов, экономическое моделирование и анализ со
Содержание
Введение 8
Глава 1. Описание методов решения задачи поиска наилучшего маршрута 10
Глава 2. Исследование выбранных алгоритмов поиска маршрута мультиагентного обучения 42
Глава 3. Разработка системы поиска маршрута 68
Глава 4. Тестирование системы поиска маршрута 74
Заключение 79
Список использованных источников 80
Список использованных источников
1. A Comprehensive Study on Pathfinding Algorithm for Static 2D Square Grid. Publisher: IEEE. Xuemeng Wei; Donglai Lu.
2. A Study on Pathfinding for Multiple Interactive Entities in an Interactive Virtual Environment. Publisher: IEEE. Burra Venkata Durga Kumar.
3. Глава 45. Задача коммивояжера [Электронный ресурс]. URL: http://mech.math.msu.su/~shvetz/54/inf/perl-problems/chCommisVoyageur.xhtml (дата обращения: 20.11.2021).
4. Colored Traveling Salesman Problem. Publisher: IEEE. Jun Li; MengChu Zhou; Qirui Sun; Xianzhong Dai; Xiaolong Yu.
5. A review of directed graphs as applied to computors. Publisher: IEEE. Paul D. Stigall; Ömür Tasar.
6. Теория графов: основные понятия и задачи [Электронный ресурс]. URL: https://function-x.ru/graphs1_relations.html (дата обращения: 20.11.2021).
7. Ориентированный граф. Степень входа и степень выхода вершины. Источник. Сток. Ориентированный путь. Ориентированный цикл (контур) [Электронный ресурс]. URL: https://life-prog.ru/1_56627_orientirovanniy-graf-stepen-vhoda-i-stepen-vihoda-vershini-istochnik-stok-orientirovanniy-put-orientirovanniy-tsikl-kontur.html (дата обращения: 20.11.2021).
8. Теория графов – презентация, доклад, проект [Электронный ресурс]. URL: https://myslide.ru/presentation/skachat-teoriya-grafov (дата обращения: 20.11.2021).
9. Simulation and Comparison of Pathfinding Algorithms using Real Turkey Data. Publisher: IEEE. Muhammet ALKAN; Musa AYDIN.
10. Pathfinding of 2D & 3D game real-time strategy with depth direction A∗ algorithm for multi-layer. Publisher: IEEE. Khammapun Khantanapoka; Krisana Chinnasarn.
11. A comparative study on RIP and OSPF protocols. Publisher: IEEE. Megha Jayakumar; N Ramya Shanthi Rekha; B. Bharathi.
12. Deep Reinforcement Learning for Router Selection in Network With Heavy Traffic RUIJIN DING 1,2,3, YADONG XU4 , FEIFEI GAO 1,2,3 , XUEMIN SHEN 5, (Fellow, IEEE), AND WEN WU 5 1 Institute for Artificial Intelligence, Tsinghua University (THUAI), Beijing 100084, China.
13. Machine Learning (машинное обучение): что это такое [Электронный ресурс]. URL: https://www.bigdataschool.ru/wiki/machine-learning (дата обращения: 28.11.2021).
14. Machine Learning. Publisher: IEEE. Panos Louridas; Christof Ebert.
15. A Review on Machine Learning Styles in Computer Vision—Techniques and Future Directions. Publisher: IEEE. Supriya V. Mahadevkar; Bharti Khemani; Shruti Patil; Ketan Kotecha; Deepali R. Vora; Ajith Abraham; Lubna Abdelkareim Gabralla.
16. Обучение с подкреплением - Викиконспекты [Электронный ресурс]. URL: https://neerc.ifmo.ru/wiki/index.php?title=Обучение_с_подкреплением (дата обращения: 28.11.2021).
17. Reinforcement learning model, algorithms and its application. Publisher: IEEE. Wang Qiang; Zhan Zhongli.
18. A Gentle Introduction to Reinforcement Learning and its Application in Different Fields. Publisher: IEEE. Muddasar Naeem; Syed Tahir Hussain Rizvi; Antonio Coronato.
19. Динамическое программирование в примерах и задачах, Учебное пособие / Калихман И. Л., Войтенко М. А., 1979. – 129 с.
20. A survey of dynamic programming computational procedures. Publisher: IEEE. R. Larson.
21. Самообучающиеся AI-агенты
Данный алгоритм обучения с подкреплением хорошо работает только с полностью исследованными моделями окружающей среды с малым количеством состояний. Дело в том, что при повышении количество состояний среды количество необходимых вычислений расчет экспоненциально, соответственно метод динамического программирования для применения в решении большинства реальных задач не эффективен. Окружающий человека мир содержит бесконечное количество состояний, именно поэтому простейшие дискретные модели бесполезны в таких ситуациях. Алгоритмы обучения с подкреплением делятся на два больших класса: модельные (Model-Based) и безмодельные (Model-Free). Алгоритмы безмодельного обучения могут успешно решать различные задачи, например, играть в видеоигры и решать роботизированные задачи, но для достижения хорошей производительности требуется множество образцов. Алгоритмы на основе моделей могут быстро получить почти оптимальное управление, изучив модель в довольно ограниченном классе динамики. В этой ситуации знания об окружающей среде могут быть получены в неконтролируемой обстановке, даже в тех случаях, когда вознаграждение недоступно. Однако его недостатки заключаются в том, что большинство алгоритмов, основанных на моделях, изучают локальные модели, переобучая несколько выборок, полагаясь на простые функциональные аппроксиматоры, обычно одну мини-партию. [27]. Рассмотрим первую группу безмодельных алгоритмов - TD-обучение (Temporal Difference learning). К TD-обучению