張險峰

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

周其忠 王長青

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

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

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

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

1 問題描述及假設(shè)

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

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

為便于后續(xù)討論方便，本文作如下假設(shè):

1)起飛區(qū)域預(yù)先指定;

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

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

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

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

無人飛行器的其他相關(guān)約束如下:

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

2)飛行速度約束.無人飛行器的飛行速度可在速度包線范圍內(nèi)進(jìn)行設(shè)置;

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

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

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

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

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

2 航跡片段樹表達(dá)及航跡回溯

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

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

圖1 航跡片段樹示意圖

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

圖2 航跡片段示意圖

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

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

3.1 擴(kuò)展區(qū)域計算改進(jìn)

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

3.2 代價函數(shù)改進(jìn)

在常規(guī)稀疏A*算法中，代價函數(shù)由當(dāng)前點(diǎn)代價和從當(dāng)前點(diǎn)到目標(biāo)的預(yù)估代價兩項組成.在航跡片段樹構(gòu)建過程中，并沒有指定目標(biāo)用以引導(dǎo)算法的搜索，因此在航跡擴(kuò)展過程中，只考慮當(dāng)前點(diǎn)的航跡代價，即主要考慮飛行時間誤差消除能力以及航程限制.

如圖2所示航跡片段P1P2中(P1為當(dāng)前擴(kuò)展點(diǎn)，P2為擴(kuò)展后的點(diǎn))，P2點(diǎn)的代價C2為

其中，l為該段擴(kuò)展航跡片段的長度;δT為該航跡片段的最大最小飛行時間差;a和b則為相應(yīng)的權(quán)系數(shù).

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

3.3 算法流程

1)初始化SAS算法運(yùn)行環(huán)境.將open，closed表置為空;

2)將起飛區(qū)域賦值給節(jié)點(diǎn)cur，并把它放入closed表中;

3)根據(jù)當(dāng)前節(jié)點(diǎn)cur的位置按起飛區(qū)域可用航向范圍及航線約束條件確定下一個導(dǎo)航修正點(diǎn)的搜索方向和可行搜索空間(待擴(kuò)展區(qū))，計算搜索空間的位置參數(shù);

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

5)子區(qū)域中搜索導(dǎo)航修正點(diǎn).

a)角度方向循環(huán);

b)由遠(yuǎn)及近以離散后的子區(qū)域為單元，以單元中心方向開始往兩側(cè)搜索，檢測子區(qū)域中是否存在可用的導(dǎo)航修正點(diǎn);

c)若未搜索到導(dǎo)航修正點(diǎn)，轉(zhuǎn)b);

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

6)open表為空，則轉(zhuǎn)8);否則從open表中取出第1項(代價最優(yōu))，稱為節(jié)點(diǎn)cur，并把它放入closed表中;

7)根據(jù)當(dāng)前節(jié)點(diǎn)cur的位置及方向按轉(zhuǎn)彎角度限制及航線約束條件確定下一個導(dǎo)航修正點(diǎn)的搜索方向和可行搜索空間(待擴(kuò)展區(qū))，計算搜索空間的位置參數(shù);轉(zhuǎn)4);

8)保存closed表數(shù)據(jù)，構(gòu)建航跡片段樹.

4 基于航跡片段樹的四維航跡規(guī)劃

在給定起始點(diǎn)和指定任務(wù)結(jié)束點(diǎn)后，航跡規(guī)劃過程可分為任務(wù)結(jié)束點(diǎn)到臨近葉節(jié)點(diǎn)的搜索、航跡樹回溯、速度優(yōu)化設(shè)置3個環(huán)節(jié).

根據(jù)任務(wù)結(jié)束點(diǎn)位置以及導(dǎo)航修正點(diǎn)間最大導(dǎo)航距離要求，從航跡片段樹中搜索附近的節(jié)點(diǎn).然后根據(jù)起飛時間誤差從中選擇滿足要求的最優(yōu)節(jié)點(diǎn)，并以此節(jié)點(diǎn)進(jìn)行航跡回溯，生成一條完整的航跡.

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

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

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

其中

5 仿真試驗

圖3 規(guī)劃區(qū)范圍及航跡片段樹示意圖

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

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

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

圖4 3個不同任務(wù)結(jié)束點(diǎn)的航跡規(guī)劃結(jié)果示意圖

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

表1 航跡結(jié)果對比

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

6 結(jié)束語

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

References)

［1］趙明元，周軍.基于A*算法的四維實時航跡規(guī)劃算法［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］嚴(yán)江江，丁明躍，周成平.基于進(jìn)化算法的多飛行器四維航跡規(guī)劃方法［J］.系統(tǒng)仿真學(xué)報，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］傅陽光，周成平，王長青，等.考慮時間約束的無人飛行器航跡規(guī)劃［J］.宇航學(xué)報，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］周其忠.復(fù)雜環(huán)境下多UCAV協(xié)同規(guī)劃技術(shù)研究［D］.武漢:武漢大學(xué)測繪學(xué)院，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)