基于貝葉斯信息更新的無(wú)人機(jī)目標(biāo)搜索策略研究

李 悅，周長(zhǎng)銀

(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,山東 青島 266590)

軍事和災(zāi)害救助中，目標(biāo)搜索是目前無(wú)人機(jī)應(yīng)用中的一個(gè)重要方面。相對(duì)于人工搜索，無(wú)人機(jī)搜索目標(biāo)受困于對(duì)目標(biāo)信息的掌握程度和無(wú)人機(jī)搜索策略，需要更好的決策算法。

針對(duì)目標(biāo)搜索問(wèn)題的研究，Koopman[1]早在第二次世界大戰(zhàn)期間就提出了基本的目標(biāo)搜索理論，基于目標(biāo)靜止、均勻分布以及在搜索區(qū)域內(nèi)勻速連續(xù)搜尋的假設(shè)，提出了發(fā)現(xiàn)概率模型。在Koopman的假設(shè)下，F(xiàn)rost[2]通過(guò)設(shè)計(jì)“掃地”實(shí)驗(yàn)對(duì)發(fā)現(xiàn)概率和掃海寬度等作了詳盡闡釋；Koester等[3]提出基于搜尋區(qū)域大小、掃海寬度和搜索努力程度的發(fā)現(xiàn)概率計(jì)算方法。為了突破均勻分布假設(shè)的限制，Brown[4]考慮了在離散空間中對(duì)移動(dòng)目標(biāo)進(jìn)行搜索的最佳策略問(wèn)題。周濤[5]對(duì)海上搜尋中發(fā)現(xiàn)概率的預(yù)測(cè)值進(jìn)行研究,但沒(méi)有提出針對(duì)掃海寬度等因素的更好策略。在海上搜索中，影響發(fā)現(xiàn)概率的核心因素是掃海寬度。吳翔等[6]就這一因素進(jìn)行重點(diǎn)探討，并提出了掃海寬度的修正模型和指數(shù)探測(cè)函數(shù)的修正模型。王博研[7]將影響發(fā)現(xiàn)概率的因素結(jié)合起來(lái)考慮，提出了計(jì)算初始搜尋區(qū)域中搜尋成功率的方法。上述文獻(xiàn)提出的模型和方法，在研究無(wú)人機(jī)目標(biāo)搜索問(wèn)題時(shí)值得借鑒和參考，但所給搜索過(guò)程都是確定性的，不能利用搜索過(guò)程獲取的新信息實(shí)時(shí)地更改搜索策略。

2011年，Stone等[8]利用貝葉斯方法提出搜尋失事飛機(jī)的數(shù)學(xué)模型，找到了墜落近兩年的法航447。2015年，Lu等[9]利用貝葉斯推理給出了最優(yōu)搜救模型。Lu[10]著重研究了墜毀飛機(jī)的定位方法，確定救援區(qū)域和搜索策略。

在關(guān)于無(wú)人機(jī)目標(biāo)搜索的研究中，多無(wú)人機(jī)協(xié)同搜索問(wèn)題得到研究人員的更多關(guān)注[11-12]。協(xié)同搜索假設(shè)目標(biāo)所在區(qū)域服從均勻分布。該假設(shè)在目標(biāo)位于搜索區(qū)域的分布信息未知的情況下是合理的，但若目標(biāo)所處位置有明顯的分布特征，則需要其他假設(shè)。

本研究借助貝葉斯信息更新方法，研究利用無(wú)人機(jī)進(jìn)行目標(biāo)搜索策略問(wèn)題，提出目標(biāo)搜索的動(dòng)態(tài)策略和相應(yīng)算法，并在正態(tài)分布假設(shè)下進(jìn)行數(shù)值模擬，驗(yàn)證所給方法的適用性。

1 基于貝葉斯更新的發(fā)現(xiàn)概率模型

發(fā)現(xiàn)概率是指目標(biāo)100%位于某一個(gè)區(qū)域時(shí)，無(wú)人機(jī)發(fā)現(xiàn)該目標(biāo)的概率。發(fā)現(xiàn)概率的大小與無(wú)人機(jī)搜索區(qū)域面積有關(guān)，也與無(wú)人機(jī)搜索設(shè)備掃視面積有關(guān)。假設(shè)無(wú)人機(jī)采取平行搜索，執(zhí)行搜索任務(wù)時(shí)的掃視寬度為ω，搜索設(shè)備單位時(shí)間的掃視距離不變，并假設(shè)每個(gè)搜索階段的搜索面積相同。

