摘要
覆盖路径规划是无人机集群实现搜索、搜救等全面探测性任务的关键技术之一.当前研究往往只关注单一区域内飞行路径的设计与优化,而较少能在多区域环境中依据无人机的性能实现区域的合理分配和区域间路径的高效寻优.同时,现有方法大多采用同构无人机集群来执行覆盖路径规划任务,忽略了无人机个体的能力差异,致使集群资源利用率不足且难以适应任务与环境的不确定性变化.本文聚焦于异构无人机集群在多区域上的覆盖路径规划问题.首先,构建了具有异构特性的无人机模型,分析了覆盖路径规划问题的路径要求和能耗约束,并以最小化任务完成时间为目标,给出了基于混合整数线性规划的精确求解公式,以获得无人机集群的最佳飞行路径方案.随后,进一步提出了一种基于时空密度聚类的启发式算法来提高覆盖路径规划问题的求解效率,依据区域在时间和空间上的密度进行汇聚,形成各个无人机待覆盖的区域簇,并优化簇内区域间的覆盖顺序和区域内的扫描路径,以保证覆盖任务的高效完成.实验结果表明,所提出方法可在较短时间内产生有效的飞行路径,且路径长度可缩短10.55%、任务完成时间可降低5.47%.
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.
作者
陈进朝
王洋
张营
尤涛
卢岩涛
杜承烈
CHEN Jin-chao;WANG Yang;ZHANG Ying;YOU Tao;LU Yan-tao;DU Cheng-lie(School of Computer Science,Northwestern Polytechnical University,Xi’an,Shaanxi 710072,China)
出处
《电子学报》
北大核心
2025年第3期705-715,共11页
Acta Electronica Sinica
基金
国家自然科学基金(No.62106202)
陕西省重点研发计划项目(No.2024GX-YBXM-118)
航空科学基金(No.2023M073053003)。
关键词
覆盖路径规划
异构无人机集群
时空密度
密度聚类
混合整数线性规划
coverage path planning
heterogeneous unmanned aerial vehicle swarms
temporal-spatial density
density-based clustering
mixed integer linear programming
