基于多優(yōu)化策略RRT的無人機實時航線規(guī)劃

李俊濤，毛紅保，張 鵬，胡京林

（空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

0 引言

隨著戰(zhàn)場復(fù)雜性的提高，各國的防空網(wǎng)絡(luò)呈現(xiàn)出高密度的趨勢［1］。同時，無人機執(zhí)行任務(wù)的復(fù)雜性也急劇增加［2］。因此，傳統(tǒng)無人機航線規(guī)劃因其過度簡化的模型和較差的實時性，產(chǎn)生的航線已難以確保無人機的安全［3］。

目前的航線規(guī)劃算法可以分為兩類：基于組合規(guī)劃思想和基于采樣的航線規(guī)劃算法?；诮M合規(guī)劃的算法主要利用離散化方式構(gòu)建任務(wù)空間模型，通過圖論或線性規(guī)劃等方法解算無人機航線。其典型方法包括 MILP 算法［4］、最優(yōu)控制法［5］、Voronoi圖法［6］以及A*算法［7］。此類算法總能解算出最優(yōu)解，但其對任務(wù)空間信息的完整性需求使得算法的實時規(guī)劃能力較弱。

基于采樣的規(guī)劃算法避免構(gòu)建空間整體結(jié)構(gòu)，采用增量方式探測空間中的安全區(qū)域形成可行航線。典型的算法包括遺傳算法［8］、蟻群算法［9］以及PSO算法［10］等?；诓蓸拥乃惴ń馑愠龅暮骄€優(yōu)化性相較組合規(guī)劃方法稍差，但規(guī)劃解算速度快。

針對目前大多數(shù)算法對模型的過度簡化和實時性差的問題，提出基于多優(yōu)化策略快速擴展隨機樹（Multi-Optimization Rapidly exploring Random Tree，MO-RRT）無人機實時航線規(guī)劃算法。RRT算法執(zhí)行效率高，且具備概率完備性，但其隨機思想也存在優(yōu)化不足的缺點。本文提出的MO-RRT算法以標準RRT算法為基礎(chǔ)，基于敵方威脅的精確建模，建立基于目標啟發(fā)的快速收斂航線規(guī)劃算法。同時，MO-RRT算法也針對航線的平滑性進行優(yōu)化設(shè)計。最終，該算法能夠?qū)崿F(xiàn)威脅環(huán)境未知的實時航線規(guī)劃。

1 標準RRT算法基本原理

標準RRT算法能夠根據(jù)實時環(huán)境信息快速地搜索規(guī)劃空間，通過組態(tài)空間的隨機采樣點，將搜索導(dǎo)向空白區(qū)域，適用于解決航線規(guī)劃問題［11］。其規(guī)劃生成過程為：

輸入：航線規(guī)劃起始點N0、目標點Ngoal；

Step1：以航線起始點作為搜索樹的根節(jié)點Nroot，對搜索樹Search-Tree初始化，僅包含根節(jié)點；

Step2：在規(guī)劃區(qū)域產(chǎn)生隨機點Nrand，在當前搜索樹Search-Tree中，遍歷所有節(jié)點，確定距Nrand最近的節(jié)點，定義為Nnear；

Step3：按一定的步長生成新節(jié)點Nnew，確定生長路徑；

Step4：判斷新節(jié)點Nnew是否在威脅區(qū)域內(nèi)，若是，則轉(zhuǎn)到Step2；否則，轉(zhuǎn)入Step5；

Step5：判斷新節(jié)點Nnew是否為規(guī)劃航線目標點Ngoal。若是，則轉(zhuǎn)入 Step6；若否，則轉(zhuǎn)入 Step2；

Step6：航線目標點Ngoal稱為搜索樹Υ中的一個葉節(jié)點，由Ngoal回溯到航線規(guī)劃起始點Nroot。由可行路徑中的節(jié)點序列生成航線關(guān)鍵點序列，規(guī)劃輸出；

輸出：航線關(guān)鍵點序列。

算法中提到的新節(jié)點生成過程如圖1所示。首先產(chǎn)生隨機點Nrand并在搜索樹中遍歷到與其最近節(jié)點Nnear。在兩節(jié)點組成的向量方向上，按固定步長截取計算新節(jié)點Nnew，其計算如式（1）所示。步長通常由無人機的性能確定，不小于無人機最短直線航段長度。式中，λ為擴展步長。

圖1 搜索樹新節(jié)點生成示意圖

2 MO-RRT多優(yōu)化策略設(shè)計

為說明優(yōu)化策略的設(shè)計思路，將MO-RRT算法中搜索樹的節(jié)點定義為一個四元組：

