DOI: https://doi.org/10.32515/2664-262X.2025.12(43).1.31-43

Оптимальне планування маршрутів безпілотних літальних апаратів для ефективного покриття заданої території

М. Ф. Семенюта, С. М. Якименко, С. І. Осадчий

Про авторів

Семенюта Марина Фролівна, доцент, кандидат фізико-математичних наук, доцент кафедри вищої математики та фізики, Центральноукраїнський національний технічний університет, м. Кропивницький, Україна, ORCID: https://orcid.org/0000-0003-4639-0545, e-mail: semeniutamf@kntu.kr.ua.

Якименко Сергій Миколайович , доцент, кандидат фізико-математичних наук, завідувач кафедри вищої математики та фізики, Центральноукраїнський національний технічний університет, м. Кропивницький, Україна, ORCID: https://orcid.org/0000-0002-5759-9603, e-mail: yasm@i.ua

Осадчий Сергій Іванович , професор, доктор технічних наук, завідувач кафедри льотної експлуатації та безпеки польотів, Українська державна льотна академія, м. Кропивницький, Україна, ORCID: https://orcid.org/0000-0002-1811-3594, e-mail: srg2005@ukr.net

Анотація

Робота присвячена розв’язанню проблеми обльоту сонячних панелей при їх технічному обслуговуванні, яка є частинним випадком задачі комівояжера. Розглянуто алгоритми здатні швидко розраховувати маршрути без значного навантаження на обчислювальні ресурси. Розроблено програму, що реалізує описану математичну модель задачі. Експериментальні дослідження дозволили визначити ефективність задіяних алгоритмів.

Ключові слова

БПЛА, задача комівояжера, жадібний метод, 2-Opt алгоритм, мурашиний алгоритм, генетичний алгоритм, граф

Повний текст:

PDF

Посилання

1. Berezhnyi, A. O. (2020). Methods and information technology for automated flight route planning of unmanned aerial vehicles to improve object search efficiency. Candidate’s thesis. Kharkiv: Kharkiv National Air Force University named after Ivan Kozhedub [in Ukrainian].

2. Vadis, D., & Avrutov, V. (2024). Methods for improving the functional efficiency of UAVs. Mekhanika gyroskopichnykh system, 48, 55–68. https://doi.org/10.20535/0203-3771482024317891 [in Ukrainian].

3. Sonmez A., Kocyigit E., Kugu E. (2015). Optimal path planning for UAVs using genetic algoritm. International Conference on Unmanned Aircraft Systems (ICUAS). June 9-12, 2015. Denver Marriott Tech CenterDenver, Colorado, USA, 2015. P.50-55. DOI: 10.1109/ICUAS.2015.7152274

4. Wang H., Pan W. (2021) Research on UAV Path Planning Algorithms. 8-th Annual International Conference on Geo-Spatial Knowledge and Intelligence IOP Conf. Series: Earth and Environmental Science 693. 2021. DOI:10.1088/1755-1315/693/1/012120

5. Jiang Y., Xu X.-X., Zheng M.-Y., Zhan Z.-H. (2024). Evolutionary computation for unmanned aerial vehicle path planning: a survey. Artificial Intelligence Review. 2024 Vol. 57, № 10. DOI: 10.1007/s10462-024-10913-0

6. Vorotnikov V., Gumenyuk I., Pozdniakov P. (2017). Planning the flight routes of the unmanned aerial vehicle by solving the travelling salesman problem. Technology Audit and Production Reserves. №4/2(36) (2017)., 44–49. [in Ukrainian] DOI:10.15587/2312-8372.2017.108537.

7. Jones M., Djahel S., Welsh K. (2023). Path-Planning for Unmanned AerialVehicles with Environment Complexity Considerations: A Survey. ACM Computing Surveys. 2023. Vol. 55, № 11. P. 234:1-234:39. DOI:10.1145/3570723

8. Cabreira T. M., Brisolara L. B., Ferreira Jr. P. R. (2019). Survey on Coverage Path Planning with Unmanned Aerial Vehicles. Drones. 2019. Vol.3, № 1. DOI: 10.3390/drones3010004

