不確定環(huán)境下的多無人機協(xié)同搜索航路規(guī)劃

吳文超，黃長強，宋磊，唐上欽，白壬潮

(1.空軍工程大學(xué) 工程學(xué)院，陜西 西安710038;2.空軍裝備部，北京100843)

利用無人機(UAV)執(zhí)行偵察任務(wù)在眾多領(lǐng)域都得到了廣泛應(yīng)用，如對敵區(qū)目標(biāo)情況進(jìn)行偵察監(jiān)視，在公海、沙漠或山區(qū)展開搜索營救以及對礦藏的資源勘察等。相對于有人駕駛飛機，UAV 成本低，可操縱性好，尤其適合于執(zhí)行危險的任務(wù)［1］。由于單架UAV 在信息收集方面的局限性，多架UAV 協(xié)同執(zhí)行復(fù)雜搜索任務(wù)吸引了越來越多的關(guān)注［2-3］。一些窮舉覆蓋航路規(guī)劃模型，如Zamboni 搜索方法已經(jīng)得到了發(fā)展應(yīng)用［4-6］。然而該方法缺乏靈活性，如在設(shè)計某地區(qū)的UAV 森林火災(zāi)偵察路線時，不能對該區(qū)域的湖泊以及其他無林地帶進(jìn)行規(guī)避，在載油有限和時間緊張的情況下，將影響到對其他更有價值區(qū)域的偵察活動。文獻(xiàn)［7］中提出的搜索算法可以對整個環(huán)境展開遍歷搜索，但沒有考慮UAV 的機動限制和搜索環(huán)境的動態(tài)特性。如UAV的物理機動性能會限制其最小轉(zhuǎn)彎半徑，而在大部分窮舉搜索算法中，允許UAV 向任何方向運動［8］。此外，任務(wù)時間和機載燃油的限制可能不允許UAV完全覆蓋整個環(huán)境，從而需要對目標(biāo)存在概率較高的特定區(qū)域進(jìn)行重點偵察。文獻(xiàn)［9］對UAV 的協(xié)同搜索展開了研究，UAV 在搜索過程中一定程度上可以避開已知區(qū)域，但是其算法無法保證對禁飛區(qū)實現(xiàn)完全回避。文獻(xiàn)［10］基于遺傳算法設(shè)計了UAV 的偵察航路，其研究是在假設(shè)目標(biāo)位置已知情況下進(jìn)行的，在環(huán)境中的目標(biāo)分布信息很少的情況下，應(yīng)用受到了限制。本文主要針對不確定環(huán)境下的多UAV 協(xié)同搜索問題展開研究，所謂不確定環(huán)境指的是在該環(huán)境中關(guān)于目標(biāo)的分布是有限的(甚至沒有)先驗信息。

1 協(xié)同搜索的問題描述

一種典型的UAV 協(xié)同搜索在線規(guī)劃和飛行控制框架如圖1所示。它包括上層決策(任務(wù)規(guī)劃)和由傳感器、跟蹤控制器和飛行器本體組成的底層控制2 部分。UAV 接收地面站發(fā)送的任務(wù)，同時借助本機傳感器或它機傳感器(通過數(shù)據(jù)鏈)實時更新環(huán)境信息，進(jìn)行航路規(guī)劃產(chǎn)生參考飛行航跡，而后跟蹤控制器根據(jù)UAV 的動力學(xué)模型產(chǎn)生激勵輸入信號，控制UAV 沿參考軌跡飛行。

與相互獨立控制的單架UAV 相比，多架UAV協(xié)同搜索能夠提供更有效的偵察能力。多架UAV在不確定環(huán)境中進(jìn)行協(xié)同搜索時，一般需要滿足以下原則［11-12］:

1)在條件允許的情況下覆蓋盡可能多的區(qū)域。

