一种考虑电池寿命的集成遗传算法，结合K均值和2优化方法，用于非结构化环境中多无人机（multi-UAVs）的离散覆盖路径规划

《ADVANCED ENGINEERING INFORMATICS》：A battery-aware integrated genetic algorithm with K-means and 2-optimization for multi-UAVs discrete coverage path planning in unstructured environment

多无人机协同离散覆盖路径规划中提出融合K-Means与2-Opt策略的改进遗传算法框架，通过聚类预处理缩小搜索空间，引入变异修复机制优化路径质量，结合电池感知动态重规划与三维A*路径寻迹实现安全高效任务执行，仿真验证显著提升规划效率与鲁棒性。

　　

王雯娜|钱华明

哈尔滨工程大学智能系统科学与工程学院，中国哈尔滨150001

摘要

随着多架无人机（multi-UAVs）在智能检测、应急响应和精准农业等应用中的部署不断增加，多无人机协同任务执行的复杂性也在不断提升。主要挑战在于提高协调效率、确保高质量路径规划以及增强对非结构化环境的适应能力。传统的遗传算法（GAs）在多无人机路径优化中常常存在收敛速度慢、路径交叉频繁以及生成的路径过长等问题。为了解决这些限制，本文提出了一种结合K-Means聚类和2-Opt算法的集成GA框架，用于低空非结构化环境中的多无人机协同离散覆盖路径规划（CPP）。首先，采用了一种改进的基于距离的K-Means聚类方法对目标点进行预处理，这有助于初始化GA种群、减少冗余搜索空间，并提高收敛速度和任务分配效率。其次，引入了一种突变-修复协同优化机制来纠正由突变引起的路径缺陷，从而在全局探索和局部细化之间取得平衡，以提高路径质量。最后，结合了电池意识的动态重新规划策略，整合了三维（3D）A*路径寻找和最优互避碰撞（ORCA）算法。通过将实际飞行路径与能耗模型相结合，该系统实现了闭环任务执行、能量监控和充电功能。仿真结果表明，所提出的方法显著提高了多无人机协同路径规划的效率、准确性和鲁棒性，为复杂现实环境中的部署提供了实用且可扩展的解决方案。

引言

多无人机技术的广泛应用已经改变了许多关键任务的应用，包括态势感知、低空勘测、环境监测和灾害响应操作。多无人机协同离散路径规划（CPP）已成为这些任务中的关键技术，它提高了效率、操作灵活性和安全性[1]、[2]。此外，通过实现分布式感知、任务分配和协调行动，它还提升了自主操作在多样化和动态环境中的效率和适应能力[3]。

在复杂、非结构化的环境中，无人机必须同时应对三个主要挑战：（1）三维地形适应、（2）实时动态碰撞避免以及（3）全局续航优化[4]、[5]。通过协同操作，多无人机系统可以克服单架无人机在载荷能力、续航能力和感知范围方面的限制。此外，由于其成本效益高、操作灵活性强和机动性强，无人机在军事、科学和民用领域具有显著优势[6]。这些特性使得多无人机特别适合在偏远、危险或地形复杂的地区执行任务[7]。为了满足覆盖任务的需求，协同离散路径规划的主要目标是将任务空间划分为多个子区域，分配无人机覆盖每个区域，同时优化能耗，包括充电行为[8]。由于任务点分布不均和现实地形的复杂性，均匀覆盖通常是无法实现的[9]。因此，这个问题通常被表述为多旅行商问题（MTSP）的一个变种，而MTSP是一个著名的非确定性多项式时间复杂度（NP-hard）问题，带来了巨大的计算挑战[10]。在此背景下，本文旨在开发一个实用且高效的解决方案框架，以提高计算效率、改善规划质量，并在操作约束下实现可靠的碰撞避免。本研究的主要贡献如下：

•

基于距离的多无人机K-Means聚类：为了解决传统GA收敛效率低和路径交叉频繁的问题，提出了一种基于距离的多无人机K-Means聚类算法，用于指导初始区域划分和任务分配。

•

结合2-Opt策略的改进GA突变-修复机制：为了解决标准GA中随机突变导致的路径延长问题，提出了一种结合2-Opt策略的多无人机GA算法。该算法通过智能段交换有效修复了长距离路径缺陷，同时保持了全局探索和局部细化之间的最佳平衡。

•

具有碰撞避免功能的电池意识动态重新规划：为了确保在非结构化低空环境中的安全和节能飞行，提出了一种电池意识动态重新规划机制。该方法使无人机能够在不同操作状态之间适应性切换，同时保持实时碰撞避免和能量可持续性。

本文的主要结构如下：第2节回顾了多无人机CPP问题的相关文献；第3节介绍了所提出的结合K-Means和2-Opt策略的电池意识集成GA；第4节展示了仿真结果；第5节进行了讨论；第6节给出了结论。

问题描述和算法分类

解决多无人机协同离散CPP问题的现有方法大致可以分为三类：确定性方法、基于市场的拍卖方法和启发式算法。

(1)

确定性方法，如基于整数线性规划的方法，可以产生精确解。然而，它们的计算成本较高，不适合大规模或动态场景下的实时部署[11]。

(2)

基于市场的拍卖方法可以实现

提出的结合K-means和2-Opt策略的电池意识集成GA

为了解决多无人机在动态环境中的能量约束、任务分配和适应性问题，提出了一种结合基于距离的K-Means聚类方法和2-Opt策略的电池意识集成GA。过程从第3.1节的基本初始化配置开始。为了在考虑无人机与任务区域距离的同时平衡工作负载，第3.2节引入了基于距离的K-Means聚类算法。

仿真分析

本文提出的方法在配备第12代Intel Core (TM) i9-12900H 2.50 GHz CPU和16 GB RAM的Windows 11系统上实现，使用Visual Studio Community 2022和Unity 2021.1.3f1c1进行开发。实验数据分析使用Python 3.12在Anaconda和PyCharm 2024.2.0.1平台上完成。为了全面评估所提算法的性能，进行了仿真实验，重点关注其计算效率、路径

计算复杂性

CMTSP算法需要存储和计算所有成对距离。在遍历$n$个目标点后，其时间复杂度为$O\left(n^{\text{2}}\right)$。对于GMTSPC，目标位置根据它们相对于初始位置的角度分布被划分为多个扇区。GMTSPC的主要步骤是排序和点分配。因此，当扇区数量为$k$时，整体时间复杂度为$O(n\text{log}nk+nk+k^{\text{2}})$。GMTSPD的主要步骤是角度排序，其时间复杂度为

结论

本文的主要创新在于提出了一种结合K-Means聚类和2-Opt算法的集成GA，专门用于解决低空非结构化环境中多无人机的离散CPP问题。首先，将改进的基于距离的K-Means聚类算法与GA结合使用，通过预处理有效减少了搜索空间。仿真结果表明，与

CRediT作者贡献声明

王雯娜：撰写——原始稿件、可视化、验证、监督、软件开发、项目管理、方法论研究、数据分析、数据整理。钱华明：撰写——审稿与编辑、资金获取。

利益冲突声明

作者声明他们没有已知的可能影响本文工作的财务利益或个人关系。