应用于河流目标搜索任务的无人机航迹规划算法

摘要

应用于河流目标搜索任务的无人机航迹规划算法，本发明将目标河流区域抽象建模为二维曲线，目标在每个曲线段内存在概率已知的情况下，采用高斯混合模型提取搜索高价值曲线段，即高价值搜索区域，并对高价值曲线段的搜索顺序进行排序，分配给执行搜索任务的无人机，以使无人机按排序后的曲线段进行目标搜索。该方法可获得近似最优结果且求解速度较快，提高无人机的目标搜索效率。

说明书

技术领域

本发明涉及无人机导航与控制技术领域，涉及一种无人机航迹规划算法，具体为一种应用于河流目标搜索任务的无人机航迹规划算法。

背景技术

无人机(Unmanned Aerial Vehicle，简称UAV)是指由动力驱动、机上无人驾驶、由无线电遥控操纵或自备程序控制的一类飞行器。作为航空技术与信息技术高度融合的产物，无人机因其性价比高、使用灵活、可执行高风险任务、不受飞行员生理条件限制等优势，在军用与民用领域得到了广泛应用。最近30多年来，世界各国对无人机领域持续关注并加大投入，无人机技术取得了长足发展与进步，代表了当今高新技术的发展方向。

目标搜索作为无人机的典型应用之一，已广泛应用于突发事件应急监控或营救等场景。由于被搜索目标(如走失人员、沉船等)的生存概率将随着时间流逝而迅速降低，因此要求无人机在尽可能短的时间内发现目标。上述问题本质上可看作航迹优化问题，使得无人机沿最优航迹飞行时可获得最大搜索回报率(即累计概率)，实现对任务区域的高效侦查覆盖与目标快速搜索。

国内外学者针对目标搜索问题进行了大量研究并提出一系列方法，主要包括几何法、随机搜索法、基于搜索图的方法等。几何法通过规划特定形状的搜索轨迹如平行线、螺旋线等，实现无人机对任务区域的遍历或全覆盖，虽然该类方法原理简单，但在目标先验信息已知的情况下其搜索效率明显较低。随机搜索法引导无人机在任务区域内随机运动，从而逐渐覆盖区域并搜索到目标，该类方法的最大优势是不需要精确的定位与复杂的优化决策过程，但同样未利用目标先验信息且不适用于大范围复杂区域。基于搜索图的方法首先将任务区域离散化为一系列栅格单元，然后基于各单元存储的目标信息，采取合适的优化策略使得无人机向最有希望的方向运动，虽然该类方法可灵活处理各类复杂情况，但无人机可能会长时间徘徊于局部区域而忽视其他高价值区域，搜索效率有待提升。此外，为解决上述局部最优问题并简化多无人机协同目标搜索任务，一种有效的思路是将任务区域分解为多个子区域并分配给各无人机，从而将复杂的协同控制问题转化为多个简单的单无人机搜索问题，主要的区域分解方法包括质心Voronoi分割采样、模糊C均值聚类、多边形分割等。

现有目标搜索研究大多应用于二维水平区域(如矩形等规则区域或不规则区域)，而针对河流区域中的目标搜索问题研究较少。作为一类特殊的任务区域，河流可看作带一定地形约束的曲线，因此相比于无人机在普通二维水平区域内的多航向甚至全航向选择，河流区域限制了无人机的飞行模式，增加了目标搜索问题的难度。针对该类问题，现有解决方案多为定性的被动策略，如无人机在河流上空飞行进行全覆盖式搜索、或直接赶赴目标的先前位置区域进行贪婪式搜索，缺乏定量分析与启发式策略指导。

发明内容

本发明的目的在于结合河流的自然条件特点，提出一种适用于河流目标搜索任务的无人机航迹规划算法，以实现河流目标任务的快速搜索。

为了实现以上目的，本发明提供如下的技术方案：

应用于河流目标搜索任务的无人机航迹规划算法，其特征在于，所述无人机的视场范围大于河流宽度，所述规划算法包括以下步骤：