其中ci為無人機的三維位置坐標；θi為飛行方向；ID為該節(jié)點區(qū)別于其他節(jié)點的標識符；Origin-id表示該節(jié)點在搜索樹中的父節(jié)點的ID，用于標識該節(jié)點在搜索樹中的位置。

針對標準RRT算法的不足，對其提出適應(yīng)性的優(yōu)化策略。主要作出以下優(yōu)化：①基于雷達跟蹤機制的威脅規(guī)避；②基于目標啟發(fā)的搜索樹節(jié)點擴展；③基于冗余航線點裁剪的航線簡化。

2.1 基于雷達跟蹤機制的威脅規(guī)避

傳統(tǒng)方法單純地將雷達發(fā)現(xiàn)目標概率等同于單次掃描探測到目標信號的概率［12-14］。這種簡化方法忽視了雷達作出目標發(fā)現(xiàn)決策所采用的“多次探測、形成跟蹤”判定準則，使無人機難以充分發(fā)揮性能優(yōu)勢。

文獻［16］對雷達威脅模型進行了概率形式的描述，從航線規(guī)劃的角度，提出考慮目標跟蹤機制的雷達威脅模型。本文將采用該模型進行防空雷達的威脅建模。

模型首先依據(jù)自身性能參數(shù)，通過雷達與目標無人機間的距離和無人機RCS幅值，解算出雷達對無人機的單次探測概率。進一步考慮防空雷達的目標跟蹤機制，解算出雷達多次掃描對無人機形成的跟蹤概率，將其與設(shè)定的判決概率閾值對比，確定無人機是否被發(fā)現(xiàn)。

2.1.1 雷達單次探測概率模型

為降低雷達對無人機的單次探測概率Psingle-d，航線規(guī)劃可調(diào)節(jié)兩者間的距離R。因此，根據(jù)雷達基本原理，可得［19］：

其中，c將其他系數(shù)進行整合，稱為雷達綜合比例系數(shù)，σ為雷達RCS幅值。

因此，在雷達的綜合比例系數(shù)c已知的情況下，根據(jù)無人機相對雷達的RCS和二者距離便可求得雷達單次目標探測概率。由此，在航線規(guī)劃中，可通過控制二者距離，降低雷達對無人機的單次探測概率。

2.1.2 基于跟蹤機制的雷達跟蹤概率模型

在單次掃描得到探測概率Psingle-d的基礎(chǔ)上，雷達判定目標發(fā)現(xiàn)的決策還基于一定的跟蹤機制，主要為以下兩項：①在M個掃描周期中，不存在多于N次未探測到目標信號；②取得的目標信息滿足跟蹤需求或航線預(yù)測。若規(guī)劃航線不同時滿足兩準則，則可實現(xiàn)其飛行安全，間歇式暴露航線便是一則良好的應(yīng)用實例。

依據(jù)雷達探測跟蹤目標成功概率Pm-track與Psingle-d的關(guān)系，實現(xiàn)基于目標跟蹤機制的雷達發(fā)現(xiàn)目標模型。利用雷達與目標間的距離R及無人機目標的RCS幅值σ，可以表示雷達跟蹤目標成功概率為：

式中，c1和c2是由防空雷達自身性能和設(shè)置參數(shù)決定的。

2.1.3 多雷達威脅模型

考慮到不同雷達的雷達波在發(fā)送與接收時均設(shè)定于不同的頻域和時域區(qū)間［17］。本文提出的多雷達威脅模型中認為各部雷達之間探測跟蹤是相互獨立的。因此，考慮到在防空系統(tǒng)中，雷達之間是可以通信的，所以對無人機目標的跟蹤概率可以表述為：

基于雷達目標跟蹤機制的威脅規(guī)避策略利用時間窗滾動策略。雷達目標跟蹤機制確認目標是在一定的時間段內(nèi)對無人機進行周期性掃描得出的。因此，利用固定長度的時間窗將探測航點附近的航線選中。對探測航點的雷達發(fā)現(xiàn)概率計算實際上是對該段時間范圍內(nèi)航線的雷達發(fā)現(xiàn)概率的均值計算。當求得的無人機跟蹤概率大于閾值Pac時，表明無人機在該點處被雷達跟蹤。

利用以上判定準則，對待擴展航線點是否在敵方防空系統(tǒng)威脅空間進行檢驗。若在威脅空間中，則舍棄該待擴展航線點；否則，該點經(jīng)其他約束條件檢驗合格后，可將其添加到航線點搜索樹中。

2.2 基于目標啟發(fā)的快速收斂

