Coverage Path Planning for Heterogeneous UAVs Based on Temporal-Spatial Density Clustering

CHEN Jin-chao; WANG Yang; ZHANG Ying; YOU Tao; LU Yan-tao; DU Cheng-lie

doi:10.12263/DZXB.20240258

您当前的位置：

首页 >

文章列表页 >

Coverage Path Planning for Heterogeneous UAVs Based on Temporal-Spatial Density Clustering

Intelligent Vision Algorithms for Unmanned Systems | 更新时间：2025-12-08

- Coverage Path Planning for Heterogeneous UAVs Based on Temporal-Spatial Density Clustering
- ACTA ELECTRONICA SINICA Vol. 53, Issue 3, Pages: 705-715(2025)
- 作者机构：
  
  西北工业大学计算机学院，陕西西安 710072
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62106202);Key Research and Development Program of Shaanxi Province(2024GX-YBXM-118);Aeronautical Science Foundation of China(2023M073053003)
- DOI：10.12263/DZXB.20240258
  CLC： TP399;
- Received：14 March 2024，
  
  Revised：2024-05-24，
  
  Published：25 March 2025
- 稿件说明：
移动端阅览
陈进朝, 王洋, 张营, 等. 基于时空密度聚类的异构无人机集群覆盖路径规划方法[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Erosion Clustering

Related Author

DU Ming-jing

WU Fu-yu

LI Yu-rui

DONG Yong-quan

WU Fu-yu

DONG Yong-quan

LI Yu-rui

DU Ming-jing

Related Institution

School of Computer Science and Technology, Jiangsu Normal University

Jiangsu Key Laboratory of Educational Intelligent Technology, Jiangsu Normal University

⁰