Coverage Path Planning Technology for UAV in Complex Planar Regions

doi:10.12382/bgxb.2025.0229

Abstract

Abstract:

Rotary-wing unmanned aerial vehicles (UAVs) have been widely used in various fields such as power inspection，agricultural and forestry protection，and counter-terrorism rescue operation due to their exceptional flexibility and multifunctionality.However，the two-dimensional coverage issue caused by irregular terrain in complex planar areas presents significant challenges for path planning.To address this issue，this paper proposes a coverage path planning technology for UAVs in complex planar regions.During the region decomposition phase，an improved boundary-cutting decomposition (BCD) method is utilized to incorporate a directional tolerance parameter Δφ during the merging of sub-regions to eliminate the redundant elongated areas generated by decomposition，which significantly reduces the frequency of backtracking in subsequent path planning.In the coverage path generation phase，four innovative coverage modes (FF/FR/RF/RR) are designed，and the endpoints are dynamically configured.A multi-mode traveling salesman problem (MM-TSP) is constructed between sub-regions.By combining a candidate arrangement set Π_ϵ generated from a relaxed TSP with a dynamic programming strategy，the computational complexity is reduced from O(n！·4ⁿ)to O(|π_ϵ|·n·4²)，enhancing both computational efficiency and task coverage efficiency.Experimental results demonstrate that this coverage path planning technology reduces the average number of waypoints by 27.24%，shortens task distance by 26.12%，and decreases estimated task time by 26.20% across five scenarios：urban，airport，mountainous area，city，and forest.These findings validate the significant advantages of this technology in reducing the path redundancy and improving the task efficiency in complex planar regions，providing an efficient solution for the coverage path planning of rotary-wing UAVs.

Key words: path planning, coverage path planning, boustrophedon decomposition method, multi-mode traveling salesman problem

ZHANG Tian, HU Yunqi, CHEN Zhaowen, WANG Qiang, YANG Zhilai, GUO Meng. Coverage Path Planning Technology for UAV in Complex Planar Regions[J]. Acta Armamentarii, 2025, 46(S1): 250229-.

Figures/Tables 12

Fig.1 CPP task in a complex region

Fig.2 Flowchart of region decomposition and coverage path planning

Fig.3 TCD and BCD Domain Decomposition Example

Fig.4 Example of the BCD

Fig.5 Cell heights of sub-regions in different scanning line directions

Fig.6 Example of supplementary scanning lines during coverage path

Fig.7 Four types of coverage path forms generated in the same scanning line direction

Fig.8 Domain decomposition optimization schematic diagram

Fig.9 Coverage path planning results formed after BCD decomposition under different strategies

Fig.10 Coverage path planning results before and after optimization

Table 1 The task regions for five coverage path planning tasks and the planning results of the method by Bahnemann et al.[15] (traditional method)，and the proposed method

场景	任务区域	传统算法	本文算法
城镇
机场
山区
城市
林地

Table 2 Comparison of estimated task completion times under different scenarios

场景	参数	传统算法	本文算法	相比减少
城镇	航点数量	72	62	13.89%
	规划距离/m	18757	16299	13.10%
	预估时间/s	3239	2813	13.15%
机场	航点数量	48	36	25.00%
	规划距离/m	8146	4786	41.25%
	预估时间/s	1433	854	40.40%
山区	航点数量	103	78	24.27%
	规划距离/m	22202	14985	32.51%
	预估时间/s	3862	2620	32.16%
城市	航点数量	113	91	19.47%
	规划距离/m	36236	25763	28.90%
	预估时间/s	6217	4437	28.63%
林地	航点数量	155	72	53.55%
	规划距离/m	30098	25624	14.86%
	预估时间/s	5260	4384	16.65%

References 21

[1]	AGBEYANGI A, ODIETE J, OLORUNLOMERUE A. Review on UAVs used for aerial surveillance[J]. Journal of Multidisciplinary Engineering Science and Technology, 2016, 3:2458-9403.
[2]	LUCIEER A, TURNER D, KING D H, et al. Using an unmanned aerial vehicle (UAV) to capture micro-topography of antarctic moss beds[J]. International Journal of Applied Earth Observation and Geoinformation, 2014, 27:53-62.
[3]	DELMERICO J, MINTCHEV S, GIUSTI A, et al. The current state and future outlook of rescue robotics[J]. Journal of Field Robotics, 2019, 36(7):1171-1191. doi: 10.1002/rob.21887
[4]	GALCERAN E, CARRERAS M. A survey on coverage path planning for robotics[J]. Robotics Autonomous Systems, 2013, 61(12):1258-1276.
[5]	张世勇, 张雪波, 苑晶, 等. 旋翼无人机环境覆盖与探索规划方法综述[J]. 控制与决策, 2022, 37(3):513-529.
	ZHANG S Y, ZHANG X B, YUAN J, et al. A survey on coverage and exploration path planning with multi-rotor micro aerial vehicles[J]. Control and Decision, 2022, 37(3):513-529. (in Chinese)
