張帆 胡航

（中國人民解放軍66133部隊 北京市 100144）

無人機蜂群在進入特定環(huán)境時，根據(jù)總體任務進行了全局任務分配，每個無人機在確定自己需要承擔的任務后需進行全局的飛行航線規(guī)劃。在航線規(guī)劃時每個無人機需考慮的要素包括：所有的任務點、任務區(qū)域、進入點和退出點。

1 RRT算法研究

1.1 RRT算法原理簡介

假設任務空間為C，Cfree表示可行區(qū)域，Cobs表示障礙區(qū)域，Cfree和Cobs同為C的子集，且滿足C=Cfree∪Cobs和Cfree∩Cobs=φ。初始位置qinit∈Cfree和目標位置qgoal∈Cfree，現(xiàn)需要為規(guī)劃出從初始位置到目標位置的可行路徑。

使用 RRT 算法進行路徑規(guī)劃分為任務空間內(nèi)的隨機樹生長和可行路徑的反向搜索兩個階段。其中隨機樹的生長，即如何構(gòu)造隨機樹是 RRT 算法的主要內(nèi)容。RRT 算法通過逐步迭代的增量方式進行隨機樹的構(gòu)造，首先在任務區(qū)域內(nèi)選定起始節(jié)點qinit作為樹的根節(jié)點，通過從根節(jié)點不斷擴展出葉節(jié)點的方式構(gòu)建隨機樹。首先以概率Pg選擇目標位置qgoal作為隨機目標點qrand，或者以概率1-Pg在任務空間內(nèi)隨機選擇一個隨機目標點qrand；從隨機樹當前所有的葉節(jié)點之中，選擇出一個離qrand最近的，稱之為臨近節(jié)點qnear；然后從qnear向qrand的方向延伸一個步長的距離ε，得到一個新的節(jié)點qnew。在延伸過程中，判斷是否與已知的威脅區(qū)域有沖突，若無沖突接受該新節(jié)點qnew，并將其添加為隨機樹的節(jié)點；若qnew與威脅區(qū)域有沖突，說明該次擴展出的新節(jié)點不符合安全要求，則舍棄該新節(jié)點，并重新進行隨機目標點qrand的選取。通過這樣不斷的延伸擴展，當隨機樹中的葉節(jié)點與目標位置足夠近的時候，則認為隨機數(shù)的構(gòu)造工作完成，此時以距離目標位置最近的葉節(jié)點為起始，依次向上搜索父節(jié)點，則可以獲得一條從起始位置到目標位置的可行路徑。二維空間內(nèi)的RRT算法節(jié)點擴展過程如圖1。

1.2 RRT算法的改進

RRT*的原理是在RRT算法的基礎(chǔ)上，生成隨機點qrand，找到樹上最臨近節(jié)點qnearest，根據(jù)設置好的步長Segment，會預先生成一個qnew，在以qnew為中心，以radius為半徑的圓內(nèi)，找到所有點半徑小于radius的節(jié)點qnear，遍歷所有的qnear，計算每個qnear作為qnew父節(jié)點時的代價，將每條路徑的代價與原路徑代價相比較。如果比原路徑代價小且能夠通過碰撞檢測，則將正在遍歷的qnear作為新的父節(jié)點。

如前所述，由于無人機的平臺性能是受限的，因此在基于RRT算法進行航線規(guī)劃時，應當考慮無人機上一節(jié)點與下一個需要擴展的節(jié)點的夾角。根據(jù)前面的討論，新產(chǎn)生的節(jié)點應當滿足如圖2所示的約束。

另一方面，直接應用RRT算法存在的缺點是算法向各個方向擴展的概率是相同的。這將會導致生成大量的冗余節(jié)點，極大的降低了算法的計算效率。在航線規(guī)劃時擴展樹中的節(jié)點均是隨機生成擴展而來，因此隨機節(jié)點xrand的選取合適與否將直接影響最終生成航線的質(zhì)量。為了得到質(zhì)量更高的xrand節(jié)點，可以采用多重隨機采樣策略，即從規(guī)劃空間中產(chǎn)生一組隨機采樣點，然后對這一組點中選擇最優(yōu)的xrand進行拓展。為了在一個采樣集合中得到最優(yōu)的xrand，需要根據(jù)相應的評價函數(shù)對節(jié)點集進行評價。由航線規(guī)劃的目的可知，優(yōu)化的航線應是連接起始點與終點，滿足各種約束且能夠保證無人機不冗余飛行的航線。因此，RRT算法擴展的與目標方向相反的航點大概率將會生成低效的飛行航線。

無人機在空中飛行時，決定飛機狀態(tài)評價的參數(shù)包括兩個參數(shù)，即當前飛行位置，飛行方向。因此在對采樣點的評價函數(shù)確定為：

如圖3所示，其中d表示采樣點到終點的歐氏距離，a表示起始點到目標點與采樣點到目標點的夾角，w1、w2分別是距離和角度的權(quán)重系數(shù)。