在標準RRT算法中，搜索樹節(jié)點擴展方式的隨意性明顯導(dǎo)致其數(shù)量規(guī)模大、結(jié)構(gòu)混雜，生成的航線僅具有可行性，而不具備優(yōu)化性，所以標準算法的收斂性差。因此，提出基于目標啟發(fā)的快速收斂優(yōu)化策略，控制搜索樹節(jié)點擴展，使算法能夠迅速收斂于最優(yōu)解。該優(yōu)化策略主要體現(xiàn)在：①隨機點Nrand產(chǎn)生；②待定節(jié)點Nundeter選擇。

在產(chǎn)生隨機點Nrand時，使一定概率產(chǎn)生的隨機點Nrand取值為目標點，使目標點啟發(fā)引導(dǎo)搜索樹生長方向朝向目標點，加快算法收斂。在每次產(chǎn)生的m個待定節(jié)點Nundeter中，利用目標代價函數(shù)對其評估，選擇最優(yōu)點作為新節(jié)點Nnew添加到搜索樹中，減少搜索樹中性能較差的航線點?；谀繕藛l(fā)的快速收斂優(yōu)化策略的具體算法流程如下。

輸入：目標點選擇概率閾值pgc（0＜pgc＜1）、單次循環(huán)隨機點產(chǎn)生個數(shù)；

Step 1：產(chǎn)生區(qū)間（0，1）之間的隨機數(shù)，并賦值于目標點選擇概率Pg；

Step 2：比較 Pg與 Pgc，若 Pg＞Pgc，則轉(zhuǎn)到 Step 3；否則，轉(zhuǎn)到Step 4；

Step 3：將目標點賦值于產(chǎn)生的隨機點，即Nrand=Ngoal；

Step 3.1：遍歷搜索樹，確定相應(yīng)最近節(jié)點Nnear，根據(jù)移動步長，產(chǎn)生待定節(jié)點Nundeter；

Step3.2：判斷Nundeter是否在威脅區(qū)Zthreaten，若Nundeter?Zthreaten，則添加Nundeter到搜索樹中，返回Step1；否則，直接返回Step 1；

Step 4：在規(guī)劃區(qū)域內(nèi)，產(chǎn)生m個隨機點Nirand（i=1，2，…，m），確定各點的最近點 Ninear；

Step 4.1：對應(yīng)產(chǎn)生m個待定節(jié)點Niundeter（i=1，2，…，m），根據(jù)目標函數(shù)Eq（5）對各個待定節(jié)點估算，取得最小值點Nmin；

Step 4.2：判斷Nmin是否在威脅區(qū)內(nèi)，若Nmin∈Zthreaten，則返回Step 1；否則，添加Nmin到搜索樹中，返回Step 1。

優(yōu)化策略流程中提到判斷節(jié)點是否在威脅區(qū)內(nèi)采用基于雷達跟蹤機制的威脅規(guī)避優(yōu)化策略進行解算決策。

航線規(guī)劃問題模型的目標函數(shù)主要包含威脅代價函數(shù)、航線長度代價函數(shù)和航線轉(zhuǎn)彎代價函數(shù)。因此，航線規(guī)劃問題模型的目標函數(shù)如下式：

其中，Wthreat、Wpath和Wturn依次代表規(guī)劃航線的威脅代價值、航線長度代價和轉(zhuǎn)彎代價。目標函數(shù)中的三項分量在MO-RRT算法產(chǎn)生的航線性能方面的作用和影響，具體如下頁表1所示。k1、k2和k3分別表示3種代價函數(shù)的權(quán)值系數(shù)，其滿足關(guān)系式：0≤k1，k2，k3≤1 和 k1+k2+k3=1。三項權(quán)值系數(shù)可以根據(jù)具體規(guī)劃需求動態(tài)設(shè)定。

表1 目標函數(shù)各項說明

待定航線點Niundeter（i=1，2，…，m）的目標函數(shù)中的三項權(quán)值分量的計算公式分別如下所示：

其中，n為區(qū)域中的敵方雷達數(shù)目，Paj為第j部雷達對Niundeter的跟蹤發(fā)現(xiàn)概率。L（Niundeter）為航線從起始點到Niundeter所經(jīng)歷的路徑長度，‖Ngoal-Niundeter‖為Niundeter到目標點的直線距離?！鳓诪楹较蚪堑母淖冎?。

2.3 基于冗余航點裁剪的航線簡化

在搜索樹中，各子節(jié)點僅對應(yīng)一個父節(jié)點。起始點為唯一的根節(jié)點，采用倒溯法可以找出整條航線中的關(guān)鍵點序列。

