Sule Itir Satoglu, Atalay ÇELİK, Enes USTAOMER

Single-drone energy efficient coverage path planning with multiple charging stations for surveillance

Drones have started to be used for surveillance within the cities, visually scanning the predefined zones, quickly detecting abnormal states such as fires, accidents, and pollution, or assessing the disaster zones. Coverage Path Planning (CPP) is a problem that aims to determine the most suitable path or motion plan for a vehicle to cover the entire desired area in the task. So, this paper proposes a novel two-dimensional coverage path planning (CPP) mathematical model with the fact that a single drone may need to be recharged within its route based on its energy consumption, and the obstacles must be avoided while constructing the route. Our study aims to create realistic routes for drones by considering multiple charging stations and obstacles for surveillance. We tested the model for a grid example based on the scenarios obtained by changing the layout, the number of obstacles and recharging stations, and area size using the Python Gurobi Optimization library. As a contribution, we analyzed the impact of the number of existing obstacles and recharging stations, the size and layout of the area to be covered on total energy consumption, and the total solution time of CPP in our study for the first time in the literature, through a detailed Scenario Analysis. Results show that the map size and the number of covered cells affect the total energy consumption, but different layouts with shuffled cells are not effective. The area size to be covered affects the total computation time, significantly. As the number of obstacles and recharging stations increases, the computation time decreases up to a certain limit, then stabilizes.

PDF

___

