无人机分散凸区域覆盖路径规划

doi:10.12305/j.issn.1001-506X.2026.11.17

摘要/Abstract

摘要：

覆盖路径规划是无人机完成任务的关键。将多区域覆盖路径规划问题建模为旅行商问题，针对单机多区域覆盖路径规划，提出基于可视图和动态规划方法的路径规划算法，解决考虑避障的多区域覆盖搜索问题，实现从原点出发并返回原点的多区域覆盖搜索最短路径规划。针对多机大规模区域覆盖路径规划，提出一种“两阶段”路径规划方法，该方法综合启发式区域分配和滚动时域精确求解，相比于一步优化算法，具有更高的灵活性和计算效率。最后，通过仿真实验和对比分析验证了所提方法的有效性和实用性。

关键词: 覆盖路径规划, 旅行商问题, 动态规划, 可视图, 启发式算法

Abstract:

Coverage path planning （CPP） is crucial for unmanned aerial vehicle （UAV） to complete tasks. The multi-region CPP problem is modeled as a traveling salesman problem. For single-UAV multi-region CPP, a path planning algorithm based on visibility graphs and dynamic programming method is proposed, which solves the multi-region coverage search problem considering obstacle avoidance, achieving the shortest path planning for multi-region coverage search starting from and returning to the origin. For multi-UAV large-scale region CPP, a “two-stage” path planning method is proposed, which integrates heuristic region allocation and rolling horizon precise solution. Compared with one-step optimization algorithms, the proposed method exhibits higher flexibility and computational efficiency. Finally, the effectiveness and practicality of the proposed method are verified through simulation experiments and comparative analysis.

Key words: coverage path planning（CPP）, traveling salesman problem（TSP）, dynamic programming, visibility graph, heuristic algorithm

中图分类号:

周瑜, 黄馨源, 李杰, 王祥科. 无人机分散凸区域覆盖路径规划[J]. 系统工程与电子技术, 2026, 48(11): 3861-3871.

Yu Zhou, Xinyuan Huang, Jie Li, Xiangke Wang. Unmanned aerial vehicle coverage path planning for dispersed convex regions[J]. Systems Engineering and Electronics, 2026, 48(11): 3861-3871.

图/表 21

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

图17

图18

表1

图19

图20

参考文献 42

