UAV search coverage under priority of important targets based on multi-location domain decomposition

Xiaoying Zheng; Jing Wu; Xiaofeng Li; Junjie Huang; Xiaoying Zheng; Jing Wu; Xiaofeng Li; Junjie Huang

doi:10.3934/era.2024115

Electronic Research Archive

2024, Volume 32, Issue 4: 2491-2513. doi: 10.3934/era.2024115

Previous Article Next Article

Research article

UAV search coverage under priority of important targets based on multi-location domain decomposition

1.
School of Mathematics and Science, Wuhan Institute of Technology, Wuhan 430073, China
2.
Department of Operations and Planning, Naval University of Engineering, Wuhan 430030, China
3.
College of Power Engineering, Naval University of Engineering, Wuhan 430030, China

Received: 06 December 2023 Revised: 08 February 2024 Accepted: 19 March 2024 Published: 27 March 2024

In recent years, the coverage path planning (CPP) of unmanned aerial vehicles (UAVs) has attracted attention in reconnaissance, patrol, and search and rescue efforts, aiming to plan the paths for UAVs to cover a specified area as efficiently as possible. This paper proposes a UAV path fast coverage model to prioritize important targets with domain composition based on the starting point and location of the targets, combined with the domain decomposition strategy of important targets. Considering the constraints of the number of UAVs, the number of operators, and the flight time, the parallel search strategy can plan the coverage scheme with the shortest search time for the search range, and further obtain the coordinate points and path coordinates of the UAV turning. Finally, through multiple simulation experiments in four maps of various islands, the proposed method is verified to have an improved performance compare to the two track path coverage algorithms methods in terms of the coverage efficiency and the time complexity, thus providing a more scientific basis for the path coverage research of multi-target searches.
- mathematical model,
- multitasking,
- path planning,
- search methods,
- process planning
Citation: Xiaoying Zheng, Jing Wu, Xiaofeng Li, Junjie Huang. UAV search coverage under priority of important targets based on multi-location domain decomposition[J]. Electronic Research Archive, 2024, 32(4): 2491-2513. doi: 10.3934/era.2024115

Related Papers:

Abstract

In recent years, the coverage path planning (CPP) of unmanned aerial vehicles (UAVs) has attracted attention in reconnaissance, patrol, and search and rescue efforts, aiming to plan the paths for UAVs to cover a specified area as efficiently as possible. This paper proposes a UAV path fast coverage model to prioritize important targets with domain composition based on the starting point and location of the targets, combined with the domain decomposition strategy of important targets. Considering the constraints of the number of UAVs, the number of operators, and the flight time, the parallel search strategy can plan the coverage scheme with the shortest search time for the search range, and further obtain the coordinate points and path coordinates of the UAV turning. Finally, through multiple simulation experiments in four maps of various islands, the proposed method is verified to have an improved performance compare to the two track path coverage algorithms methods in terms of the coverage efficiency and the time complexity, thus providing a more scientific basis for the path coverage research of multi-target searches.

References