Sifton, J. (2012). A Brief History of Drones, The Nation, 7, 325-335.
Hassanalian, M., Abdelkefi, A. (2017). Classifications, applications, and design challenges of drones: A review. Progress in Aerospace Sciences, 91, 99-131.
Goldman Sachs (2016). Drones: reporting for work, Goldman Sachs Research, 2016.
Idries, M.F., Mohamed, A. N., Al-Jaroodi, J., & Jawhar, I. (2014). UAVs for smart cities: Opportunities and challenges. In 2014 International Conference on Unmanned Aircraft Systems (ICUAS), 267-273.
Alam, M., Chamoli, A., & Hasan, N. (2022). Smart Cities and the Internet of Drones. The Internet of Drones: AI Applications for Smart Solutions, CRC Press, 295-323.
Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E. (2018). Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 72(4), 411-458.
Cai, G., Dias, J., & Seneviratne, L. (2014). A survey of small-scale unmanned aerial vehicles: Recent advances and future development trends. Unmanned Systems, 2(2), 175-199.
Torabbeigi, M., Lim, G. J., & Kim, S. J. (2018). Drone delivery schedule optimization considering the reliability of drones. In 2018 International Conference on Unmanned Aircraft Systems (ICUAS), 1048-1053.
Gijseghem W., Agarwal, U. (2020). Drone Delivery Multi-Agent Routing Optimization. In AIAA Aviation 2020 Forum, https://doi.org/10.2514/6.2020-3208.
Maghazei O., Netland, T. (2020). Drones in manufacturing: exploring opportunities for research and practice, Journal Manufacturing Technology Management, 31(6), 1237–1259.
Ozkan, O., Kaya, M. (2021). UAV routing with genetic algorithm based matheuristic for border security missions. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 11(2), 128-138.
Amza, C.G., Cantemir, D., Oikonomoula,A., Cantemir, I., Poterucha, P., & Salucci, G. (2018). Guidelines on Industry 4.0 and Drone Entrepreneurship for VET Students, Danmar Computers LLC, Rzeszów.
Ham, A. (2019). Drone-Based Material Transfer System in a Robotic Mobile Fulfillment Center, IEEE Transactions on Automation Science and Engineering, 17(2), 957-965.
Erdelj, M., Natalizio, E. (2016). UAV-assisted disaster management: Applications and open issues. In 2016 international conference on computing, networking and communications (ICNC), Hawaii, USA.
Wawrla, L., Maghazei, O. & Netland, T. (2019). Applications of drones in warehouse operations, Whitepaper. ETH Zurich, D-MTEC, www.pom.ethz.ch.
Companik, E., Gravier, M. & Farris, M. (2018). Feasibility of Warehouse Drone Adoption and Implementation, Journal of Transportation Management, 28(2), 31-48.
Abdullahi, H. S., Mahieddine, F., & Sheriff, R. E. (2015). Technology impact on agricultural productivity: A review of precision agriculture using unmanned aerial vehicles. In International conference on wireless and satellite systems, 388-400 Springer, Cham.
Frankelius, P., Norrman, C., & Johansen, K. (2019). Agricultural Innovation and the Role of Institutions: Lessons from the Game of Drones, Journal of Agricultural and Environmental Ethics, 32, 681–707.
Glock, K., Meyer, A. (2022). Spatial coverage in routing and path planning problems. European Journal of Operational Research, 305(1), 1-20.
Cabreira, T. M., Brisolara, L. B., & Paulo R, F. J. (2019). Survey on coverage path planning with unmanned aerial vehicles. Drones, 3(1), 4-41.
Avellar, G., Pereira, G., Pimenta, L., & Iscold, P. (2015). Multi-UAV Routing for Area Coverage and Remote Sensing with Minimum Time, Sensors, 15, 27783-27803.
Nedjati, A., Izbirak, G., Vizvari, B. & Arkat, J. (2016). Complete Coverage Path Planning for a Multi-UAV Response System in Post-Earthquake Assessment, Robotics, 5(4), 26-40.
Wang, Y., Kirubarajan, T., Tharmarasa, R., Jassemi-Zargani, R., & Kashyap, N. (2018). Multiperiod Coverage Path Planning and Scheduling for Airborne Surveillance, IEEE Transactions on Aerospace and Electronic Systems, 54(5), 2257–2273.
Zhang, X., Duan, L. (2020). Energy-Saving Deployment Algorithms of UAV Swarm for Sustainable Wireless Coverage, IEEE Transactions on Vehicular Technology, 69(9), 10320-10335.
Bahabry, A, Wan, X., Ghazzai, H., Menouar, H., Vesonder, G., & Massoud, Y. (2019). Low-Altitude Navigation for Multi-Rotor Drones in Urban Areas, IEEE Access, 7, 87716-87731.
Bircher, A., Kamel, M., Alexis, K. et al. (2016). Three-dimensional coverage path planning via viewpoint resampling and tour optimization for aerial robots. Autonomous Robots, 40, 1059-1078.
Balasubramanian, E., Elangovan, E., Tamilarasan, P., Kanagachidambaresan, G. R., & Chutia, D. (2022). Optimal energy efficient path planning of UAV using hybrid MACO-MEA* algorithm: theoretical and experimental approach. Journal of Ambient Intelligence and Humanized Computing, 1-21.
Vasquez-Gomez, J. I., Marciano-Melchor, M., Valentin, L., & Herrera-Lozada, J. C. (2020). Coverage path planning for 2d convex regions. Journal of Intelligent & Robotic Systems, 97(1), 81-94.
Choi, Y., Choi, Y., Briceno, S., & Mavris, D. N. (2020). Energy-constrained multi-UAV coverage path planning for an aerial imagery mission using column generation. Journal of Intelligent & Robotic Systems, 97(1), 125-139.
Aiello, G., Valavanis, K. P., & Rizzo, A. (2022). Fixed-wing uav energy efficient 3d path planning in cluttered environments. Journal of Intelligent & Robotic Systems, 105(3), 1-13.
Modares, J., Ghanei, F., Mastronarde, N., & Dantu, K. (2017, May). Ub-anc planner: Energy efficient coverage path planning with multiple drones. In 2017 IEEE international conference on robotics and automation (ICRA), 6182-6189).
Shivgan, R., & Dong, Z. (2020, May). Energy-efficient drone coverage path planning using genetic algorithm. In 2020 IEEE 21st International Conference on High Performance Switching and Routing (HPSR), 1-6.
Bezas, K., Tsoumanis, G., Angelis, C. T., & Oikonomou, K. (2022). Coverage Path Planning and Point-of-Interest Detection Using Autonomous Drone Swarms, Sensors, 22(19), 7551-7569.
Vazquez-Carmona, E. V., Vasquez-Gomez, J. I., Herrera-Lozada, J. C., & Antonio-Cruz, M. (2022). Coverage path planning for spraying drones. Computers & Industrial Engineering, 168, 108125-108134.
Tevyashov, G. K., Mamchenko, M. V., Migachev, A. N., Galin, R. R., Kulagin, K. A., Trefilov, P. M., & Goloburdin, N. V. (2022). Algorithm for Multi-drone Path Planning and Coverage of Agricultural Fields. In Agriculture Digitalization and Organic Production: Proceedings of the First International Conference, ADOP 2021, St. Petersburg, Russia, June 7–9, 299-310, Springer Singapore.
Bae, H., Moon, I. (2016). Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles, Applied Mathematical Modelling, 40(13), 6536–6549.
Baras, N., Dasygenis, M., & Ploskas, N. (2019, May). Multi-robot coverage path planning in 3-dimensional environments. In 2019 8th International Conference on Modern Circuits and Systems Technologies, (MOCAST), 1-4.
Nam, L. H., Huang, L., Li, X. J., & Xu, J. F. (2016). An approach for coverage path planning for UAVs. In the 2016 IEEE 14th international workshop on advanced motion control (AMC), 411-416.
Kyriakakis, N. A., Marinaki, M., Matsatsinis, N., & Marinakis, Y. (2022). A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning. European Journal of Operational Research, 300(3), 992-1004.
Shen, Z., Song, J., Mittal, K., & Gupta, S. (2021). CT-CPP: Coverage Path Planning for 3D Terrain Reconstruction Using Dynamic Coverage Trees. IEEE Robotics and Automation Letters, 7(1), 135-142.
Di Franco, C., & Buttazzo, G. (2015). Energy-aware coverage path planning of UAVs. In 2015 IEEE international conference on autonomous robot systems and competitions, 111-117.
Keskin, K., Urazel, B. (2021). Fuzzy control of dual storage system of an electric drive vehicle considering battery degradation. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 11(1), 30-40.
DJI. (2022). DJI Mini 3 Pro User Manual. Shenzhen, China. https://dl.djicdn.com/downloads/DJI_Mini_3_Pro/UM/DJI_Mini_3_Pro_user_manual_v1.0_en.pdf
CPP Python Codes https://docs.google.com/document/d/1CjSqz_9I30zEI3AHbZweJXocJGjowV4qVUcNogJHqu4/edit?usp=sharing