9. Semeniuta, M.F., Osadchy, S.I., & Chesak, O. (2024). A systems approach to area monitoring using a swarm of UAVs. In Modern problems and achievements in radio engineering, telecommunications and information technologies: Abstracts of the 12th International Scientific and Practical Conference (Zaporizhzhia, December 10–12, 2024), (pp. 459–463). Zaporizhzhia: National University “Zaporizhzhia Polytechnic”. [in Ukrainian].

10. Hulianytskyi, L.F., & Rybalchenko, O.V. (2023). Route optimization in planning missions of hybrid transport systems “drone + vehicle”. Kibernetyka ta kompiuterni tekhnolohii, 3, 44–58. [in Ukrainian]. DOI: 10.34229/2707-451X.23.3.4

11. Uddin F., Riaz N., Manan A., Mahmood I., Song Oh-Y., Malik A. J., Abbasi A. A. (2023). An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour. Applied Sciences. Vol. 13(12) (2023). DOI: 10.3390/app13127339

12. Lin S., Kernighan B.W. An effective heuristic algorithm for the travelling salesman problem. Operations Research. 1973. Vol. 21, № 2. P. 498–516. https://www.cs.princeton.edu/~bwk/btl.mirror/tsp.pdf

13. Ahmed M. R., Shibli A. A.l, Marhaban M. H., Kaiser M. S., Myo T., Albroumi B. (2023). Ant Colony Optimization-Based Path Planning for UAV Navigation in Dynamic Environments. The 7-th International Conference on Automation, Control and Robots (ICACR) August 4-6 2023, Kuala Lumpur, Malaysia,. 2023. P.168-173.

14. Murugananthan V., Rehan M. Y. E. S., Srinivasan R., Kavitha M., Kavitha R. (2023). Traveling Salesman Problem with Ant Colony Optimization. 2-nd International Conference on Edge Computing and Applications (ICECAA). 2023. DOI: 10.1109/ICECAA58104.2023.10212262

15. Flores-Caballero G., Rodríguez-Molina A., Aldape-Pérez M., Villarreal-Cervantes M. G. (2020). Optimized Path-Planning in Continuous Spaces for Unmanned Aerial Vehicles Using Meta-Heuristics. IEEE Access. Vol.8. 2020. P.176774-176788. DOI: 10.1109/ACCESS.2020.3026666

16. Yin Y., Wang Z., Zheng L., Su Q., Guo Y. (2014). Autonomous UAV Navigation with Adaptive Control Based on Deep Reinforcement Learning. Electronics. 2024, 13(13). DOI: 10.3390/electronics13132432

17. Bose S., Maheswaran N., Logeswari G., Anitha T., Prabhu D., Gokulraj G. (2024). Adaptive Deep Learning Techniques for Real-Time Shortest Path Optimization in Drone Ambulance Operations during Disaster. 8th International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I- SMAC). DOI: 10.1109/I-SMAC61858.2024.10714626.

18. Zhang C., Feng Q. (2020). Research on UAV Path Planning Combined with Ant Colony and A*. IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). 2020. DOI: 10.1109/ITNEC48623.2020.9084730.

Пристатейна бібліографія ГОСТ

1. Бережний А. О. Методи та інформаційна технологія автоматизованого планування маршрутів польотів безпілотних літальних апаратів для підвищення ефективності пошуку об’єктів: дис. на здобуття наукового ступеня канд. техн. наук: 05.13.06 / Харківський національний університет Повітряних Сил імені Івана Кожедуба, Харків, 2020. 192 с.

2. Вадіс Д., Аврутов В. Методи підвищення функціональної ефективності БПЛА. Механіка гіроскопічних систем: науково-технічний збірник. 2024. Вип. 48. С.55-68. URL: https://doi.org/10.20535/0203-3771482024317891

3. Sonmez A., Kocyigit E., Kugu E. (2015). Optimal path planning for UAVs using genetic algoritm. International Conference on Unmanned Aircraft Systems (ICUAS). June 9-12, 2015. Denver Marriott Tech CenterDenver, Colorado, USA, 2015. P.50-55. DOI: 10.1109/ICUAS.2015.7152274

4. Wang H., Pan W. (2021) Research on UAV Path Planning Algorithms. 8-th Annual International Conference on Geo-Spatial Knowledge and Intelligence IOP Conf. Series: Earth and Environmental Science 693. 2021. DOI:10.1088/1755-1315/693/1/012120

