基于航跡片段樹的快速四維航跡規劃方法

張險峰

(北京航空航天大學 宇航學院，北京100191)

周其忠 王長青

(北京機電工程研究所，北京100074)

隨著信息化的發展，時間因素在現代戰爭飛行器使用中的影響越來越突出.這不僅要求能快速完成飛行器的航跡規劃，還希望在無人飛行器作戰使用時，能在比較充裕的發射時間段內發射，且還能按指定時間到達目標.在無人飛行器本身具備一定時間控制能力情況下，時間作為一個不可忽視的因素，開始受到人們的關注和重視.2008年，趙明元［1］等基于啟發式A*算法提出了一種四維實時航跡規劃方法，通過在飛行過程中實時調整推力以解決準時到達目標的問題.2009年，嚴江江［2］等提出了一種基于進化算法的多飛行器四維航跡規劃方法，通過在三維航跡規劃的基礎上加入時間代價約束，完成多個無人飛行器能夠同時到達并避免飛行過程中的相互碰撞.2011年，傅陽光［3］等也提出了一種基于進化算法的航跡規劃方法，并對發射時間誤差、飛行器速度調整能力及飛行速度誤差3個因素對飛行器到達目標點時間誤差的影響展開了研究.

盡管這些文獻都考慮了時間維，但文獻［1］主要研究了飛行器沿指定航跡飛行過程中的在線四維航跡調整，未考慮組合導航對地形、景象的要求，且不適于平時規劃，文獻［2］采用整個航程內的平均速度來計算飛行時間，同時沒有考慮起飛時間誤差以及飛行速度本身因控制以及外部環境產生的時間誤差，文獻［3］雖然考慮因素全面，但存在規劃結果不確定，且時間長的不足.這均與無人飛行器快速作戰使用需求有一定的差距.

本文首次提出航跡片段樹的概念，以預先指定的起飛區域/點(實際情況下，這些信息是明確的)為根節點，利用改進的稀疏A*算法，在考慮飛行器組合導航、時間調整以及各種機動性能約束的前提下，生成覆蓋整個規劃區范圍的立體空間航跡片段樹.對于任意指定的目標點，均可以通過在該樹中尋找最優葉節點，并通過回溯以及速度優化設置，快速完成四維航跡規劃.

1 問題描述及假設

為達到預期目的，往往對飛行器到達指定地點的時間有嚴格要求.一般情況下，航跡規劃給出的航跡只給出了理論飛行時間，而在實際使用時，無人飛行器的實際起飛時間將與預期要求有一定的誤差，并且無人飛行器在飛行過程中因風向、風力等氣象因素，以及飛行器本身的控制誤差影響，使得實際到達指定地點的時間有較大誤差.

為解決該問題，現代的無人飛行器具備了速度自主調整能力:即在飛行過程中，能根據當前飛行時間以及預期時間的差值，在一定的速度范圍內進行速度的自主調整，使得盡可能消除當前飛行時間誤差，對于消除之后剩余的時間誤差，將由下一個航段消除.依次類推，直至按指定時間到達指定地點.

為便于后續討論方便，本文作如下假設:

1)起飛區域預先指定;

2)起飛時間偏差dT:是指起飛時間與預期起飛時間的偏差，可提前也可推遲，一般為數分鐘;

3)飛行速度誤差dV:無人飛行器飛行過程中因風等氣象環境以及飛行器本身控制等因素所造成的綜合速度誤差;

4)速度調整能力kV:無人飛行器在飛行過程中速度自主調整能力范圍，本文假設只能在平直飛行狀態下才能進行速度自主調整，且可在整個速度包線范圍［Vmin，Vmax］內進行調整;

5)速度調整策略:在飛行過程中，無人飛行器在當前航段飛行過程中盡可能多的消除進入該段之前的累計時間誤差.

無人飛行器的其他相關約束如下:

1)飛行高度約束.在規劃過程中需考慮無人飛行器的最大飛行高度限制、最小安全飛行高度以及在空中管制區域的飛行高度限制;

