一種用于航跡規劃的網絡圖構造方法研究*

周志鵬，周成平，趙慶璐

(華中科技大學，武漢 430074)

0 引言

隨著現代防空體系的越來越完善，越來越多的先進防空武器系統被應用到實戰之中，單個導彈已經不能單獨的完成摧毀敵方目標的任務，更多的時候需要不同的發射平臺發射多枚導彈進行協同攻擊，以提高導彈的突防概率，多任務的協同航跡規劃是當今也將是未來比較熱門的研究方向[2]。無人飛行器種類繁多，不同種類無人飛行器的航跡規劃問題模型不同，規劃難度也有顯著差異。文中提出的方法主要針對巡航導彈這一類無人飛行器，該類無人飛行器的問題模型的一個重要特征是具有輔助制導約束，規劃環境復雜。

對于巡航導彈多任務協同規劃方法的研究已經存在很多，他們雖然使用的算法各異，但共同點是均基于柵格圖規劃環境，且各種協同規劃方法均難以在短時間內規劃出結果。通過對多任務協同規劃系統的分析發現，單任務的可行航跡生成速度是影響整個多任務協同規劃系統規劃速度的一個十分重要的因素。如此，縮短多任務協同規劃系統的規劃時間的目的可以通過縮短單任務生成可行航跡過程的時間來實現。基于柵格圖環境的單任務航跡規劃方法研究已經十分的成熟，但是由于柵格圖的特性所決定，絕大多數的算法在柵格圖上的規劃速度均難以有所突破。鑒于此，文中提高單任務規劃速度的思路是將柵格圖環境稀疏為航跡網絡圖環境，如此一來，單任務規劃的搜索空間將大大減少，速度也必然得到提升。

1 巡航導彈圖規劃空間構造方法

1.1 多任務規劃系統簡介

多任務規劃系統整體流程圖見圖1。

一般地，從戰術的角度看，多任務規劃系統可分為任務分配(或攻擊計劃)子系統、多航跡協同規劃子系統、效能評估子系統3個部分(圖1)。

文中的研究重點在于航跡規劃技術領域。基于進化算法的多任務協同規劃系統的流程一般為:為每個任務生成可行航跡，檢查協同代價，若不滿足要求則再次為某一個或全部任務生成新的可行航跡，重新協同，直到滿足協同要求為止。可見單任務的航跡規劃是多任務協同規劃系統的關鍵技術之一，多任務協同規劃系統中的航跡規劃的部分與單任務航跡規劃系統中的航跡規劃部分相比，所使用的技術相同，但目標有差異，且運行次數也不相同。單任務系統一般只專注于代價最優或較優，對得到的可行航跡的數量或有要求，但不強制，協同規劃系統中，航跡規劃模塊在保證航跡較優的情況下，必須具備生成多組可行解的能力，相應地，在協同代價的評價體系中，單任務的最優解不是該系統所主要關注。單任務規劃系統中，每規劃一個任務，航跡規劃部分一般只需執行一次即可，而在協同航跡規劃系統中，規劃N個任務，每個任務需產生M個解，航跡規劃部分則需執行N*M次。總體來說，協同規劃的單任務規劃方面由于需要多次重復調用，所以必須滿足以下兩個要求，第一，可給出一組互異可行解，第二，時間越短越好[4-8]。

當前對于存在輔助制導約束的巡航導彈的多任務協同規劃技術研究仍主要基于柵格圖規劃環境，盡管他們使用的算法種類有很多，但是由柵格圖規劃環境的特性所決定，這些方法在規劃時間上均難以達到令人滿意的程度。相比之下，已經在無人機航跡規劃中廣泛應用的 Voronoi圖方法[9-10]和航跡片段法[11]能夠在很短的時間內規劃出航跡，相同條件下，圖規劃環境較之柵格圖規劃環境的規劃速度快的原因有二:一是圖規劃環境是解空間的稀疏化，搜索空間相應減少;二是在構建圖規劃環境的過程中，已經將構建航跡所必須的一些計算工作完成，在規劃時只需進行少量工作就可以快速組建航跡。但是目前為止還沒有一種可以適用于巡航導彈問題模型的圖規劃環境構建方法，文中在前人研究的基礎上提出了一種解決該問題方案。

圖1 多任務規劃系統

1.2 有向航跡網絡圖