5. Jiang Y., Xu X.-X., Zheng M.-Y., Zhan Z.-H. (2024). Evolutionary computation for unmanned aerial vehicle path planning: a survey. Artificial Intelligence Review. 2024 Vol. 57, № 10. DOI: 10.1007/s10462-024-10913-0

6. Vorotnikov V., Gumenyuk I., Pozdniakov P. (2017). Planning the flight routes of the unmanned aerial vehicle by solving the travelling salesman problem. Technology Audit and Production Reserves. №4/2(36) (2017)., 44–49. [in Ukrainian] DOI:10.15587/2312-8372.2017.108537.

7. Jones M., Djahel S., Welsh K. (2023). Path-Planning for Unmanned AerialVehicles with Environment Complexity Considerations: A Survey. ACM Computing Surveys. 2023. Vol. 55, № 11. P. 234:1-234:39. DOI:10.1145/3570723

8. Cabreira T. M., Brisolara L. B., Ferreira Jr. P. R. (2019). Survey on Coverage Path Planning with Unmanned Aerial Vehicles. Drones. 2019. Vol.3, № 1. DOI: 10.3390/drones3010004

9. Семенюта М.Ф., Осадчий С.І., Чесак О. Системний підхід до моніторингу територій з використанням рою БПЛА. Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій: тези доповідей ХІІ Міжнар. наук.-практ. конф., 10-12 грудня 2024. р., м. Запоріжжя. [Електронний ресурс] /Електрон. дані. – Запоріжжя: НУ «Запорізька політехніка», 2024. С. 459-463.

10. Гуляницький Л.Ф., Рибальченко О.В. Оптимізація маршрутів при плануванні місій гібридних транспортних систем «дрон+транспортний засіб». Кібернетика та комп'ютерні технології. 2023. №3 (2023). С. 44–58. DOI: 10.34229/2707-451X.23.3.4

11. Uddin F., Riaz N., Manan A., Mahmood I., Song Oh-Y., Malik A. J., Abbasi A. A. (2023). An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour. Applied Sciences. Vol. 13(12) (2023). DOI: 10.3390/app13127339

12. Lin S., Kernighan B.W. An effective heuristic algorithm for the travelling salesman problem. Operations Research. 1973. Vol. 21, № 2. P. 498–516. https://www.cs.princeton.edu/~bwk/btl.mirror/tsp.pdf

13. Ahmed M. R., Shibli A. A.l, Marhaban M. H., Kaiser M. S., Myo T., Albroumi B. (2023). Ant Colony Optimization-Based Path Planning for UAV Navigation in Dynamic Environments. The 7-th International Conference on Automation, Control and Robots (ICACR) August 4-6 2023, Kuala Lumpur, Malaysia, 2023. P.168-173.

14. Murugananthan V., Rehan M. Y. E. S., Srinivasan R., Kavitha M., Kavitha R. (2023). Traveling Salesman Problem with Ant Colony Optimization. 2-nd International Conference on Edge Computing and Applications (ICECAA). 2023. DOI: 10.1109/ICECAA58104.2023.10212262

15. Flores-Caballero G., Rodríguez-Molina A., Aldape-Pérez M., Villarreal-Cervantes M. G. (2020). Optimized Path-Planning in Continuous Spaces for Unmanned Aerial Vehicles Using Meta-Heuristics. IEEE Access. Vol.8. 2020. P.176774-176788. DOI: 10.1109/ACCESS.2020.3026666

16. Yin Y., Wang Z., Zheng L., Su Q., Guo Y. (2014). Autonomous UAV Navigation with Adaptive Control Based on Deep Reinforcement Learning. Electronics. 2024, 13(13). DOI: 10.3390/electronics13132432

17. Bose S., Maheswaran N., Logeswari G., Anitha T., Prabhu D., Gokulraj G. (2024). Adaptive Deep Learning Techniques for Real-Time Shortest Path Optimization in Drone Ambulance Operations during Disaster. 8th International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I- SMAC). DOI: 10.1109/I-SMAC61858.2024.10714626.

18. Zhang C., Feng Q. (2020). Research on UAV Path Planning Combined with Ant Colony and A*. IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). 2020. DOI: 10.1109/ITNEC48623.2020.9084730.


Copyright (c) 2025 М. Ф. Семенюта, С. М. Якименко, С. І. Осадчий