[6]	AVELLAR G, PEREIRA G, Pimenta L, et al. Multi-UAV routing for area coverage and remote sensing with minimum time[J]. Sensors, 2015, 15:27783-27803:. doi: 10.3390/s151127783 pmid: 26540055
[7]	陈洋, 周锐. 通信受限条件下多无人机协同环境覆盖路径规划[J]. 中国惯性技术学报, 2024, 32(3):273-281.
	CHEN Y, ZHOU R, Coverage path planning for multi UAV collaborative environment under communication constraints[J]. Journal of Chinese Inertial Technology, 2024, 32(3):273-281. (in Chinese)
[8]	MUÑOZ J, LÓPEZ B, QUEVEDO F, et al. Multi UAV coverage path planning in urban environments[J]. Sensors, 2021, 21:7365.
[9]	FEVGAS G, LAGKAS T, ARGYRIOU V, et al. Coverage path planning methods focusing on energy efficient and cooperative strategies for unmanned aerial vehicles[J]. Sensors, 2022, 22(3):1235.
[10]	LATOMBE J C. Robot motion planning[M]. Norwell,MA,US: Kluwer Academic Publishers, 1990.
[11]	CHOSET H, PIGNON P. Coverage path planning:the boustrophedon cellular decomposition[C]// Proceedings of the International Conference on Field and Service Robotics.Canberra, Australia:Springer,1998:203-209.
[12]	CHOSET H. Coverage of known spaces:the boustrophedon cellular decomposition[J]. Annals of Mathematics, 2000, 9(3):247-253.
[13]	ACAR E U, CHOSET H, ZHANG Y G, et al. Path planning for robotic demining:robust sensor-based coverage of unstructured environments and probabilistic methods[J]. The International Journal of Robotics Research, 2003, 22:441-466.
[14]	LUO C, YANG S X. A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments[J]. IEEE Transactions on Neural Networks, 2008, 19(7):1279-1298.
[15]	BÄHNEMANN R, LAWRANCE N, CHUNG J J, et al. Revisiting boustrophedon coverage path planning as a generalized traveling salesman problem[C]// Proceedings of the International Conference on Field and Service Robotics.Kyoto,Japan:Springer, 2021(16):277-290.
[16]	APOSTOLIDIS S D, KAPOUTSIS P C, KAPOUTSIS A C, et al. Cooperative multi-UAV coverage mission planning platform for remote sensing applications[J]. Autonomous Robots, 2022, 46(2):373-400.
[17]	HE H, NORBY J, WANG S J, et al. Environmental sampling with the boustrophedon decomposition algorithm[J/OL]. Ithaca,NY, US: Cornell University, 2022(2022-07-13)[2025-03-15]. http://arxiv.org/abs/2207.06209.
[18]	GONG J, KIM H, LEE S. Resilient multi-robot coverage path redistribution using boustrophedon decomposition for environmental monitoring[J]. Sensors, 2024, 24(23):7482.
[19]	MANZINI T, MURPHY R. Differentiable boustrophedon paths that enable optimization via gradient descent[C]//Proceedings of the 2024 IEEE International Conference on Robotics and Automation (ICRA). Yokohama,Japan:IEEE,2024:8778-8783.
[20]	XU A, VIRIYASUTHEE C, REKLEITIS I. Optimal complete terrain coverage using an unmanned aerial vehicle[C]// Proceedings of the 2011 IEEE International Conference on Robotics and Automation,Shanghai, China:IEEE,2011:2513-2519.
[21]	SHAHID S T, SIDDIQUE S M A, ALAM M M. UAV Survey Coverage Path Planning of Complex Regions Containing Exclusion Zones[J/OL]. Ithaca,NY, US: Cornell University, 2024(2024-11-11)[2025-03-15].https://doi.org/10.48550/arXiv.2411.07053.