2)飛行速度約束.無人飛行器的飛行速度可在速度包線范圍內進行設置;

3)爬升/下滑速度約束.由于無人飛行器本身性能限制，爬升/下滑的速度是有限的，一般是每秒數十米;

4)轉彎半徑/角度約束.無人飛行器有最小轉彎半徑的限制，并且該最小轉彎半徑隨飛行速度的提高而加大;

5)精確導航要求.從一個航跡片段進入下一個航跡片段時，要保證慣導誤差散布要求;

6)禁飛區限制.航跡片段不能通過禁飛區;

7)航程約束.無人飛行器具有最大飛行航程限制.

2 航跡片段樹表達及航跡回溯

對于長航時飛行器來說，在不使用GPS或沒有GPS信號的情況下，每飛行一段距離后則需要尋找一個地面信標臺或典型地物標識進行導航修正，以避免因導航誤差過大而無法執行后續任務.由于最大導航距離不僅依賴于剛剛經過的信標修正或地物修正的慣導導航精度，而且與下一次修正時刻對導航誤差的容忍程度也密切相關.這種緊密的航跡前后依賴關系造成無法事先確定出最大導航距離參數.如果將該問題留給航跡搜索算法，當搜索到最大導航距離之后仍未找到合適的導航修正手段，搜索算法就必須回退.為避免上述問題，提高搜索效率，提出了基于導航修正點航跡片段樹的搜索算法.

如圖1所示為本文所定義的航跡片段樹示意圖.圖中的每個片段上均有一個信標臺或地物修正點(矩形框所示).在本研究中，航跡片段樹具有如下特點:①相鄰兩個片段之間最多有一個高度變化點或一個轉彎點;②相鄰兩個導航修正點之間的飛行時間滿足最大導航誤差散布的要求;③相鄰兩個航跡片段之間滿足最短距離限制;④每個節點均有唯一標識，并且包含指向其父節點的標識.

圖1 航跡片段樹示意圖

通過該航跡片段樹，可以將整個規劃空間進一步表達為可行航跡空間，航跡規劃時即可直接從該航跡片段樹中進行搜索，避免了在實際規劃空間中的航跡復雜搜索.該航跡片段樹中任意節點到其所擴展葉節點之間代表著是一條可行航跡，因此在指定結束點之后，可根據結束點進入約束尋找最優葉節點，然后通過其父節點標識回溯，直至回溯到根節點，完成航跡的快速規劃.如圖1所示，從起始點S到結束點T之間的航跡就可以通過回溯產生{T，6，2，1，S}.

圖2 航跡片段示意圖

3 基于稀疏A*的航跡片段樹生成

傳統的基于概略圖的方法中，Voronoi圖［4］以及隨機路線圖［5］并不適合對三維復雜環境進行建模.另外，對于無人飛行器來說，其起飛區域相對固定，因此可以考慮以此區域附近一個點作為數的根節點，生成航跡樹.本文采取基于約束的稀疏A*［6］算法，并進行適應性改進，用于航跡片段樹的構建，以滿足四維航跡快速規劃的需要.

3.1 擴展區域計算改進

稀疏A*的擴展區域為一扇形區域，主要與轉彎能力以及組合導航進區要求相關.角度范圍與轉彎角度范圍限制一致，半徑方向有最大長度和最小長度限制.在一般稀疏A*算法中，半徑方向最短長度為前后兩個導航修正點工作距離的半長度之和，最大長度為以當前飛行速度能滿足進入下一個導航修正點慣導誤差散布要求的距離.在這種擴展區域中所搜索的航跡，其可供飛行器進行速度調整的范圍可能受到限制.為解決該問題，本文對最大長度的計算方法進行了改進:用可用速度包線的下限進行最大長度的計算.通過這種改進，使得所規劃航跡的速度可在整個速度包線范圍內進行設置，且滿足進入下一個導航修正點的慣導誤差散布要求.

