基于时空密度聚类的异构无人机集群覆盖路径规划方法

陈进朝; 王洋; 张营; 尤涛; 卢岩涛; 杜承烈

doi:10.12263/DZXB.20240258

您当前的位置：

首页 >

文章列表页 >

基于时空密度聚类的异构无人机集群覆盖路径规划方法

面向无人系统的智能视觉算法 | 更新时间：2025-12-08

- 基于时空密度聚类的异构无人机集群覆盖路径规划方法
- Coverage Path Planning for Heterogeneous UAVs Based on Temporal-Spatial Density Clustering
- 电子学报 2025年53卷第3期页码：705-715
- 作者机构：
  
  西北工业大学计算机学院，陕西西安 710072
- 作者简介：
  
  [ "陈进朝男，1987年6月出生于河南省许昌市.现为西北工业大学计算机学院副研究员.主要研究方向为无人机及其集群系统、嵌入式与实时系统、机器学习、群体决策与智能控制.E-mail: cjc@nwpu.edu.cn" ]
  [ "王洋男，2000年2月出生于贵州省毕节市.现为西北工业大学计算机学院硕士研究生.主要研究方向为深度强化学习和无人机集群的智能控制.E-mail: m14728684922@163.com" ]
  [ "张营男，1989年4月出生于河南省南阳市.现为西北工业大学计算机学院副教授.主要研究方向为信息感知与系统认知、人机融合与增强智能、无人驾驶、自主决策与节能控制.E-mail: ying_zhang@nwpu.edu.cn" ]
  [ "尤涛男，1983年1月出生于河南省三门峡市.现为西北工业大学计算机学院副教授.主要研究方向为实时与嵌入式系统、自主决策与控制、故障诊断与处理、无人机系统智能控制.E-mail: youtao@nwpu.edu.cn" ]
  [ "卢岩涛男，1991年5月出生于陕西省西安市.现为西北工业大学计算机学院副教授.主要研究方向为无人驾驶、无人机集群动态感知、对抗性样本及鲁棒性强化、无人机集群协同决策.E-mail: yantaolu@nwpu.edu.cn" ]
  [ "杜承烈男，1970年10月出生于陕西省西安市.现为西北工业大学计算机学院教授.主要研究方向为实时分布式计算系统、信息物理融合系统、智能交通、分布式系统的建模、仿真和验证.E-mail: ducl@nwpu.edu.cn" ]
- 基金信息：
  
  国家自然科学基金(62106202);陕西省重点研发计划项目(2024GX-YBXM-118);航空科学基金(2023M073053003)
- DOI：10.12263/DZXB.20240258
  中图分类号： TP399;
- 收稿：2024-03-14，
  
  修回：2024-05-24，
  
  纸质出版：2025-03-25
- 稿件说明：
移动端阅览
陈进朝, 王洋, 张营, 等. 基于时空密度聚类的异构无人机集群覆盖路径规划方法[J]. 电子学报, 2025, 53(03): 705-715.

CHEN Jin-chao, WANG Yang, ZHANG Ying, et al. Coverage Path Planning for Heterogeneous UAVs Based on Temporal-Spatial Density Clustering[J]. Acta Electronica Sinica, 2025, 53(03): 705-715.
陈进朝, 王洋, 张营, 等. 基于时空密度聚类的异构无人机集群覆盖路径规划方法[J]. 电子学报, 2025, 53(03): 705-715. DOI：10.12263/DZXB.20240258

CHEN Jin-chao, WANG Yang, ZHANG Ying, et al. Coverage Path Planning for Heterogeneous UAVs Based on Temporal-Spatial Density Clustering[J]. Acta Electronica Sinica, 2025, 53(03): 705-715. DOI：10.12263/DZXB.20240258

摘要