由于算法中節(jié)點選取的隨機性，使得航線節(jié)點序列中存在大量冗余節(jié)點。因此，為降低飛行距離，并減少對無人機飛行狀態(tài)的調(diào)整，對航線中的冗余節(jié)點進行裁剪。

冗余節(jié)點裁剪主要考慮兩不相鄰航點間連線是否穿過威脅區(qū)。若不存在威脅，則兩節(jié)點間的節(jié)點均視為冗余。其流程如下：

輸入：初始航線節(jié)點序列為{p1，p2，…，pn}，其中p1和pn分別為航線的起始點和目標點；

Step1：構(gòu)建冗余節(jié)點裁剪后的精簡航點序列集合Γ，該集合初始為空集；

Step2：將目標節(jié)點pn添加到集合Γ中，令j=n、i=1；

Step3：檢查航線節(jié)點pj與pi間是否存在威脅，若存在威脅，轉(zhuǎn)入Step4；若不存在威脅，轉(zhuǎn)入Step5；

Step4：若 i=j-1，則設(shè) j=j-1、i=1，轉(zhuǎn)入 Step3；否則 i=i+1，轉(zhuǎn)入 Step3；

Step5：將節(jié)點pi加入精簡航線節(jié)點序列集合Γ，并令j=i、i=1。若 j=1，則冗余節(jié)點裁剪結(jié)束；否則，轉(zhuǎn)入Step3。

輸出：精簡航線關(guān)鍵點序列。

3 實時航線規(guī)劃算法

實時航線規(guī)劃要求無人機在有限的探測能力下，在遇到威脅致使航線失效時，能夠快速生成新的規(guī)劃航線。

圖2 基于MO-RRT的無人機實時航線規(guī)劃

無人機在依據(jù)預(yù)先規(guī)劃航線飛行時，其不斷對周圍的環(huán)境進行探測。若沒有未知威脅出現(xiàn)，則無人機跟蹤預(yù)先規(guī)劃航線飛行，直到抵達目標點。若出現(xiàn)突發(fā)威脅時，判斷待飛航線是否經(jīng)過威脅區(qū)域，若經(jīng)過，則將當前飛行位置點設(shè)為起始點，對航線進行重新規(guī)劃，無人機按新產(chǎn)生的航線飛行。如此循環(huán)，直到無人機到達目標點。

4 仿真實驗

4.1 仿真環(huán)境

為驗證基于MO-RRT的無人機預(yù)先/實時航線規(guī)劃算法的有效性，對其進行仿真實驗。仿真試驗中算法涉及到的參數(shù)設(shè)置具體見表2所示。

表2 算法仿真實驗參數(shù)設(shè)置

RRT算法的隨機性使得相同條件下的各次規(guī)劃結(jié)果存在差異。為消除隨機性影響，對各算法執(zhí)行1 000次實驗，統(tǒng)計各項規(guī)劃結(jié)果的平均值。

4.2 實驗結(jié)果與分析

4.2.1 優(yōu)化策略驗證

設(shè)置規(guī)劃范圍為60 km×60 km的區(qū)域，目標點的坐標為（10，10），終止點為（59，59）；雷達的部署位置為（30，30）。圖3中兩幅圖依次表示在標準RRT算法和MO-RRT算法規(guī)劃下的航線生成圖。

圖3 不同優(yōu)化策略下的規(guī)劃生成航線

對不同優(yōu)化策略下的兩種算法的千次仿真實驗的性能結(jié)果數(shù)據(jù)統(tǒng)計如表3所示。

表3 兩算法規(guī)劃航線性能比較

由以上對比可知，標準RRT算法生成的搜索樹節(jié)點數(shù)量大（2 034.2）、形狀復(fù)雜，生成航線不具備最優(yōu)性。而MO-RRT算法的平均搜索樹節(jié)點數(shù)為118.4，能有效降低搜索樹規(guī)模，加快算法收斂。同時，通過比較飛行距離均值可知，標準RRT算法生成的航線嚴格處于雷達威脅區(qū)域外（圖中灰色區(qū)域），增加了航線長度；而MO-RRT算法生成的航線則以較短航線穿越雷達最大探測范圍，又確保不被雷達發(fā)現(xiàn)。

4.2.2 實時航線規(guī)劃驗證

MO-RRT算法的實時航線規(guī)劃仿真驗證實驗通過在復(fù)雜戰(zhàn)場環(huán)境下進行。圖4為MO-RRT航線實時規(guī)劃執(zhí)行過程中的各個典型階段。

