Тип работы:
Предмет:
Язык работы:


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

Работа №161425

Тип работы

Бакалаврская работа

Предмет

математика

Объем работы46
Год сдачи2024
Стоимость4750 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
0
Не подходит работа?

Узнай цену на написание


Введение 3
1. Обзор 4
1.1. Предварительные сведения о задаче 4
1.2. Обзор литературы 5
2. Формальная постановка задачи 9
3. Методы 11
3.1. Алгоритм A* 11
3.2. WA* 12
3.3. Focal Search и GBFS 14
3.4. TurnA* 16
3.5. PGM и FocalTurnA* 17
4. Обучение 19
4.1. Архитектура модели 19
4.2. Датасет 22
4.3. Сетап и обучение 26
5. Эксперименты 29
6. Выводы по результатам экспериментального исследования 41
Заключение 43
Список литературы 44


Нахождение кратчайшего пути в графе - классическая задача, актуальная и на сегодняшний день. В век развития технологий эта задача нашла применение в самых различных сферах: транспортная навигация, робототехника, сети связи и многие другие. Особенно возрастает потребность уметь решать эту задачу для мобильных агентов. Планирование оптимальной траектории агента поможет в обеспечении безопасно сти, эффективности и точности перемещения.
Классический алгоритм A*, решающий эту задачу, во многом опирается на значения эвристических функций, которые зачастую являются функциями расстояния. Основная проблема этих эвристик в том, что они являются независимыми от экземпляра, то есть не учитывают препятствия и особенности карты, на которой осуще ствляется поиск.
Также, алгоритм A* обычно используют на графах, не учитывающих мобильные ограничения агента. Агент не является материальной точкой и не умеет скользить между вершинами. На этапе планирования хотелось бы принимать во внимание, что агенту придется поворачивать во время прохождения пути.
Для решения этих проблем и построения оптимальной траектории мобильного агента также могут помочь современные методы машинного обучения. Они активно используются в задаче нахождения кратчайшего пути и могут значительно улучшить поиск.
Целью данной дипломной работы является повышение эффективности планирования траектории мобильного агента. Для этого был разработан модифицированный алгоритм поиска TurnA* и создан метод построения зависимых от экземпляра эвристик на основе моделей машинного обучения. По результатам экспериментального исследования, с помощью этих эвристик удалось добиться улучшений в решении поставленной задачи.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!


В данной работе была исследована задача планирования траектории мобильного агента, и изучены современные подходы к ее решению. Формально поставлена задача о построении оптимального пути мобильного агента с поворотами, и созданы алгоритмы TurnA* и FocalTurnA* - модификации алгоритмов A* и Focal Search соответственно.
Был создан датасет, включающий в себя карты с разными топологиями местности, пары стартов и целей, а также истинные значения Path Guidance Maps - второстепенных эвристик для алгоритма FocalTurnA*.
Были созданы и обучены модели PGM_64 и PGM_128, с использованием архитектуры трансформера, по предсказанию PGM для карт размеров 64х64 и 128x128.
По результатам экспериментов были сделаны следующие выводы:
Алгоритмы FocalTurnA* и GBFS, использующие предсказания моделей в качестве второстепенной эвристики, показали существенные улучшения по числу шагов, числу раскрытых вершин и времени поиска кратчайшего пути, однако в картах 128х128 процент найденных оптимальных решений не слишком высок. Для более эффективной работы алгоритма FocalTurnA* следует выбирать вес, не меньший 1,5. На основании отслеживаемых метрик и времени решения батча из 128 задач, алгоритм GBFS в среднем показывает себя лучше, чем FocalTurnA*. Планировщики, использующие предсказания моделей, добились метрик, относительно близких к своим идеальным версиям, использующим истинные значения, но качество этих предсказаний все еще можно улучшить.
GITHUB: HTTPS://GITHUB.COM/MARKPERMYAK/TURNASTAR



