Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A novel hybrid path planning method for sweep coverage of multiple UAVs

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Sweep coverage (SC) is an NP-hard problem that needs to be solved with a small number of mobile sensors (sensor nodes) to monitor or observe targets in wireless sensor networks (WSNs) over a period of time. One of the proposed solutions to optimize the lifetime of WSNs is to monitor targets in the area of interest (AoI) by path planning of the sensor nodes. Considering the applications of unmanned aerial vehicles (UAVs) in military and civilian fields, in this study, we model multiple UAVs to solve the SC problem based on non-uniformly distributed targets in the AoI. In this modeling, we conduct effective coverage path planning for UAVs by performing an SC task for targets in the AoI with multiple asynchronously flying UAVs. To this end, we propose a new approach, which we call Weighted Targets Sweep Coverage, based on the metaheuristic Crow Search Algorithm and the heuristic Greedy algorithm. In our proposed approach, we define a new objective function by considering the UAV task completion time and the AoI coverage rate as metrics. In the Monte Carlo simulations that we perform to measure the performance, we run 5 different scenarios considering the number of targets defined for AoI and the alpha parameters defined for the objective function. The results of the scenario studies show that the proposed approach outperforms the other algorithms by up to 21% and 50% in terms of UAV task completion time and AoI coverage rate, respectively.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1
Fig. 3
Algorithm 2
Fig. 4

Similar content being viewed by others

Data availability

No datasets were generated or analyzed during the current study.