文中所提出的方法主要是用于解決存在輔助制導約束的巡航導彈航跡規劃問題。輔助制導約束是指航跡中每隔一定距離范圍內必須設置一個輔助制導點，用于糾正由于慣導導航帶來的飛行誤差。輔助制導方式一般為地形匹配或景象匹配，這種輔助制導點的分布完全取決于規劃環境，且實際情況下分布并不十分豐富，沒有辦法使用先規劃航跡再添加輔助制導點的方法，必須在規劃中對該約束條件進行處理。基于上述描述，如果要為該問題模型生成圖規劃環境，則輔助制導點必須作為圖中的擴展結點。最直接的擴展方式是使用樹的擴展，且規劃時回溯路徑不再需要任何規劃算法。但是該方法的局限性在于，樹的規模隨擴展的深度的增加呈指數級增長，使用該方法所能解決的規劃環境規模十分有限。文中采用圖結構，圖規模與規劃環境的面積成線性關系，有很好的可擴展性。

生成圖規劃環境的第二個問題是通過結點方向問題。在任務未定的條件下，通過一個節點在任意方向是等可能的。兩個相鄰結點間的連接若均考慮全方向的情況下必然產生組合爆炸。對于該問題，文中提出的解決方案是將規劃環境網格化，為每個網格選擇一個輔助制導點作為該網格的代表點，該點即為網絡圖上的擴展節點。然后以一個網格作為擴展起點向外擴展，生成覆蓋整個區域的網絡。這樣的一張網絡覆蓋了以起點網格為發射點的所有任務的解空間，而且合理的削減了結點角度的選擇范圍。如果以每一個網格為起點均生成這樣的一張網絡，則可覆蓋整個規劃環境的解空間。

生成圖規劃環境的第三個問題是通過同一結點的航跡段的方向問題，經過同一結點的兩個航跡段，必須滿足一個航跡段的進入該節點方向，與另一個航跡段離開該節點方向相同才可以成功拼接。所以經過每一個結點只能有一個角度，且航跡段必須分為進入段與離開段，即生成圖上的邊是有向的。航跡網絡上的邊必須有向的另外一個原因是巡航導彈實際飛行中的飛行管道問題，巡航導彈的飛行管道隨著飛行距離的增加而增加，同樣一段航跡以相對的方向飛行所覆蓋的飛行管道是不同的，所以文中航跡網絡的有向性不僅體現在經過一個節點的航跡段被分為進入段與離開段，而且進入段與離開段是固定的且不能相互轉化。即這樣的一張網絡僅可以用來規劃以該網絡起點為發射點，以某一點為目標點的航跡，反之，若以該起點為目標點，則不能規劃。

巡航導彈一般均為三維規劃，即二維平面規劃加高度規劃，基于文中提出的航跡網絡的結構，對于高度規劃擬采用對整個規劃環境生成一個最低飛行曲面的方法，在網絡生成時只需保證航跡段的高度在該曲面以上即可，此種方法的弊端十分明顯，規劃出的航跡的平均高度會增高。但文中的目的主要在于驗證將柵格圖環境轉化為圖環境的方法的可行性，高度規劃暫不是研究重點。

綜上所述文中方法所構建出來的圖規劃環境是一種有向航跡網絡圖。

1.3 有向航跡網絡圖構建原則

圖2 網絡圖結構

由于以每個網格為起點網絡相互獨立且結構相同，在此對一張網絡的結構進行說明，網絡圖的簡化示意圖如圖2所示。

圖2所示為一個以網格P為起點的部分網絡圖。網絡圖的生成遵循以下4個原則:

圖3 三個角度方向的連接

1)生成網格代表點，將柵格圖規劃環境按一定粒度劃分為網格，為每一個網格尋找一個輔助匹配區點作為其代表點，該代表點盡量靠近網格中心為原則。實際上，地形輔助匹配點與景象輔助匹配點在很多情況下不能夠在全角度上發揮作用，即一個匹配點只在一個角度范圍內通過它時，才能起到輔助匹配的作用，在這個范圍以外通過該點，那么這個點就無法作為一個輔助匹配點。鑒于此種情況，文中給出的一種解決策略是以靠近網格中心為原則尋找一組輔助匹配點可以覆蓋360°全部范圍，將這一組點作為網格代表點。在給定起點的條件下，選擇n個角度作為通過該網格的角度通道(參見第4條，文中n=3)，在這一組網格代表點中，依次找出包含每一個角度的點，在這里，同一個點可以被選擇多次，在第4條中有論述，雖然這樣的一個點的空間位置相同，但是由于角度不同，在網絡圖的結構中它是作為不同的結點存在。

2)擴展標準，在實際應用中，一個節點擴展到它的子節點的擴展步長為輔助制導點間的距離約束條件。在圖2中，為簡化起見，以曼哈頓距離等于2作為標準進行擴展。