S1：将待搜索的目标河流抽象为二维平面曲线，以向前距离L_s为自变量，对平面曲线做离散化处理为M＝L/L_s个离散化单元，其中L为河流总长度，L_s为每个离散化单元的长度；

S2：任意一个采样周期内，无人机在两个离散化单元s_m内移动；待搜索目标在每个离散化单元s_m内存在的概率p(s_m)已知，且p(s_m)∈[0,1]，且满足

S3：任意个离散化单元组成搜索曲线段，S_k＝{s_m,s_m+1,...,s_n}，1≤m＜n≤M，利用高斯混合模型描述待搜索目标在每个搜索曲线段内存在的概率信息，提取以P_k,1和P_k,2为区域边界的高价值搜索曲线段S_k；

S4：定义子区域转场时间为当前搜索曲线段边界点P_i,p转到下一搜索曲线段边界点P_j,q的最短飞行时间，定义所述转场时间为：

T(P_i,p,P_j,q)＝λ₁·Dubins_cost(P_i,p,P_j,q)，其中i≠j且i,j∈{1,2,...K}，且p,q∈{1,2}；其中λ₁表示子区域转场时间的比例系数；Dubins_cost(P_i,p,P_j,q)表示Dubins曲线的长度，p表示第i个搜索曲线段的飞出点标志位，q表示第j个搜索曲线段的进入点标志位，K表示高价值搜索曲线段的数量；

定义子区域覆盖时间为无人机在搜索曲线段内搜索飞行的时间，为C_k＝λ₂·L_k，其中λ₂表示子区域覆盖时间的比例系数，L_k表示搜索曲线段的长度，L_k＝(n-m+1)·L_s；

定义子区域覆盖回报为无人机完全覆盖高价值搜索曲线段所获得的累计概率：R_k；

S5：采用上述子区域转场时间、子区域覆盖时间和子区域覆盖回报作为评价指标，采取最近插入法对各高价值搜索曲线段进行搜索顺序的迭代排序，排序建模为：

S6：按顺序依次连接优化后的高价值搜索曲线段，获得无人机的最终搜索路径。

作为优选：提取高价值搜索曲线段的方法包括以下步骤：

采用K个一维高斯函数组成高斯混合模型，其中k＝1,2,...K，u_k为每个高斯函数的均值，σ_k为每个高斯函数的标准差；

设每个高斯函数所占的权重系数为α_k，且满足

将待搜索曲线段的目标概率为

估计每个高斯函数的权重系数α_k、均值u_k、标准差σ_k，对p(s)进行迭代估计，直至满足收敛条件；

获取到各高斯函数95.4％概率的对应区间，以P_k,1＝u_k-2σ_k和P_k,2＝u_k+2σ_k为区域边界点的高价值搜索曲线段，则L_k＝4σ_k；R_k＝0.954α_k。

作为优选：所述收敛条件为|p(s)-p'(s)|＜ξ，其中p(s)和p'(s)分别为迭代前后的目标概率值，所述ξ＝10^-5。

作为优选：若多架无人机执行搜索任务，则进一步包括以下步骤：对排序后的高价值搜索曲线段分配给多架无人机，进行区域分配。

作为优选：区域分配的方法，包括以下步骤：

将高价值搜索曲线段集合分配给每架无人机，为每架无人机获得一个集合为A_i的分配高价值搜索曲线段集合；

按步骤S5中的方法，对每架无人机集合A_i内的高价值搜索曲线段进行指标计算，获得J_i；

对区域分配建模为其中，N_u表示无人机的总数，ρ₁表示总搜索收益的比例系数，ρ₂表示任务平衡度的比例系数；

采用迭代方法，对区域分配建模求解，确定区域分配策略。

作为优选：所有无人机所分配的高价值搜索曲线段集合满足如下的约束条件：

本发明的有益效果为：

