[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Energy-Efficient Multi-UAV Multi-Region Coverage Path Planning Approach

  • Research Article-Computer Engineering and Computer Science
  • Published:
Arabian Journal for Science and Engineering Aims and scope Submit manuscript

Abstract

Due to the high deployment flexibility and strong maneuverability, unmanned aerial vehicles (UAVs) have gained a significant attention in civilian and military applications. One of the main essential aspects of UAV is coverage path planning (CPP), which autonomously obtains sufficient paths to cover the entire region of interest (RoI). Several advantages have been offered by UAVs’ CPP such as cost and time efficiency, reduced human intervention, resource optimization, data collection, scalability, and adaptability. However, the flight time of UAVs is constrained by battery capacity, necessitating energy-efficient solutions to prolong flight duration. This paper introduces a novel approach for energy-efficient multi-UAV multi-region CPP to generate appropriate paths that cover multiple disjoint regions, aiming to minimize overall energy consumption. First, we employ a back-and-forth strategy to generate intra-region path patterns with minimum turns and propose a smoothing turns approach (STA) based on Bezier curves to effectively reduce an energy consumption due to taking turns. Then, the inter-region path planning is formulated as a multi-constraint optimization problem and solved utilizing the CPLEX solver for small-scale problems and heuristic approaches for large-scale ones. A region allocation approach is proposed to assign RoIs to appropriate UAVs. Simulations are conducted to evaluate the performance of the proposed approach in terms of energy consumption. Comparative results against EECPPA and Nearest Neighbor (NN) approaches demonstrate advantages in energy consumption reduction. Besides, heuristic methods yield superior solutions for large-scale problems within shorter execution times compared to the CPLEX solver. These comparisons highlight the superiority of the proposed approach over existing methods in generating higher-quality solutions.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Algorithm 2
Algorithm 3
Algorithm 4
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

References

  1. Zuo, Y.; Tharmarasa, R.; Jassemi-Zargani, R.; Kashyap, N.; Thiyagalingam, J.; Kirubarajan, T.T.: Milp formulation for aircraft path planning in persistent surveillance. IEEE Trans. Aerosp. Electron. Syst. 56(5), 3796–3811 (2020)

    Article  Google Scholar 

  2. Ahmed, G.; Sheltami, T.; Mahmoud, A.; Yasar, A.: Iod swarms collision avoidance via improved particle swarm optimization. Trans. Res. Part A Policy Pract. 142, 260–278 (2020)

    Article  Google Scholar 

  3. Majeed, A.; Hwang, S.O.: A multi-objective coverage path planning algorithm for uavs to cover spatially distributed regions in urban environments. Aerospace 8(11), 343 (2021)

    Article  Google Scholar 

  4. Ahmed, G.A.; Sheltami, T.R.; Mahmoud, A.S.; Imran, M.; Shoaib, M.: A novel collaborative iod-assisted vanet approach for coverage area maximization. IEEE Access 9, 61211–61223 (2021)

    Article  Google Scholar 

  5. Chen, J.; Zhang, Y.; Wu, L.; You, T.; Ning, X.: An adaptive clustering-based algorithm for automatic path planning of heterogeneous uavs. IEEE Trans. Intell. Transp. Syst. 23(9), 16842–16853 (2021)

    Article  Google Scholar 

  6. Ng, K.; Sancho, N.: Regional surveillance of disjoint rectangles: a travelling salesman formulation. J. Oper. Res. Soc. 60(2), 215–220 (2009)

    Article  Google Scholar 

  7. Sheltami, T.; Ahmed, G.; Yasar, A.: An optimization approach of iod deployment for optimal coverage based on radio frequency model. CMES Comput. Model. Eng. Sci. 5, 69 (2024)

    Google Scholar 

  8. Tan, C.S.; Mohd-Mokhtar, R.; Arshad, M.R.: A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms. IEEE Access (2021)

  9. AHMED, G.A.; Sheltami, T.R.O.; Mahmoud, A.S.; Yasar, A.: 3d simulation model for iod-to-vehicles communication in iod-assisted vanet (2023)

  10. Chen, H.; Chang, K.; Agate, C.S.: Uav path planning with tangent-plus-lyapunov vector field guidance and obstacle avoidance. IEEE Trans. Aerosp. Electron. Syst. 49(2), 840–856 (2013)

    Article  Google Scholar 

  11. Ragi, S.; Chong, E.K.: Uav path planning in a dynamic environment via partially observable markov decision process. IEEE Trans. Aerosp. Electron. Syst. 49(4), 2397–2412 (2013)

    Article  Google Scholar 

  12. Ergezer, H.; Leblebicioglu, K.: Path planning for uavs for maximum information collection. IEEE Trans. Aerosp. Electron. Syst. 49(1), 502–520 (2013)

    Article  Google Scholar 

  13. Tian, X.; Bar-Shalom, Y.; Pattipati, K.R.: Multi-step look-ahead policy for autonomous cooperative surveillance by uavs in hostile environments. In: 2008 47th IEEE Conference on Decision and Control, pp. 2438–2443 (2008). IEEE

  14. Ahmed, G.; Sheltami, T.; Deriche, M.; Yasar, A.: An energy efficient iod static and dynamic collision avoidance approach based on gradient optimization. Ad Hoc Netw. 118, 102519 (2021)

    Article  Google Scholar 

  15. Ahmed, G.; Sheltami, T.; Ghaleb, M.; Hamdan, M.; Mahmoud, A.; Yasar, A.: Energy-efficient internet of drones path-planning study using meta-heuristic algorithms. Appl. Sci. 14(6), 2418 (2024)

    Article  Google Scholar 

  16. Ahmed, G.; Sheltami, T.: A safety system for maximizing operated uavs capacity under regulation constraints. IEEE Access (2023)

  17. Modares, J.; Ghanei, F.; Mastronarde, N.; Dantu, K.: Ub-anc planner: Energy efficient coverage path planning with multiple drones. In: 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 6182–6189 (2017). IEEE

  18. Hameed, I.A.: Intelligent coverage path planning for agricultural robots and autonomous machines on three-dimensional terrain. J. Intell. Robot. Syst. 74(3), 965–983 (2014)

    Article  Google Scholar 

  19. Sharma, G.; Dutta, A.; Kim, J.-H.: Optimal online coverage path planning with energy constraints. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1189–1197 (2019)

  20. Alidaee, B.; Wang, H.; Landram, F.: A note on integer programming formulations of the real-time optimal scheduling and flight path selection of uavs. IEEE Trans. Control Syst. Technol. 17(4), 839–843 (2009)

    Article  Google Scholar 

  21. Song, B.D.; Kim, J.; Kim, J.; Park, H.; Morrison, J.R.; Shim, D.H.: Persistent uav service: an improved scheduling formulation and prototypes of system components. J. Intell. Robot. Syst. 74(1), 221–232 (2014)

    Article  Google Scholar 

  22. Nigam, N.; Bieniawski, S.; Kroo, I.; Vian, J.: Control of multiple uavs for persistent surveillance: algorithm and flight test results. IEEE Trans. Control Syst. Technol. 20(5), 1236–1251 (2011)

    Article  Google Scholar 

  23. Song, B.D.; Kim, J.; Morrison, J.R.: Rolling horizon path planning of an autonomous system of uavs for persistent cooperative service: Milp formulation and efficient heuristics. J. Intell. Robot. Syst. 84(1–4), 241–258 (2016)

    Article  Google Scholar 

  24. Garey, M.R.: A guide to the theory of np-completeness. Computers and intractability (1979)

  25. Zheng, W.; Qiaoqiao, L.; Hongtao, T.; Jianxun, L.: Multiple task planning based on ts algorithm for multiple heterogeneous unmanned aerial vehicles. In: Proceedings of 2014 IEEE Chinese Guidance, Navigation and Control Conference, pp. 630–635 (2014). IEEE

  26. Turker, T.; Sahingoz, O.K.; Yilmaz, G.: 2d path planning for uavs in radar threatening environment using simulated annealing algorithm. In: 2015 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 56–61 (2015). IEEE

  27. Wang, G.; Li, Q.; Guo, L.: Multiple uavs routes planning based on particle swarm optimization algorithm. In: 2010 2nd International Symposium on Information Engineering and Electronic Commerce, pp. 1–5 (2010). IEEE

  28. Di Franco, C.; Buttazzo, G.: Energy-aware coverage path planning of uavs. In: 2015 IEEE International Conference on Autonomous Robot Systems and Competitions, pp. 111–117 (2015). IEEE

  29. Di Franco, C.; Buttazzo, G.: Coverage path planning for uavs photogrammetry with energy and resolution constraints. J. Intell. Robot. Syst. 83(3), 445–462 (2016)

    Article  Google Scholar 

  30. Ghaddar, A.; Merei, A.: Energy-aware grid based coverage path planning for uavs. In: Proceedings of the Thirteenth International Conference on Sensor Technologies and Applications SENSORCOMM, Nice, France, pp. 27–31 (2019)

  31. Shivgan, R.; Dong, Z.: Energy-efficient drone coverage path planning using genetic algorithm. In: 2020 IEEE 21st International Conference on High Performance Switching and Routing (HPSR), pp. 1–6 (2020). IEEE

  32. Maza, I.; Ollero, A.: Multiple uav cooperative searching operation using polygon area decomposition and efficient coverage algorithms. In: Distributed Autonomous Robotic Systems 6, pp. 221–230. Springer, ??? (2007)

  33. Cabreira, T.M.; Ferreira, P.R.; Di Franco, C.; Buttazzo, G.C.: Grid-based coverage path planning with minimum energy over irregular-shaped areas with uavs. In: 2019 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 758–767 (2019). IEEE

  34. Artemenko, O.; Dominic, O.J.; Andryeyev, O.; Mitschele-Thiel, A.: Energy-aware trajectory planning for the localization of mobile devices using an unmanned aerial vehicle. In: 2016 25th International Conference on Computer Communication and Networks (ICCCN), pp. 1–9 (2016). IEEE

  35. Zhao, C.; Liu, Y.; Zhao, J.: Path planning method of uav area coverage searching based on pega. Sci. Technol. Rev. 32(22), 85–90 (2014)

    Google Scholar 

  36. Hu, X.; Lin, Z.: Coverage path planning of penaeus vannamei feeding based on global and multiple local areas. In: International Conference on Data Service, pp. 687–697 (2019). Springer

  37. Chen, J.; Du, C.; Lu, X.; Chen, K.: Multi-region coverage path planning for heterogeneous unmanned aerial vehicles systems. In: 2019 IEEE International Conference on Service-Oriented System Engineering (SOSE), pp. 356–3565 (2019). IEEE

  38. Király, A.; Abonyi, J.: Redesign of the supply of mobile mechanics based on a novel genetic optimization algorithm using google maps api. Eng. Appl. Artif. Intell. 38, 122–130 (2015)

    Article  Google Scholar 

  39. Papachristos, C.; Alexis, K.; Carrillo, L.R.G.; Tzes, A.: Distributed infrastructure inspection path planning for aerial robotics subject to time constraints. In: 2016 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 406–412 (2016). IEEE

  40. Vasquez-Gomez, J.I.; Herrera-Lozada, J.-C.; Olguin-Carbajal, M.: Coverage path planning for surveying disjoint areas. In: 2018 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 899–904 (2018). IEEE

  41. Chen, J.; Ling, F.; Zhang, Y.; You, T.; Liu, Y.; Du, X.: Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system. Swarm Evol. Comput. 69, 101005 (2022)

    Article  Google Scholar 

  42. Chen, J.; Li, T.; Zhang, Y.; You, T.; Lu, Y.; Tiwari, P.; Kumar, N.: Global-and-local attention-based reinforcement learning for cooperative behaviour control of multiple uavs. IEEE Trans. Veh. Technol. 2, 96 (2023)

    Google Scholar 

  43. Huang, W.H.: Optimal line-sweep-based decompositions for coverage algorithms. In: Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164), vol. 1, pp. 27–32 (2001). IEEE

  44. Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986)

  45. Feo, T.A.; Resende, M.G.: Greedy randomized adaptive search procedures. J. Global Optim. 6(2), 109–133 (1995)

    Article  MathSciNet  Google Scholar 

  46. Poon, M.; Gu, R.; Yuan, Y.: A vehicle routing problem with option for outsourcing and time-dependent travel time. IEEE Access 10, 49757–49770 (2022)

    Article  Google Scholar 

  47. Wu, Y.; Wang, J.: Algorithm Design Practice for Collegiate Programming Contests and Education. CRC Press, London (2018)

    Book  Google Scholar 

  48. Joshi, P.: Artificial Intelligence with Python. Packt Publishing Ltd, London (2017)

    Google Scholar 

  49. Ahmed, G.; Sheltami, T.; Mahmoud, A.; Yasar, A.: Energy-efficient uavs coverage path planning approach. CMES Comput. Model. Eng. Sci. 136(3), 3239–3263 (2023)

  50. Kirk, J.: Traveling Salesman Problem-Nearest Neighbor, MATLAB Central File Exchange. Accessed: Jan (2020)

Download references

Acknowledgements

This research was funded by Project Number INML2104 under the interdisciplinary center of smart mobility and logistics at King Fahd University of Petroleum and Minerals.

Author information

Authors and Affiliations

  1. Computer Engineering, Interdisciplinary Research Center of Smart Mobility and Logistics, King Fahd University of Petroleum and Minerals, Dhahran, 31261, Saudi Arabia

    Gamil Ahmed, Tarek Sheltami & Ashraf Mahmoud

Authors
  1. Gamil Ahmed
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tarek Sheltami
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ashraf Mahmoud
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tarek Sheltami.

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

Ahmed, G., Sheltami, T. & Mahmoud, A. Energy-Efficient Multi-UAV Multi-Region Coverage Path Planning Approach. Arab J Sci Eng 49, 13185–13202 (2024). https://doi.org/10.1007/s13369-024-09295-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13369-024-09295-w

Keywords

Search

Navigation