一种基于势博弈的多无人机协同搜索方法

摘要

本发明是一种基于势博弈的多无人机协同搜索方法，其实施步骤为：步骤一：多无人机协同搜索问题建模；步骤二：多无人机协调运动的势博弈建模和双对数-线性学法势博弈求解；步骤三：根据传感器探测信息更新概率图，对更新后的概率图进行信息融合，获取目标存在概率；步骤四：根据目标存在概率更新不确定度，并进行多无人机协同搜索。本发明能实现多无人机协同搜索，包含基于势博弈的协调运动、概率图更新、信息融合等过程，由于自身分布式的控制方式，方法计算简单，具有较强的鲁棒性，能有效应对外界干扰。

主权项

一种基于势博弈的多无人机协同搜索方法，其特征在于，该方法的步骤如下：步骤一：多无人机协同搜索问题建模用n架无人机对一个连续的任务区域进行搜索，记为V＝{v₁,v₂,...,v_n}；表示实数域；每架无人机作为独立的决策者采用分布式策略对任务区域进行探索，将连续的任务区域平均分配为M＝L_x×L_y个单，其中，L_x，L_y表示任务区域横向、纵向分配的份数，M表示划分的单元的个数；每个单元用其中心位置g＝[x,y]^T等价代替；其中，x，y表示横、纵坐标的位置，T为数学符号转置；无人机v_i在时刻t对其覆盖范围内的基本单元进行一次独立的测量，测量结果为Z_i,g,t，其中μ_i,t表示无人机v_i在时刻t的位置，R_si表示无人机传感器的探测范围；若其中心位置位于之内，则某一单元g内的信息被无人机v_i检测到；在时刻t，无人机v_i执行一次测量，观测结果表示如下，$Z_{i,g,t}=\left\{\begin{array}{cc}1,& if|g-{\mu }_{i,t}|\le R_{si}\\ 0,& otherwise.\end{array}\right.---\left(1\right)$此外，将正确率和误警率分别定义为P(Z_i,g,t＝1|θ_g＝1)＝p_c和P(Z_i,g,t＝1|θ_g＝0)＝p_f，并假设这两个参数已知，且在整个任务执行过程中保持不变，其中θ_g表示目标存在于单元g中的概率；对于多无人机网络的通信拓扑，将其建模为一个动态图G_t＝(ε_t,v_t)，该动态图中v_t为顶点集合，表示为v_t＝{1,2,...,N}，ε_t为连接边集合，表示为ε_t＝{{i,j}:i,j∈v；||μ_i,t‑μ_j,t||≤R_Ci}，其中μ_i,t和μ_j,t表示两个不同无人机v_i和v_j在时刻t的位置，R_Ci为无人机的通信范围；无人机v_i在时刻t的邻居集合表示为N_i,t＝{j∈v|{i,j}∈ε_t}∪{i}，为表征方便，设该无人机本身属于其邻居集合；无人机v_i在时刻t的度记为d_i,t＝|N_i,t|，表示它将自身位置信息和传感器信息传递给邻居个体的能力；步骤二：多无人机协调运动的势博弈建模和双对数‑线性学习法势博弈求解2.1多无人机协调运动的势博弈建模将多无人机协调运动建模成势博弈的过程中，包括三方面的要素：博弈参与者、参与者行动集及效用函数；博弈参与者即为参与搜索过程的n架无人机，需要考虑的为行动集和效用函数的设计；博弈参与者行动集A_i的设计：它定义了博弈参与者可选择的全部行为，其中的元素被称为行动，是参与者在博弈过程中的决策变量；无人机的搜索效率取决于其传感器性能以及其所在的位置，将某一博弈者的行动集定义为在任务区域内它所能选择的位置，A_i＝{g|g∈Ω},无人机v_i的行动表示为a_i∈A_i，整个无人机群体的集体行动表示为a＝(a₁,a₂,...,a_n)，称作行动组合；设a(t‑1)为无人机v_i在时刻t‑1的行动组合，则根据无人机运动特性以及障碍物等行动约束，将时刻t行动集简化为上一时刻行动集的函数，受限的行动集，记为对于博弈者任一行动a_i∈A_i，有a_i∈C_i(a_i)，即无人机被允许停留在上一时刻的位置；在无人机被布置到任务器搜集信息时，密度函数η:用来记录无人机对任务区域内目标时间发生概率的了解程度；表示正的实数集；由于信号衰减，传感器性能随着目标单元与无人机位置之间的几何距离增大而降低，因此用非减可微函数f(||q‑p_i||):对传感器的信号强度进行量化分析，q∈Ω为任务区域中单元格的位置，p_i为无人机v_i的位置；无人机的性能用概率密度函数和信号衰减综合表示如下：$\Phi \left(a\right)=\Phi (p_1,p_2,...,p_n)={\int }_{\Omega }f\left(\underset{i\in \{1,2,...n\}}{min}\right||q-p_i|\left|\right)\eta \left(q\right)dq---\left(2\right)$其中$f\left(\right||q-p_i|\left|\right)=\left\{\begin{array}{cc}\left|\right|q-p_i\left|\right|& \left|\right|q-p_i\left|\right|\le R_{Si}\\ 0& otherwise\end{array}\right.$式中η(q)为密度函数，R_Si为无人机v_i的传感距离；博弈参与者效用函数U_i(a_i,a_‑i)的设计：无人机v_i的效用函数设计为整体效用的边际贡献值，记做$\begin{array}{c}{U}_i\left(a_i,a_{-i}\right)={\int }_{\Omega }f\left(\underset{i\in \left\{1,2,...,n\right\}}{\min }\left|\right|q-p_i\left|\right|\right)\eta \left(q\right)dq\\ -{\int }_{\Omega }f\left(\underset{i\in \left\{1,2,...,i-1,i+1,...,n\right\}}{\min }\left|\right|q-p_i\left|\right|\right)\eta \left(q\right)dq.\end{array}---\left(3\right)$根据势函数的定义，按照式(3)设计效用函数，构成的博弈为势博弈，满足势博弈的相关性质，能利用各种学习算法保证其最优性和收敛性；2.2双对数‑线性学习法的势博弈求解采用双对数‑线性学习法对问题进行求解，减少无人机计算资源的负担，有利于多无人机的实时运动控制；在双对数‑线性学习法中，首先按异步时间模型以相同的概率随机选择一架无人机v_i∈V改变其位置；与此同时，其他无人机保持之前的行动不变a_‑i(t)＝a_‑i(t‑1)；选择出的无人机从其受限行动集C_i(a_i(t‑1))中选出尝试动作以改变其位置$P({\hat{a}}_i=a_i)=1/z_i,\forall a_i\in C_i\left(a_i\right(t-1\left)\right)/a_i(t-1)---\left(4\right)$$P({\hat{a}}_i=a_i(t-1\left)\right)=1-\left(\right|C_i\left(a_i\left(t-1\right)\right)|-1)/z_i---\left(5\right)$其中z_i表示无人机v_i在受限行动集中行动的最大个数，表示为无人机v_i在选择出尝试动作后，在时刻t按照策略p_i(t)∈Δ(A_i)来更新其动作，博弈者策略p_i(t)定义如下：$p_i^{a_i(t-1)}\left(k\right)=\frac{e^{\frac{1}{\tau }{U}_i\left(a\right(t-1\left)\right)}}{e^{\frac{1}{\tau }{U}_i\left(a\right(t-1\left)\right)}+e^{\frac{1}{\tau }{U}_i({\hat{a}}_i,a_{-i}(t-1\left)\right)}}---\left(6\right)$$p_i^{{\hat{a}}_i}\left(t\right)=\frac{e^{\frac{1}{\tau }{U}_i\left({\hat{a}}_i,a_{-i}\left(t-1\right)\right)}}{e^{\frac{1}{\tau }{U}_i\left(a\left(t-1\right)\right)}+e^{\frac{1}{\tau }{U}_i\left({\hat{a}}_i,a_{-i}\left(t-1\right)\right)}}---\left(7\right)$式中U_i(a(t‑1))和分别是无人机当前行动的效用以及按照选定尝试动作改变后的假想效用；式中参数τ定义了噪声的强度，即无人机作决策时在多大程度上会选择次优动作；当τ→0时，无人机会以概率1选择a_‑i(t‑1)的最佳应对动作；注意，当时，时，对于无人机v_i∈V和其行动集中的任一对动作可达性表示存在一系列的行动对所有的t∈{1,2,...,m}满足对于无人机v_i∈V和其行动集中的任一对动作表示其可逆性；对于构造成效用函数为式(2)的势博弈的多无人机协调运动问题，如果博弈者遵循双对数‑线性学习法，并且其受限行动集满足可达性和可逆性，则无人机在t→∞，τ→0时将移动到最大化其覆盖性能的位置；步骤三：根据传感器探测信息更新概率图，对更新后的概率图进行信息融合，获取目标存在概率3.1根据传感器探测信息更新概率图首先根据先验知识建立表征各无人机对任务区域的理解程度的概率图，然后通过贝叶斯规则和在运动过程中获得的信息对概率图进行更新，具体步骤如下；在搜索过程中，每架无人机v_i保存一个它对任务区域所有基础单元的概率图P_i,g,t，表示在时刻t目标存在于单元g中的概率，θ_g＝1和θ_g＝0分别表示目标是否存在于单元g；无人机v_i根据传感器观测信息B_i,t更新其概率图，公式如下P_i,g,t＝P(θ_g＝1|B_i,t).     (8)目标存在于单元g在无人机v_i在时刻t观测值为Z_i,g,t时的条件概率P(θ_g＝1|Z_i,g,t)按照贝叶斯公式表示为$P({\theta }_g=1|Z_{i,g,t})=\frac{P\left(Z_{i,g,t}\right|{\theta }_g=1)P({\theta }_g=1)}{P\left(Z_{i,g,t}\right)}---\left(9\right)$其中P(θ_g＝1)为目标存在于单元g中的先验概率；将无人机v_i在前一时刻t‑1对于目标存在于单元g的概率估计P_i,g,t‑1作为先验概率，结合对于g在时刻t的观测Z_i,g,t，式(9)变为$P_{i,g,t}=\frac{P\left(Z_{i,g,t}\right|{\theta }_g=1)P_{i,g,t-1}}{P\left(Z_{i,g,t}\right)}---\left(10\right)$根据贝叶斯公式上式的分母表示为P(Z_i,g,t)＝P(Z_i,g,t|θ_g＝1)P(θ_g＝1)+P(Z_i,g,t|θ_g＝0)P(θ_g＝0)，其中P(Z_i,g,t|θ_g＝1)和P(Z_i,g,t|θ_g＝0)为正确检测率和误警率，为建模部分中的p_c和p_f；将式(10)代入式(9)中，概率图更新规则表示如下，$\begin{array}{c}{P}_{i,g,t}=P\left({\theta }_g=1|Z_{i,g,t}\right)\\ =\frac{P\left(Z_{i,g,t}|{\theta }_g=1\right)P\left({\theta }_g=1\right)}{P\left(Z_{i,g,t}|{\theta }_g=1\right)P\left({\theta }_g=1\right)+P\left(Z_{i,g,t}|{\theta }_g=0\right)P\left({\theta }_g=0\right)}\\ =\left\{\begin{array}{cc}\frac{p_c{P}_{i,g,t-1}}{p_c{P}_{i,g,t-1}+p_f\left(1-P_{i,g,t-1}\right)}& if{Z}_{i,g,t}=1\\ \frac{\left(1-p_c\right)P_{i,g,t-1}}{\left(1-p_c\right)P_{i,g,t-1}+\left(1-p_f\right)\left(1-P_{i,g,t-1}\right)}& if{Z}_{i,g,t}=0\\ P_{i,g,t-1}& otherwise.\end{array}\right.\end{array}---\left(11\right)$在0＜p_c＜1和0＜p_f＜1时，为了简化运算，设$Q_{i,g,t}\stackrel{\Delta }{=}ln(\frac{1}{P_{i,g,t}}-1)---\left(12\right)$则概率更新规则变换为$Q_{i,g,t}=\left\{\begin{array}{cc}{Q}_{i,g,t-1}+ln\frac{p_f}{p_c}& if{Z}_{i,g,t}=1\\ Q_{i,g,t-1}+ln\frac{1-p_f}{1-p_c}& if{Z}_{i,g,t}=0\\ Q_{i,g,t-1}& otherwise.\end{array}\right.---\left(13\right)$这样，对于P_i,g,t∈(0,1)，P_i,g,t和Q_i,g,t存在一对一映射，实现从Q_i,g,t恢复P_i,g,t；3.2对更新后的概率图进行信息融合，获取目标存在概率在步骤三中“根据传感器探测信息更新概率图”部分，无人机v_i利用传感器探测到的新息对上一时刻t‑1的概率图H_i,g,t进行更新；每架无人机将更新后的概率图传输给它当前的邻居，邻居由通信距离和各自的位置决定；然后，利用线性组合的方式对自身更新的概率图和通信获取的邻居概率图进行融合，如下式$Q_{i,g,t}={\omega }_{i,i,t}{H}_{i,g,t-1}+\underset{j\in N_i\left(t\right)}{\Sigma }{\omega }_{i,j,t}{H}_{j,g,t-1}---\left(14\right)$其中ω_i,j,t是无人机v_i概率图Q_j,g,t‑1的权重；将不是无人机v_i邻居个体的权重设为ω_i,j,t＝0，上式写成如下的形式；$Q_{i,g,t}=\underset{j=1}{\overset{N}{\Sigma }}{\omega }_{i,j,t}{H}_{j,g,t}---\left(15\right)$这里W_t＝(ω_i,j)采用著名的Metropolis权重矩阵，表示为${\omega }_{i,i,t}=\left\{\begin{array}{cc}\frac{1}{1+\max \left\{d_i\left(t\right),d_j\left(t\right)\right\}}& if\left\{i,j\right\}\in ϵ\left(t\right)\\ 1-\underset{\left\{i,k\right\}\in ϵ\left(t\right)}{\Sigma }{\omega }_{i,k,t}\left(t\right)& ifi=j\\ 0& otherwise\end{array}\right.---\left(16\right)$其中d_i(t),d_j(t)表示节点i和j的度，在实际配置中，将W_t∈R^n×n存储成稀疏矩阵的形式，减少所需存储空间；若无人机网络连通，则W_t为遍历性双随机矩阵，使各概率图渐进稳定到平均一致性；该权重矩阵适用于分布式配置，无人机无需了解无人机网络的通信拓扑等全局信息，甚至不需要参与整个任务的无人机数目；对于式(15)定义的分布式信息估计过程，如果执行任务的无人机网络通信拓扑满足以下两个条件之一，则能够保证渐进收敛到概率图初始状态的平均值：或者无人机的通信网络为连通图；或者无人机的通信网络为存在独立通信失败的连通图；步骤四：根据目标存在概率更新不确定度，并进行多无人机协同搜索通过与邻居通信进行信息融合，得到估计值||Q_i,j,k||，该值用来刻画无人机v_i对于任务区域Ω单元g的不确定度；||Q_i,j,k||越大，无人机v_i的不确定值越小，反之亦然；而搜索问题构造成了一个具有受限行动集的势博弈，并利用双对数线性学习方法进行协调运动；因此，利用||Q_i,j,k||构造势博弈效用函数中的密度函数η(q)，形式如下：${\eta }_{i,g,k}\stackrel{\Delta }{=}{e}^{-k_{\eta }\left|\right|Q_{i,g,k}\left|\right|}---\left(17\right)$其中k_η为正的增益参数，η_i,g,k表示无人机v_i在时刻k对于单元g的不确定度值；协同搜索问题被分解为三个连续的部分：协调运动、传感器观测和信息融合更新；开始更新前，每个无人机初始化一个概率图，该图存储着每个单元中目标存在的概率；随后无人机根据步骤二中建立的势博弈模型进行协调运动，以优化整体的搜索性能；当到达新的位置之后，无人机利用传感器对覆盖范围内的单元进行探测；随后，结合探测到的数据，无人机根据步骤三对各自的概率图进行更新，并通过与邻居个体进行通信进行信息融合；重复步骤二和步骤三，直至各单元的不确定度降低到设定的阈值之下，此时搜索任务完成。