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

M. I. Shakhov; O. H. Baybuz

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

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 Artiﬁcial 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.