Вестник КРАУНЦ. Физ.-мат. науки. 2020. Т. 31. № 2. C. 70-78. ISSN 2079-6641

Содержание выпуска/Contents of this issue

Научная статья

УДК 51-74

Планирование траектории группы беспилотных летательных
аппаратов с использованием годографа Пифагора и составных кривых Бернштейна-Безье на плоскости

Д. Л. Винокурский, К.Ю. Ганьшин, О. С. Мезенцева, Ф. В. Самойлов

Северо-Кавказский Федеральный Университет, 355017, г. Ставрополь, ул. Пушкина, 1

E-mail: info@ncfu.ru

В работе представлен метод построения траектории движения группы беспилотных летательных аппаратов (БПЛА) апроксимацией годографа Пифагора составными многочленами Бернштейна-Безье на плоскости.

Ключевые слова: беспилотный летательный аппарат, многочлены БернштейнаБезье, годограф Пифагора.

DOI: 10.26117/2079-6641-2020-31-2-70-78

Поступила в редакцию: 22.05.2020

В окончательном варианте: 05.06.2020

Для цитирования. Винокурский Д. Л., Ганьшин К. Ю., Мезенцева О. С., Самойлов Ф.В Планирование траектории группы беспилотных летательных аппаратов с использованием годографа Пифагора и составных кривых Бернштейна-Безье на плоскости // Вестник КРА-
УНЦ. Физ.-мат. науки. 2020. Т. 31. № 2. C. 70-78. DOI: 10.26117/2079-6641-2020-31-2-70-78

Конкурирующие интересы. Авторы заявляют, что конфликтов интересов в отношении авторства и публикации нет.
Авторский вклад и ответсвенность. Все авторы участвовали в написании статьи и полностью несут ответственность за предоставление окончательной версии статьи в печать. Окончательная версия рукописи была одобрена всеми авторами.

