基于快速擴展隨機樹算法的多無人機編隊重構方法研究

李樾, 韓維, 陳清陽, 張勇

(1.海軍航空大學 航空基礎學院, 山東 煙臺 264001; 2.國防科技大學 空天科學學院, 湖南 長沙 410073)

多無人機編隊飛行,即多架無人機為適應任務要求而進行的某種隊形排列和任務分配的組織模式,它既包括編隊飛行的隊形產生、保持和變換,也包括飛行任務的規劃和組織[1]。隨著無人機數量不斷增多以及所執行任務的日趨復雜,對多無人機編隊飛行的控制要求也相應提高,同時,任務及環境的頻繁變化要求編隊中的各無人機必須能夠進行靈活的位置變換,即編隊的重構[2]。近年來隨著多無人機編隊技術的發展,該問題逐漸成為研究熱點之一,其重點是對飛行安全及編隊變換效率的研究。

目前,實現多無人機編隊重構的主要方法包括:勢能域函數法、概略圖法、生物算法以及最優控制法等[3]。其中,勢能域函數法應用較廣,但是在環境條件未知且存在動態障礙的情況下,建模存在一定的難度,極易陷入局部最優值[4];概略圖法利用網格圖的形式進行航跡規劃,是機器人領域廣泛采用的一種重構方法[5],但在與無人機動力學模型結合時存在難度,且求解的實時性較差;生物算法包括蟻群算法、魚群算法、粒子群算法等,這些算法的計算效率不一,并且為了規劃出利于跟蹤的航跡,往往還需要借助其他技術,如文獻[6]將粒子群算法和Dubins軌跡相結合,以達到既滿足無人機動力學約束又提高搜索效率的目的;最優控制方法的典型代表是偽譜法,其局限性與勢能域函數方法類似[7],同時,計算的復雜也限制了其應用的范圍。

近年來, RRT算法因適用于解決包含威脅區域和動力學約束條件的運動規劃問題而受到了更多的關注。該方法原理簡單,搜索效率高,由Lavalle在1998年首次提出[8],是一種基于采樣的單查詢隨機搜索算法。其無需在規劃前對節點擴展進行預處理,而是利用傳感器采集的信息對規劃空間進行迅速有效地搜索[9],但不足之處在于,計算量較大、節點處不利于跟蹤、難以生成最優航跡等[10]。針對傳統RRT算法的缺點,許多改進的RRT算法被運用到無人機航跡規劃和編隊重構中。

文獻[11]提出了一種自適應步長的RRT算法,以解決復雜環境中無人機航跡規劃的問題,該算法的改進體現在計算效率和搜索能力上;文獻[12]提出了一種滾動時域與RRT算法相結合的無人機航跡規劃算法,主要通過偏離采樣和節點剔除的方法來提高算法的運算效率;文獻[13]根據無人機航向角變化率,對基本RRT算法生成的航跡進行了優化處理;Farinella等[14]提出了一種基于模型預測法的RRT算法,該算法以中繼衛星為探測傳感器,能達到實時避障的目的;田曉亮[15]將改進的RRT算法應用到多無人機編隊重構中,但僅以2架無人機為例進行仿真,并未考慮編隊重構過程中可能發生的內部碰撞以及最終編隊構型的問題。

總的來說,目前對傳統RRT算法的改進多集中于計算效率和實時規劃方面,對規劃航跡的可跟蹤性以及編隊應用領域的研究相對較少。針對以上不足,本文提出了一種基于RRT算法的多無人機編隊重構方法,以二維平面內按長-僚模式編隊的無人機為研究對象,重點研究其在飛行器動力學、協同及防碰撞等約束下的航跡變換過程,并結合RRT算法的特點,對所規劃的航跡進行冗余裁剪、光滑處理,以實現多無人機編隊在復雜環境中安全、快速變換隊形的目的。

1 問題提出

1.1 多無人機編隊建模

當前,相對成熟的無人機編隊控制模式包含:長-僚模式、模型預測控制模式、基于行為分析的模式、虛擬結構模式以及人工勢場模式等[1]。其中,長-僚模式利用預設的編隊隊形,通過控制長機的飛行速度及姿態來調節僚機的飛行指令,以實現對編隊隊形的控制。長-僚模式具有控制簡單、易實現等優點,因此本文采用該控制模式。

圖1 編隊坐標系下長-僚機的二維位置關系圖