2)為了提高搜索效率，應(yīng)對環(huán)境中的無回報區(qū)域(環(huán)境信息完全已知區(qū)域)盡可能進(jìn)行規(guī)避，而對環(huán)境中目標(biāo)存在概率較大的區(qū)域進(jìn)行重點偵察。

3)滿足UAV 機動限制要求，在數(shù)據(jù)通訊延遲和編隊中的某架UAV 出現(xiàn)故障時不影響其他UAV的協(xié)同搜索任務(wù)。

4)保證UAV 飛行安全。

需要說明:當(dāng)對環(huán)境信息完全不確定的情況下應(yīng)當(dāng)盡可能的進(jìn)行區(qū)域覆蓋，以求獲得盡可能多的目標(biāo)信息，而當(dāng)存在部分先驗已知信息時，需要對目標(biāo)存在概率很小的區(qū)域進(jìn)行規(guī)避，對目標(biāo)存在概率較大的區(qū)域進(jìn)行重點偵察。所以第1)、2)條只是應(yīng)用的前提條件不同，并不矛盾。第3)條是從應(yīng)用角度提出的，要求得到的路徑具有物理可行性，并能夠適應(yīng)突發(fā)事件的發(fā)生。第4)條是從安全角度提出的，由于政治、軍事或地理方面的原因，UAV 在搜索過程中要保證徹底避免進(jìn)入禁飛區(qū)。另外由于UAV 可以在不同高度下航行，因此本文不考慮UAV之間的碰撞規(guī)避問題。

根據(jù)上述原則，本文將環(huán)境劃分為目標(biāo)信息未知環(huán)境，已知環(huán)境和禁飛區(qū)，并對這3 種區(qū)域區(qū)別對待:UAV 主要針對未知環(huán)境展開搜索;UAV 應(yīng)當(dāng)盡量避免對已知環(huán)境進(jìn)行搜索(但在受到轉(zhuǎn)彎限制的情況下可以經(jīng)過);UAV 必須完全避開禁飛區(qū)。下面就路徑?jīng)Q策算法設(shè)計以及針對3 種區(qū)域的不同對策設(shè)計展開研究。

2 協(xié)同搜索航路規(guī)劃

2.1 環(huán)境模型

本文使用笛卡爾柵格識別地圖描述環(huán)境，每一柵格被賦予一個值代表UAV 關(guān)于該區(qū)域目標(biāo)分布的感知能力。設(shè)環(huán)境E 為一個Lx×Ly的有界區(qū)域，將UAV 在t=kT 時刻對于(x，y)坐標(biāo)處的目標(biāo)分布的不確定性能力表示為η(x，y，k)，且滿足η(x，y，k)∈［0，1］.η(x，y，k)值越大，表示的不確定性越高，如果η(x，y，k)=1，表示UAV 在t 時刻完全不知道目標(biāo)在單元(x，y)的分布情況。

2.2 UAV 模型

假定所有UAV 以定常速度v 運動，θmax為UAV物理操縱性能限制最大轉(zhuǎn)彎角，UAV 的運動數(shù)學(xué)模型如下:

當(dāng)某架UAV 經(jīng)過某區(qū)域(x，y)時，有

式中:p 為機載傳感器對目標(biāo)的探測能力。如果對某單元多次搜索，η(x，y，k)趨向于0.

2.3 路徑?jīng)Q策算法

UAV 使用識別地圖儲存關(guān)于環(huán)境的不確定知識，通過數(shù)據(jù)融合算法載入UAV 傳感器，隨著識別地圖不斷更新，航路點決策函數(shù)利用地圖確定搜索特定環(huán)境區(qū)域的值，并且產(chǎn)生航路導(dǎo)引每架UAV 進(jìn)行搜索。這種航路應(yīng)該考慮到UAV 的操縱限制，即首先要求產(chǎn)生的航路物理可行，然后利用回報函數(shù)定義一種控制問題(該回報函數(shù)表征探索目標(biāo)的收益)，最終選擇一條可產(chǎn)生最大回報的航路。算法設(shè)計如下:

首先將路徑規(guī)劃問題時間離散化，即只允許UAV 在離散時間間隔T 內(nèi)做出決策。假定UAVi 在時刻t=kT 的位置為pi(k)，將pi(k+1)的可能位置離散化為m 個點，每個點的位置可以表示為(k+1)，j=1，2，…，m，則UAVi 在時刻t=kT 的所有可能點的位置可以表示為如下集合:(k+1)={p1i(k+1)，…(k+1)，…(k+1)}UAV 從pi(k)運動到下一位置pi(k+1)的距離為dt，并且應(yīng)滿足±θm的角度范圍限制?？紤]到UAV 之間的數(shù)據(jù)傳輸延遲，UAVi 的開始q 個位置，pi(1)，pi(2)，…，pi(q)需要提前做出選擇。當(dāng)UAVi 在時刻t 位于位置pi(k)時，它已經(jīng)決定了下面的q 個位置:pi(k+1)，pi(k+2)，…，pi(k+q).當(dāng)UAV 到達(dá)pi(k)后，它開始選擇位置pi(k+q+1)，將在時刻t=k+q+1 到達(dá)。只考慮UAV 3 種航路選擇狀態(tài):左轉(zhuǎn)θmax，直飛，右轉(zhuǎn)θmax，即m 值取3，當(dāng)q=3 時的航路搜索樹如圖2所示。

3 搜索回報函數(shù)

協(xié)同航路搜索的關(guān)鍵是設(shè)計一個搜索回報函數(shù)，對每條可行路徑的回報值進(jìn)行評估。根據(jù)前面提出的協(xié)同航路規(guī)劃方法，每架UAV 使用回報函數(shù)J 選擇它的搜索航路:

式中:J1，J2，J3為航路選擇點的對應(yīng)回報標(biāo)準(zhǔn);ωi為相應(yīng)的權(quán)重，0≤ωi≤1，且為重要性因子，γ≥1.收益標(biāo)準(zhǔn)的優(yōu)先性通過調(diào)整權(quán)重ωi實現(xiàn)，航路選擇點的重要性通過調(diào)整γ 來體現(xiàn)。如果UAVi 在時刻t=kT 選擇第j∈［1，2，…，m］條路徑，則J1(i，j，k)，J2(i，j，k)分別計算如下:

圖2 3 步航路搜索樹示意圖Fig.2 Illustration of recursive 3-step planning tree

式中:(x，y)為UAVi 沿第j 條航路飛行的航路點;η(x，y;k)為UAVi 在時刻k 關(guān)于點(x，y)的不確定值。從(7)式和(8)式可以看出，J1(i，j，k)表示當(dāng)前位置pi(k)與(k-1)之間不確定性減少的程度，J2(i，j，k)表示(k)，(k)，…(k)的平均不確定度。

UAV 之間通過數(shù)據(jù)鏈傳輸實現(xiàn)信息共享，在UAV 相互之間距離很近，運動方向大致相同或相反的情況下容易出現(xiàn)航路重疊。為避免出現(xiàn)這種情況，將其他UAV 視為軟障礙，運用一種人工勢場算法使一定距離范圍內(nèi)的其他UAV 對UAVi 施加綜合抗力Fi(k)，使UAVi 從(k+q+1)中選擇航路點pi(k+q+1)，實現(xiàn)航路規(guī)避。

在時刻k 由其他所有UAV 作用到UAVi 上的綜合抗力可以表示為

其中:

式中:Fi(k)為在時刻t=kT 由相鄰UAV 作用到UAVi 上的綜合抗力;Rij為UAVi 與UAVj 的距離;Rij為對應(yīng)的單位向量。k1取值對應(yīng)于距離Rij為0時的抗力大小。設(shè)計參數(shù)μ ＞0，對應(yīng)于抗力隨距離增加而減少的速率。Rmax、βmax、φmax分別為UAVj 與UAVi 之間產(chǎn)生抗力作用的最大允許距離、最大允許角度和最大允許方位角之差。如圖3所示。