為便于計(jì)算發(fā)現(xiàn)概率和確定最優(yōu)搜索區(qū)域，采用離散化方法，把目標(biāo)所在區(qū)域Ω分割為N個(gè)邊長(zhǎng)為ω的正方形區(qū)域R1,R2,…，RN。假設(shè)目標(biāo)位置的初始信息集合記為D0，根據(jù)D0可以給出目標(biāo)位于Rk的先驗(yàn)概率為P(BRk|D0)[13]，k=1,2,…,N,其中BRk表示目標(biāo)位于區(qū)域Rk這一事件。

記R(t)是第t階段的任務(wù)搜索區(qū)域，假設(shè)R(t)是由R1,R2,…，RN中m×n個(gè)相連的小正方形R1(t),R2(t),…，Rm×n(t)組成，此時(shí)，無(wú)人機(jī)實(shí)際搜索區(qū)域面積為mnω2，且

R(t)={R1(t),R2(t),…，Rm×n(t)}?{R1,R2,…,RN}。

AR(t)表示無(wú)人機(jī)在區(qū)域R(t)內(nèi)搜索時(shí)發(fā)現(xiàn)目標(biāo)這一事件，則目標(biāo)被發(fā)現(xiàn)的概率為

(1)

其中P(ARi(t)|BRi(t),Dt-1)表示目標(biāo)位于Ri(t)時(shí)發(fā)現(xiàn)目標(biāo)的概率[14]，表示為

(2)

其中zi(t)表示在R(t)內(nèi)每一小區(qū)域Ri(t)上的掃視距離。則由(1)式，有

(3)

當(dāng)搜索進(jìn)行到t階段時(shí)，可以通過(guò)多種方法確定最優(yōu)搜索區(qū)域[15-16]。本研究以發(fā)現(xiàn)概率確定最優(yōu)搜索區(qū)域，發(fā)現(xiàn)概率根據(jù)式(1)算出。原則上，選取發(fā)現(xiàn)概率P(AR(t)|Dt-1)最大的區(qū)域R(t)作為搜索區(qū)域。

(4)

t+1階段的目標(biāo)搜索區(qū)域R(t+1)由m×n個(gè)相連的小正方形R1(t+1),R2(t+1),…,Rm×n(t+1)組成，可表示為：

R(t+1)={R1(t+1),R2(t+1),…,Rm×n(t+1)}?{R1,R2,…,RN}，

則t+1階段目標(biāo)位于區(qū)域Ri(t+1)(i=1,2,…,m×n)上的先驗(yàn)概率P(BRi(t+1)|Dt)可由(4)式給出，進(jìn)而由(3)式，可計(jì)算t+1階段目標(biāo)被發(fā)現(xiàn)的概率P(AR(t+1)|Dt)。

以上搜索區(qū)域的確定過(guò)程可以重復(fù)進(jìn)行下去，直到目標(biāo)被發(fā)現(xiàn)為止。若經(jīng)過(guò)s個(gè)階段才發(fā)現(xiàn)搜索目標(biāo)，則“前s個(gè)階段搜尋發(fā)現(xiàn)目標(biāo)”的累計(jì)發(fā)現(xiàn)概率定義為：

(5)

2 最優(yōu)搜索策略

單位時(shí)間搜索設(shè)備內(nèi)掃視距離v0稱為掃視速度。假設(shè)無(wú)人機(jī)在一次搜索任務(wù)中的最大停留時(shí)間為T。最優(yōu)搜索策略是在給定條件下發(fā)現(xiàn)概率最大的策略，記為Z(t)={Z1(t),Z2(t),…,Zmn(t)}。

最優(yōu)搜索策略可由如下規(guī)劃給出：

(6)

這里要求v0T≥mnω，即無(wú)人機(jī)的掃視面積v0Tω不小于實(shí)際搜索面積mnω2，在實(shí)際應(yīng)用中是合理的。

結(jié)合以上分析，給出基于貝葉斯更新的最優(yōu)搜索算法如下：

Step 1:給出初始先驗(yàn)分布P(BRk|D0)；初始值v0,T,n,m；t=1；