由于距離與方向量綱不統(tǒng)一，還需對該評價函數(shù)中的d和a進行歸一化處理，即計算k 個采樣點的距離和角度值，然后求出其平均值d和a，即：

圖1：RRT搜索原理圖示

圖2：基于無人機的機動性能確定航線規(guī)劃的約束

圖3：節(jié)點評價函數(shù)構(gòu)造示意圖

圖4：貝塞爾曲線

求出均值后，再對每一個采樣點對應的距離和角度進行歸一化處理，因此評價函數(shù)變?yōu)椋?/p>

另一種改進方法為基于最近鄰可達點的改進RRT方法，即NAPRRT。由于基本RRT算法過程中包含了大量的浮點運算，影響了算法效率，針對此問題，希望在擴展子節(jié)點時優(yōu)先擴展當前節(jié)點附近的、無碰的節(jié)點，而不需要處理隨機點角度相關(guān)的復雜運算，故提出該種改進方法。

2 貝塞爾曲線路徑的平滑處理

貝塞爾對于路徑平滑非常有效，它有一個最重要的特點就是在不更改整條路徑形狀的前提下重新構(gòu)建局部路線。研究中運用貝塞爾曲完成RRT*算法執(zhí)行后的后續(xù)工作，創(chuàng)建一條更加平滑的路徑。

貝塞爾曲線可以定義為下式：

在此重點考慮n-3的情況，即三次貝塞爾多項式Bp(t)。隨著伯恩斯坦多項式的擴展，得到貝塞爾曲線的參數(shù)方程：

上式中，四個點P1、P2、P3和P4確定了一個三次貝塞爾曲線，其中，P1和P4為曲線的端點，P2和P3為曲線的控制點，曲線的屬性如下：

（1）Bp(0)=P1且Bp(1)=P4；

根據(jù)貝塞爾曲線的屬性（1），將路徑段Gp構(gòu)建為P1=qinit與P4=qgoal，也就是說，隨機數(shù)在擴展的過程中，每一個擴展的端點qinit可以定為P1，每一個擴展的目標點qgoal可以定為P4，那么隨機樹就能夠按照三次貝塞爾曲線進行擴展了。擴展過程如圖4所示。

3 融合RRT*和貝塞爾曲線的無人機蜂群航線規(guī)劃方法

圖5：參照無人機調(diào)整航線示意圖

情況設想中，有多個無人機編隊共同執(zhí)行任務，各編隊執(zhí)行的任務各不相同。編隊中各架飛機執(zhí)行任務情況相同，無人機之間保持通信，同時到達任務點執(zhí)行任務。因此，無人機蜂群在完成任務過程中是作為一個集群在飛行，需要保證群隊飛行的效果。每架無人機在規(guī)劃航線時都必須考慮編隊飛行，而不僅僅考慮自身航線最優(yōu)。

為了達到此目的，可在編隊中選出一架參照無人機，參照無人機獨立運用RRT*和貝塞爾曲線規(guī)劃出最優(yōu)航線，同時將最優(yōu)航線發(fā)布給編隊中其他無人機，其他無人機據(jù)此進行自身航線規(guī)劃。參照無人機的選擇標準有：起始狀態(tài)下位于編隊中的位置（前方或中間）、飛行能力較強、油料較多。具體方法如下：

（1）運用RRT*算法和貝塞爾曲線規(guī)劃出參照無人機執(zhí)行任務的最優(yōu)路線；

（2）參照無人機向編隊中其他無人機發(fā)布最優(yōu)航線，其他無人機以一定安全距離伴隨飛行；

（3）參照無人機適當調(diào)整自己的航線，需要考慮其他無人機的可飛性，適當增加參照無人機與障礙物間的距離，保證其他無人機伴隨飛行時的安全等，使整個編隊到達下一個任務點的時間最短或盡可能避障、遠離威脅,如圖5所示。

（4）其他無人機規(guī)劃伴隨飛行航線應以無人機間安全距離和避障等為約束，編隊規(guī)模較小時，其他無人機根據(jù)參照無人機方位飛行，使整個盡可能避免沖突、遠離威脅；編隊規(guī)模較大，則編隊中部分無人機與參照無人機的距離遠，無法很好地進行通信和伴隨飛行，這時需要將編隊進行分層，如果參照無人機在編隊前部，則中部無人機伴隨參照無人機飛行，后部無人機以中部無人機為參照伴隨飛行。

接著，假設每個無人機編隊中的無人機為等距橫向排列，設置編隊中無人機之間的間隔為λ米，機群中先到達執(zhí)行任務點的無人機在匯合過程任務范圍內(nèi)徘徊，匯合過程路徑由貝塞爾曲線產(chǎn)生；

最后，將規(guī)劃好的航路段分配給所屬的無人機編隊，并將無人機編隊的每個航路段連接起來，無人機編隊等間距λ生成五條航線，同時將第3個步驟中生成的匯合過程路徑與編隊航線連接起來，即為規(guī)劃的完整航線。