Задача максимізації зваженої кількості об’єктів, обстежених дроном
DOI:
https://doi.org/10.25140/2411-5363-2025-1(39)-134-150Ключові слова:
дрон; БПЛА; максимізація кількості обстежених об'єктів; планування траєкторії; дискретизація; комбінаторна оптимізація; жадібний алгоритм; частковий перебір; евристичний методАнотація
У сучасних умовах розвитку безпілотних технологій актуальними є задачі планування траєкторій дронів з максимальним охопленням об’єктів. Задача полягає в побудові прямої, яка перетинає найбільш значущі об’єкти на площині. Через неперервність простору прямих і дискретність розташування цілей застосовано дискретизацію. Метою роботи є розробка та порівняльний аналіз трьох підходів: жадібного алгоритму, часткового перебору секторів і евристичного методу. Проведено математичне обґрунтування, визначено критерії охоплення об’єктів, оцінено складність і ефективність методів. Результати показали: жадібний алгоритм демонструє найменший час виконання, але є менш точним; евристичний забезпечує баланс між точністю й швидкістю; частковий перебір – найточніший, але найповільніший. Задача може бути використана як компонент у складніших моделях планування місій дронів.
Посилання
Galceran, E., & Carreras, M. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12), 1258–1276. https://doi.org/10.1016/j.robot.2013.09.004.
Chung, T. H., Hollinger, G. A., & Isler, V. (2011). Search and pursuit-evasion in mobile robotics. Autonomous Robots, 31(4), 299–316. https://doi.org/10.1007/s10514-011-9231-8.
Dhillon, S. S., & Smith, J. (2003). Wireless communication coverage using autonomous UAVs. IEEE Transactions on Aerospace and Electronic Systems, 39(2), 152–165. https://doi.org/10.1109/ TAES.2003.1205972.
Hu, J., Zhang, L., & Wang, J. (2020). Drone-based environmental monitoring: An overview of recent developments. Remote Sensing, 12(4), 687. https://doi.org/10.3390/rs12040687.
Stachniss, C., Leonard, J. J., & Thrun, S. (2008). Simultaneous localization and mapping (SLAM): A survey of current trends. IEEE Transactions on Robotics, 24(5), 1050–1067. https://doi.org/ 10.1109/TRO.2008.2005913.
Isler, V., & Bajcsy, R. (2005). The sensor selection problem for surveillance applications. IEEE Transactions on Systems, Man, and Cybernetics, 35(4), 639–648. https://doi.org/10.1109/ TSMCB.2005.850150.
Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research, 30(7), 846–894. https://doi.org/10.1177/ 0278364911406761.
LaValle, S. M. (2006). Planning algorithms. Cambridge University Press. https://doi.org/1 0.1017/CBO9780511546877.
Richards, A., & How, J. P. (2002). Aircraft trajectory planning with collision avoidance using mixed-integer linear programming. AIAA Guidance, Navigation, and Control Conference, 1(1), 221–238. https://doi.org/10.2514/6.2002-4588.
Lin, L., Wu, Y., & Duan, H. (2018). UAV swarm intelligence for cooperative search and tracking. IEEE Transactions on Cybernetics, 48(3), 891–904. https://doi.org/10.1109/ TCYB.2017.2671359
Evers, L., & Farinelli, A. (2019). UAV path planning under uncertainty for maximum information collection. Journal of Field Robotics, 36(2), 125–145. https://doi.org/10.1002/rob.21800.
Penicka, R., Saska, M., & Thomas, J. (2017). UAV surveillance of multiple moving targets using trajectory optimization. Autonomous Robots, 41(5), 1061–1078. https://doi.org/10.1007/s10514-017-9614-3.
Smith, R. G., & Becker, K. (2017). Real-time UAV mission planning using metaheuristic optimization techniques. Journal of Aerospace Engineering, 31(3), 04017085. https://doi.org/10.1061/ (ASCE)AS.1943-5525.0000875
Bazgan, C., Hugot, H., & Vanderpooten, D. (2019). Efficient algorithms for optimizing UAV surveillance trajectories. Operations Research, 67(4), 952–969. https://doi.org/10.1287/opre.2019.1887.
Altahir, A. A., & Khalid, N. A. (2021). Drone trajectory optimization for maximum coverage in surveillance missions. IEEE Access, 9, 124568–124580. https://doi.org/10.1109/ ACCESS.2021.3088791.
Cormen, T. H., Leiserson, C. E., Rivest, R. R., & Stein, C. (2022). Introduction to algorithms (4th ed.). Massachusetts Institute of Technology. https://surl.li/ltcqew.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