式中:k2為非負(fù)參數(shù);αi(j，k)為綜合抗力Fi(k)與(k+q+1)中每一可行路徑的方位差。從協(xié)同的觀點來看，顯然應(yīng)該選擇具有最小αi(j，k)的航路。

將(6)式標(biāo)準(zhǔn)化，有

Jn為標(biāo)準(zhǔn)化代價函數(shù)，計算如下

圖3 UAV 抗力產(chǎn)生條件示意圖Fig.3 Sketch of rivaling force conditions between UAVs

4 禁飛區(qū)回避決策設(shè)計

針對禁飛區(qū)回避問題一種可能的方法是將禁飛區(qū)內(nèi)的搜索回報函數(shù)設(shè)定為最小值。但是這并不能保證UAV 不會進(jìn)入禁飛區(qū)。如圖4中當(dāng)UAV 以航向角θ=90°飛到節(jié)點b2時，受最大轉(zhuǎn)彎角的限制，當(dāng)可選節(jié)點均位于禁飛區(qū)時，UAV 將無法避免進(jìn)入禁飛區(qū)。下面介紹一種新的解決辦法，以θmax=45°為例進(jìn)行說明。

解決的思路是在UAV 要選擇的位置還沒有進(jìn)入禁飛區(qū)時提前做出選擇，當(dāng)pi(k+q+1)與禁飛區(qū)的邊界距離小于1 個步長dt 的距離時，如圖4陰影部分所示，UAV 開始從b1，b2，b3三個位置中做出選擇。圖4中UAV 從a1進(jìn)入b2時，由于受到轉(zhuǎn)彎限制，UAV 無法避開禁飛區(qū)，因此b2為不可行點，即使b2點具有比b1和b3更高的收益也必須放棄，而此時b1和b3為可行點，UAV 可分別到達(dá)點c1和c7，展開下一步搜索。需要注意的是當(dāng)UAV 從b1和b3的正下方進(jìn)入時，這2 點又都變成了不可行點，因此判斷某點是否可行點取決于該點的位置和UAV 進(jìn)入該點的角度。針對圖4中的矩形禁飛區(qū)進(jìn)一步分析可發(fā)現(xiàn)，當(dāng)x1≤xb≤x2并且y1- dt≤yb＜y1時，如果(xb，yb)處UAV 的航向角為90°，則該點為不可行點，航向角為45°時則該點為可行點。同理可對陰影框的其他部分進(jìn)行分析。為了保證下一步搜索時UAV 不會進(jìn)入禁飛區(qū)，將所有位于禁飛區(qū)內(nèi)的選擇點不論航向角大小均列為不可行點。

設(shè)M={(xi，yi)，θi}為陰影區(qū)內(nèi)的所有點和所有航向角的集合;Mf為陰影區(qū)內(nèi)所有可行點和可行航向角的集合，則在圖4中Mf應(yīng)滿足(14)式～(21)式:

需要說明的是，(14)式～(21)式只針對圖4.隨著禁飛區(qū)位置和形狀的不同，Mf會有所變化，需要根據(jù)具體情況分析，但分析策略類似。

UAV 整個搜索程序如下:

1)任務(wù)參數(shù)初始化。

2)for k=1 to n.

3)if pi(k+q+1)∈E.

4)if (pi(k+q+1)，θi(k+q+1))?M.

5)計算pi(k+q+1)的m 個可能位置處的回報函數(shù)J，選擇J 值最大的航路。

6)else 根據(jù)pi(k+q+1)的m 個可能位置是否滿足Mf中可行點的條件從中選取m'個可行位置和對應(yīng)的可行航向角，選擇J 值最大的航路。

7)end if.