長-僚模式下的編隊坐標系固聯于長機,其原點Ol位于長機的質心,OlXl軸沿長機飛行速度的矢量方向,以前方為正;OlZl軸位于機體對稱平面內,與OlXl軸垂直,指向下;OlYl軸與OlXlZl平面垂直,并與其余2軸構成右手直角坐標系[16]。以2架按長-僚模式編隊的無人機為例,圖1展示了其在編隊坐標系下的二維位置關系圖。其中,[x,y]為僚機F在該坐標系下相對長機L的坐標;V,ψ和μ分別表示無人機相對于慣性坐標系的速度、航跡方位角和航跡滾轉角(μ并未在圖1中標出),下標L表示長機、F表示僚機;ψE是長機和僚機的航跡方位角之差,即ψE=ψF-ψL,與之類似,μE=μF-μL。

(1)

(2)

1.2 傳統RRT算法的原理

傳統RRT算法通過隨機采樣并逐漸增加葉節點的方式生成隨機擴展樹T,主要包括3個步驟:構造采樣點、尋找根節點和擴展節點[13]。下面對其基本原理進行簡要介紹。

Zrand的連線上,以Znear為起點計算出Znew,如果Znew與Znear之間不存在威脅,則將Znew加入到T中,若不然則重新生成采樣點Zrand;重復上述過程,直至|Znew-ZG|≤L,輸出T,并依次連接各根節點,即得到了一條自ZI至ZG的航跡。

1.3 傳統RRT算法在編隊應用中的不足

利用傳統RRT算法生成的航跡具有節點多、在轉彎段曲率不連續等特點,無人機在跟蹤該類航跡時,極易出現因航跡振蕩而造成的飛機失穩現象。這是由于無人機在節點轉彎段缺少提前的預切換,從而導致轉彎時機的滯后,使得飛機允許的最小轉彎半徑與節點轉彎處期望的轉彎半徑不匹配,特別是當飛機地速較大時,所允許的最小轉彎半徑與期望的轉彎半徑相差更大,振蕩現象會更為明顯;另外,節點的冗余對航跡跟蹤的穩定性也會造成一定的影響。

在復雜的飛行環境中,航跡振蕩不利于無人機飛行安全,特別是在多無人機編隊重構過程中,極易導致機間碰撞或與外部障礙的碰撞。因此,基于RRT算法的多無人機編隊重構算法應首先保證各無人機的安全。具體來說,應盡量減少無人機非必要的轉彎,并確保無人機在必要的轉彎處平穩過渡飛行,其關鍵是要滿足無人機最小轉彎半徑的約束,避免提前轉彎或滯后轉彎。

2 基于傳統RRT算法的航跡修正

根據1.3節的分析,針對傳統RRT算法所生成的航跡,可以從兩方面進行修正,一是對隨機樹中不必要的節點進行去除,避免多次機動引起的飛機失穩;另一方面是在節點之間生成過渡航跡,引導無人機轉彎時進入其允許曲率的弧形航跡。其中,多余節點的去除在現有的文獻中運用較為廣泛[9,12,17],其思想也相對統一,具體在2.1節進行歸納總結。

2.1 多余節點的去除

設T中所有節點組成的集合為Root={ZI,Z1,Z2,Z2…Zn,ZG},由于節點擴展具有隨機性,因而在保證航跡可行的基礎上,Root中存在非必須經過的航跡節點,將這些節點視為“多余”的,并將去除多余節點后的節點集合記為Refined,顯然Refined?Root,這表明新的航跡長度相較之前有所縮減。Refined的求解過程具體如下:

首先令Refined={ZI},檢驗ZI,ZG連線之間能否直接通行,即是否滿足無碰撞威脅和飛機動力學約束,若可通行,則ZG加入Refined,結束循環;若不可通行,則依次檢驗ZI,Zi之間連線能否通行,其中初始循環i=n,每次循環后i=i-1(1

圖2 多余節點去除算法的流程圖

2.2 過渡航跡的生成

在傳統RRT算法的節點切換過程中,為了解決飛機允許的最小轉彎半徑與期望轉彎半徑可能不匹配的問題,借鑒Dubins軌跡的思想[18],以飛機在節點處轉彎過程中耗時最短為目標,提出了過渡航跡的概念,其思想是利用以Rmin為半徑的弧形航跡作為連接節點前后2段航跡的規劃航跡。問題解決的關鍵在于確定過渡航跡存在的條件及無人機切入、切出過渡航跡的條件。

(3)

(4)

(5)

當過渡航跡存在時,為避免迭代搜索帶來的計算效率問題,利用幾何法直接解算Oc,過程如(6)式所示

(6)

過渡航跡生成的示意圖如圖3所示,其中無人機滿足逆時針盤旋轉彎的條件。順時針盤旋與之類似,在此不加贅述。

圖3 過渡航跡生成的示意圖

圖4 節點切換策略的選擇示意圖

3 RRT算法在編隊重構中的應用

多無人機編隊的重構過程具有變量多、約束條件復雜等特點,并且由于空中環境的復雜與不確定性,保證編隊的飛行安全是編隊重構的首要要求。

3.1 環境設定

在編隊重構過程中,空中可能會存在因地形、雷達或防空火炮等形成的障礙或禁飛區[15],它們統稱為威脅區。威脅區的建模不作為本文的研究重點,統一將其近似為規劃空域中的若干圓[13],且不可穿越,用Si表示,其圓心坐標及半徑均采用隨機數的方式獲得,從而得到威脅區的模型如(7)式所示

?i=1,2…,m

(7)

式中,(ai,bi),ri分別表示第i個威脅區的圓心坐標和半徑,m為威脅區的個數。顯然

(8)

在此基礎上,設編隊中飛機屬同構飛機,初始隊形和目標隊形皆已知,各飛機保持勻速飛行,且速度域的區間長度小于15,即速度不作為調節重構時間的主要因素。編隊重構過程的示意圖如圖5所示。其中,m=2,編隊中無人機數v=3。

圖5 編隊重構過程的示意圖

3.2 約束條件

在重構過程中,首先利用改進的RRT算法規劃出長機航跡(設只有一架長機),后將其作為外部威脅輸入到僚機的航跡規劃中,并結合編隊中另外的約束條件生成編隊重構的整體方案。這些約束條件能保證重構過程中航跡變換的可行性,具體如下:

1) 無人機最小轉彎半徑的約束

過渡航跡的構造可以滿足這一約束條件。

2) 最小航跡長度約束

飛機受機動能力的限制,在改變姿態前需要保持一段距離的平飛,將其允許的最小值定義為最小航跡長度,記為lmin。在利用RRT算法對隨機樹進行擴展時,步長L應滿足最小航跡長度約束如(9)式所示

L≥lmin

(9)

3) 目標隊形的幾何約束

針對設定任務的需要,各無人機到達目標隊形時,位置應滿足一定的幾何約束關系,即形成特定的編隊隊形。其中,梯行隊形常用于攻擊;“長龍”隊形常用于轟炸、偵察、空投以及夜間截擊;“一”字隊形常用于寬大正面搜索;菱形隊形常用于摧毀點、線狀目標[16]。

4) 僚機節點擴展的約束

為保證長機在長-僚模式下的絕對領導,也為降低同時求解多機航跡的難度,首先利用改進的RRT算法求解出長機的航跡,并以此為基礎擴展僚機的節點,具體通過降低近似時間段內采樣點重合度的方式進行調節。

(10)

(11)

式中,xr為Zrand的橫坐標;n0為x方向的單位向量。求解方程可得lx,并根據已知的長機航跡得到此時長機的位置(lx,ly)。當xI-xG≈0或xI-xG?yI-yG時,可先求長機的縱坐標ly,其原理與(11)式類似。

利用僚機節點擴展的約束可以降低僚機與長機碰撞的可能,為下文所提的防碰撞約束打下基礎。

5) 編隊重構的時序約束

根據任務需求的不同,編隊完成重構的時序要求也不同,具體包含同時到達、等間隔順次到達和非等間隔順次到達等。其中,同時到達新的隊形有助于編隊實施下一個作戰任務,充分發揮協同作戰的優勢[20]。下面以同時到達為時序約束進行分析。

(12)

若保證同時到達,則僚機的路徑長度應保證t在其到達時間的區間的交集內,具體約束見(13)式

(13)

等間隔順次到達和非等間隔順次到達等時序約束與上述過程類似。

6) 編隊內部的防碰撞約束

為防止編隊內部的碰撞,應檢測飛行過程中各時刻的機間距。具體來講,假設在修正后的航跡上每隔步長Δn進行一次采樣,長機、僚機的采樣個數依次記為n1、n2…nv;同理,時刻T下的采樣點坐標記為[xi(T),yi(T)](i=1,2,…v)。由此可計算采樣點的比例系數kij

?i、j=1,2,…v且i≠j

(14)

則τ時刻各無人機間距|dij|τ可由(15)式得

|dij|τ=

?i，j=1,2,…v且i≠j,0<τ≤t

(15)

式中,[ ]代表取整運算,則此時約束條件可表示為:

|dij|τ>dmin

(16)

7) 編隊外部的防碰撞約束

以3.1節威脅區模型為基礎,在重構過程中,每架飛機的位置到威脅區中心(aj,bj)的距離都應滿足下式

[xi(T)-aj]2+[yi(T)-bj]2≥(λ*rj)2,