Step 2:根據(jù)(6)式求解t階段的最優(yōu)搜索策略(Z*(t),R*(t))；

Step 4:利用(4)式，更新先驗(yàn)分布P(BRi(t+1)|Dt)，計(jì)算發(fā)現(xiàn)概率P(AR(t+1)|Dt)；

Step 5:令t=t+1，返回Step 2。

需要注意，如果在下一階段搜索前，有額外信息獲得，例如獲得目標(biāo)位置的新線索，這時(shí)需要對(duì)信息集Dt-1的更新進(jìn)行干預(yù)，加入額外信息。同時(shí)，搜索區(qū)域目標(biāo)位置的先驗(yàn)分布也可能發(fā)生變化，相應(yīng)地，須對(duì)先驗(yàn)分布P(BRi(t)|Dt-1)重新調(diào)整，具體調(diào)整方法在下節(jié)數(shù)值實(shí)驗(yàn)中給出。

3 數(shù)值模擬

在目標(biāo)搜索的研究中，通常把目標(biāo)最有可能的位置坐標(biāo)稱為基點(diǎn)，基點(diǎn)可能不止一個(gè)。設(shè)M是基點(diǎn)個(gè)數(shù)，fk(x,y)是目標(biāo)位于第k個(gè)基點(diǎn)所在區(qū)域內(nèi)的概率分布，假設(shè)fk(x,y)為二維正態(tài)分布。

3.1 無(wú)貝葉斯干預(yù)下的模擬實(shí)驗(yàn)

目標(biāo)位于區(qū)域Rk內(nèi)的初始概率計(jì)算公式：

(7)

假設(shè)在Ω內(nèi)有5個(gè)基點(diǎn)A、B、C、D、E，以這5個(gè)基點(diǎn)將Ω劃分為5個(gè)區(qū)域，每個(gè)區(qū)域又劃分為3×3個(gè)等面積的小區(qū)域。5個(gè)區(qū)域的概率分布以及概率信息如表1所示。

表1 概率分布與概率Tab.1 Probability distribution and probability

根據(jù)(7)式計(jì)算每個(gè)區(qū)域在該區(qū)域概率分布下的概率，然后挑選出概率最大的三個(gè)區(qū)域作為任務(wù)區(qū)域。接著將任務(wù)區(qū)域的概率進(jìn)行歸一化，公式如下：

(8)

其中n為選擇出的任務(wù)區(qū)域ΩR的個(gè)數(shù)。

為了避免實(shí)驗(yàn)的偶然性，取a∈[1,2]，間隔為0.2進(jìn)行實(shí)驗(yàn)。對(duì)最優(yōu)搜索策略模型進(jìn)行求解可得每個(gè)階段的發(fā)現(xiàn)概率如表2(表中用P1代替P(BR1|D0)，P2代替P(BR2|D0)，P3代替P(BR3|D0))。

表2 無(wú)貝葉斯干預(yù)的發(fā)現(xiàn)概率Tab.2 Probability of discovery without Bayesian intervention

從表2中可以看到，選取正態(tài)分布比均勻分布得到的累積發(fā)現(xiàn)概率更大。這是由于均勻分布在目標(biāo)所處搜索區(qū)域的概率分布是相同的，但是正態(tài)分布在目標(biāo)所處搜索區(qū)域的概率分布在正態(tài)分布的峰值處最大，因此累計(jì)概率更大。在正態(tài)分布與均勻分布下，每階段發(fā)現(xiàn)概率的變化分別如圖1和圖2所示。

從圖1和圖2中可以看出，不論是正態(tài)分布還是均勻分布，每個(gè)階段的發(fā)現(xiàn)概率都隨著a的增大而逐漸增大。說(shuō)明掃視面積系數(shù)a對(duì)發(fā)現(xiàn)概率有一定影響，但是根據(jù)圖1和圖2中直線之間的距離來(lái)看，發(fā)現(xiàn)概率的增大與a的增大不是線性關(guān)系。

圖1 正態(tài)分布下每階段發(fā)現(xiàn)概率Fig.1 Probability of discovery at each stage under normal distribution

圖2 均勻分布下每階段發(fā)現(xiàn)概率Fig.2 Probability of discovery at each stage under uniform distribution