8)else 執(zhí)行轉(zhuǎn)彎程序，使UAV 回到環(huán)境中。

9)end if.

10)k=k+1.

11)end for.

5 仿真實驗分析

設(shè)E(x，y)為待偵察區(qū)域，50 km≤x≤200 km，50 km≤y≤200 km，A 為根據(jù)先驗知識不需要進(jìn)行偵察的區(qū)域，B 為禁飛區(qū)。假定在每一樣本時間內(nèi)，UAV 只允許在-45°～45°之間的角度進(jìn)行直飛，左轉(zhuǎn)或右轉(zhuǎn)。

實驗1 設(shè)需要進(jìn)行重點偵察的區(qū)域F(x，y)坐標(biāo)為:130 km≤x≤180 km，60 km≤y≤110 km.剩余部分為完全不確定區(qū)域，即η(x，y)=1，ω1=1/3，ω2=1/3，ω3=1/3，(x，y)∈F 時，γ=3，(x，y)?F時，γ=1.機載傳感器對目標(biāo)的探測能力p=0.6.5 架UAV 從不同基地起飛開始執(zhí)行偵察任務(wù)，其起飛點坐標(biāo)分別為(50，50)，(80，50)，(110，50)，(140，50)，(170，50)，運行60 步長的仿真結(jié)果如圖5所示。

圖5 設(shè)置重點搜索區(qū)域的5 架UAV 協(xié)同搜索仿真結(jié)果Fig.5 Simulation results of cooperative search with a key search zone for five UAVs

由圖5可知，UAV1 有一段航路經(jīng)過A 區(qū)，而UAV1 和UAV2 盡管一度接近禁飛區(qū)但最后都順利避開。由于對F(x，y)搜索能獲得更高的收益，該區(qū)航路明顯比較密集。

實驗2 為了便于與其他算法進(jìn)行比較，設(shè)γ為常數(shù)，取值1，其他參數(shù)設(shè)定同試驗1.試驗分2部分進(jìn)行:首先運行80 步長，然后假定UAV1、UAV4 和UAV5 設(shè)備故障返航，分別對UAV2 和UAV3 運行20 步長，分別運用Zamboni 搜索、隨機搜索和本文的協(xié)同搜索算法進(jìn)行仿真，仿真結(jié)果分別如圖6～圖8所示(UAV2 和UAV3 的后半段航跡用星號線表示)。

圖6 5 架UAV 的Zamboni 搜索仿真結(jié)果Fig.6 Simulation results of Zamboni search for five UAVs

圖7 5 架UAV 的隨機搜索仿真結(jié)果Fig.7 Simulation results of random search for five UAVs

由圖6和圖7可以看出，Zamboni 搜索和隨機搜索的航跡不會受到區(qū)域A 和B 的影響，而圖8中的協(xié)同搜索只有一架UAV 的航跡經(jīng)過區(qū)域A，所有UAV 都避開了區(qū)域B.另外，Zamboni 覆蓋算法和協(xié)同搜索算法幾乎沒有路徑重疊，而隨機搜索出現(xiàn)了多處多架UAV 航跡段重疊的情況。在3 架UAV 故障后，Zamboni 算法中的UAV2 和UAV3 仍然按照既定航線搜索，故障UAV 未完成的任務(wù)將得不到執(zhí)行，算法不具有魯棒性。圖7中UAV3 后20 步長中的航跡與UAV1 出現(xiàn)了重疊，這也降低了搜索收益。而從圖8可以看出UAV2 和UAV3 后20 步長中仍能保持之前的協(xié)同搜索策略，并且依然能夠避開禁飛區(qū)。