圖4（a）表示根據(jù)戰(zhàn)場中已知的威脅進行的預(yù)先航線規(guī)劃（綠色粗線為預(yù)先規(guī)劃航線）；無人機按航線飛行時，在某一航點探測到前方存在突發(fā)威脅，如圖4（b）所示，藍色線條表示已飛航線；進而觸發(fā)MO-RRT航線實時規(guī)劃算法以當前點為實時規(guī)劃起點，進行航線實時重規(guī)劃，如圖4（c）所示，紅色線條為實時重規(guī)劃航線；圖4（d）為依據(jù)重規(guī)劃航線飛行的無人機航線。

航線的實時重規(guī)劃性能主要從重規(guī)劃時間、航線節(jié)點數(shù)及航線長度體現(xiàn)。MO-RRT算法對上述場景進行千次實驗，得出其重規(guī)劃時間為180 ms，能夠為規(guī)避突發(fā)威脅提供充足時間。此外，重規(guī)劃航線節(jié)點個數(shù)為83、航線長度為247.02 km，保證了實時規(guī)劃航線的穩(wěn)定性和優(yōu)化性。

圖4 實時航線規(guī)劃過程

5 結(jié)論

本文提出的基于MO-RRT無人機實時航線規(guī)劃算法，實現(xiàn)無人機在高密度雷達威脅的戰(zhàn)場環(huán)境下規(guī)避突發(fā)威脅并實現(xiàn)最優(yōu)飛行航跡。該算法充分利用RRT算法隨機采樣的優(yōu)點，同時考慮雷達的跟蹤準則提高航線安全性，目標啟發(fā)策略進一步加快算法的收斂速度，使算法具備實時性。通過裁剪冗余節(jié)點，有效降低了航線長度，并減少了大量不必要的無人機姿態(tài)調(diào)整。仿真結(jié)果表明該算法具備良好的實時性和優(yōu)化性，算法具備一定的理論和應(yīng)用價值。

［1］魏瑞軒，李學(xué)仁.無人機系統(tǒng)及作戰(zhàn)使用［M］.北京：國防工業(yè)出版社，2009.

［2］姚敏，王緒芝，趙敏.無人機群協(xié)同作戰(zhàn)任務(wù)分配方法研究［J］.電子科技大學(xué)學(xué)報，2013，42（5）：723-727.

［3］郜晨，甄子洋，龔華軍.雷達威脅環(huán)境下的多無人機協(xié)同航跡規(guī)劃［J］.應(yīng)用科學(xué)學(xué)報，2014，32（3）：287-292.

［4］JEAN B.A new mixed-integer linear programming model forrescue path planning in uncertain adversarial nvironment［J］.ComputerandOperationsResearch，2012，39（12）：3420-3430.

［5］WILLIAMS P.Three-dimensional aircraft terrain-following via real-time optimal control［J］.Journal of Guidance，Control and Dynamic，2007，30（4）：1201-1205.

［6］PENG C，LU X Q，DAI J Y，et al.Research of path planning method based on the improved Voronoi diagram［C］//Proc.of the 25th Chinese Control and Decision Conference，2013.

［7］魏瑞軒，許卓凡，王樹磊，等.基于Laguerre圖的自優(yōu)化A-Star無人機航路規(guī)劃算法［J］.系統(tǒng)工程與電子技術(shù)，2015，37（3）：577-582.

［8］JU M Y，CHENG C W.Smooth path planning using genetic algorithms［C］//Proc.of the 9th World Congress on Intelligent Control and Automation，2011.

［9］ZHAO S G，LI M.Path planning of inspection robot based on ant colony optimization algorithm［C］//Proc.of the International Conference on Electrical and Control Engineering，2010.

［10］FOO J L.Path planning of unmanned aerial vehicle using B-splines and particle swarm optimization ［J］.Journal of Aerospace Computing，Information and Communication，2009，6（4）：271-290.

［11］LAVALLE S M，KUFFNER J J.Randomized kinodynamic planning［J］.Int J Robots Res，2001（20）：378-440.

［12］鄭文昌，李磊，徐帆江，等.基于進化算法的無人飛行器多航跡規(guī)劃［J］.宇航學(xué)報，2005，26（2）：223-227.

［13］黃長強.無人作戰(zhàn)飛機精確打擊技術(shù)［M］.北京：國防工業(yè)出版社，2011.

［14］阮穎錚.雷達截面與隱身技術(shù)［M］.北京：國防工業(yè)出版社，1998.

［15］高龍波，李本威，張赟.無人機遠航工作軌跡優(yōu)化研究［J］.兵器裝備工程學(xué)報，2016，36（3）：94-97.

［16］FRANK W M.Radar cross-section reduction via route planning and intelligent control［J］.IEEE Transactions and Control Systems Technology，2002，10（5）：696-700.