3.2 代價函數改進

在常規稀疏A*算法中，代價函數由當前點代價和從當前點到目標的預估代價兩項組成.在航跡片段樹構建過程中，并沒有指定目標用以引導算法的搜索，因此在航跡擴展過程中，只考慮當前點的航跡代價，即主要考慮飛行時間誤差消除能力以及航程限制.

如圖2所示航跡片段P1P2中(P1為當前擴展點，P2為擴展后的點)，P2點的代價C2為

其中，l為該段擴展航跡片段的長度;δT為該航跡片段的最大最小飛行時間差;a和b則為相應的權系數.

航跡片段P1P2的最大、最小飛行時間按如下式子計算:

3.3 算法流程

1)初始化SAS算法運行環境.將open，closed表置為空;

2)將起飛區域賦值給節點cur，并把它放入closed表中;

3)根據當前節點cur的位置按起飛區域可用航向范圍及航線約束條件確定下一個導航修正點的搜索方向和可行搜索空間(待擴展區)，計算搜索空間的位置參數;

4)離散待擴展區.以導航修正點間最短距離和最長距離為半徑的圓弧將待擴展區從距離上劃分為M區域.然后每次旋轉θ角度來劃分這M個區域;

5)子區域中搜索導航修正點.

a)角度方向循環;

b)由遠及近以離散后的子區域為單元，以單元中心方向開始往兩側搜索，檢測子區域中是否存在可用的導航修正點;

c)若未搜索到導航修正點，轉b);

d)若搜索到導航修正點，計算當前節點cur到該修正點之間的三維航線:①若該航線滿足約束，則計算該片段的各種參數，并放入open表，并轉a);②否則轉b);

6)open表為空，則轉8);否則從open表中取出第1項(代價最優)，稱為節點cur，并把它放入closed表中;

7)根據當前節點cur的位置及方向按轉彎角度限制及航線約束條件確定下一個導航修正點的搜索方向和可行搜索空間(待擴展區)，計算搜索空間的位置參數;轉4);

8)保存closed表數據，構建航跡片段樹.

4 基于航跡片段樹的四維航跡規劃

在給定起始點和指定任務結束點后，航跡規劃過程可分為任務結束點到臨近葉節點的搜索、航跡樹回溯、速度優化設置3個環節.

根據任務結束點位置以及導航修正點間最大導航距離要求，從航跡片段樹中搜索附近的節點.然后根據起飛時間誤差從中選擇滿足要求的最優節點，并以此節點進行航跡回溯，生成一條完整的航跡.

在航跡搜索完成之后，需對每個航跡片段的速度進行設置.假設第i個航跡段的規劃飛行速度為Vi，需要消除的時間誤差為Ei(包含第i-1段消除之后的時間誤差殘余以及第i-1段本身因各種因素導致的飛行時間誤差，其中在起始點的時間誤差為dT).如圖2所示，根據規劃的速度，飛行時間為

由于所生成的航跡片段滿足整個速度包絡內的速度使用要求，因此Vi可按誤差最大消除考慮，有

無人飛行器完成第i個航跡片段飛行后的時間誤差殘余為

其中

5 仿真試驗

圖3 規劃區范圍及航跡片段樹示意圖

如圖3所示，本文給出了一個4.5°×4°的規劃范圍，空間粒度為1″.圖中底圖為該范圍的高度灰度圖，顏色越淺則代表海拔高度越高，其中橢圓區域表示各種人文、氣象、攔截禁飛區.該圖中給出了航跡片段樹的示意，“黑點”表示該片段上各種屬性的導航修正點，“灰點”表示轉彎控制點，航跡片段為兩個導航修正點之間的折線連線(在特殊情況下也有直線連接).

假設導航修正點之間的最大飛行時間間隔是300 s，無人飛行器飛行速度范圍［200 m/s，300 m/s］，最小轉彎半徑7.5 km，最大轉彎角度±45°，爬升/下滑速度為30 m/s，最大航程1 000 km，飛行速度控制誤差為±2 m/s.

