复杂平面区域的无人机覆盖路径规划技术

doi:10.12382/bgxb.2025.0229

摘要/Abstract

摘要：

旋翼无人机凭借其卓越的灵活性和多功能性，在电力巡检、农林植保和反恐救援等领域得到了广泛应用。然而在复杂平面区域作业中，不规则地形的二维覆盖问题对路径规划提出了严峻挑战。针对这一问题，提出一种复杂平面区域的无人机覆盖路径规划技术，在区域分解阶段，采用方向容差-牛耕分解法，消除分解产生的冗余狭长区域，显著降低后续路径规划中的折返频次；在覆盖路径生成阶段，采用4模覆盖TSP规划法，设计4种覆盖模式并动态配置端点，并在分解得到的子区域间构建多模式旅行商问题，采用动态规划方法将计算复杂度由O(n！·4ⁿ)降至O(|π_ϵ|·n·4²)，兼顾计算效率的同时提升区域覆盖任务效率。实验结果表明：该技术在城镇、机场、山区、城市、林地5个场景中，平均航点数量减少27.24%，任务距离缩短26.12%，任务预估时间减少26.20%，验证了其在复杂平面区域中降低路径冗余、提升任务效率的显著优势，为旋翼无人机覆盖路径作业提供了高效解决方案。

关键词: 路径规划, 覆盖路径规划, 牛耕分解法, 多模式旅行商问题

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

张天, 胡蕴琪, 陈昭文, 王强, 杨志来, 国萌. 复杂平面区域的无人机覆盖路径规划技术[J]. 兵工学报, 2025, 46(S1): 250229-.

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-.

图/表 12

图1 复杂区域的CPP任务

Fig.1 CPP task in a complex region

图2 区域分解与CPP流程图

Fig.2 Flowchart of region decomposition and coverage path planning

图3 TCD与BCD区域分解示例

Fig.3 TCD and BCD Domain Decomposition Example

图4 BCD示例

Fig.4 Example of the BCD

图5 子区域在不同扫描线方向下的单元高度

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

图6 覆盖路径时补充扫描线示例

Fig.6 Example of supplementary scanning lines during coverage path

图7 同一扫描线方向下生成的4种覆盖路径形式

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

图8 区域分解优化示意图

Fig.8 Domain decomposition optimization schematic diagram

图9 不同策略下BCD分解后形成的CPP结果图

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

图10 采用覆盖路径优化前后的CPP结果图

Fig.10 Coverage path planning results before and after optimization

表1 5个CPP任务的任务区域、Bahnemann等[15]的方法(传统方法)规划结果、本方案规划结果对比

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

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

表2 不同场景下结果对比

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%

参考文献 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.