覆盖路径规划是无人机集群实现搜索、搜救等全面探测性任务的关键技术之一.当前研究往往只关注单一区域内飞行路径的设计与优化，而较少能在多区域环境中依据无人机的性能实现区域的合理分配和区域间路径的高效寻优.同时，现有方法大多采用同构无人机集群来执行覆盖路径规划任务，忽略了无人机个体的能力差异，致使集群资源利用率不足且难以适应任务与环境的不确定性变化.本文聚焦于异构无人机集群在多区域上的覆盖路径规划问题.首先，构建了具有异构特性的无人机模型，分析了覆盖路径规划问题的路径要求和能耗约束，并以最小化任务完成时间为目标，给出了基于混合整数线性规划的精确求解公式，以获得无人机集群的最佳飞行路径方案.随后，进一步提出了一种基于时空密度聚类的启发式算法来提高覆盖路径规划问题的求解效率，依据区域在时间和空间上的密度进行汇聚，形成各个无人机待覆盖的区域簇，并优化簇内区域间的覆盖顺序和区域内的扫描路径，以保证覆盖任务的高效完成.实验结果表明，所提出方法可在较短时间内产生有效的飞行路径，且路径长度可缩短10.55%、任务完成时间可降低5.47%.

Abstract

Coverage path planning is one of the key technologies for unmanned aerial vehicle(UAV) swarms in performing the exploration missions such as search and rescue. However

the current research often focuses on the design and optimization of flight paths in a single region

without taking into account quantitatively the effect of UAV capability on region division and start and end point selection in multi-region environment. Meanwhile

most of the existing methods use homogeneous UAV swarms to perform the coverage path planning task

ignoring the ability differences among the UAVs

resulting in a low utilization ratio of swarm resources and much difficulty in adapting to the uncertain changes of tasks and environments. This paper focuses on the coverage path planning problem of heterogeneous UAVs on multiple regions. First

by modeling the heterogeneous UAVs and analyzing the road and energy constraints of the path planning problem

we propose an exact formulation based on mixed integer linear programming to completely search the solution space and to find the best flight roads for UAVs. Then we present an efficient path planning algorithm based on temporal-spatial density clustering to improve the solving efficiency of the coverage path planning problem. The proposed algorithm groups regions according to their densities in time and space

allocates a reasonable group to each UAV

and optimizes the visiting orders of regions and the scan paths in regions

ensuring that the coverage task would be finished effectively. Experimental results show that the proposed method will provide reasonable flight paths for UAVs

and the total flight length and the task completion time can be reduced by 10.55% and 5.47%

respectively.

关键词

Keywords

references

谈玲 , 许海 , 刘玉风 , 等 . 基于多无人机的空中计算网络资源分配算法 [J ] . 电子学报 , 2023 , 51 ( 11 ): 3070 - 3078 .

TAN L , XU H , LIU Y F , et al . Resource allocation algorithm of AirComp network based on multiple UAVs [J ] . Acta Electronica Sinica , 2023 , 51 ( 11 ): 3070 - 3078 . (in Chinese)

任双 , 周洁 , 高嵩 , 等 . 基于注意力机制的无人机集群协同分群控制算法 [J ] . 电子学报 , 2023 , 51 ( 7 ): 1898 - 1905 .

REN S , ZHOU J , GAO S , et al . Cooperative fission control algorithm of UAV swarm based on attention mechanism [J ] . Acta Electronica Sinica , 2023 , 51 ( 7 ): 1898 - 1905 . (in Chinese)

YU H L , MEIER K , ARGYLE M , et al . Cooperative path planning for target tracking in urban environments using unmanned air and ground vehicles [J ] . IEEE/ASME Transactions on Mechatronics , 2015 , 20 ( 2 ): 541 - 552 .

CHEN J C , DU C L , ZHANG Y , et al . A clustering-based coverage path planning method for autonomous heterogeneous UAVs [J ] . IEEE Transactions on Intelligent Transportation Systems , 2022 , 23 ( 12 ): 25546 - 25556 .

CHEN X C , CHEN J C , DU C L , et al . Region coverage path planning of multiple disconnected convex polygons based on simulated annealing algorithm [C ] // Proceedings of 2021 IEEE 4th International Conference on Computer and Communication Engineering Technology (CCET) . Piscataway : IEEE , 2021 : 238 - 242 .

ROBERGE V , TARBOUCHI M , LABONTE G . Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning [J ] . IEEE Transactions on Industrial Informatics , 2013 , 9 ( 1 ): 132 - 141 .

许凯波 , 鲁海燕 , 黄洋 , 等 . 基于双层蚁群算法和动态环境的机器人路径规划方法 [J ] . 电子学报 , 2019 , 47 ( 10 ): 2166 - 2176 .

