Сравнительный анализ алгоритмов поиска оптимального пути
Автор: Султанова Ахира Бахман
Журнал: Бюллетень науки и практики @bulletennauki
Рубрика: Технические науки
Статья в выпуске: 12 т.6, 2020 года.
Бесплатный доступ
В данной статье рассмотрены широко используемые алгоритмы поиска оптимальных путей. В настоящее время существует довольно широкий список алгоритмов поиска кратчайшего пути, которые активно применяются в мобильной робототехнике для поиска оптимального маршрута. Предлагается двухуровневая система, осуществляющая планирование движения . Произведен сравнительный анализ различных методов поиска пути: их длины, сложности, числа точек поворота. Целью статьи является исследование и сравнительный анализ алгоритмов из области искусственного интеллекта для поиска кратчайшего пути в лабиринте и шестиугольная сетке. Изучаемые алгоритмы: A* (звезда), алгоритм Дейкстры, алгоритм BFS (Breadth first search), DFS (Depth First Search) и Greedy. Алгоритмы сравниваются по двум критериям: длина найденного пути и время нахождения пути. Результаты, представленные аналитически и графически, показывают применение пять алгоритмов для лабиринтов с различным размером и количеством препятствий.
Интеллектуальный робот, интеллектуальный интерфейс, система управления поведением, неопределенные среды, поиск пути, алгоритм дейкстры, алгоритм a*, алгоритм bfs, алгоритм dfs, алгоритм greedy
Короткий адрес: https://sciup.org/14117724
IDR: 14117724 | DOI: 10.33619/2414-2948/61/25
Список литературы Сравнительный анализ алгоритмов поиска оптимального пути
- Peri V. M., Simon D. Fuzzy logic control for an autonomous robot //NAFIPS 2005-2005 Annual Meeting of the North American Fuzzy Information Processing Society. IEEE, 2005. P. 337-342. DOI: 10.1109/NAFIPS.2005.1548558
- Van Den Berg J. et al. ANA*: anytime nonparametric A* // Proceedings of twenty-fifth AAAI conference on artificial intelligence (AAAI-11). 2011. V. 2. P. 1.
- Bnaya Z., Stern R., Felner A., Zivan R., Okamoto S. Multi-agent path finding for self interested agents // Sixth Annual Symposium on Combinatorial Search. 2013.
- Harabor D. D., Grastien A. Improving Jump Point Search // ICAPS. 2014.
- Uras T., Koenig S., Hernández C. Subgoal graphs for optimal pathfinding in eight-neighbor grids // Twenty-Third International Conference on Automated Planning and Scheduling. 2013.
- Björnsson Y., Enzenberger M., Holte R., Schaeffer J., Yap P. Comparison of different grid abstractions for pathfinding on maps // IJCAI. 2003. P. 1511-1512.
- Othman M. F., Samadi M., Asl M. H. Simulation of dynamic path planning for real-time vision-base robots // FIRA RoboWorld Congress. Springer, Berlin, Heidelberg, 2013. P. 1-10.
- DOI: 10.1007/978-3-642-40409-2_1
- Кудинов Ю. И. Нечеткие системы управления // Известия Академии наук. Техническая кибернетика. 1990. №5. С. 196-206.
- Niederberger C., Radovic D., Gross M. Generic path planning for real-time applications // Proceedings Computer Graphics International, 2004. IEEE, 2004. P. 299-306.
- DOI: 10.1109/CGI.2004.1309225
- Ma T., Yan Q., Liu W., Guan D., Lee S. Grid task scheduling: algorithm review // IETE Technical Review. 2011. V. 28. №2. P. 158-167.
- Burchardt H., Salomon R. Implementation of path planning using genetic algorithms on mobile robots // 2006 IEEE International Conference on Evolutionary Computation. IEEE, 2006. P. 1831-1836.
- DOI: 10.1109/CEC.2006.1688529