Контент публикуется на условиях лицензии Creative Commons Attribution 4.0 International (https://creativecommons.org/licenses/by/4.0/deed.ru)

© Винокурский Д. Л. и др., 2020

Список литературы (ГОСТ)

  1. Kolushev A., Bodanov A. Multiple-Agent Optimal Path Planning for Mobile Robot in Environment with Obstacles // Proceedings of the third international Andrei Ershov memorial conference on Perspective System Informatics. 1999. pp. 503-510.
  2. Tarapata Z. Military Route Planning in Battle Field Simulation, Effectiveness Problem and Potential Solution // Proceeding of 4th WSEAS international conference on Computer Engineering and Application CEA 10. 2003. pp. 47-56.
  3. Hart P., Nilsson N. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // Syst Sci Cybern. 1968. no. 2. pp. 100-107.
  4. Yang D., Hong S. Road Map Construction Algorithm for Mobile Robot Path Planning using Skeleton Map // Advance Robotic. 2007. vol. 21. pp. 51-63.
  5. Tokuta A. Extending the Visibility Graph Algorithm for Robot Path Planning // Technical Report Department of Mathematics and Computer Science.
  6. Santos R., Steffen V. Robot Path Planning in Constrained Work Space using Optimal Control Techniques // Multibody System Dynamics. 2006. pp. 159-177.
  7. Constantinescu D., Croft E. Robot Smooth and Time Optimal Trajectory Planning for Industrial Manipulators along Specified Paths // J. Robotics syst. 2000. vol. 17. pp. 223-249.
  8. Vukdbralovic M., Kircanski M. One Method for simplified Manipulator Model Construction and its Application in Quazioptimal Trajectory Synthesis // Mechanism and Machine Theory. 1982. vol. 17. pp. 369-378.
  9. Pfeifer F., Johanni A. Concept for Manipulator Trajectory Planning. IEEE Trans // IEEE Trans Robotic Automat. 1987. vol. 3(3). pp. 115-123.
  10. Singh S., Leu C. Optimal Trajectory Generation for Robot Manipulators Using Dynamic Programming // J. Dyn. Sys. Meas Control. 1987. vol. 109. no. 2. pp. 88-96.
  11. Lee M., Takagi H. Integrating Design Stages of Fuzzy Systems Using Genetic Algortithms // Proc. 2nd IEEE Int. Conf. Fuzzy Systems, San Francisco. 1993. pp. 612-617.
  12. Belarbi K., Titel F. Genetic algorithm for the design of a class of fuzzy controllers: An alternative approach // IEEE Transactions on Fuzzy Systems. 2000. no. 8. pp. 398-405.
  13. Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. United States: Addison-Wesley Longman Publishing, 1989. 372 p.
  14. Whitley D. A Genetic Algorithm Tutorial // Technical Report CS-93-103, Dept. of Computer Science, Colorado State University. 1994. pp. 65-85.
  15. Subchan S., White B. et al. Pythagorean Hodograph (PH) path planning for tracking airborne contaminant using sensor swarm // Instrumentation and Measurement Technology Conference Proceeding, 2008. pp. 501-506.
  16. Armando A., Campos F. A Path Planning Algorithm for UAVs with Limited Climb Angle // The 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems October 11-15, 2009 St. Louis, US. 2009.
  17. Farouki R., Sakkalis T. Pythagorean hodographs // IBM Journal of Research and Development. 1990. no. 5. pp. 736-752.
  18. Farouki R., Neff C. Hermite interpolation by Pythagorean hodograph quintics // Mathematics of Computation. 1995. pp. 1589-1609.
  19. Moon H., Farouki C. et al. Construction and shape analysis of PH quintic Hermite interpolants // Comput. Aided Geom. Design. 2001. no. 2. pp. 93-115.
  20. Farouki R. The elastic bending energy of Pythagorean hodograph curves // Comput. Aided Geom. Design. 1996. no. 2. pp. 227-241.
  21. Григорьев М., Малоземов В. Полиномы Бернштейна и составные кривые Безье // Ж. вычисл. матем. и матем. физ. 2006. C. 1962–1971
  22. Kozak J., Knez M. et al. On interpolation by planar cubic G2 Pythagorean-hodograph spline curves // Mathematics of Computation. 2010. pp. 305–326.
  23. Singh I., Achille M. et al. Modeling of Continuum Manipulators Using Pythagorean Hodograph Curves // Soft Robotics. 2018
  24. Dhulkefl E., Durdu A. et al. Path Planning Algorithms for Unmanned Aerial Vehicles // International Journal of Trend in Scientific Research and Development. 2019. vol. 4. no 3. pp. 359–362.
  25. Wang X., Meng X. et al. UAV Online Path Planning Based on Improved Genetic Algorithm // Chinese Control Conference (CCC), Guangzhou. 2019. pp. 4101-4106.
  26. Wu C., Chiu Z. et al. Time-Optimal Trajectory Planning along Parametric Polynomial Lane-Change Curves with Bounded Velocity and Acceleration: Simulations for a Unicycle Based on Numerical Integration // Modelling and Simulation in Engineering. 2018. pp. 1-19.
  27. Ma J., Liu Y. et al. Robot Path Planning Based on Genetic Algorithm Fused with Continuous Bezier Optimization // Comput Intell Neurosci. 2020. pp. 1-10.

Research Article

MSC 65D07

The planning of the trajectory of UAV group with the performance of Pythagorean Hodograph and Bernstein-Bezier composite curves in the plane

D. L. Vinokursky, K. Y. Ganshin, O. S. Mezentseva, Ph. V. Samoylov

Federal State Autonomous Educational Institution for Higher Education «North-Caucasus Federal University Stavropol, 355017, Pushkin st.1, Russia
E-mail: info@ncfu.ru

In this article, the method of trajectory building of motion of unmanned aerial vehicles group by approximation of Pythagorean Hodograph and Bernstein-Bezier composite polynomials has been presented.

Key words: unmanned aerial vehicles, Bernstein-Bezier polynomial, Pythagorean Hodograph

DOI: 10.26117/2079-6641-2020-31-2-70-78

Original article submitted: 22.05.2020

Revision submitted: 05.06.2020

For citation. Vinokursky D. L., Ganshin K.Y., Mezentseva O. S., Samoylov Ph.V. The planning of the trajectory of UAV group with the performance of Pythagorean Hodograph and Bernstein-Bezier composite curves in the plane.Vestnik KRAUNC. Fiz.-mat. nauki. 2020, 31: 2, 70-78. DOI: 10.26117/2079-6641-2020-31-2-70-78

Competing interests. The authors declare that there are no conflicts of interest regarding authorship and publication.
Contribution and Responsibility. All authors contributed to this article. Authors are solely responsible for providing the final version of the article in print. The final version of the manuscript was approved by all authors.

The content is published under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/deed.ru)

