本发明公开了一种异构无人机群协同电力巡检方法，包括以下步骤：步骤1，建立多目标优化的任务分配模型，包括异构无人机群模型和电力装置巡检任务模型；步骤2，建立异构无人机巡检任务的代价函数，包括异构无人机巡检任务收益和异构无人机巡检任务损失；步骤3，基于蒙特卡洛树搜索算法，求解最优代价函数，得到每个无人机的任务序列；步骤4，利用已有的航迹规划算法对每个无人机的航迹进行规划。本发明的方法可以实现多型号无人机共存情形下的无人机群的电力装置巡检，相比较传统方法，可以合理调配各型无人机参与巡检，降低无人机巡检成本，提高电力巡检效率。
1.一种异构无人机群协同电力巡检方法，其特征在于，包括以下步骤：
步骤1，建立异构无人机群协同电力巡检的任务分配模型，包括异构无人机群模型和电力装置巡检任务模型；
步骤2，基于任务分配模型建立异构无人机群巡检任务分配的多目标优化问题，包括定义巡检任务的代价函数为异构无人机巡检任务收益和异构无人机巡检任务损失的差值，以及定义多目标优化问题；其中，所述代价函数表示为：J(V,T)＝Re(V,T)‑Cost(V,T)，Re(V,T)、Cost(V,T)分别为异构无人机巡检任务收益、任务损失，其中，所述异构无人机巡检任务收益具体表示为：式中，pij为无人机Vi访问任务点Tj得到的收益率：
其中，|·|表示相应载荷数量，STj表示载荷需求， 表示无人机的资源载荷；
式中，Value(Tj)为巡检任务Tj的预设价值， nk
为定点检视任务中任务点Tj范围内的待检视目标数量，vi为每个待检视目标的单位价值，K和distance分别为线路巡查任务中电力线路的单位价值和任务点Tj范围内的电力线总长度；
其中， 表示无人机单位航程燃耗代价，(xi(t0),yi(t0),zi(t0))为任务规划决策做出时的无人机坐标，(Xj1,Yj1,Zj1)、(Xj2,Yj2,Zj2)分别是任务Tj起点和终点的三维坐标；
多目标优化问题的数学描述为寻找最优的{xij},i＝1,2,...,N,j＝1,2,...,M使得：maxJ(V,T)
其中，J(V,T)为巡检任务的代价函数， 为任务点Tj的最大性能约束， 表示无人机的资源载荷， 表示无人机的性能约束，上式保证参与任务点Tj巡检的无人机序列的最大航速和最小航速满足任务需要；
步骤3，基于蒙特卡洛树搜索算法，求解最优代价函数，得到每个无人机的任务序列并分配给各个无人机，具体的，基于蒙特卡洛树搜索MCTS算法求解最优代价函数，包括首先输入当前需要参与巡检的无人机信息和任务点信息，然后根据无人机及任务信息，构建MCTS搜索树；MCTS搜索树上每个节点存储一个表格，表示当前时刻的任务分配方案；同时每个节点记录当前节点处得到的代价函数和访问次数，以及无人机执行任务的序列；通过选择、扩展、模拟、回溯四个步骤循环进行MCTS搜索树的构建，直至达到循环中止条件，输出任务分配情况；
步骤4，各个无人机基于分配的任务序列执行任务，实现无人机群的电力巡检。
2.根据权利要求1所述的异构无人机群协同电力巡检方法，其特征在于，所述步骤1的异构无人机群模型包括N个巡检无人机，第i个无人机Vi的属性集合表示为其中， 表示无人机类型， 表示无人机单位航程燃耗代价， 表示无人机的资源载荷，包括光电吊舱、相机、红外热像仪， 表示无人机的性能约束，包括最大航程、转弯半径、滞空时间、极限航速与升限；电力装置巡检任务模型的任务分为：定点检视任务和线路巡查任务，单次执行的任务为一个或者由若干个定点检视任务和线路巡查任务的组合。
3.根据权利要求1或2所述的异构无人机群协同电力巡检方法，其特征在于：步骤2中任务分配的多目标优化问题，对于需要多个资源载荷的任务，将任务指派给单个搭载所有所需载荷的无人机或通过组建无人机联盟的形式执行该任务；多目标优化问题为：在无人机满足任务性能约束条件的前提下，对于参与电力巡检的每个无人机Vi,i＝1,2,...,N，找到其对应的任务序列Seqi＝{Tp,Tq,...,Tr},Tp,Tq,...,Tr∈T，使得所有无人机总的任务代价函数J(V,T)最大。
4.根据权利要求1所述的异构无人机群协同电力巡检方法，其特征在于，步骤3中基于蒙特卡洛树搜索算法求解最优代价函数的具体步骤为：步骤3.1：输入参与巡检的无人机信息和任务点信息；
步骤3.2：定义MCTS搜索树的节点，MCTS搜索树的每个节点处存储一个表格，代表当前时刻的任务分配方案，表中第i行第j列元素为xij；每个节点记录当前任务分配方案的代价函数J(V,T)和访问次数N(s0)，以及无人机执行任务的序列X＝{xij}；任务规划开始，初始化MCTS搜索树，根节点处所有无人机均未被分配任务；
步骤3.3：从根节点出发，根据UCB公式选择每层的子节点，直到到达一个可扩展节点；
步骤3.4：从可扩展节点出发，根据任务约束随机选择一个状态xij将其置1，并将其作为新节点添加到MCTS搜索树，更新当前节点无人机执行任务的序列X＝X∪xij，xij为本步中置
步骤3.5：对于步骤3.4中新添加的子节点，通过模拟，对该节点的价值进行估计；模拟是指从新节点出发，不断执行步骤3.4的扩展操作，直至达到搜索结束条件，搜索结束条件为完成所有任务分配或规划时间超过规定搜索时间；
步骤3.6：将执行步骤3.5得到的新节点的代价回溯给该节点所在的整个搜索树支路，同时更新每个节点的访问次数；
步骤3.7：如果当前时刻未超过规定的搜索时间，返回步骤3.3；
步骤3.8：如果当前时刻超过规定搜索时间，从根节点出发，根据UCB公式选择每层的子节点直至最后一层，输出最终节点存储的无人机执行任务序列X；
步骤3.9：输入步骤3.8得到的无人机执行任务序列X，将其转化任务分配表格，对于第i行依次输出xij,j＝1,2,...,M得到无人机Vi对应的任务序列Seqi＝{Tp,Tq,...,Tr},Tp,Tq,...,Tr∈T，每个无人机依次执行序列任务；
步骤3.10：如果得到的无人机序列能够完成所有任务点的巡检，则表示求得的任务序列为此次无人机巡检任务的任务分配方案，此时输出每个无人机Vi的任务序列Seqi＝{Tp,Tq,...,Tr},Tp,Tq,...,Tr∈T，任务规划结束，执行步骤4，否则进入步骤
步骤3.11：如果得到的无人机序列无法完成所有任务点的巡检，则根据当前无人机状态，对所有未完成任务进行再次分配，更新所有未被执行的任务点信息和当前时刻的无人机信息，重新执行步骤3.1到步骤3.9的任务规划过程。
5.根据权利要求4所述的异构无人机群协同电力巡检方法，其特征在于：UCB公式表示为：式中，J(V,T)为此时刻对应的无人机巡检代价函数，N(s0)为当前节点在搜索树上的访问次数，N(sk)为当前节点的父节点访问次数，c为平衡搜索树搜索和扩展的常值系数。
一种异构无人机群协同电力巡检方法
技术领域
[0001] 本发明涉及无人机电力巡检技术领域，具体地说，涉及一种异构无人机群协同电力巡检方法，本发明中所述的异构无人机群包括搭载不同载荷的多旋翼无人机、固定翼无人机、无人直升机。
背景技术
[0002] 由于我国面积广阔，地形地貌复杂多变，架空输电线路常常需要穿越森林、高山、丘陵等复杂地形。架空输电线路中的绝缘子、导线和金具等电力设备长期暴露野外，需要承受着设备的自然损耗、人为破坏、雷击、冰雪和暴雨等外部风险；同时，这些电力设备还长期承受着内部高电流的冲击。随着输电线路运行时间的增加，上述问题易导致输电线路中的主要部件产生损坏或故障隐患。
[0003] 长期以来，为保证电力的安全稳定运行，电力巡线工作主要以人工巡检方式为主。该方式不仅巡检效率低，而且巡检人员也存在着人身安全隐患。近年来，无人机和计算机视觉的发展为输电线路的稳定运行和维护提供了新的方法和手段。利用计算机视觉技术对无人机航拍图像中的电力设备进行自动检测成为提高工作效率、保障工作人员安全、维护电力稳定运行的重要途径。
[0004] 另一方面，由于电力部门内部的采购差异以及实际巡检需要，当前的无人机电力巡检中存在包括多旋翼无人机、固定翼无人机以及无人直升机在内的多型号无人机，由多型号无人机构成的异构无人机群进行任务分配时，由于无人机功能的差异及各种任务的不同，其任务分配问题比单一型号多无人机任务分配问题更加复杂。合理调配各型无人机参与巡检，对不同类型的多架无人机进行任务规划，有助于合理降低无人机出动频率，降低无人机巡检成本，提高电力巡检效率。常用的无人机任务分配方法集中于同构无人机的任务规划，应用较多的方法包括粒子群算法、多无人机的遗传算法等，但这些方法不能很好的解决本发明涉及的多异构无人机的任务规划问题。粒子群算法存在粒子早熟和容易陷入局部最优的问题，遗传算法在无人机数量较多时编码和解码过程复杂，同样容易陷入局部最优，而基于蒙特卡洛树搜索的任务分配方法通过增量非对称方式进行搜索树构建和扩展，在保证搜索时间有限的前提下尽可能寻求全局最优解，同时在构建搜索树时过多考虑无人机数量，搜索过程简单清晰，在解决面向无人机巡检作业的大规模无人机任务分配问题时收敛速度快。
发明内容
[0005] 针对上述提出的技术问题，本发明提供一种异构无人机群协同电力巡检方法，解决了目前电力巡检作业中存在的多型号无人机共存情形下无人机之间的任务分配问题。
[0006] 为实现以上目的，本发明针对当前电力巡检集群化、异构化的需求，提出了一种针对异构无人机群的协同电力巡检方法，首先由控制中心进行任务分配问题求解，将终端输入的巡检任务合理分配给附近无人机；接着对派出执行巡检作业任务的无人机进行航迹规划，使之能够避开飞行过程中的障碍物，高效完成巡检。具体包括以下步骤：
[0007] 步骤1，建立异构无人机群协同电力巡检的任务分配模型，包括异构无人机群模型和电力装置巡检任务模型；
[0008] 步骤2，基于任务分配模型建立异构无人机群巡检任务分配的多目标优化问题，包括定义巡检任务的代价函数为异构无人机巡检任务收益和异构无人机巡检任务损失的差值，以及定义多目标优化问题；
[0009] 步骤3，基于蒙特卡洛树搜索算法，求解最优代价函数，得到每个无人机的任务序列并分配给各个无人机；
[0010] 步骤4，各个无人机基于分配的任务序列执行任务，实现无人机群的电力巡检。
[0011] 有益效果
[0012] 1) 本发明通过约定异构无人机的载荷属性，建立了一种通用的多异构无人机电力巡检模型。
[0013] 2) 本发明通过蒙特卡洛树搜索策略进行多异构无人机任务建模和规划，能够有效解决电力巡检中存在的多无人机协同巡检问题，在求解大规模无人机任务分配问题时收敛速度快。
[0014] 3) 本发明实现了电力巡检无人机的任务分配以及分配后的无人机任务序列遍历顺序的一体化求解，输入无人机和任务点信息后可直接得出单个无人机的任务序列。
附图说明
[0015] 图1为本发明所提供的异构无人机群协同电力巡检任务分配流程图；
[0016] 图2为本发明所提供的异构无人机群协同电力巡检任务分配应用背景示意图；
[0017] 图3为本发明所提供的用于无人机任务规划的蒙特卡洛树搜索流程图；
[0018] 图4为本发明所提供的无人机任务规划输出的巡检任务分配方案示例；
[0019] 图5为本发明一个实施例的巡检开始时参与巡检的无人机和任务点分布情况；
[0020] 图6为本发明一个实施例的规划结束后无人机的巡检方案。
具体实施方式
[0021] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0022] 如图1至图4所示，本发明公开了一种异构无人机群协同电力巡检方法，其中多无人机任务规划主要解决的问题是：将任务群分配给各无人机。
[0023] 步骤1：基于多无人机巡检任务的特征，建立异构无人机群协同电力巡检的任务分配模型。
[0024] 首先建立异构无人机群模型。巡检作业中无人机的数量为N，以V={V1,V2,…,VN} 表示参与巡检任务的无人机集合，无人机提前部署于各个无人机机场，巡检作业时从无人机机场起飞执行巡检任务。第i个无人机Vi在t时刻的三维空间坐标为(xi(t),yi(t),zitag cost load voyage tag(t))，定义无人机 Vi的属性集合Pi={Pi ，Pi ，Pi ，Pi }。其中，Pi 表示无人机类cost load
型，Pi 表示无人机单位航程燃耗代价，Pi 表示无人机的资源载荷（对电力巡检无人机voyage
而言，资源载荷主要包括光电吊舱、相机、红外热像仪等），Pi 表示无人机的性能约束，包括最大航程、转弯半径、滞空时间、极限航速与升限。
[0025] 接着建立电力装置巡检任务模型。环境中任务数目为M，任务集合以T={T1,T2,…,Tj,…,TM}表示，根据无人机巡检任务的特征，可将任务分为两类：定点检视任务和线路巡查任务，定点检视任务主要包括绝缘子故障判断、塔杆异物检视等；线路巡查任务是指无人机沿电力线巡查线上是否有杂物附着。两类任务在计算价值时有所区别，定点检视任务价值与检视目标有关，定义第k个检视目标的价值为vk，k=1,2,…,n ，n为定点检视任务总数；而对于线路巡查任务，定义单位长度线路巡查价值为k，电力线总长度为distance，则此任务的价值为k·distance。单个任务可能由若干个上述的两类任务构成，由此得到单个任务Tj的价值为Value(Tj)。定义任务Tj起点和终点的三维坐标为(Xj1,Yj1,Zj1)、(Xj2,Yj2,Zj2)（对于定点检视任务，认为起点和终点坐标相同），载荷需求为STj=(stj1,stj2,…,stjz)，其中stji为光电吊舱、相机、红外热像仪等，为方便计算本文中的资源需求权重均设为1。巡检任务Tj的预设价值设置为：
[0026]
[0027] 其中，vi为任务点Tj范围内的待检视目标单位价值，nk为任务点Tj范围内的待检视目标数量，K和distance分别为电力线路的单位价值和任务点Tj范围内的电力线总长度。
[0028] 步骤2：建立异构无人机群巡检任务分配的多目标优化问题。
[0029] 集合V中的任一无人机vi根据自身资源载荷Piload和无人机类型的Pitag不同，可以选择执行任务集T中的部分或者全部任务，对于需要多个资源载荷的任务，既可以将任务指派给单个搭载所有所需载荷的无人机，也可以通过组建无人机联盟的形式执行该任务。例如实施例中任务sk0需要相机载荷和红外热像仪载荷，可以选择由无人机UAV2单独执行，也可以选择由无人机UAV0和无人机UAV1通过联盟形式执行。
[0030] 巡检任务的代价函数定义为：
[0031] J(V,T)=Re(V,T)‑Cost(V,T)
[0032] 其中，Re(V,T)为异构无人机巡检任务收益：
[0033]
[0034]
[0035] Pij 为无人机vi访问任务点Tj得到的收益率，由以下公式给出：
[0036]
[0037] 其中，|·|表示相应载荷数量。Cost(V,T)为异构无人机巡检任务损失，定义为：
[0038]
[0039] 其中，(xi(t0),yi(t0),zi(t0)) 为任务规划决策做出时的无人机坐标，(Xj1,Yj1,Zj1)、(Xj2,Yj2,Zj2)分别是任务Tj起点和终点的三维坐标。
[0040] 异构无人机集群巡检任务的多目标优化问题可以描述为：在无人机满足任务性能约束条件的前提下（即航速区间和资源载荷满足检视和巡检任务需要），对于参与电力巡检的每个无人机Vi，i=1,2,…,N，找到其对应的任务序列Seqi={Tp,Tq,…,Tr},Tp,Tq,…,Tr∈T ，使得所有无人机总的任务代价函数J(V,T)最大。多目标优化问题的数学描述为寻找最优的{xij},i=1,2,…,N，j=1,2,…,M 使得：
[0041]
[0042] 其中，Pjmax为任务点Tj的最大性能约束，上式保证参与任务点Tj巡检的无人机序列的最大航速和最小航速满足任务需要，例如：当无人机完成定点检视任务时，需要保证航速不能过快，避免影响检视精度。同时保证参与巡检的无人机集群搭载的资源载荷能满足巡检需要。
[0043] 步骤3：在建立巡检无人机的任务分配模型后，基于蒙特卡洛树搜索（Monte‑Carlo tree search, MCTS）算法求解最优代价函数J。MCTS是一种针对博弈优化的最优决策方法，通过增量非对称方式进行搜索树构建和扩展，具体步骤如下：
[0044] 步骤3.1：输入参与巡检的无人机信息和任务点信息。
[0045] 步骤3.2：定义MCTS搜索树的节点，MCTS搜索树的具体结构如图3所示，树上每个节点处存储一个表格，代表当前时刻的任务分配方案，表中第i行第j列元素为xij，表格第i行记录无人机Vi任务序列，第j列记任务点Tj的参检无人机集合；同时每个节点记录当前任务分配方案的代价函数J(V,T)和访问次数N(s0)，以及无人机执行任务的序列X={xij}。任务规划开始，初始化MCTS搜索树，根节点处所有无人机均未被分配任务，即xij=0，i=1,2,…,N，j=1,2,…,M，X=∅。
[0046] 步骤3.3：从根节点出发，根据UCB公式选择每层的子节点，直到到达一个可扩展节点（当前节点的任务分配表格中存在可执行的操作）。其中UCB由以下公式给出：
[0047]
[0048] 式中，J(V,T)为此时刻对应的无人机巡检代价函数，N(s0) 为当前节点在搜索树上的访问次数，N(sk)为当前节点的父节点访问次数。c为平衡搜索树搜索和扩展的常值系数，本发明中取其为典型值 。
[0049] 步骤3.4：从可扩展节点出发，根据任务约束随机选择一个状态xij将其置1，并将其作为新节点添加到MCTS搜索树，更新当前节点无人机执行任务的序列X=X∪xij，xij为本步中置1的状态。
[0050] 步骤3.5：对于步骤3.4中新添加的子节点，通过模拟，对该节点的价值进行估计。模拟是指从新节点出发，不断执行步骤3.4的扩展操作，直至搜索结束（完成所有任务分配或规划时间超过规定搜索时间）。
[0051] 步骤3.6：将执行步骤3.5得到的新节点的代价回溯给该节点所在的整个搜索树支路（包含根节点），同时更新每个节点的访问次数。
[0052] 步骤3.7：如果当前时刻未超过规定的搜索时间，返回步骤3.3。
[0053] 步骤3.8：如果当前时刻超过规定搜索时间，从根节点出发，根据UCB公式选择每层的子节点（此时令c=0）直至最后一层，输出最终节点存储的无人机执行任务序列X。
[0054] 步骤3.9：输入步骤3.8得到的无人机执行任务序列X，将其转化为图4所示的任务分配表格，表中参数xij定义如前文所述，表格每行记录无人机任务序列，每列记录每个任务点的参检无人机集合。对于第i行依次输出xij，j=1,2,…,M 可得到无人机Vi对应的任务序列Seqi={Tp,Tq,…,Tr},Tp,Tq,…,Tr∈T，每个无人机依次执行序列任务。
[0055] 步骤3.10：如果得到的无人机序列能够完成所有任务点的巡检，输出每个无人机Vi的任务序列Seqi={Tp,Tq,…,Tr},Tp,Tq,…,Tr∈T，任务规划结束，执行步骤4 。
[0056] 步骤3.11：如果得到的无人机序列无法完成所有任务点的巡检，更新所有未被执行的任务点信息和当前时刻的无人机信息，重新执行步骤3.1到步骤3.9的任务规划过程。
[0057] 步骤4：在步骤3将任务序列指派给单个无人机后，利用已有的航迹规划算法对每个无人机的航迹进行规划。
[0058] 本发明中的实施例具体实施过程如下：在Intel 12500H硬件平台使用Python语言开展仿真实验，仿真初始条件设置为：任务区域为500米*500米的正方形区域，在任务区域内随机布置三架无人机，无人机的载荷在相机和红外热像仪中随机选择，无人机最大航程cost均设置为1000米，航程代价Pi 均设置为1单位每米；任务区域内随机设置五个任务点。图5表示巡检开始时参与巡检的无人机和任务点分布情况，圆圈表示无人机UAV0， UAV1， UAV2，携带的载荷分别为相机、红外热像仪、相机和红外热像仪。三角表示任务点sk0 sk4。
~
每个任务点的预设价值Value(sk0) Value(sk4)分别为：1000，500，500，1000，500, 所需载~
荷分别为：相机和红外热像仪、相机、红外热像仪、相机和红外热像仪、相机。根据步骤1和步骤2建立任务分配模型和多目标优化问题后，根据步骤3，构建蒙特卡洛树，并对多目标优化问题进行求解。首先输入参与巡检的无人机信息和任务点信息，定义蒙特卡洛树的节点信息，初始化MCTS搜索树，并将搜索状态表格置0。按照选择‑扩展‑模拟‑回溯四步循环执行操作。从根节点出发，根据UCT公式进行选择至可扩展节点。在可扩展节点上，从当前搜索状态表格中，随机选择一个可执行的操作，将其置1，实现扩展一个新的子节点。在新添加的子节点处，开始模拟，模拟为执行扩展步骤至巡检任务完成。最后执行回溯步骤。循环执行上述操作至搜索时间结束，搜索时间设置为10秒。
[0059] 图6表示规划结束后无人机的巡检方案。其中无人机UAV0执行任务sk1, 无人机UAV1执行任务sk2, 无人机UAV2按sk3, sk0, sk4顺序执行任务。可以看出通过本专利提出的任务分配方案，三台无人机在较短时间内能够完成所有任务点的巡检工作，满足任务需求，且此算法可以使得巡检总代价函数最优。
[0060] 在完成无人机任务分配以后，可以根据蚁群算法完成每个无人机从起始位置到任务点之间的航迹规划以及避障工作。
[0061] 最后应说明的是：以上所述仅为本发明的优选实施例，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