?j=1,2…,m,1≤i≤v,0

(17)

式中,λ為安全系數,通常取λ=1.2～1.5。

4 仿真與試驗驗證

4.1 編隊重構試驗

已知編隊重構的規劃空間可以表示為集合{(x,y)|0≤x≤1 000,0≤y≤1 000},1架長機和2架僚機構成編隊。初始隊形構成“一”字型,用于橫向搜索,長、僚機坐標分別為

[p1-int,p2-int,p3-int]T=

[(100,0),(0,0),(200,0)]T

在飛行過程中,3架飛機允許的空速范圍為20～25 m/s,且受風的影響很小(可忽略不計),最大航跡滾轉角為μmax=0.6 rad。設規劃空間內存在三處隨機生成的威脅區,表示為obsi=(ai,bi,ri)。現要求編隊由原隊形迅速變換成“長龍”隊形,以進入備戰狀態,且各飛機同時抵達,忽略飛機進入目標隊形時航向嚴格一致的約束,目標點具體坐標為

[p1-goal,p2-goal,p3-goal]T=

[(800,500),(800,400),(800,600)]T

其中隨機生成的威脅區為

[obs1,obs2,obs3]T=

[(300,150,30),(500,300,45),(700,350,70)]T

以上述條件為基礎,從飛行安全角度出發,取dmin=40 m,檢測步長Δn=0.1 m,最小航跡段長度lmin=15 m,由公式(9)及文獻[21]可確定此時節點擴展步長L=20 m較為合理;另外,外部防碰撞系數λ=1.2,最小轉彎半徑由(3)式求得Rmin≈120 m;根據參考文獻[9]及多次試驗室仿真發現,RRT算法中節點采樣的概率取經驗值P=0.5較為合理。

在MATLAB R2013a中進行仿真,計算機配置為:Intel酷睿i7處理器,主頻3.60 GHz,內存32 G,64位win7操作系統。

下面首先從重構方法的可行性及無人機的安全2個方面對本文所提重構方法的結果進行分析,具體見表1。

表1 RRT算法求解的編隊重構方案

從表1可以看出,3架飛機的規劃速度均在設定范圍內,并且在重構指令下達后的38.38 s同時到達新的隊形位置,滿足所要求的時序約束,實現了編隊重構。圖6展示了重構過程的航跡圖,從圖中看出,多余節點的去除,使得規劃航跡大大縮短,并且裁剪后的航跡均滿足過渡航跡存在的條件,通過過渡航跡引導,使得航跡平滑連續,為航跡的跟蹤提供了有利保障。

下面分析重構過程的安全性。圖7展示了重構過程中機間距的變化,結合圖6和圖7可以看出,利用RRT算法所規劃的航跡與外部威脅區沒有相交,滿足與外部威脅之間無碰撞的約束;同時,雖然各飛機的航跡有些重合,但是經過空間內同一位置的時間并不一致,3架飛機在同一時刻的間距始終在40 m以上,滿足機間安全距離的約束,沒有內部碰撞的危險,利于無人機的安全飛行。

圖6 RRT算法規劃的航跡

接下來,為驗證本文所提重構方法的優勢,在相同仿真條件下,采用文獻[6]中提出的改進的粒子群算法以及最優控制理論中常用的偽譜法[24]等2種方法進行對比試驗,其中粒子群算法的參數與文獻[6]保持一致,而偽譜法則基于GPOPS-Ⅱ工具包實現。2種方法所規劃的重構方案如圖8～9所示。

圖7 編隊重構中的飛機間距圖 圖8 粒子群算法規劃的航跡 圖9 偽譜法規劃的航跡

從試驗結果可以看出,粒子群算法和偽譜法均能實現同等約束條件下的編隊隊形重構,且航跡較為光滑,利于無人機實現航跡跟蹤,具備一定的可行性。下面通過具體的試驗數據(見表2),對比3種重構方法。

表2 3種編隊重構方法對比

表2中數據均為各算法運行50次后所取得平均值。從表中可以看出偽譜法計算的到達時間最小(37.13 s),即求解精度最高,但耗時最長(34.83 s),計算效率較低;RRT算法的精度比偽譜法低,高于粒子群算法,但計算時間分別是二者的7.1%和12.1%;而粒子群算法因需要不斷調整Dubins軌跡弧線段的半徑而導致搜索效率降低,同時由于航跡構成的特殊性,其重構方案中的各機航跡最長,相應的到達時間也最長;另外三者的最小機間距均在40 m以上,最小障礙物間距均大于0 m,即滿足重構過程中的安全性。