© Vinokursky D. L. et al, 2020

Список литературы/References

  1. Kolushev A., Bodanov A., “Multiple-Agent Optimal Path Planning for Mobile Robot in Environment with Obstacles”, Proceedings of the third international Andrei Ershov memorial conference on Perspective System Informatics, 1999, 503-510.
  2. Tarapata Z., “Military Route Planning in Battle Field Simulation, Effectiveness Problem and Potential Solution”, Proceeding of 4th WSEAS international conference on Computer Engineering and Application CEA 10., 2003, 47-56.
  3. Hart P., Nilsson N., “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, Syst Sci Cybern, 2 (1968), 100-107.
  4. Yang D., Hong S., “Road Map Construction Algorithm for Mobile Robot Path Planning using Skeleton Map”, Advance Robotic, 21 (2007), 51-63.
  5. Tokuta A., “Extending the Visibility Graph Algorithm for Robot Path Planning”, Technical Report Department of Mathematics and Computer Science.
  6. Santos R., Steffen V., “Robot Path Planning in Constrained Work Space using Optimal Control Techniques”, Multibody System Dynamics, 2006, 159-177.
  7. Constantinescu D., Croft E., “Robot Smooth and Time Optimal Trajectory Planning for Industrial Manipulators along Specified Paths”, J. Robotics syst., 17 (2000), 223-249.
  8. Vukdbralovic M., Kircanski M., “One Method for simplified Manipulator Model Construction and its Application in Quazioptimal Trajectory Synthesis”, Mechanism and Machine Theory, 17 (1982), 369-378.
  9. Pfeifer F., Johanni A., “Concept for Manipulator Trajectory Planning. IEEE Trans”, IEEE Trans Robotic Automat 3(3), 1987, 115-123.
  10. Singh S., Leu C., “Optimal Trajectory Generation for Robot Manipulators Using Dynamic Programming”, J. Dyn. Sys. Meas Control 109 (2), 1987, 88-96.
  11. Lee M., Takagi H., “Integrating Design Stages of Fuzzy Systems Using Genetic Algortithms”, Proc. 2nd IEEE Int. Conf. Fuzzy Systems, San Francisco, 1993, 612-617.
  12. Belarbi K., Titel F., “Genetic algorithm for the design of a class of fuzzy controllers: An alternative approach”, IEEE Transactions on Fuzzy Systems, 8 (2000), 398-405.
  13. Goldberg D., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc.75 Arlington Street, Suite 300 Boston, MAUnited States, 1989, 372 p.
  14. Whitley D., A Genetic Algorithm Tutorial, Technical Report CS-93-103, Dept. of Computer Science, Colorado State University., 1994.
  15. Subchan S., White B. et al., “Pythagorean Hodograph (PH) path planning for tracking airborne contaminant using sensor swarm.”, Instrumentation and Measurement Technology Conference Proceeding 2008, IMTC 2008, 2008, 501-506.
  16. Armando A., Campos F., “A Path Planning Algorithm for UAVs with Limited Climb Angle”, The 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems October 11-15, 2009 St. Louis, US, 2009.
  17. Farouki R., Sakkalis T., “Pythagorean hodographs”, IBM Journal of Research and Development, 1990, №5, 736-752.
  18. Farouki R., Neff C., “Hermite interpolation by Pythagorean hodograph quintics”, Mathematics of Computation, 1995, 1589-1609.
  19. Moon H., Farouki C. et al., “Construction and shape analysis of PH quintic Hermite interpolants”, Comput. Aided Geom. Design., 2001, №2, 93-115.
  20. Farouki R., “The elastic bending energy of Pythagorean hodograph curves”, Comput. Aided Geom. Design., 1996, №2, 227-241.
  21. Григорьев М., Малоземов В., “Полиномы Бернштейна и составные кривых Безье”, Ж. вычисл. матем. и матем. физ., 2006, 1962–1971. [Grigor’ev M., Malozemov V., “Polinomy Bernshteyna i sostavnye krivykh Bez’e.”, Zh. vychisl. matem. i matem. fiz., 2006, 1962–1971].
  22. Kozak J., Knez M. et al., “On interpolation by planar cubic G2 Pythagorean-hodograph spline curves”, Mathematics of Computation, 2010, 305–326.
  23. Singh I., Achille M. et al., “Modeling of Continuum Manipulators Using Pythagorean Hodograph Curves”, Soft Robotics, 2018.
  24. Dhulkefl E., Durdu A. et al., “Path Planning Algorithms for Unmanned Aerial Vehicles”, International Journal of Trend in Scientific Research and Development, 3:4 (2019), 359–362.
  25. Wang X., Meng X. et al., “UAV Online Path Planning Based on Improved Genetic Algorithm”, 2019 Chinese Control Conference (CCC), Guangzhou, 2019, 4101-4106.
  26. Wu C., Chiu Z. et al., “Time-Optimal Trajectory Planning along Parametric Polynomial Lane-Change Curves with Bounded Velocity and Acceleration: Simulations for a Unicycle Based on Numerical Integration”, Modelling and Simulation in Engineering, 2018, 1-19.
  27. Ma J., Liu Y. et al., “Robot Path Planning Based on Genetic Algorithm Fused with Continuous Bezier Optimization”, Comput Intell Neurosci, 2020, 1-10