(1)本发明将目标河流区域抽象建模为二维曲线，大大减少了问题复杂度与计算量；

(2)本发明利用自适应高斯混合模型来近似描述河流区域特征并提取高价值子区域，可量化提取出高斯函数95.4％概率的对应区间，针对性的对高价值子区域进行搜索任务分配，量化结果的精度较高且利于后续问题的解决；

(3)本发明利用最近插入法进行区域排序，该方法可获得近似最优结果且求解速度较快；

(4)本发明提供的算法适用于一架或多架无人机搜索路径的规划。

附图说明

图1是本发明的方法流程图；

图2是将河流抽象为二维曲线示意图；

图3是河流区域内的目标概率图；

图4是目标概率基于自适应高斯混合模型的近似结果；

图5是基于最近插入法的子区域排序迭代过程；

图6是以三架无人机进行目标搜索采用本发明方法优化出来的无人机航迹。

具体实施方式

以下将结合附图对本发明的具体实施方式进行清楚完整地描述。显然，具体实施方式所描述的实施例仅为本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本发明的保护范围。

本发明提供了一种用于对无人机的搜索航迹进行规划的算法，具体的为一种当无人机用于河流目标搜索任务时的无人机航迹规划算法。采用该规划算法，可以极大的提高无人机的搜索效率。

为了提高无人机的搜索效率，无人机搭载的视觉传感器的视线始终指向正下方，且其视场范围大于河流的宽度，如此，可以保证无人机在向前行进的过程中，可以搜索整个河道宽度的范围。方法的整体流程图参考图1。

本实施例首先提供一种适用于一架无人机执行搜索任务的搜索航迹的规划算法。

应用于河流目标搜索任务的无人机航迹规划算法，包括以下步骤：

S1：将目标河流抽象为二维平面曲线并进行离散化处理。

参考图2，由于无人机的搜索视角宽度大于河流的宽度，因此，可以忽略河流的宽度，将待搜索的目标河流抽象为二维平面曲线。以向前距离L_s为自变量，对平面曲线做离散化处理为M＝L/L_s个离散化单元，其中L为目标河流总长度，L_s为每个离散化单元的长度；进行离散化处理后，将获得M个河流的离散化单元。

S2：构造单位采样周期内各离散化单元的概率信息。

单位采样周期内，无人机的搜索范围为上述河流的离散化单元的长度。具体的说，任意一个采样周期内，无人机在两个离散化单元s_m内移动；待搜索目标在每个离散化单元s_m内存在的概率p(s_m)已知，且p(s_m)∈[0,1]，且满足概率图参考图3。

S3：提取高价值搜索曲线段。

由于目标在每个搜索曲线段内存在的概率不同，有高有低，为了提高搜索效率，需要选择目标存在概率高的曲线段进行搜索，因此，需要提取高价值搜索曲线段。

任意个离散化单元组成搜索曲线段，S_k＝{s_m,s_m+1,...,s_n}，1≤m＜n≤M，利用高斯混合模型描述待搜索目标在每个搜索曲线段内存在的概率信息，提取以P_k,1和P_k,2为区域边界的高价值搜索曲线段S_k；其中高价值搜索曲线段的数量为K，k∈{1,2,...,K}。

具体方法为：采用K个一维高斯函数：

组成高斯混合模型，其中k＝1,2,...K，u_k为每个高斯函数的均值，σ_k为每个高斯函数的标准差；

设每个高斯函数所占的权重系数为α_k，且满足

将待搜索曲线段的目标概率为

估计每个高斯函数的权重系数α_k、均值u_k、标准差σ_k，定义一个由D个单元位置组成的训练样本，采用最大期望法对p(s)进行迭代估计，直至满足收敛条件；所述收敛条件为p(s)-p'(s)＜ξ，其中p(s)和p'(s)分别为迭代前后的目标概率值，ξ取值视具体收敛精度需求而定，本实施例中ξ＝10^-5。迭代结果参考图4。