3)擴展方向，網絡圖中除起點 P向360°方向擴展，其他所有的點的擴展方向均采用背離起點的原則，此原則即為，過被擴展點做被擴展點與起點連線的垂線，該垂線將規劃環境分成兩部分，擴展時只考察與起點異側部分的點，且不包含垂線上的點。上節所述采用以一個網格為起點擴展一張網絡的方法可以有效的削減結點的角度選擇。在發射點確定的情況下只對前方的結點進行擴展是合理的。

4)經過輔助制導點的角度，起點P無角度限制，其他點均采用固定角度。即上節所述的航跡段對接問題。結合第二步，每一個結點只通過一個角度擴展它前方180°范圍的點顯然會增加邊界航跡的不合理性。在實際生成網絡圖中采用了3個角度通道。如圖3所示，這樣的改進其實是將一個網格結點變為3個位置相同但角度不同的3個擴展結點，所以仍然符合上節提出的經過每一個結點只能有一個角度，且航跡段是有向的原則。理論上，將角度通道增加到n個，則有擴展關系的兩個網格之間至多會有n2條航跡段相連，在綜合考慮生成時間儲存空間及解空間稀疏程度的情況下，文中選擇了3個角度通道來生成網絡。

1.4 可行性分析

基于前兩節的論述，按照此設計思想，將網格粒度縮小至以柵格圖規劃環境的像素為單位，然后不再使用較少的角度通道，而是對全角度進行擴展，那么在兩輔助制導點間連接方法固定的情況下，這樣生成的航跡網絡即為該柵格圖規劃環境的解空間。

鑒于在現有技術條件下，網格劃分到像素級別和以極小粒度的角度覆蓋全方向在處理時間與儲存空間上均難以實現，所以文中的設計思想是對理論上的完美網絡進行簡化，從而與現有的技術條件相吻合。通過前兩節的描述，可以看出簡化包含兩個方面，降分辨率處理(以網格來替代像素)，簡化角度(只選擇若干個角度通道)。

首先討論降分辨率簡化，降分辨率本質上是把網格中的所有點用一個點來代表。這樣做的一個后果就是使得網格中的非代表點的輔助制導點沒有被考察。在邊長為L的正方形內選取一點，正方形內其他點距該點的平均距離最小為:

平均距離最大為:

文中用來測試的模擬柵格圖規劃環境為10°*15°(經緯度)，約 1000km*1500km，分辨率 1″*1″，在處理時間及儲存空間條件允許的情況下，可以將網格邊長尺度縮小至在10km左右，由于代表點的選擇以靠近網格中心為原則，未擴展點與代表點的平均距離可以控制在10km以內，即航跡網絡上的一個航跡段代表的是它的兩個端點為圓心，10km為半徑的兩個圓形區域之間的所有連接。即對一個航跡段的端點在幾公里的范圍內進行一個小擾動，根據實際經驗，擾動后的航跡絕大多數情況下依然可以是可行的。降分辨率可能導致的另外一種情況是在某些本可以存在連接關系的網格對中，由于只選擇兩個代表點，使得兩代表點間的連接超出或小于航跡距離要求而被廢棄。這種邊界情況的出現比例同樣依賴于網格的大小，但在既定網格粒度下，可以使用進化算法來進行兩匹配區點的連接，進化算法連接與幾何連接相比優點在于，幾何連接所得航跡長度固定而進化算法連接的航跡長度擁有彈性，這樣對邊界情況的處理更加合理。

對于角度的簡化，文中對一個網格選擇了3個角度通道方向來擴展該網格前方的180°區域。由于一張網絡圖只為以該網絡圖起點為發射點的任務提供解集，所以不考慮極端條件下，經過非起點的網格的航跡的角度均在指向網格前方180°范圍內，在選擇了3個角度通道來代表180°區間的情況下，不采用網絡圖方法經過該點所使用的角度與固定角度通道的差值最多有20°，根據以往航跡規劃的經驗，認為這個角度差異是不會嚴重影響連接成功率的。

2 實驗結果

文中利用一套模擬的規劃環境對上述方法進行了實驗驗證，初始規劃環境為柵格圖環境，大小為36000*54000，分辨率為經緯度 1″*1″。硬件環境為商用PC機，處理器Intel E7200，內存2G，硬盤250G。

選擇了兩種網格尺度，分別為1000*1000和500*500(像素)，根據分辨率可知網格的實際距離尺度大約為30km和15km。按上文所述，為每一個網格尋找一個匹配區結點作為該網格代表點，但存在一部分網格不包含匹配區點，鑒于巡航導彈的規劃中存在這樣一種情況，即優先考慮地形或景像匹配，將GPS輔助導航方式作為補充。所以在這些網格中選取一個GPS輔助導航點作為其代表點。