[1] Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs”. Numerische Mathematik, 7(1), 269-271.
[2] Hart, P., Nilsson, N., & Raphael, B. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107
[3] Pohl, I. 1970. “Heuristic search viewed as path finding in a graph”. Artificial intelligence, 1(3-4): 193-204
[4] Pearl, J.; and Kim, J. H. 1982. “Studies in semi-admissible heuristics”. IEEE transactions on pattern analysis and machine intelligence, (4): 392-399.
[5] Pohl, I. 1969. “Bidirectional Heuristic Search in Path Problems”. Ph.D. Dissertation, Stanford University
[6] Richard E. Korf. “Depth-first iterative-deepening: An optimal admissible tree search”, Artificial Intelligence, Volume 27, Issue 1, 1985,
[7] Daniel, K. and Nash, A. and Koenig, S. and Felner, A. 2010. “Theta*: Any-Angle Path Planning on Grids”. Journal of Artificial Intelligence Research, Volume 39.
[8] D. Harabor and A. Grastien. 2011. “Online Graph Pruning for Pathfinding on Grid Maps”. In Proceedings of the 25th National Conference on Artificial Intelligence (AAAI), San Francisco, USA.
[9] L. E. Kavraki, P Svestka, J.-C. Latombe, and M. H. Overmars. “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” TRA, 12(4): 566-580, 1996
[10] S. M. LaValle and J. J. Kuffner Jr.. “Randomized kinodynamic planning,” IJRR, 20(5): 378-400, 2001.
[11] S. Karaman and E. Frazzoli. “Sampling-based algorithms for optimal motion planning,” IJRR, 30(7): 846-894, 2011.
[12] Gammell, Jonathan D. and Srinivasa, Siddhartha S. and Barfoot, Timothy D.. “Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs”, 2015 IEEE International Conference on Robotics and Automation (ICRA 2015), pp. 3067-3074.
[13] Takahashi, T.; Sun, H.; Tian, D.; and Wang, Y. 2019. “Learning heuristic functions for mobile robot path planning using deep neural networks”. In Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), 764-772.
[14] Binghong Chen, Chengtao Li, Hanjun Dai, Le Song 2020. “Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search”, presented at ICML 2020.
[15] Yonetani, R.; Taniai, T.; Barekatain, M.; Nishimura, M.; and Kanezaki, A. 2021. “Path planning using neural A* search”. In Proceedings of the 38th International Conference on Machine Learning (ICML 2021), 12029-12039.
[16] Li, Z.; Chen, Q.; and Koltun, V. 2018. “Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search”.
[17] Bhardwaj, M.; Choudhury, S.; and Scherer, S. 2017. “Learning heuristic search via imitation”. In Proceedings of the 1st Conference on Robot Learning (CoRL 2017), 271-280.
[18] Sanjiban Choudhury, Mohak Bhardwaj, Sankalp Arora, Ashish Kapoor, Gireeja Ranade, Sebastian Scherer, Debadeepta Dey, 2017. “Data-driven Planning via Imitation Learning”.
[19] Edward Groshev, Maxwell Goldstein, Aviv Tamar, Siddharth Srivastava, Pieter Abbeel, 2017. “Learning Generalized Reactive Policies using Deep Neural Networks”.
[20] Leah Chrestien, Tomas Pevny, Antonin Komenda, Stefan Edelkamp, 2021. “Heuristic Search Planning with Deep Neural Networks using Imitation, Attention and Curriculum Learning”.
[21] Michal Pandy, Weikang Qiu, Gabriele Corso, Petar Velickovic, Rex Ying, Jure Leskovec, Pietro Lid, 2022. “Learning Graph Search Heuristics”.
[22] Daniil Kirilenko, Anton Andreychuk, Aleksandr Panov, Konstantin Yakovlev. “TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers”. Proceedings of the AAAI Conference on Artificial Intelligence. 37, 10 (Jun. 2023), 12436-12443
[23] Fukushima, Kunihiko (1980). "Neocognitron: A Self-organizing Neural Network Model for a Mechanism of Pattern Recognition Unaffected by Shift in Position". Biological Cybernetics. 36 (4): 193-202.
[24] He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016. “Deep Residual Learning for Image Recognition”. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
[25] Yuxin Wu and Kaiming He, “Group Normalization”, 2018.
[26] Prajit Ramachandran and Barret Zoph and Quoc V. Le, “Searching for Activation Functions”, 2017.
[27] Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, E.; and Polosukhin, I. 2017. “Attention is all you need”. Advances in neural information processing systems, 30.
[28] Jimmy Lei Ba and Jamie Ryan Kiros and Geoffrey E. Hinton, “Layer Normalization”, 2016.
[29] Diederik P Kingma, Jimmy Ba. “Adam: A Method for Stochastic Optimization”, 2014
[30] Sturtevant, N. R. 2012. Benchmarks for Grid-Based Pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 4(2): 144-148.


Работу высылаем на протяжении 30 минут после оплаты.




©2025 Cервис помощи студентам в выполнении работ