在上述参数迭代估计过程中，每个单元位置对应的训练个体数量占比与目标概率一致，即D_m＝p(s_m)D；可引入消除、合并与分裂等动态机制自适应调整模型数量。若某高斯模型的权重很小且与其他模型有一定距离，说明该分量为多余噪声分量，可直接消除；若两个高斯模型距离很近且权重不大，则认为它们反映相同的特征分布，出现过拟合现象，因此它们可合并为一个高斯分量；若某高斯分量的权重、标准差均较大，说明出现欠拟合现象，需将其分裂为两个高斯分量。

根据参数估计结果，即可量化提取出各高斯函数95.4％概率的对应区间，作为高价值的河流子区域(即高价值搜索曲线段)，获取到以P_k,1＝u_k-2σ_k和P_k,2＝u_k+2σ_k为区域边界点的高价值曲线段，则高价值搜索曲线段的长度L_k＝4σ_k。

S4：定义量化评价指标，采用最近插入法对高价值搜索曲线段进行等级评估和排序，确定无人机对各高价值搜索曲线段的搜索顺序。本实施例定义以下三种评价指标子区域转场时间、子区域覆盖时间和子区域覆盖回报。

定义子区域转场时间为当前搜索曲线段边界点P_i,p(或搜索起始位置P_initial)转到下一搜索曲线段边界点P_j,q的最短飞行时间，由于最终获得的多个高价值搜索曲线段为相对分离的曲线段，各个曲线段的边界点之间为非连续点，而子区域转场时间表示的即为在相互不连续的曲线段之间运动的时间。通常Dubins曲线为考虑航向约束的任意两点间的无人机最短航线，定义所述转场时间为：

T(P_i,p,P_j,q)＝λ₁·Dubins_cost(P_i,p,P_j,q)，其中i≠j且i,j∈{1,2,...K}，且p,q∈{1,2}；其中λ₁表示子区域转场时间的比例系数；Dubins_cost(P_i,p,P_j,q)表示Dubins曲线的长度，p表示第i个搜索曲线段的飞出点标志位，q表示第j个搜索曲线段的进入点标志位，K表示高价值搜索曲线段的数量；

定义子区域覆盖时间为无人机在搜索曲线段内搜索飞行的时间，为C_k＝λ₂·L_k，其中λ₂表示子区域覆盖时间的比例系数，L_k表示搜索曲线段的长度，为L_k＝(n-m+1)·L_s；由于采用高斯模型提取的高价值曲线段的长度为L_k＝4σ_k，因此，C_k＝λ₂·4σ_k。

λ₁和λ₂的关系与无人机在不同阶段的飞行速度关系成反比，例如，无人机在子区域间转场的飞行速度是它覆盖子区域(即在子区域上空)时的飞行速度的2倍，则上述参数应满足

定义子区域覆盖回报为无人机完全覆盖高价值搜索曲线段所获得的累计概率R_k，该概率为各个高价值搜索曲线段目标存在概率的和；而相对于经过高斯模型提取的高价值曲线段，由于河流子区域为各高斯函数95.4％概率对应的区间范围，且权重系数为α_k，因此子区域覆盖回报定义如下：R_k＝0.954α_k。

S5：对各高价值搜索曲线段的搜索顺序进行排序，以实现最优的高效搜索策略。

采用上述子区域转场时间、子区域覆盖时间和子区域覆盖回报作为评价指标，采取最近插入法对各高价值搜索曲线段L_p进行搜索顺序的迭代排序，排序建模为：

其中，P_initial为搜索起始位置，分别表示开始搜索的第一条高价值曲线段的两个端点，表示开始搜索的第一条高价值曲线段的子区域覆盖回报，表示开始搜索的第一条高价值曲线段的子区域覆盖时间。相应的，分别表示第k条高价值曲线段的相应指标。

