Аналіз та можливість модифікації наявних алгоритмів пошуку оптимального шляху на квадратній сітці з використанням методів паралельного програмування

M. I. Shakhov, O. H. Baybuz

Анотація


Сформована постановка задачі пошуку оптимального шляху на неперервній місцевості шляхом її дискретизації за допомогою квадратної сітки. Проведений огляд та аналіз найпоширеніших алгоритмів планування шляху на квадратній сітці, які є різновидами алгоритму А*. У якості алгоритму пошуку оптимального шляху на квадратній сітці, що враховує фізичні обмеження безпілотного літального апарату, був обраний алгоритм 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.


Посилання

  • Поки немає зовнішніх посилань.


Контактна інформація:

Байбуз Олег Григорович - науковий редактор 

Тел: (056) 744-76-83

Україна, 49044, м. Дніпро, пр. Дмитра Яворницького, 35

--------------------------------------------------------------------

Дніпровський національний університет імені Олеся Гончара

National Library of Ukraine Vernadsky

Google Scholar

Open Academic Journals Index

Bielefeld Academic Search Engine

Open Archives

  Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.


Open Science in Ukraine - website development