1	Xue X Y, Tian Y, Yang Z Y, et al. Research on a UAV spray system combined with grid atomized droplets[J]. Frontiers in Plant Science, 2024, 14, 1286332. doi: 10.3389/fpls.2023.1286332
2	Cruz H, Eckert M, Meneses J, et al. Efficient forest fire detection index for application in unmanned aerial systems （UASs）[J]. Sensors, 2016, 16 (6): 893. doi: 10.3390/s16060893
3	Pan M X, Chen C C, Yin X J, et al. UAV-aided emergency environmental monitoring in infrastructure-less areas: Lora mesh networking approach[J]. IEEE Internet of Things Journal, 2022, 9 (4): 2918. doi: 10.1109/JIOT.2021.3095494
4	Xie J F, Chen J. Multiregional coverage path planning for multiple energy constrained UAVs[J]. IEEE Trans. on Intelligent Transportation Systems, 2022, 23 (10): 17366. doi: 10.1109/TITS.2022.3160402
5	Yang H T, Lu X Q, Zhou X A, et al. Expected length of the shortest path of the traveling salesman problem in 3D space[J]. Journal of Advanced Transportation, 2022, 2022 (1): 124950.
6	Dijkstra E W. A note on two problems in connexion with graphs[M]//Krzysztof R, Hoare T, ed. Edsger Wybe Dijkstra: His Life,Work, and Legacy. New York: Association for Computing Machinery, 2022: 287.
7	Zhang J, Bai J P. Dijkstra algorithm based cooperative caching strategy for UAV-assisted edge computing system[J]. Wireless Networks, 2024, 30 (3): 1201. doi: 10.1007/s11276-023-03551-x
8	Sadaf J, Ali H, Rizwan A, et al. State-of-the-art and future research challenges in UAV swarms[J]. IEEE Internet of Things Journal, 2024, 11 (11): 19023. doi: 10.1109/JIOT.2024.3364230
9	Xiao H, Sun C M, Wang W S. UAV route planning and light searching method based on optical sensing[J]. IEEE Internet of Things Journal, 2025, 12 (12): 21931. doi: 10.1109/JIOT.2025.3550126
10	Zhang H H, Gan X S, Li S F, et al. UAV safe route planning based on PSO-BAS algorithm[J]. Journal of Systems Engineering and Electronics, 2022, 33 (5): 1151. doi: 10.23919/JSEE.2022.000111
11	Liu Z Y, Li L H, Zhang X, et al. Considering both energy effectiveness and flight safety in UAV trajectory planning for intelligent logistics[J]. Vehicular Communications, 2025, 52, 100885. doi: 10.1016/j.vehcom.2025.100885
12	Abid M, El K S, Amzil A, et al. Optimization of UAV flight paths in multi-UAV networks for efficient data collection[J]. Arabian Journal for Science and Engineering, 2024, 50 (10): 7207.
13	Gustavo S C A, Guilherme P, Pimenta A S, et al. Multi-UAV routing for area coverage and remote sensing with minimum time[J]. Sensors, 2015, 15（11）, 27783. doi: 10.3390/s151127783
14	Luciano B, Egidio D A, Massimiliano M, et al. Path planning and real-time collision avoidance based on the essential visibility graph[J]. Applied Sciences, 2020, 10 (16): 5613. doi: 10.3390/app10165613
15	Ilyas H, Issmail E H, Francois S. A multiphase dynamic programming algorithm for the shortest path problem with resource constraints[J]. European Journal of Operational Research, 2024, 315 (2): 470. doi: 10.1016/j.ejor.2023.11.047
16	Hart P, Nilsson N, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Trans. on Systems Science and Cybernetics, 1968, 4 (2): 100. doi: 10.1109/TSSC.1968.300136
17	Khatib O. Real time obstacle avoidance for manipulators and mobile robots[C]//IEEE International Conference on Robotics and Automation, 1985: 500.
18	Lin H I, Muhammad A F S, Ming F H. Robot path planning based on three-dimensional artificial potential field[J]. Engineering Applications of Artificial Intelligence, 2025, 144, 110127. doi: 10.1016/j.engappai.2025.110127
19	Wang Y Q, Zhu J, Huang H P, et al. Bi-objective ant colony optimization for trajectory planning and task offloading in UAV-assisted MEC systems [J]. IEEE Trans. on Mobile Computing, 2024, 23(12): 12360.
20	Zhi L W, Zuo Y. Collaborative path planning of multiple AUVs based on adaptive multi-population PSO[J]. Journal of Marine Science and Engineering, 2024, 12 (2): 223. doi: 10.3390/jmse12020223
21	Debnath D, Vanegas F, Boiteau S, et al. An integrated geometric obstacle avoidance and genetic algorithm TSP model for UAV path planning[J]. Drones, 2024, 8, 302. doi: 10.3390/drones8070302
22	Zang Y C, Huang X Q, Lu M, et al. E²VRP-CPP: an energy-efficient approach for multi-UAV multi-region coverage path planning optimization in the enhanced vehicle routing problem[J]. Drones, 2025, 9 (3): 200. doi: 10.3390/drones9030200
23	Xie J F, Carrillo L R G, Jin L. Path planning for UAV to cover multiple separated convex polygonal regions[J]. IEEE Access, 2020, 8, 51770. doi: 10.1109/ACCESS.2020.2980203
24	Little J D C, Murty K G, Sweeney D W, et al. An algorithm for the traveling salesman problem[J]. Operations Research, 1963, 11 (6): 972. doi: 10.1287/opre.11.6.972
25	Luna M A, Isaac M S A, Cortizas M F, et al. Spiral coverage path planning for multi-UAV photovoltaic panel inspection applications[C]//International Conference on Unmanned Aircraft Systems, 2023.
26	Luna M A, Molina M, Gomez R D S, et al. A multi-UAV system for coverage path planning applications with in-flight re-planning capabilities[J]. Journal of Field Robotics, 2024, 41 (5): 1480. doi: 10.1002/rob.22342
27	Wang L, Zhuang X D, Zhang W T, et al. Coverage path planning for UAVs: an energy-efficient method in convex and non-convex mixed regions[J]. Drones, 2024, 8 (12): 776. doi: 10.3390/drones8120776
28	Datsko D, Nekovar F, Penicka R, et al. Energy-aware multi-UAV coverage mission planning with optimal speed of flight[J]. IEEE Robotics and Automation Letters, 2024, 9 (3): 2893. doi: 10.1109/LRA.2024.3358581
29	闫川, 甄子洋, 张继豪, 等. 突防飞行与多区域搜索一体化侦察航迹规划[J]. 飞行力学, 2023, 41 (1): 20.
30	田双喜, 陈洪辉, 徐彬杰, 等. 车辆支持的多无人机多区域覆盖路径规划算法[J]. 国防科技大学学报, 2024, 46 (6): 227.
31	夏阳升, 石建迈, 陈超, 等. 车机协同多区域覆盖侦察路径规划方法[J]. 指挥与控制学报, 2020, 6 (4): 372.
32	刘瑶, 夏阳升, 石建迈, 等. 车载多无人机协同多区域覆盖路径规划方法[J]. 系统工程与电子技术, 2023, 45 (5): 1380.
33	杨鹏程, 杨清清, 高盈盈, 等. 基于强化学习的海上移动目标搜索路径规划 [EB/OL]. [2025-06-01]. https: //link. cnki. net/urlid/11.2422. tn. 20240614.1103. 005.
34	Zhao C Y, Liu J, Yoon S, et al. Energy constrained multi-agent reinforcement learning for coverage path planning[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems, 2023.
35	Lasse D N, Inkyung S, Peter N. Convex decomposition for a coverage path planning for autonomous vehicles: interior extension of edges[J]. Sensors, 2019, 19 (19): 4165. doi: 10.3390/s19194165
36	Vink K, Solomon G, Ali K. An area-decomposition based approach for cooperative tasking and coordination of UAVs in a search and coverage mission[C]//IEEE Aerospace Conference, 2019.
37	陈海, 王新民, 焦裕松, 等. 一种凸多边形区域的无人机覆盖航迹规划算法[J]. 航空学报, 2010, 31 (9): 1802.
38	Lozano P, Wesley M A. An algorithm for planning collision-free paths among polyhedral obstacles[J]. Communications of the ACM, 1979, 22 (10): 560. doi: 10.1145/359156.359164
39	Hu X B, Yang C S, Zhou J, et al. Research on 3D layered visibility graph route network model and multi-objective path planning for UAVs in complex urban environments[J]. Aerospace Science and Technology, 2025, 159, 109947. doi: 10.1016/j.ast.2025.109947
40	Singh A, Baghel A S. A new grouping genetic algorithm approach to the multiple traveling salespers on problem[J]. Soft Computing, 2009, 13 (1): 95. doi: 10.1007/s00500-008-0312-1
41	Johnson D S, Mcgeoch L A. The traveling salesman problem: a case study in local optimization[J]. Local Search in Combinatorial Optimization, 1997, 1(1): 215.
42	夏小云, 庄鹤林, 杨火根, 等. 自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题[J]. 计算机集成制造系统, 2022, 28 (11): 3545.

区域数	UAV数	所有UAV总飞行距离/m		UAV飞行距离标准差/m		优化用时/s
区域数	UAV数	文献[4]	本文	文献[4]	本文	文献[4]	本文
10	2	2080	2058	44.9	71.3	0.35	0.70
10	3	2206	2184	33.0	32.6	0.73	1.03
20	4	3882	3884	45.9	34.0	2.89	2.86
20	5	4140	3987	60.0	35.7	3.28	3.15
20	6	4273	4237	59.2	40.8	3.37	3.30
25	5	5819	5686	88.9	37.3	4.89	4.64
25	6	5933	5885	71.0	47.0	5.06	5.00
30	5	6801	6380	104.5	42.9	7.22	7.14
30	6	6959	6665	108.6	46.6	9.45	7.67

[1]	汤罗浩, 雷洪涛, 石建迈, 刁博阳, 朱承. 多平台协同鲁棒团队形成问题与算法[J]. 系统工程与电子技术, 2026, 48(8): 2659-2668.
[2]	周晨宇, 张超, 李聪. 基于空闲资源碎片整合的测控数传一体化资源调度算法[J]. 系统工程与电子技术, 2026, 48(6): 1946-1964.
[3]	羊钊, 胡锦标, 王艳, 齐洪彪. 考虑异巢起降的无人机山地巡检覆盖路径规划[J]. 系统工程与电子技术, 2025, 47(8): 2622-2631.
[4]	陈威, 王从庆, 曾强, 李战. 面向飞机表面视觉检查的无人机覆盖路径规划[J]. 系统工程与电子技术, 2025, 47(4): 1206-1213.
[5]	于海宝, 许卫东, 谢雨谋, 魏洪, 叶雨佳, 郑龙华. 基于动态规划的阵地伪装方案优化方法[J]. 系统工程与电子技术, 2025, 47(11): 3721-3728.
[6]	师明, 高宇辉, 张弓. 基于HTN的巡视器动态规划方法[J]. 系统工程与电子技术, 2024, 46(2): 631-639.
[7]	刘瑶, 夏阳升, 石建迈, 陈超, 黄金才. 车载多无人机协同多区域覆盖路径规划方法[J]. 系统工程与电子技术, 2023, 45(5): 1380-1390.
[8]	吴靖宇, 朱世强, 宋伟, 施浩磊, 吴泽南. 基于改进单元分解法的全覆盖路径规划[J]. 系统工程与电子技术, 2023, 45(12): 3949-3957.
[9]	张佳唯, 钱凤臣, 杨俊强, 赵骞, 张峥嵘. 弹性光网络中路由与频谱分配算法综述[J]. 系统工程与电子技术, 2022, 44(6): 2001-2010.
[10]	赵长啸, 李二帅, 何锋, 王鹏. TSN时间敏感流量带宽分配与优化[J]. 系统工程与电子技术, 2022, 44(6): 2027-2034.
[11]	辛立强, 张超, 赵灵芝, 刘建平. 面向复杂关联测控需求的冲突规避调度算法[J]. 系统工程与电子技术, 2022, 44(5): 1581-1588.
[12]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[13]	郭建国, 苏亚鲁. 高超飞行器自适应动态规划的控制系统设计[J]. 系统工程与电子技术, 2021, 43(6): 1628-1635.
[14]	周鑫, 王维平, 朱一凡, 王涛, 井田. 基于顺次分配机制的无人装备体系架构方案空间搜索方法[J]. 系统工程与电子技术, 2021, 43(11): 3211-3219.
[15]	吴文海, 郭晓峰, 周思羽. 基于NURBS和GOBL-ACDE的航迹规划算法[J]. 系统工程与电子技术, 2020, 42(5): 1073-1082.