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

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

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

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

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

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

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

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

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

4)保證UAV 飛行安全。

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

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

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

2.1 環(huán)境模型

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

2.2 UAV 模型

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

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

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

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

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

首先將路徑規(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，并且應滿足±θm的角度范圍限制?？紤]到UAV 之間的數(shù)據(jù)傳輸延遲，UAVi 的開始q 個位置，pi(1)，pi(2)，…，pi(q)需要提前做出選擇。當UAVi 在時刻t 位于位置pi(k)時，它已經(jīng)決定了下面的q 個位置:pi(k+1)，pi(k+2)，…，pi(k+q).當UAV 到達pi(k)后，它開始選擇位置pi(k+q+1)，將在時刻t=k+q+1 到達。只考慮UAV 3 種航路選擇狀態(tài):左轉θmax，直飛，右轉θmax，即m 值取3，當q=3 時的航路搜索樹如圖2所示。

3 搜索回報函數(shù)

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

式中:J1，J2，J3為航路選擇點的對應回報標準;ωi為相應的權重，0≤ωi≤1，且為重要性因子，γ≥1.收益標準的優(yōu)先性通過調(diào)整權重ω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 關于點(x，y)的不確定值。從(7)式和(8)式可以看出，J1(i，j，k)表示當前位置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為對應的單位向量。k1取值對應于距離Rij為0時的抗力大小。設計參數(shù)μ ＞0，對應于抗力隨距離增加而減少的速率。Rmax、βmax、φmax分別為UAVj 與UAVi 之間產(chǎn)生抗力作用的最大允許距離、最大允許角度和最大允許方位角之差。如圖3所示。

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

將(6)式標準化，有

Jn為標準化代價函數(shù)，計算如下

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

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

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

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

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

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

UAV 整個搜索程序如下:

1)任務參數(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'個可行位置和對應的可行航向角，選擇J 值最大的航路。

7)end if.

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

9)end if.

10)k=k+1.

11)end for.

5 仿真實驗分析

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

實驗1 設需要進行重點偵察的區(qū)域F(x，y)坐標為: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.機載傳感器對目標的探測能力p=0.6.5 架UAV 從不同基地起飛開始執(zhí)行偵察任務，其起飛點坐標分別為(50，50)，(80，50)，(110，50)，(140，50)，(170，50)，運行60 步長的仿真結果如圖5所示。

圖5 設置重點搜索區(qū)域的5 架UAV 協(xié)同搜索仿真結果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 為了便于與其他算法進行比較，設γ為常數(shù)，取值1，其他參數(shù)設定同試驗1.試驗分2部分進行:首先運行80 步長，然后假定UAV1、UAV4 和UAV5 設備故障返航，分別對UAV2 和UAV3 運行20 步長，分別運用Zamboni 搜索、隨機搜索和本文的協(xié)同搜索算法進行仿真，仿真結果分別如圖6～圖8所示(UAV2 和UAV3 的后半段航跡用星號線表示)。

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

圖7 5 架UAV 的隨機搜索仿真結果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 未完成的任務將得不到執(zhí)行，算法不具有魯棒性。圖7中UAV3 后20 步長中的航跡與UAV1 出現(xiàn)了重疊，這也降低了搜索收益。而從圖8可以看出UAV2 和UAV3 后20 步長中仍能保持之前的協(xié)同搜索策略，并且依然能夠避開禁飛區(qū)。

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

圖8 5 架UAV 的協(xié)同搜索仿真結果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 結論

通過對目標信息未知環(huán)境，已知環(huán)境和禁飛區(qū)實施不同對策，解決了UAV 在不確定環(huán)境中的協(xié)同搜索問題。仿真實驗結果表明，本文提出的協(xié)同搜索算法對未知環(huán)境可以實施重點偵察，在機載燃油充足的情況下也可以展開覆蓋搜索。對已知環(huán)境能夠實現(xiàn)較好的規(guī)避，并完全避免了UAV 進入禁飛區(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è)大學學報，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.