[1]	Y. Li, W. Han, Y. Wang, Deep reinforcement learning with application to air confrontation intelligent decision-making of manned/unmanned aerial vehicle cooperative system, IEEE Access, 8 (2020), 67887-67898. https://doi.org/10.1109/ACCESS.2020.2985576 doi: 10.1109/ACCESS.2020.2985576
[2]	P. Radoglou-Grammatikis, P. Sarigiannidis, T. Lagkas, L. Moscholios, A compilation of UAV applications for precision agriculture, Comput. Netw., 172 (2020), 1389-1286. https://doi.org/doi:10.1016/j.comnet.2020.107148 doi: 10.1016/j.comnet.2020.107148
[3]	M. Pavone, E. Frazzoli, Decentralized policies for geometric pattern formation, in 2007 American Control Conference (ACC), (2007), 3949-3954. https://doi.org/10.1109/ACC.2007.4283108
[4]	M. Yao, X. Feng, P. Li, Y. Li, Z. Peng, Z. Lu, Object-level complete coverage path planning for excavators in earthwork construction, Sci. Rep., 13 (2023), 12818. https://doi.org/10.1038/s41598-023-40038-3 doi: 10.1038/s41598-023-40038-3
[5]	J. Chen, F. Ling, Y. Zhang, T. You, Y. Liu, X. Du, Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system, Swarm Evol. Comput., 69 (2021), 101005. https://doi.org/10.1016/j.swevo.2021.101005 doi: 10.1016/j.swevo.2021.101005
[6]	S. Aggarwal, N. Kumar, Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges, Comput. Commun., 149 (2020), 270-299. https://doi.org/10.1016/j.comcom.2019.10.014
[7]	J. Chen, P. Han, Y. Zhan, T. You, P. Zheng, Scheduling energy consumption-constrained workflows in heterogeneous multi-processor embedded systems, J. Syst. Architect., 142 (2023), 102938. https://doi.org/10.1016/j.sysarc.2023.102938 doi: 10.1016/j.sysarc.2023.102938
[8]	L. Yan, C. Hai, J. Meng, X. Wang, Coverage path planning for UAVs based on enhanced exact cellular decomposition method, Mechatronics, 21 (2011), 876-885. https://doi.org/10.1016/j.mechatronics.2010.10.009 doi: 10.1016/j.mechatronics.2010.10.009
[9]	R. S. Nilsson, K. Zhou, Method and bench-marking framework for coverage path planning in arable farming, Biosyst. Eng., 198 (2020), 248-265. https://doi.org/10.1016/j.biosystemseng.2020.08.007 doi: 10.1016/j.biosystemseng.2020.08.007
[10]	S. Ivić, A. Andrejčuk, S. Družeta, Autonomous control for multi-agent non-uniform spraying, Appl. Soft Comput., 80 (2019), 742-760. https://doi.org/10.1016/j.asoc.2019.05.001 doi: 10.1016/j.asoc.2019.05.001
[11]	A. Bouras, Y. Bouzid, M. Guiatn, Areas division and multiple UAV coverage path planning for gas distribution map, in 19th International Multi-Conf. Systems (IMCS), (2022), 1554-1560. https://doi.org/10.1109/SSD54932.2022.9955697
[12]	Y. Choi, Y. Choi, S. I. Briceno, D. N. Mavris, Energy-constrained multi-UAV coverage path planning for an aerial imagery mission using column generation, J. Intell. Robotic Syst., 97 (2020), 125-139. https://doi.org/10.1007/s10846-019-01010-4 doi: 10.1007/s10846-019-01010-4
[13]	Y. Jin, Pareto-based multi-objective machine learning, in 7th International Conference on Hybrid Intelligent Systems (ICHIS), (2007), 2. https://doi.org/10.1109/HIS.2007.73
[14]	G. Avellar, G. Pereira, L. Pimenta, P. Iscold, Multi-UAV routing for area coverage and remote sensing with minimum time, Sensors, 15 (2015), 27783-27803. https://doi.org/10.3390/s151127783 doi: 10.3390/s151127783
[15]	Y. Jia, S. Zhou, Q. Zeng, C. Li, D. Chen, K. Zhang, et al., The UAV path coverage algorithm based on the greedy strategy and Ant Colony optimization, Electronics, 11 (2022), 2667. https://doi.org/10.3390/electronics11172667 doi: 10.3390/electronics11172667
[16]	S. Cho, J. Park, H. Park, S. Kim, Multi-UAV coverage path planning based on hexagonal grid decomposition in maritime search and rescue, Mathematics, 10 (2022), 83. https://doi.org/10.3390/math10010083 doi: 10.3390/math10010083
[17]	M. Popović, T. Vidal-Calleja, G. Hitz, I. Sa, R. Siegwart, J. Nieto, Multiresolution mapping and informative path planning for UAV-based terrain monitoring, in 2017 IEEE/RSJ International Conference Intelligent Robots and System (IICIRS), (2017), 1382-1388. https://doi.org/10.1109/IROS.2017.8202317
[18]	D. Chanchal, K. Pawan, An improved weighted sum-fuzzy Dijkstra's algorithm for shortest path problem, Soft Comput., 26 (2022), 3217-3226. https://doi.org/10.1007/s00500-022-06871-w doi: 10.1007/s00500-022-06871-w
[19]	H. Wang, J. Zhou, G. Zheng, Y. Liang, HAS: Hierarchical A-Star algorithm for big map navigation in special areas, in 2014 5th International Conference Digital Home (ICDH), (2014), 222-225. https://doi.org/10.1109/ICDH.2014.49
[20]	G. Hu, J. Zhong, G. Wei, SaCHBA_PDN: modified honey badger algorithm with multi-strategy for UAV path planning, Expert Syst. Appl., 223 (2023), 119941. https://doi.org/10.1016/j.eswa.2023.119941 doi: 10.1016/j.eswa.2023.119941
[21]	M. Yuan, T. Zhou, M. Chen, Improved lazy theta algorithm based on octree map for path planning of UAV, Def. Technol., 2 (2023), 8-18. https://doi.org/10.1016/j.dt.2022.01.006 doi: 10.1016/j.dt.2022.01.006
[22]	J. A. GoncaAlves, R. Henriques, UAV photogrammetry for topographic monitoring of coastal areas, Isprs J. Photogramm., 104 (2015), 101-111. https://doi.org/10.1016/j.isprsjprs.2015.02.009 doi: 10.1016/j.isprsjprs.2015.02.009
[23]	A. Batyra, M. D. Vroey, From one to many islands: the emergence of search and matching models, B. Econ. Res., 64 (2011), 393-414. https://doi.org/10.1111/j.1467-8586.2010.00389.x doi: 10.1111/j.1467-8586.2010.00389.x
[24]	D. G. Reina, H. Tawfik, S. L. Toral, Multi-subpopulation evolutionary algorithms for coverage deployment of UAV-networks, Ad Hoc Netw., 68 (2018), 16-32. https://doi.org/10.1016/j.adhoc.2017.09.005 doi: 10.1016/j.adhoc.2017.09.005
[25]	H. Song, J. Yu, J. Qiu, Z. Sun, K. Lang, Q. Luo, et al., Multi-UAV disaster environment coverage planning with limited-endurance, in 2022 International Conference Robotics and Automation (ICRA), (2022), 10760-10766. https://doi.org/10.1109/ICRA46639.2022.9812201
[26]	A. B. Bugnot, M. Mayer-Pinto, L. Airoldi, E. C. Heery, E. L. Johnston, L. P. Critchley, et al., Current and projected global extent of marine built structures, Nat. Sustain., 4 (2021), 33-41. https://doi.org/10.1038/s41893-020-00595-1 doi: 10.1038/s41893-020-00595-1
[27]	S. Xiao, X. Tan, J. Wang, A simulated annealing algorithm and grid map-based UAV coverage path planning method for 3D reconstruction, Electronics, 10 (2021), 853. https://doi.org/10.3390/electronics10070853 doi: 10.3390/electronics10070853
[28]	J Chen, T Li, Y Zhang, T You, Y Lu, P Tiwari, et al., Global-and-local attention-based reinforcement learning for cooperative behaviour control of Multiple UAVs, IEEE Trans. Veh. Technol., 73 (2023), 1-13. https://doi.org/10.1109/TVT.2023.3327571L doi: 10.1109/TVT.2023.3327571L
[29]	L. Lin, M. A. Goodrich, Hierarchical heuristic search using a gaussian mixture model for UAV coverage planning, IEEE Trans. Cybern., 44 (2014), 2532-2544. https://doi.org/10.1109/TCYB.2014.2309898 doi: 10.1109/TCYB.2014.2309898
[30]	S. Pulit, L. T. Ene, T. Gobakken, E. Naesset, Use of partial-coverage UAV data in sampling for large scale forest inventories, Remote Sens. Environ., 194 (2017), 115-126. https://doi.org/10.1016/j.rse.2017.03.019 doi: 10.1016/j.rse.2017.03.019
[31]	H. Wu, X. Tao, N. Zhang, X. Shen, Cooperative UAV cluster-assisted terrestrial cellular networks for ubiquitous coverage, IEEE J. Sel. Areas Comm., 36 (2018), 2045-2058. https://doi.org/10.1109/JSAC.2018.2864418 doi: 10.1109/JSAC.2018.2864418

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)