圖9為搜索效率隨仿真步長的變化情況。由于多處航路經(jīng)過區(qū)域A 和B，造成Zamboni 算法的偵察效率比協(xié)同搜索低，而部分UAV 故障導(dǎo)致在仿真后半段搜索效率幾乎沒有提高;隨機搜索不僅多處航路經(jīng)過區(qū)域A 和B，而且出現(xiàn)多處航路重疊，所以搜索效率也不高;與前2 種非協(xié)同方法相比，協(xié)同搜索可以使搜索環(huán)境的不確定度減少的更快。

圖8 5 架UAV 的協(xié)同搜索仿真結(jié)果Fig.8 Simulation results of cooperative search for five UAVs

圖9 5 架UAV 在3 種搜索樣式下的搜索效率Fig.9 Search efficiencies in three search patterns for five UAVs

6 結(jié)論

通過對目標(biāo)信息未知環(huán)境，已知環(huán)境和禁飛區(qū)實施不同對策，解決了UAV 在不確定環(huán)境中的協(xié)同搜索問題。仿真實驗結(jié)果表明，本文提出的協(xié)同搜索算法對未知環(huán)境可以實施重點偵察，在機載燃油充足的情況下也可以展開覆蓋搜索。對已知環(huán)境能夠?qū)崿F(xiàn)較好的規(guī)避，并完全避免了UAV 進(jìn)入禁飛區(qū)。UAV 在整個仿真過程中都能夠滿足機動限制，并能夠在友機故障的情況下繼續(xù)實現(xiàn)協(xié)同。與3 種非協(xié)同搜索算法相比，本文提出的協(xié)同搜索算法具有更高的搜索效率。

References)

［1］ Schoenwald D A.AUVs:in space，air，water，and on the ground［J］.IEEE Control Syst，2000，20(6):15-18.

［2］ Chandler P，Rasmussen S，Pachter M.UAV cooperative path planning［C］∥Proceedings of AIAA Guidance，Navigation，and Control Conference and Exhibit.Denver:American Institute of Aeronautics and Astronautics，2000:1255-1265.

［3］ Chandler P，Pachter M，Rasmussen S.Hierarchical control for autonomous teams［C］∥Proceedings of AIAA Guidance，Navigation，and Control Conference and Exhibit.Montreal:American Institute of Aeronautics and Astronautics，2001:632-642.

［4］ Svennebring J，Koenig S.Building terrain-covering ant robots:a feasibility study［J］.Autonomous Robots，2004，16(3):313-332.

［5］ Wagner I A，Lindenbaum M，Bruckstein A M.MAC versus PC:determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains［J］.International Journal of Robotics Research，2000，19(1):12-31.

［6］ Yang S，Luo C.A neural network approach to complete coverage path planning［J］.IEEE Transactions on Systems，Man and Cybernetics，2004，34(1):718-725.

［7］ Choset H.Coverage for robotics:a survey of recent results［J］.Annals of Mathematics and Artificial Intelligence，2001，31:113-126.

［8］ Sujit P B，Ghose D.Search using multiple UAVs with flight time constraints［J］.IEEE Transactions on Aerospace and Electronic Systems，2004，40(2):491-510.

［9］ Yang Y.Cooperative search by uninhabited air vehicles in dynamic environment［D］.Cincinnati:University of Cincinnati，2005.

［10］ 柳長安，王和平，李為吉.無人機的偵察航路規(guī)劃［J］.西北工業(yè)大學(xué)學(xué)報，2003，21(4):490-493.LIU Chang-an，WANG He-ping，LI Wei-ji.On path planning for more efficient reconnaissance of UAV［J］.Journal of Northwestern Polytechnical University，2003，21(4):490-493.(in Chinese)

［11］ Polycarpou M，Yang Y，Passino K.A cooperative search framework for distributed agents［C］∥Proceedings of the 2001 IEEE International Symposium on Intelligent Control.Mexico:Institute of Electrical and Electronics Engineers，2001:1-6.

［12］ Butenko S，Murphey R，Pardalos P.Cooperative control:models，applications and algorithms［M］.Dordrecht:Kluwer Academic Publishers，2003:283-321.