References

  1. Hasan Ali N, Özdağ R (2022) Coverage analysis and a new metaheuristic approach using the Elfes Probabilistic detection model in wireless sensor networks. Measurement 200:111627. https://doi.org/10.1016/j.measurement.2022.111627

    Article  Google Scholar 

  2. Liu C, Du H (2021) t, K -sweep coverage with mobile sensor nodes in wireless sensor networks. IEEE Internet Things J 8(18):13888–13899. https://doi.org/10.1109/JIOT.2021.3070062

    Article  Google Scholar 

  3. Gao X, Chen Z, Pan J, Wu F, Chen G (2020) Energy efficient scheduling algorithms for sweep coverage in mobile sensor networks. IEEE Trans on Mobile Comput 19(6):1332–1345. https://doi.org/10.1109/TMC.2019.2910074

    Article  Google Scholar 

  4. J. Wubben, J. P. Matos-Carvalho, D. Pedro, S. Tomic, and C. T. Calafate (2024), Empirical evaluation of multi UAV coverage path planning for aerial surveying. In: Presented at the 20th International Conference on Distributed Computing in Smart Systems and the Internet of Things (DCOSS-IoT), Abu Dhabi, United Arab Emirates: IEEE

  5. Lin C, Han G, Xu T, Martínez-García M (2021) Energy-optimal data collection for unmanned aerial vehicle-aided ındustrial wireless sensor network-based agricultural monitoring system: a clustering compressed sampling approach. IEEE Trans Ind Inf 17(6):4411–4420

    Article  Google Scholar 

  6. Xie R, Meng Z, Wang L, Li H, Wang K, Wu Z (2021) Unmanned aerial vehicle path planning algorithm based on deep reinforcement learning in large-scale and dynamic environments. IEEE Access 9:24884–24900

    Article  Google Scholar 

  7. Wen H (2024) Route planning for UAVs maritime search and rescue considering the targets moving situation. Ocean Eng 310:118623

    Article  Google Scholar 

  8. Harikumar K, Senthilnath J, Sundaram S (2019) Multi-UAV oxyrrhis marina-inspired search and dynamic formation control for forest firefighting. IEEE Trans Automat Sci Eng 16(2):863–873. https://doi.org/10.1109/TASE.2018.2867614

    Article  Google Scholar 

  9. Filist S et al (2024) An unmanned aerial vehicle autonomous flight trajectory planning method and algorithm for the early detection of the ignition source during fire monitoring. Int J Remote Sens 12(45):4178–4197. https://doi.org/10.1080/01431161.2024.2358451

    Article  Google Scholar 

  10. Ozdag R (2022) Multi-metric optimization with a new metaheuristic approach developed for 3D deployment of multiple drone-BSs. Peer-to-Peer Netw Appl 15(3):1535–1561. https://doi.org/10.1007/s12083-022-01298-4

    Article  Google Scholar 

  11. Liu Y, Xie J, Xing C, Xie S, Luo X (2024) Self-organization of UAV networks for maximizing minimum throughput of ground users. IEEE Trans Veh Technol 73(8):11743–11755. https://doi.org/10.1109/TVT.2024.3369020

    Article  Google Scholar 

  12. Amhaz A, Elhattab M, Sharafeddine S, Assi C (2024) UAV-assisted cooperative downlink NOMA: deployment and resource allocation. IEEE Trans Veh Technol 73(9):1–14. https://doi.org/10.1109/TVT.2024.3386839

    Article  Google Scholar 

  13. Li J, Xiong Y, She J, Wu M (2020) A path planning method for sweep coverage with multiple UAVs. IEEE Internet Things J 7(9):8967–8978. https://doi.org/10.1109/JIOT.2020.2999083

    Article  Google Scholar 

  14. Gharehchopogh FS, Abdollahzadeh B (2022) An efficient harris hawk optimization algorithm for solving the travelling salesman problem. Cluster Comput 25(3):1981–2005. https://doi.org/10.1007/s10586-021-03304-5

    Article  Google Scholar 

  15. Hu W et al (2023) Multi-UAV coverage path planning: a distributed online cooperation method. IEEE Trans Veh Technol 72(9):1–14. https://doi.org/10.1109/TVT.2023.3266817

    Article  Google Scholar 

  16. Wang H, Du H (2022) Time sensitive sweep coverage with minimum UAVs. Theoret Comput Sci 928:197–209. https://doi.org/10.1016/j.tcs.2022.06.025

    Article  MathSciNet  Google Scholar 

  17. Tang J, Liang Y, Li K (2024) Dynamic scene path planning of uavs based on deep reinforcement learning. Drones 8(2):60. https://doi.org/10.3390/drones8020060

    Article  Google Scholar 

  18. Qadir Z, Zafar MH, Moosavi SKR, Le KN, Mahmud MAP (2022) Autonomous UAV path-planning optimization using metaheuristic approach for predisaster assessment. IEEE Internet Things J 9(14):12505–12514. https://doi.org/10.1109/JIOT.2021.3137331

    Article  Google Scholar 

  19. Popescu D, Dragana C, Stoican F, Ichim L, Stamatescu G (2018) A collaborative UAV-WSN network for monitoring large areas. Sensors 18(12):4202. https://doi.org/10.3390/s18124202

    Article  Google Scholar 

  20. Tutsoy O, Asadi D, Ahmadi K, Nabavi-Chashmi SY, Iqbal J (2024) Minimum distance and minimum time optimal path planning with bioinspired machine learning algorithms for faulty unmanned air vehicles. IEEE Trans Intell Transport Syst 25(8):9069–9077. https://doi.org/10.1109/TITS.2024.3367769

    Article  Google Scholar 

  21. Ahmadi SM, Kebriaei H, Moradi H (2018) Constrained coverage path planning: evolutionary and classical approaches. Robotica 36(6):904–924. https://doi.org/10.1017/S0263574718000139

    Article  Google Scholar 

  22. Aggarwal S, Kumar N (2020) Path planning techniques for unmanned aerial vehicles: a review, solutions, and challenges. Comput Commun 149:270–299. https://doi.org/10.1016/j.comcom.2019.10.014

    Article  Google Scholar 

  23. Datsko D, Nekovar F, Penicka R, Saska M (2024) Energy-aware multi-UAV coverage mission planning with optimal speed of flight. IEEE Robot Autom Lett 9(3):2893–2900. https://doi.org/10.1109/LRA.2024.3358581

    Article  Google Scholar 

  24. D. Zhang, Y. Xu, and X. Yao (2018) An Improved Path Planning Algorithm for Unmanned Aerial Vehicle Based on RRT-Connect. In: 2018 37th Chinese Control Conference (CCC), Wuhan: IEEE, pp 4854–4858. https://doi.org/10.23919/ChiCC.2018.8483405

  25. Liu M, Zhang H, Yang J, Zhang T, Zhang C, Bo L (2024) A path planning algorithm for three-dimensional collision avoidance based on potential field and B-spline boundary curve. Aerosp Sci Technol 144:108763. https://doi.org/10.1016/j.ast.2023.108763

    Article  Google Scholar 

  26. Kim M-J, Kang TY, Ryoo C-K (2024) Real-time path planning for unmanned aerial vehicles based on compensated voronoi diagram. Int J Aeronaut Space Sci. https://doi.org/10.1007/s42405-024-00771-z

    Article  Google Scholar 

  27. J. Liu, X. Wang, B. Bai, and H. Dai (2018) Age-optimal trajectory planning for UAV-assisted data collection. In: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Honolulu, HI: IEEE, pp 553–558. https://doi.org/10.1109/INFCOMW.2018.8406973

  28. Athira KA, Yalavarthi R, Saisandeep T, Harshith KS, Sha A (2024) ACO-DTSP algorithm: optimizing UAV swarm routes with workload constraints. Proc Comput Sci 235:163–172. https://doi.org/10.1016/j.procs.2024.04.019

    Article  Google Scholar 

  29. Perazzo P, Sorbelli FB, Conti M, Dini G, Pinotti CM (2017) Drone path planning for secure positioning and secure position verification. IEEE Trans on Mobile Comput 16(9):2478–2493. https://doi.org/10.1109/TMC.2016.2627552

    Article  Google Scholar 

  30. Y. Zhang, Y. Zhang, Z. Liu, Z. Yu, and Y. Qu (2018) Line-of-Sight Path Following Control on UAV with Sideslip Estimation and Compensation. In: 2018 37th Chinese Control Conference (CCC), Wuhan: IEEE, pp 4711–4716. https://doi.org/10.23919/ChiCC.2018.8483606

  31. J. De Waen, H. T. Dinh, M. H. Cruz Torres, and T. Holvoet (2017) Scalable multirotor UAV trajectory planning using mixed integer linear programming. In: 2017 European Conference on Mobile Robots (ECMR), Paris: IEEE, pp 1–6. https://doi.org/10.1109/ECMR.2017.8098706

  32. Kyriakis P, Moustris G (2019) Terrain following for fixed-wing unmanned aerial vehicles using feedback equivalence. IEEE Control Syst Lett 3(1):150–155. https://doi.org/10.1109/LCSYS.2018.2854239

    Article  MathSciNet  Google Scholar 

  33. Pehlivanoglu YV, Pehlivanoglu P (2021) An enhanced genetic algorithm for path planning of autonomous UAV in target coverage problems. Appl Soft Comput 112:107796. https://doi.org/10.1016/j.asoc.2021.107796

    Article  Google Scholar 

  34. Yu Z, Si Z, Li X, Wang D, Song H (2022) A novel hybrid particle swarm optimization algorithm for path planning of UAVs. IEEE Internet Things J 9(22):22547–22558. https://doi.org/10.1109/JIOT.2022.3182798

    Article  Google Scholar 

  35. X. Li and J. Chen (2017) An Efficient Framework for Target Search with Cooperative UAVs in a FANET. In: 2017 IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications (ISPA/IUCC), Guangzhou: IEEE, pp 306–313. https://doi.org/10.1109/ISPA/IUCC.2017.00051

  36. Yang Q, Yoo S-J (2018) Optimal UAV path planning: sensing data acquisition over IoT sensor networks using multi-objective bio-inspired algorithms. IEEE Access 6:13671–13684. https://doi.org/10.1109/ACCESS.2018.2812896

    Article  Google Scholar 

  37. Aljalaud F, Kurdi H, Youcef-Toumi K (2023) Bio-inspired multi-UAV path planning heuristics: a review. Mathematics 11(10):2356. https://doi.org/10.3390/math11102356

    Article  Google Scholar 

  38. Wu Z, Li J, Zuo J, Li S (2018) Path planning of UAVs based on collision probability and kalman filter. IEEE Access 6:34237–34245. https://doi.org/10.1109/ACCESS.2018.2817648

    Article  Google Scholar 

  39. Farmani N, Sun L, Pack DJ (2017) A scalable multitarget tracking system for cooperative unmanned aerial vehicles. IEEE Trans Aerosp Electron Syst 53(4):1947–1961. https://doi.org/10.1109/TAES.2017.2677746

    Article  Google Scholar 

  40. Puente-Castro A, Rivero D, Pazos A, Fernandez-Blanco E (2022) UAV swarm path planning with reinforcement learning for field prospecting. Appl Intell 52(12):14101–14118. https://doi.org/10.1007/s10489-022-03254-4

    Article  Google Scholar 

  41. Zeng Y, Xu X, Zhang R (2018) Trajectory design for completion time minimization in UAV-enabled multicasting. IEEE Trans Wireless Commun 17(4):2233–2246. https://doi.org/10.1109/TWC.2018.2790401

    Article  Google Scholar 

  42. Z. Luo, Z. Liu, J. Shi, Q. Wang, T. Zhou, and Y. Liu (2018) The Mathematical Modeling of the Two-Echelon Ground Vehicle and Its Mounted Unmanned Aerial Vehicle Cooperated Routing Problem. In: 2018 IEEE Intelligent Vehicles Symposium (IV), Changshu: IEEE, pp 1163–1170. https://doi.org/10.1109/IVS.2018.8500391

  43. Qu C, Gai W, Zhang J, Zhong M (2020) A novel hybrid grey wolf optimizer algorithm for unmanned aerial vehicle (UAV) path planning. Knowl-Based Syst 194:105530. https://doi.org/10.1016/j.knosys.2020.105530

    Article  Google Scholar 

  44. Dasdemir E, Köksalan M, Tezcaner Öztürk D (2020) A flexible reference point-based multi-objective evolutionary algorithm: an application to the UAV route planning problem. Comput Op Res 114:104811. https://doi.org/10.1016/j.cor.2019.104811

    Article  MathSciNet  Google Scholar 

  45. Yu X, Li C, Yen GG (2021) A knee-guided differential evolution algorithm for unmanned aerial vehicle path planning in disaster management. Appl Soft Comput 98:106857. https://doi.org/10.1016/j.asoc.2020.106857

    Article  Google Scholar 

  46. C. Ntakolia, K. S. Platanitis, G. P. Kladis, C. Skliros, and A. D. Zagorianos (2022) A Genetic Algorithm enhanced with Fuzzy-Logic for multi-objective Unmanned Aircraft Vehicle path planning missions. In: 2022 International Conference on Unmanned Aircraft Systems (ICUAS), Dubrovnik, Croatia: IEEE, pp 114–123. https://doi.org/10.1109/ICUAS54217.2022.9836068

  47. Nie Z, Du H (2021) An approximation algorithm for general energy restricted sweep coverage problem. Theoret Comput Sci 864:70–79. https://doi.org/10.1016/j.tcs.2021.02.028

    Article  MathSciNet  Google Scholar 

  48. Liang W, Zhang Z (2022) Approximation algorithm for prize-collecting sweep cover with base stations. Theoret Comput Sci 929:1–10. https://doi.org/10.1016/j.tcs.2022.06.026

    Article  MathSciNet  Google Scholar 

  49. Liang W, Zhang Z, Du D-Z (2023) A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems. Optim Lett. https://doi.org/10.1007/s11590-023-02008-6

    Article  Google Scholar 

  50. Liang D, Feng B, Liao X (2024) A path planning method for chargeable sweep coverage with multiple charging stations. IEEE Access 12:34931–34941. https://doi.org/10.1109/ACCESS.2024.3373543

    Article  Google Scholar 

  51. Gao X, Fan J, Wu F, Chen G (2022) Cooperative sweep coverage problem with mobile sensors. IEEE Trans Mobile Comput 21(2):480–494. https://doi.org/10.1109/TMC.2020.3008348

    Article  Google Scholar 

  52. Jia Y et al (2022) The UAV path coverage algorithm based on the greedy strategy and ant colony optimization. Electronics 11(17):2667. https://doi.org/10.3390/electronics11172667

    Article  Google Scholar 

  53. Askarzadeh A (2016) A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm. Comput Struct 169:1–12. https://doi.org/10.1016/j.compstruc.2016.03.001

    Article  Google Scholar 

  54. Xiang D, Lin H, Ouyang J, Huang D (2022) Combined improved A* and greedy algorithm for path planning of multi-objective mobile robot. Sci Rep 12(1):13273. https://doi.org/10.1038/s41598-022-17684-0

    Article  Google Scholar 

  55. Castello Rosa ADF, Pereira FH (2024) An intensification approach based on fitness landscape characteristics for job shop scheduling problem. J Comb Optim 47(5):77. https://doi.org/10.1007/s10878-024-01176-0

    Article  MathSciNet  Google Scholar 

  56. Lian J, Wang P, Li G (2023) A greedy algorithm based compensation circuit for optimizing the output statistics of APUF. Microelectron J 131:105636. https://doi.org/10.1016/j.mejo.2022.105636

    Article  Google Scholar 

  57. Gao X, Fan J, Wu F, Chen G (2018) Approximation algorithms for sweep coverage problem with multiple mobile sensors. IEEE/ACM Trans Netw 26(2):990–1003. https://doi.org/10.1109/TNET.2018.2815630

    Article  Google Scholar 

  58. C. Liu, H. Du, and Q. Ye(2016) Sweep Coverage with Return Time Constraint. In: 2016 IEEE Global Communications Conference (GLOBECOM), Washington, DC, USA: IEEE, pp 1–6. https://doi.org/10.1109/GLOCOM.2016.7842310

Download references

Author information

Authors and Affiliations

  1. Department of Computer Engineering, Faculty of Engineering, Van Yüzüncü Yıl University, Van, Turkey

    Recep Özdağ

Authors
  1. Recep Özdağ
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

As a single author, the entire manuscript was written by the author.

Corresponding author

Correspondence to Recep Özdağ.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Özdağ, R. A novel hybrid path planning method for sweep coverage of multiple UAVs. J Supercomput 81, 83 (2025). https://doi.org/10.1007/s11227-024-06574-z

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11227-024-06574-z

Keywords

Search

Navigation