Винокурский Дмитрий Леонидович – кандидат физико-математических наук, доцент, доцент кафедры информаионных систем и технологий, Институт информационных технологий и телекоммуникаций «Северо-Кавказский федеральный университет», г. Ставрополь, Россия, ORCID 0000-0002-5225-8076.

Vinokursky Dmitry Leonidovich – Ph.D. (Phys. & Math.), Associate Professor, docent of Chair of Information Systems and Technologies, Institute of Information Technologies and Telecommunications «North-Caucasus Federal University Stavropol, Russia, ORCID: 0000-0002-5225-8076.

Ганьшин Константин Юрьевич – аспирант кафедры информационных систем и технологий, Институт информационных технологий и телекоммуникаций «Северо-Кавказский федеральный университет», г. Ставрополь, Россия, ORCID: 0000-0001-7495-0736.

Ganshin Konstantit Yuryevich – graduate student, Chair of Information Systems and Technologies, Institute of Information Technologies and Telecommunications «North-Caucasus Federal University Stavropol, Russia, ORCID: 0000-0001-7495-0736.

Мезенцева Оксана Станиславовна – кандидат физико-математических наук, доцент, профессор кафедры информационных систем и технологий, Институт информационных технологий и телекоммуникаций ФГАОУ ВО «Северо-Кавказский федеральный университет», г. Ставрополь, Россия, ORCID 0000-0001-5503-1056.

Mezentseva Oksana Stanislavovna – Ph.D. (Phys. & Math.) Associate Professor, Professor of the Department of Information Systems and Technologies, Institute of Information Technologies and Telecommunications FSAEI HE «North-Caucasus Federal University Stavropol, Russia, ORCID 0000-0001-5503-1056.

Самойлов Филипп Владимирович – аспирант кафедры информационных систем и технологий, Институт информационных технологий и телекоммуникаций ФГАОУ ВО «Северо-Кавказский федеральный университет», г. Ставрополь, Россия, ORCID 0000-0003-3555-4479.

Samoilov Philipp Vladimirovich – Graduate student, Chair of Information Systems and Technologies, Institute of Information Technologies and Telecommunications FSAEI HE «North-Caucasus Federal University Stavropol, Russia, ORCID 0000-0003-3555-4479.

Читать статью/Read articleСкачать/Download