XU K B , LU H Y , HUANG Y , et al . Robot path planning based on double-layer ant colony optimization algorithm and dynamic environment [J ] . Acta Electronica Sinica , 2019 , 47 ( 10 ): 2166 - 2176 . (in Chinese)

DI FRANCO C , BUTTAZZO G . Coverage path planning for UAVs photogrammetry with energy and resolution constraints [J ] . Journal of Intelligent & Robotic Systems , 2016 , 83 ( 3 ): 445 - 462 .

LI Y , CHEN H , JOO ER M , et al . Coverage path planning for UAVs based on enhanced exact cellular decomposition method [J ] . Mechatronics , 2011 , 21 ( 5 ): 876 - 885 .

陈海 , 王新民 , 焦裕松 , 等 . 一种凸多边形区域的无人机覆盖航迹规划算法 [J ] . 航空学报 , 2010 , 31 ( 9 ): 1802 - 1808 .

CHEN H , WANG X M , JIAO Y S , et al . An algorithm of coverage flight path planning for UAVs in convex polygon areas [J ] . Acta Aeronautica et Astronautica Sinica , 2010 , 31 ( 9 ): 1802 - 1808 . (in Chinese)

ZHANG Z , LI J X , WANG J . Sequential convex programming for nonlinear optimal control problem in UAV path planning [C ] // Proceedings of 2017 American Control Conference (ACC) . Piscataway : IEEE , 2017 : 1966 - 1971 .

HAWARY A F , CHIPPERFIELD A J . Routing strategy for coverage path planning in agricultural monitoring activity using UAV [C ] // Proceedings of 2016 International Congress on Recent Development in Engineering and Technology (RDET) . Kuala : EARET , 2016 : 68 - 74 .

SAHINGOZ O K . Flyable path planning for a multi-UAV system with Genetic Algorithms and Bezier curves [C ] // Proceedings of 2013 International Conference on Unmanned Aircraft Systems (ICUAS) . Piscataway : IEEE , 2013 : 41 - 48 .

YUE X , ZHANG W . UAV path planning based on K-means algorithm and simulated annealing algorithm [C ] // Proceedings of 2018 37th Chinese Control Conference (CCC) . Piscataway : IEEE , 2018 : 2290 - 2295 .

SUN Y , CHEN J C , DU C L . Path planning of UAVs based on improved ant colony system [C ] // Proceedings of 2020 IEEE International Conference on Progress in Informatics and Computing (PIC) . Piscataway : IEEE , 2020 : 396 - 400 .

CHEN J C , ZHANG Y , WU L W , et al . An adaptive clustering-based algorithm for automatic path planning of heterogeneous UAVs [J ] . IEEE Transactions on Intelligent Transportation Systems , 2022 , 23 ( 9 ): 16842 - 16853 .

SUN Y , CHEN J C , DU C L , et al . Path planning of UAVs based on improved clustering algorithm and ant colony system algorithm [C ] // Proceedings of 2020 IEEE 5th Information Technology and Mechatronics Engineering Conference (ITOEC) . Piscataway : IEEE , 2020 : 1097 - 1101 .

CHEN J C , DU C L , LU X , et al . Multi-region coverage path planning for heterogeneous unmanned aerial vehicles systems [C ] // Proceedings of 2019 IEEE International Conference on Service-Oriented System Engineering (SOSE) . Piscataway : IEEE , 2019 : 356 - 3565 .

RODRIGUEZ A , LAIO A . Clustering by fast search and find of density peaks [J ] . Science , 2014 , 344 ( 6191 ): 1492 - 1496 .

CHEN X Y , DAI Y H . Research on an improved ant colony algorithm fusion with genetic algorithm for route planning [C ] // Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) . IEEE , 2020 : 1273 - 1278 .

ANTUNES J R , BRISOLARA L , FERREIRA P R . UAVs as data collectors in the WSNs: Investigating the effects of back-and-forth and spiral coverage paths in the network lifetime [C ] // 2020 X Brazilian Symposium on Computing Systems Engineering (SBESC) . Piscataway : IEEE , 2020 : 1 - 8 .

CHEN J C , LING F Y , ZHANG Y , et al . Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system [J ] . Swarm and Evolutionary Computation , 2022 , 69 : 101005 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

侵蚀聚类