[發明專利]一種基于勢博弈的多無人機協同搜索方法

有效

• 申請號: 201610143227.0
• 申請日: 2016-03-14
• 公開（公告）號: CN105700555B
• 公開（公告）日: 2018-04-27
• 發明（設計）人: 段海濱;李沛
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G05D1/12
• 分類號: G05D1/12;G05B13/04
• 代理公司: 北京慧泉知識產權代理有限公司11232
• 代理人: 王順榮,唐愛華

1.一種基于勢博弈的多無人機協同搜索方法，其特征在于，該方法的步驟如下：

步驟一：多無人機協同搜索問題建模

用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執行一次測量，觀測結果表示如下，

Zi,g,t=1,if|g-μi,t|≤Rsi0,otherwise.---(1)]]>

此外，將正確率和誤警率分別定義為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的位置；無人機的性能用概率密度函數和信號衰減綜合表示如下：

Φ(a)=Φ(p1,p2,...,pn)=∫Ωf(mini∈{1,2,...n}||q-pi||)η(q)dq---(2)]]>

其中

f(||q-pi||)=||q-pi||||q-pi||≤RSi0otherwise]]>

式中η(q)為密度函數，R_Si為無人機v_i的傳感距離；

博弈參與者效用函數U_i(a_i,a_-i)的設計：無人機v_i的效用函數設計為整體效用的邊際貢獻值，記做

Ui(ai,a-i)=∫Ωf(mini∈{1,2,...,n}||q-pi||)η(q)dq-∫Ωf(mini∈{1,2,...,i-1,i+1,...,n}||q-pi||)η(q)dq.---(3)]]>

根據勢函數的定義，按照式(3)設計效用函數，構成的博弈為勢博弈，滿足勢博弈的相關性質，能利用各種學習算法保證其最優性和收斂性；

2.2雙對數-線性學習法的勢博弈求解

采用雙對數-線性學習法對問題進行求解，減少無人機計算資源的負擔，有利于多無人機的實時運動控制；在雙對數-線性學習法中，首先按異步時間模型以相同的概率隨機選擇一架無人機v_i∈V改變其位置；與此同時，其他無人機保持之前的行動不變a_-i(t)＝a_-i(t-1)；選擇出的無人機從其受限行動集C_i(a_i(t-1))中選出嘗試動作以改變其位置

P(a^i=ai)=1/zi,∀ai∈Ci(ai(t-1))/ai(t-1)---(4)]]>

P(a^i=ai(t-1))=1-(|Ci(ai(t-1))|-1)/zi---(5)]]>

其中z_i表示無人機v_i在受限行動集中行動的最大個數，表示為

無人機v_i在選擇出嘗試動作后，在時刻t按照策略p_i(t)∈Δ(A_i)來更新其動作，博弈者策略p_i(t)定義如下：

piai(t-1)(t)=e1τUi(a(t-1))e1τUi(a(t-1))+e1τUi(a^i,a-i(t-1))---(6)]]>

pia^i(t)=e1τUi(a^i,a-i(t-1))e1τUi(a(t-1))+e1τUi(a^i,a-i(t-1))---(7)]]>

式中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(θg=1|Zi,g,t)=P(Zi,g,t|θg=1)P(θg=1)P(Zi,g,t)---(9)]]>

其中P(θ_g＝1)為目標存在于單元g中的先驗概率；將無人機v_i在前一時刻t-1對于目標存在于單元g的概率估計P_i,g,t-1作為先驗概率，結合對于g在時刻t的觀測Z_i,g,t，式(9)變為

Pi,g,t=P(Zi,g,t|θg=1)Pi,g,t-1P(Zi,g,t)---(10)]]>

根據貝葉斯公式上式的分母表示為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)中，概率圖更新規則表示如下，

Pi,g,t=P(θg=1|Zi,g,t)=P(Zi,g,t|θg=1)P(θg=1)P(Zi,g,t|θg=1)P(θg=1)+P(Zi,g,t|θg=0)P(θg=0)=pcPi,g,t-1pcPi,g,t-1+pf(1-Pi,g,t-1)if Zi,g,t=1(1-pc)Pi,g,t-1(1-pc)Pi,g,t-1+(1-pf)(1-Pi,g,t-1)if Zi,g,t=0Pi,g,t-1otherwise.---(11)]]>

在0＜p_c＜1和0＜p_f＜1時，為了簡化運算，設

Qi,g,t=Δln(1Pi,g,t-1)---(12)]]>

則概率更新規則變換為

Qi,g,t=Qi,g,t-1+lnpfpcif Zi,g,t=1Qi,g,t-1+ln1-pf1-pcif Zi,g,t=0Qi,g,t-1otherwise.---(13)]]>

這樣，對于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進行更新；每架無人機將更新后的概率圖傳輸給它當前的鄰居，鄰居由通信距離和各自的位置決定；然后，利用線性組合的方式對自身更新的概率圖和通信獲取的鄰居概率圖進行融合，如下式

Qi,g,t=ωi,i,tHi,g,t-1+Σj∈Ni(t)ωi,j,tHj,g,t-1---(14)]]>

其中ω_i,j,t是無人機v_i概率圖Q_j,g,t-1的權重；將不是無人機v_i鄰居個體的權重設為ω_i,j,t＝0，上式寫成如下的形式；

Qi,g,t=Σj=1Nωi,j,tHj,g,t---(15)]]>

這里W_t＝(ω_i,j)采用著名的Metropolis權重矩陣，表示為

ωi,i,t=11+max{di(t),dj(t)}if{i,j}∈ϵ(t)1-Σ{i,k}∈ϵ(t)ωi,k,t(t)if i=j0otherwise---(16)]]>

其中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)，形式如下：

ηi,g,k=Δe-kη||Qi,g,k||---(17)]]>

其中k_η為正的增益參數，η_i,g,k表示無人機v_i在時刻k對于單元g的不確定度值；

協同搜索問題被分解為三個連續的部分：協調運動、傳感器觀測和信息融合更新；開始更新前，每個無人機初始化一個概率圖，該圖存儲著每個單元中目標存在的概率；隨后無人機根據步驟二中建立的勢博弈模型進行協調運動，以優化整體的搜索性能；當到達新的位置之后，無人機利用傳感器對覆蓋范圍內的單元進行探測；隨后，結合探測到的數據，無人機根據步驟三對各自的概率圖進行更新，并通過與鄰居個體進行通信進行信息融合；重復步驟二和步驟三，直至各單元的不確定度降低到設定的閾值之下，此時搜索任務完成。