此处需要说明的是，子区域的两个边界点标志位分别为1和2，他们的和为3。1和2不是指个数，而是指标记，例如，第5个子区域的两个边界点为P_5,1，P_5,2。由于无人机对第k-1个子区域的进入点标志位为n_k-1，则对该子区域搜索完毕后的无人机飞出点标志位为3-n_k-1。

子区域排序问题可看作典型的旅行商问题，因此采取最近插入法获得近似最优的排序结果。在每次迭代过程中，从剩余的未排序子区域集合中任意选取某个子区域并将其插入到已排序子区域序列{l₁,...,l_I}的任意位置，并按排序模型公式计算新排序区域的指标值J(I+1)，进而计算指标值的增量ΔJ＝J(I+1)-J(I)，从上述所有可能情况中选择ΔJ取最大值时的情况，然后将选出的某未排序子区域插入到已排序子区域序列中。上述迭代过程重复K步，即完成K个子区域的近似排序。

图5给出了由搜索起始位置P_initial，相对三个子区域(P_1,1,P_1,2)、(P_2,1,P_2,2)和(P_3,1,P_3,2)，采用最近插入法对3个子区域近似排序的过程，其中实线表示河流子区域，虚线表示所有可能的转场航迹段，实线表示确定的转场航迹段。可以看出，从起始位置P_initial可能的转场路径包括(P_initial,P_1,1)、(P_initial,P_1,2)、(P_initial,P_2,1)、(P_initial,P_2,2)、(P_initial,P_3,1)、(P_initial,P_3,2)；经过1次迭代计算之后，确定(P_initial,P_1,1)为最优路径，并开始进行下一次路径迭代计算，可能的转场路径包括如图(c)所示，经过迭代计算后，确定(P_1,2,P_2,1)为最优路径；如此反复，最终获得图(f)所示的搜寻路径。

排序结束后，可确定每个河流子区域的等级(即子区域的搜索顺序)，以及各个子区域进入点的标志位(即从每个子区域的两个端点中的哪一个端点进入子区域)，无人机将按标志位进入子区域，按子区域的顺序逐一进行搜索。

以上的搜索算法适用于一架无人机执行搜索任务的搜索轨迹规划。

而现有技术中，为了实现高效的搜索，通常多架无人机共同执行搜索的任务。因此，本实施例进一步提供一种多架无人机共同执行搜索任务的情况下，无人机搜索轨迹规划的算法。

当有多架无人机共同执行搜索任务时，需要综合考虑总搜索收益和任务的平衡度，将子区域分配给各架无人机。

具体的说，若多架无人机执行搜索任务，则进一步包括以下步骤：对排序后的价值搜索曲线段分配给多架无人机，进行区域分配。

区域分配的方法，包括以下步骤：

将高价值搜索曲线段分配给每架无人机，每架无人机获得一个集合为A_i的分配高价值搜索曲线段集合，曲线段集合内包括多条高价值搜索曲线段；

为了避免无人机之间发生碰撞，要求每个子区域仅分配给一架无人机，而为了保证无人机的高效利用，要求为每架无人机至少分配一个子区域，因此所有无人机所分配的高价值搜索曲线段集合满足如下的约束条件：

其中，N_u表示无人机的数量，K表示高价值搜索曲线段的数量。

对多架无人机搜索路径进行分配的过程参考步骤S4、S5中的方法，对每架无人机获得的曲线段集合A_i内的高价值搜索曲线段进行指标计算(包括子区域转场时间、子区域覆盖时间和子区域覆盖回报)，获得J_i；

对区域分配建模为其中，N_u表示无人机的总数，ρ₁表示总搜索收益的比例系数，ρ₂表示任务平衡度的比例系数；ρ₁和ρ₂的取值需根据具体任务需求进行赋值，例如各机探测能力相近时，可增大ρ₂的值；各机探测能力差别较大时，可增大ρ₁的值。

采用迭代方法，对区域分配建模求解，确定区域分配策略，如图6所示。最终的优化航迹可表示为：

采用本发明所述的算法进行无人机航迹的规划，可实现目标河流段的高效搜索。