綜上,本文所提的基于RRT算法的重構方法可以較好地滿足編隊飛行的安全需求,且更適用于對求解效率要求較高的場景,同時求解精度較高,對實際工程有一定的指導性。

4.2 過渡航跡的效果驗證

針對本文對傳統RRT算法所做改進,利用文獻[19]所述的引導長度自適應的航跡跟蹤算法進行試驗,主要考察過渡航跡的跟蹤效果。試驗用無人機如圖10所示。其翼展2.4 m,機身長度1.6 m,起飛重量6.4 kg,動力來源于電機驅動的螺旋槳。飛機為常規式布局,翼型較厚,適宜低速飛行。

圖10 試驗用無人機

試驗前,由4個預設的航路點圍成一個邊長為500 m、鄰角為0.75π rad(0.25π rad)的菱形,并將其作為規劃航跡,其中4個航路點自西南角開始,逆時針依次記為A、B、C、D,用來模擬RRT算法中生成的節點。

飛行試驗時,有大約3 m/s的偏南風,設定期望空速恒為15 m/s,允許最大航跡滾轉角μmax=0.6 rad,相應的最小轉彎半徑Rmin≈50 m,為安全起見,實際飛行時取Rmin=70 m,其他試驗參數與文獻[19]保持一致。

試驗共進行2個架次,在每個架次中,待飛行高度達到約120 m上空時,地面站引導無人機逆時針依次經過A～D航路點,完成一圈飛行后引導無人機下降并對其進行捕網回收。其中,第一個架次不加過渡航跡,利用跟蹤算法中引導線變化自行轉彎,第二個架次加入過渡航跡引導,令無人機跟蹤過渡航跡完成轉彎。飛行結束后保存并記錄試驗數據,截取以航路點A為起點到飛機開始下降的一段數據進行分析,得到航跡跟蹤圖如圖11所示:

圖11 有無過渡航跡引導的航跡跟蹤對比圖

從圖11可以看出,未加過渡航跡進行引導飛行時,雖然在拐鈍角彎時(如經過B航路點時)能保持較好的跟蹤精度,但在拐銳角彎(如經過C航路點時)則會出現十分明顯的振蕩現象;加入過渡航跡引導時,雖然受偏南風影響會在經過C航路點時出現一定的飛行誤差,但總體而言,能實現較為平穩的轉彎,不需要在直線飛行段進行長時間姿態調節,跟蹤精度更高。

飛機航跡滾轉角的變化情況,是衡量飛行穩定性的一個重要指標,截取由BC段向CD段轉彎時航跡滾轉角的變化進行分析,如圖12所示。圖12中,未加過渡航跡的μ值相比過渡航跡的μ值變化更遲(滯后大約10 s),且調節時間更長(過渡航跡只用了13 s完成轉彎,而無過渡航跡時持續了約25 s),甚至持續到節點C時仍未調整平穩。另外,由于按過渡航跡飛行時,設定的轉彎半徑略大于無人機實際所允許的Rmin,因此其在轉彎段的μ值并沒有長時間維持在μmax,而未加過渡航跡引導時,飛機則長時間處于μmax下飛行,這也從另一個角度驗證了1.3節關于轉彎段產生振蕩原因的假設。

圖12 有無過渡航跡引導的航跡滾轉角對比圖

綜上,過渡航跡利于飛機平穩的跟蹤,適用于解決諸如RRT算法生成的多節點機動轉彎的問題,能為飛行安全提供有效保障。

5 結 論

本文基于快速隨機樹算法,對二維平面內多無人機編隊的重構問題進行了研究。分析和試驗的結果表明:

1) RRT算法具有搜索范圍廣、效率高的特點,適用于解決包含威脅區和動力學約束條件的運動規劃問題,以此為基礎可以拓展到多無人機編隊的重構方法當中。

2) 通過多余節點去除、過渡航跡生成等修正策略,提高了RRT算法所規劃航跡的可跟蹤性。其中,過渡航跡的引入能避免因轉彎時滯而造成的期望轉彎轉彎半徑與無人機最小轉彎半徑不匹配的問題,相比非過渡航跡有較為明顯的優勢。

3) 所提的編隊重構方法以無人機自身動力學、編隊協同以及防碰撞等約束為基礎,結合RRT算法可實現諸如同時到達等時序要求的編隊重構,且方案安全可行。

4) 通過與粒子群及偽譜法等重構方法對比,所提重構方法在安全性的前提下具有較高的計算效率和求解精度。將提出的重構方法利用飛行試驗進行驗證并拓展到三維復雜環境中、優化重構完成的時間以及提高動態威脅下在線重構能力,是下一步值得研究的內容。