Аналіз та можливість модифікації наявних алгоритмів пошуку оптимального шляху на квадратній сітці з використанням методів паралельного програмування
Анотація
Сформована постановка задачі пошуку оптимального шляху на неперервній місцевості шляхом її дискретизації за допомогою квадратної сітки. Проведений огляд та аналіз найпоширеніших алгоритмів планування шляху на квадратній сітці, які є різновидами алгоритму А*. У якості алгоритму пошуку оптимального шляху на квадратній сітці, що враховує фізичні обмеження безпілотного літального апарату, був обраний алгоритм LIAN. Були виявлені недоліки алгоритму LIAN та можливі шляхи їх вирішення, а також запропоновані варіанти його модифікації з використанням методів паралельного програмування.
Ключові слова
Повний текст:
PDFПосилання
Nash A., Daniel K., Koenig S., Felner, A. Theta*: Any-Angle Path Planning on Grids // Journal of Artificial Intelligence Research. 2010. N 39. P. 533–579.
Aurenhammer, F. Voronoi diagrams – a survey of a fundamental geometric data structure // ACM Computing Surveys. 1991. Vol. 23, Issue 3. P. 345–405.
Yahja A., Stentz A., Singh S., Brumitt B. Framed-quadtree path planning for mobile robots operating in sparse environments // In Proceedings of the International Conference on Robotics and Automation. 20-20 May 1998. P. 650–655.
Choset H., Lynch K., Hutchinson S., Kantor G., Burgard W., Kavraki L., Thrun S. Principles of Robot Motion: Theory, Algorithms, and Implementations // MIT Press. 2005.
Lozano-Pérez T., Wesley M. An algorithm for planning collision-free paths among polyhedral obstacles // Communication of the ACM. 1979. Vol. 22., N.10. P. 560–570.
Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE Transactions on Systems Science and Cybernetics. 1968. P. 100–107.
Thorpe C. Path relaxation: Path planning for a mobile robot // In Proceedings of the AAAI Conference on Artificial Intelligence. 1984. P. 318–321.
Kim H., Kim D., Shin J. U., Kim H., Myung H. Angular rate-constrained path planning algorithm for unmanned surface vehicles // Ocean Engineering. 2014. Vol. 84. P. 37–44.
Yakovlev K., Baskin E., Hramoin I. Grid-Based Angle-Constrained Path Planning // KI 2015: Advances in Artificial Intelligence. Lecture Notes in Computer Science. Springer International Publishing, Switzerland, 2015. P. 208–221.
DOI: http://dx.doi.org/10.15421/431809
Посилання
- Поки немає зовнішніх посилань.
Контактна інформація:
Байбуз Олег Григорович - відповідальний редактор
Тел: (056) 766-49-52
Mail: olegbaybuz68@gmail.com
Україна, 49010, м. Дніпро, пр. Гагаріна, 72
--------------------------------------------------------------------
Дніпровський національний університет імені Олеся Гончара
National Library of Ukraine Vernadsky
Bielefeld Academic Search Engine
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.