兩種網格尺度下生成一張網絡圖的情況如下:

由此可見，生成的航跡數量非常多，圖4僅顯示部分網絡的示意圖

圖4 航跡網絡圖

圖4為1000*1000網格尺度下所生成的部分航跡網絡，該尺度下規劃環境被分為36*54個網格，如圖截取的區域僅有12*7大小。如圖4所示，P點為網絡起點，在P點的眾多子節點中只選擇了A1顯示，在A1的子節點中也只選擇了 B1、B2、B3進行顯示。網絡圖的效果與文中的預期完全一致。

為驗證在該航跡網絡上的規劃效率，文中在該網絡上實現了蟻群算法的單任務規劃，蟻群算法屬于進化算法，可以給出多個可行解，十分符合協同規劃的需求。鑒于協同規劃還需另行考慮其他許多因素，因此文中并未實現協同規劃模塊。本實驗的目的是要證明在該航跡網絡圖上，單任務規劃的時間得到極大提高，進而必然將降低協同規劃的規劃時間。

蟻群算法的參數選擇對規劃結果的影響十分明顯，其中螞蟻數目與進化代數的參數選擇，分別采用螞蟻數目與任務長度線性相關，進化代數固定為100代。

對不同任務的規劃結果如下:

任務 任務長螞蟻數量 可行航規劃度/km 跡數量 用時/s任務1 468.18 103 101 3任務2 773.48 170 170 7任務3 1616.97 355 355 34

航跡規劃結果截圖如圖5只為每一個任務顯示了最優的10條航跡。

圖5 規劃結果

可以看出使用航跡網絡的方法能夠在短時間內得到大量可行解。但是因為其基于網絡圖的特點，不同的航跡會公用部分航跡段，而從圖中總體來看，航跡的多樣性還是十分飽滿的。

3 總結

文中對存在輔助制導約束的巡航導彈航跡規劃問題提出了一種將柵格圖規劃環境轉化為圖規劃環境的方法。該方法的優勢在于可以很快得出多組可行航跡，適合大批量的任務規劃，尤其適用于多任務協同規劃;該方法作為針對一類問題模型所提出的解決方法，可適用于多種武器系統，這在實際應用中有著重要的意義。該方法的不足之處在于若只進行少量的任務規劃，使用該方法則費效比較高;生成數據量較大，需要對數據有高效的管理方法。

綜上所述，在經過簡化從而適應目前技術水平的情況下，還是可以看到此種方法可以得出令人滿意的結果。可以在短時間內規劃出大量的可行航跡，且航跡的多樣性比較令人滿意。而且可以預見，隨著硬件技術的進步，該方法的性能也必將越來越高。

[1]丁明躍，鄭昌文，周成平，等.無人飛行器航跡規劃[M].北京:電子工業出版社，2009.

[2]黃賽超，劉順利，姚弘毅.從四次局部戰爭看美軍巡航導彈的使用及發展[J].飛航導彈，2007(7):19－21.

[3]任敏，吳昊，沈林成.巡航導彈的任務模式和規劃需求[J].飛航導彈，2009(1):29－32.

[4]張志勇，畢義明，鄭重.巡航導彈協同作戰任務規劃需求[J].飛航導彈，2012(6):32－36.

[5]鄭昌文，丁明躍，周成平，等.多飛行器協調航跡規劃方法[J].宇航學報，2003，24(2):115－120.

[6]史戰偉，周成平，丁明躍，等.基于進化計算的多無人飛行器協同航跡規劃[J].戰術導彈技術，2007(5):49－53.

[7]劉宇坤，謝軍.基于 K路徑算法的多無人機協同航跡規劃[J].微計算機信息，2008，24(8－3):208－209.

[8]葉媛媛，閔春平.多無人機協同航路規劃的共同進化方法[J].計算機仿真，2007，24(5):37－39.

[9]Chandler P，Rasumussen S，Pachter M.UAV cooperative path planning[C]//Proceedings of AIAA Guidance，Navigation，and Control Conference，2000.

[10]McLain T W，Beard R W.Trajectory planning for coordinated rendezvous of unmanned air vehicles[C]//Proceedings of the AIAA Guidance，Navigation，and Control Conference，2000.

[11]Li Shidong，Ding Mingyue，Cai Chao.A novel path planning method based on path network[C]//Proceedings of the SPIE 6th International Symposium on Multipectral Image Processing and Pattern Recognition，2009.