圖4 所示以(118.5°，23.5°)為起點，按速度包線中最慢速度產生的航跡片段樹結果(航跡片段樹節點總數為10 733，導航修正點之間最大距離60 km，最小距離30 km)，以及任務結束點1(115.1，21.5)、任務結束點 2(116.25°，21.1°)以及任務結束點3(119.25°，21.75°)在不同起飛時間誤差情況下的航跡示意圖.其中“小旗”表示起飛位置，“三角”表示任務結束點.

圖4 3個不同任務結束點的航跡規劃結果示意圖

在主頻為2.83 GHz的計算機上，從航跡片段樹(生成航跡片段樹的時間為73min)中搜索航跡并完成速度優化設置的時間均為0.2～0.5 s，這表明本算法可以近實時完成航跡搜索.上述5條航跡的結果對比詳見表1.

表1 航跡結果對比

從表1可以看出:①在無人飛行器飛行速度范圍限定情況下，時間誤差修正能力與航跡總長度有關，即航跡越長越可能消除時間誤差;②由于飛行控制誤差以及其他干擾情況的存在，使得無人飛行器到達指定地點的時間為一個范圍，且最小為從最后一個導航修正點到指定地點之間因控制/氣象因素造成的時間誤差.

6 結束語

為消除起飛時間誤差以及飛行過程中各種干擾對無人飛行器到達指定地點時間的影響，本文提出了一種基于航跡片段樹的快速四維航跡規劃方法.該方法通過對稀疏A*算法的擴展區域計算以及代價函數的設置進行了適應性改進，確保產生的航跡片段自然滿足飛行器的各項約束，并將航跡搜索空間轉換為航跡片段樹;同時提出了航跡回溯以及最優速度設置方法，滿足了能消除飛行器時間誤差的四維航跡快速規劃需求.試驗結果表明，本文提出的方法可以近實時完成四維航跡規劃，所規劃的航跡能滿足按時到達指定地點的要求.

References)

［1］趙明元，周軍.基于A*算法的四維實時航跡規劃算法［J］.火力與指揮控制，2008，33(8):98-111 Zhao Mingyuan，Zhou Jun.Algorithm of 4D real-time path planning based on A*algorithm ［J］.Fire Control and Command Control，2008，33(8):98-111(in Chinese)

［2］嚴江江，丁明躍，周成平.基于進化算法的多飛行器四維航跡規劃方法［J］.系統仿真學報，2009，21(4):1125-1129 Yan Jiangjiang，Ding Mingyue，Zhou Chengping.4D route planning for multi-UAV based on evolutionary algorithm ［J］.Joural of System Simulation，2009，21(4):1125-1129(in Chinese)

［3］傅陽光，周成平，王長青，等.考慮時間約束的無人飛行器航跡規劃［J］.宇航學報，2011，32(4):749-755 Fu Yangguang，Zhou Chengping，Wang Changing，et al.Path planning for UAV considering time constrait［J］.Journal of Astronautics，2011，32(4):749-755(in Chinese)

［4］ Bhattacharya P，Gavrilova M L.Roadmap-based path planning using the Voronoi diagram for a clearance-based shortest path［J］.IEEE Robotics ＆ Automation Magazine，2008，15(2):58-66

［5］ Baumann M A，Dupuis D C，Leonard S，et al.Occlusion-free path planning with a probabilistic roadmap［C］//2008 IEEE/RSJ International Conference on Intelligent Robots and Systems，IROS Nice.France:Inst.of Elec and Elec Eng Computer Society，2008:2151-2156

［6］周其忠.復雜環境下多UCAV協同規劃技術研究［D］.武漢:武漢大學測繪學院，2010 Zhou Qizhong.Research on cooperative planning for multiple UCAVs in complicated environments［D］.Wuhan:School of Geodesy and Geomatics，Wuhan University，2010(in Chinese)