3.2 有貝葉斯干預(yù)下的模擬實(shí)驗(yàn)

在3.1節(jié)實(shí)驗(yàn)中加入貝葉斯干預(yù)，即在完成第一階段搜索之后，加入一個(gè)新的信息NF(-6,13;8,8;0)，pF=0.52>pA，則更新F區(qū)域?yàn)榈诙A段搜索區(qū)域，A區(qū)域?yàn)榈谌A段搜索區(qū)域，此時(shí)每個(gè)階段的發(fā)現(xiàn)概率如表3。

表3 貝葉斯干預(yù)下發(fā)現(xiàn)概率Tab.3 Probability of discovery under Bayesian intervention

從表2和表3中可以看出，加入貝葉斯干預(yù)后，第一階段的發(fā)現(xiàn)概率是相同的，說(shuō)明貝葉斯干預(yù)對(duì)干預(yù)前一階段的發(fā)現(xiàn)概率沒(méi)有影響；而第二階段與第三階段的發(fā)現(xiàn)概率均有增加，這是由于加入貝葉斯干預(yù)后，概率分布重新調(diào)整，干預(yù)后新加入的區(qū)域比原區(qū)域目標(biāo)存在的概率大，因此發(fā)現(xiàn)概率也增大，累計(jì)發(fā)現(xiàn)概率也會(huì)增大。圖3給出了有貝葉斯干預(yù)和無(wú)貝葉斯干預(yù)情況下的累計(jì)發(fā)現(xiàn)概率對(duì)比。

圖3 有無(wú)貝葉斯干預(yù)下累計(jì)概率對(duì)比Fig.3 Comparisons of cumulative probability with and without Bayesian intervention

從圖3中能夠明顯看出在加入貝葉斯干預(yù)后累計(jì)發(fā)現(xiàn)概率增大，尤其是a=1到a=1.2時(shí)，增長(zhǎng)趨勢(shì)明顯。這是由于加入貝葉斯干預(yù)后，概率進(jìn)行重新分配，第二階段與第三階段所占概率比相較之前較高，因此發(fā)現(xiàn)概率增大，累計(jì)發(fā)現(xiàn)概率也會(huì)增大。

4 結(jié)論

在已有文獻(xiàn)中，大都假設(shè)目標(biāo)位于搜索區(qū)域位置的分布為均勻分布，但通常情況下，由于預(yù)先獲取了目標(biāo)所在區(qū)域的分布以及該區(qū)域的地理特點(diǎn)信息，容易推斷目標(biāo)在某一些基點(diǎn)上的分布概率可能大一些，在其他位置則可能小一些。因此，在已掌握這些信息的情況下，均勻分布的假設(shè)就顯得不盡合理。本研究首先確定目標(biāo)的初始先驗(yàn)分布，然后計(jì)算每個(gè)目標(biāo)在相同區(qū)域內(nèi)的初始概率，選擇合理的任務(wù)區(qū)域后，將任務(wù)區(qū)域概率歸一化，最終得到目標(biāo)在搜索區(qū)域上的概率分布，最后給出最優(yōu)搜索策略。基于貝葉斯更新思想，利用貝葉斯公式獲取目標(biāo)信息的后驗(yàn)分布，進(jìn)而由所給目標(biāo)搜索策略模型做出決策，保證了搜索信息在不同階段的動(dòng)態(tài)傳遞性。同時(shí)，由于使用貝葉斯干預(yù)，在貝葉斯更新過(guò)程中能夠采用目標(biāo)新信息，使得所做決策更具實(shí)時(shí)性和合理性。

所給模型也有一定局限性。首先，在對(duì)海上搜索目標(biāo)制定搜索策略時(shí)，由于目標(biāo)隨洋流漂流移動(dòng)，會(huì)帶來(lái)較大誤差。解決這個(gè)問(wèn)題，可以通過(guò)對(duì)正態(tài)分布密度函數(shù)進(jìn)行改進(jìn)，加大基點(diǎn)在洋流方向上概率分布的拖尾來(lái)實(shí)現(xiàn)。其次，沒(méi)有考慮多無(wú)人機(jī)協(xié)作的搜索策略問(wèn)題，搜索成本、無(wú)人機(jī)最大工作時(shí)間等因素也是需要進(jìn)一步考慮的問(wèn)題。