一種航跡網絡圖粒子群優化生成方法＊

黃自強 蔡 超 孫希霞

（華中科技大學自動化學院多譜信息處理技術國防科技重點實驗室 武漢 430074）

1 引言

飛行器航跡規劃是在綜合考慮飛行器到達時間、燃料消耗、威脅以及特定飛行區域等因素的前提下，為飛行器規劃出一條最優，或者是較滿意的飛行航跡，以保證圓滿完成飛行任務［1］。在現代戰爭中，由于戰場環境的動態變化以及任務的不確定性，飛行器的航跡規劃空間往往非常大，規劃算法非常耗時，無法滿足在線實時規劃的要求。有研究者根據高速公路網規劃的思想，提出了基于網絡圖的分階段航跡規劃方法［2～6］。第一步，在預處理階段構造滿足一系列約束條件的航跡片段，這些航跡片段構成網絡圖。第二步，給定規劃任務，利用網絡圖搜索出一條從指定發射點到目標點的航跡。這樣路徑規劃問題被轉化為一個網絡圖的搜索問題。這種方法大幅縮減了航跡規劃過程的搜索量，從而加快了規劃速度，能滿足在線實時規劃的要求。類似的方法還有通視圖法、隨機路線圖法等［7～11］。通視圖是由規劃空間中的障礙物的相互可見的頂點間的連線構成。通視圖可用于求解二維規劃空間中的最短路徑問題，盡管它可用于高維規劃空間，但此時生成的路徑將不再是最短的。另外，通視圖不能表達物體運動的方向性約束，這樣使得生成網絡圖可行解較少。隨機路線圖法是一種針對多自由度問題的路徑規劃方法。該方法在規劃空間中隨機進行采樣生成路線圖，然后在該路線圖中搜索路徑。該方法的優點之一就是可以在規劃時間和路徑的質量之間進行權衡，構造隨機路線圖的時間越長，得到最優路徑的可能性就越大。在確定環境下，隨機路線圖一般可以事先構造。

已有的航跡網絡圖生成方法并沒有考慮網絡圖的最優性，包括：1）空間覆蓋能力；2）網絡圖總體代價最優性；3）重組航跡的最優性等。

本文利用粒子群優化算法優化網絡圖節點的分布，使航跡網絡圖整體代價較優，重組航跡也較優。

2 航跡網絡圖及其優化問題

航跡網絡圖是由網絡節點和節點間的航跡片段構成如圖1所示。航跡網絡圖的構建過程，首先是對規劃空間進行等網格劃分，將規劃空間劃分為一個個相互毗鄰的網格。多個較小的網格又可以形成一個較大的網格，這樣實現了多尺度網格的劃分。在每個網格內，在匹配區內隨機選取節點。然后根據飛行器飛行約束、環境約束等約束條件進行節點間的航跡片段規劃。其規劃結果就構成了一幅初始的航跡網絡圖。航跡網絡圖可以表示為G＝（V，E），其中V為圖中節點的集合，E為航跡片段（圖G中的邊）的集合，節點具有八個飛行方向（由匹配區導航點的性質決定），空間位置由坐標（x，y，z）表示。

圖1 網絡節點及小尺度航跡片段

航跡網絡圖主要受規劃空間、網格大小、節點分布以及航跡片段生成算法等因素的影響。在規劃空間、網格大小和航跡片段生成算法都已確定的情況下，節點位置的改變會造成航跡網絡圖空間分布的較大改變，相應的航跡網絡總體代價也會有較大的改變。這里，我們用航跡網絡圖中所有航跡片段代價的和來表示網絡圖的總體代價，航跡片段的代價考慮航跡長度、高度、轉彎次數、威脅等因素。

航跡網絡圖的優化，除了考慮網絡圖的代價因素外，還要考慮網絡的密集程度，規劃空間的覆蓋能力，分布均勻性等。

網格的劃分決定了航跡網絡的密集程度。航跡片段規劃算法采用A＊搜索算法，在滿足給定約束條件的情況下，A＊算法能夠規劃出節點間的最小代價航跡片段。改變航跡網絡節點位置，將影響航跡片段經過的空間位置及代價大小，相應地改變航跡網絡的總體代價和空間覆蓋能力。

結合上述分析，本文設計出一種通過求解航跡網絡節點最優分布進而獲得最優航跡網絡的優化方法。

3 基于粒子群算法的網絡圖優化

3.1 粒子群算法原理

粒子群算法是基于群體的演化算法，其思想來源是人工生命和演化計算理論。由于其簡單、有效的特點，可以用于復雜高維問題的求解，已得到眾多學者的重視［7］。在粒子群算法中，每個粒子在搜索空間中的位置代表了所求問題的一個解。每個粒子還有一個速度，來決定它們移動的方向和位置。每個粒子通過優化函數決定了它當前的適應值。粒子群算法初始化為一群隨機的粒子，然后通過迭代找到最優解，在每一次迭代中，粒子通過兩個“極值”來更新自己的位置和速度。其中，第一個“極值”是粒子本身所找到的最好解（個體極值pbest）；另一個“極值”是整個種群目前所找到的最好的解（全局極值點gbest）［12～15］。粒子更新位置和速度的公式如下：

其中，是粒子i在第k次迭代中第d維的速度。C1、C2是加速系數（學習因子）表示每個粒子飛向pbest和gbest位置的隨機加速項的權重。合適的值可以加快收斂不易陷入局部最優。一般取C1＝C2＝2。rand1和rand2是［0，1］之間的隨機數。粒子i的位置用D維向量Xi＝（xi1，xi2，…，xiD）T來表示，速度為Vi＝（vi1，vi2，…，viD）T。

算法流程如下：

1）初始化。以隨機的方式產生出每一個粒子的初始位置與速度。

2）評價每一個粒子。根據適應度函數計算出粒子當前的適應值，并更新個體和全局極值。

3）粒子的更新。用式（1）和式（2）對每一個粒子的速度和位置進行更新。

4）檢驗是否符合結束條件。如果當前的迭代次數達到了預先設定的最大次數或最小錯誤要求，則停止迭代，輸出最優解。否則轉到步驟2）。

利用粒子群優化算法獲得優化航跡網絡需要解決粒子位置坐標與航跡網絡空間分布的對應關系問題，還需要解決粒子適應度函數與航跡網絡代價的關系。下面將分別進行討論。

3.2 基于粒子群算法的航跡網絡圖優化

航跡網絡圖的優化有其特殊性。第一，航跡片段的代價是由航跡規劃算法中的評價函數確定的。節點發生改變時，航跡片段的代價值往往沒有明確的變化趨向。相應地，代價值的變化給出的節點變化引導往往也是不可靠的。換句話說，代價值的變化與節點的變化沒有明確的關聯。而航跡片段的代價值是優化函數的主要變量，這就造成了優化函數值影響因素的復雜性問題。第二，網絡圖往往含有大量的節點，任意一個節點的改變都會造成網絡圖的改變，進而對網絡圖的優劣產生影響。因此網絡圖的優化是一個高維復雜優化問題。

采用經典的數學規劃方法解決此問題時，必須在精度和求解效率間做某種折中。其中，線性規劃法計算速度快，但將該模型線性化存在困難；非線性規劃法可以較精確地計及模型的非線性，但一般要求目標函數連續可導，且定義于凸可行域；動態規劃法對目標函數無嚴格限制，容易計及約束條件，但對于高維問題將面臨維數災難。而人工智能算法為求解這類問題提供了新的思路。其中，粒子群優化算法簡單、有效，依賴的經驗參數少，可以求解復雜的高維非線性函數優化。

基于粒子群算法的網絡圖優化是通過調整網絡圖中節點的分布，使網絡圖的代價降低同時保持網絡圖的豐富性。當網絡圖中的節點位置改變時，網絡圖中的航跡片段需重新生成，進而形成一個新的航跡網絡圖。這類似于粒子群優化算法中的粒子從一個位置移動到另一個位置。粒子通過相互引導向最優值靠攏，多個網絡圖之間也可以相互引導，從而使網絡圖向最優的網絡圖靠攏。因此可以將網絡圖看作一個粒子，應用粒子群優化算法求解網絡圖的優化問題。

將網絡圖看作一個粒子，每個節點坐標p作為粒子坐標Q的一個分量。則粒子的坐標標為：Qk＝（，，，…，，）T由第k張航跡網絡圖中所有節點坐標構成，其中N為節點個數。（xj，yj）為航跡網絡中第j個節點pj的坐標，1≤j≤N。構造如下目標函數：

其中f（，）為節點間對應的航跡片段的代價，由航跡片段規劃算法求得。如果之間沒有規劃出可行航跡，則定義f）為一個懲罰常量值，以使節點朝向能規劃出航跡的方向移動。Ωj為第j個網格包含的區域，表示限定第j個節點的位置落在第j個網格內，該限定的目的是航跡網絡的節點的分布比較均勻，避免過度集中和過度稀疏的情況發生。

實現過程中，Ωj是一個正方形網格。在網絡圖中，設定節點坐標表示為pj＝（xj，yj），1?j?N。由于節點限制在正方形網格內，節點坐標滿足：

Xj、Xj＋1為節點pj所在網格的豎直方向邊界的橫坐標。Yj、Yj＋1為節點pj所在網格的水平方向邊界的縱坐標。粒子的速度Vk為

vjx、vjy分別為節點pj＝（xj，yj）的x和y方向上的運動速度。粒子每一維速度限定在一定范圍內，滿足約束條件：

調整Vdmax可以限定粒子的運動速度。如果粒子速度過大，可能會飛躍最優解；粒子速度太小，則容易陷入局部最優。

在優化模型的目標函數中，懲罰代價可以根據航跡片段的數目以及片段的平均代價來設定：

其中，fave為已生成的航跡片段的平均代價，α為懲罰系數，nall為理論上網絡圖能夠生成的航跡片段數，nr為實際生成的航跡片段數。nall取值與節點個數和網格尺度有關。節點個數越多，nall值就越大；反之，就越小。懲罰代價與航跡片段數目成反比：當節點個數和網格尺度確定時，實際生成的片段數nr越大，懲罰代價就越小，否則懲罰代價越大。

因此，兩節點間的代價函數定義為

基于粒子群算法的網絡圖優化流程：

1）初始化種群。以隨機的方式產生出每一個粒子的初始位置與速度。若有匹配區限制，則節點必須分布在匹配區上。

2）生成航跡片段。對每個粒子，利用A＊算法生成航跡片段，從而生成航跡網絡圖。

3）求得適應度值。根據式（3）求得每個粒子當前的適應度值，并更新個體和全局極值。

4）更新粒子位置和速度。根據新得到的個體和全局極值更新粒子的位置和速度。判斷每個粒子中節點是否滿足網格邊界約束和匹配區約束條件。若節點不滿足約束條件，則調整節點使其滿足約束條件。

5）檢驗是否符合結束條件。如果達到了預先設定的最大迭代次數或最小錯誤要求，則停止迭代，輸出最優解。否則轉到步驟2）。

算法流程圖：

圖2 粒子群算法優化網絡圖的流程圖

算法初始化中，在每個網格內隨機生成一個節點，并判斷節點是否在匹配區上，若在匹配區上，則節點位置確定；否則在網格內按一定策略逐點搜索匹配區。若找到匹配區則節點確定，否則該網格內不設定節點，粒子在該節點對應的分量上不予考慮。所有的節點生成后，利用A＊算法規劃出航跡片段。按式（3）求取各粒子個體最優值的初值，其中所有粒子適應度值的最小值為全局最優值的初值。

在航跡網絡圖的優化過程中，節點必須滿足網格邊界約束和匹配區約束條件。在每一次迭代過程中，節點移動后，可能移動到相鄰網格或超出規劃空間，也有可能不在匹配區上。這時必須對不滿足約束條件的節點進行調整。當節點不滿足網格邊界約束時，將該節點置于節點運動路線與網格邊界的交點處，并將其速度反向。這樣處理可使粒子盡早脫離“非法區域”，盡可能多地探索合理的規劃空間。當節點不滿足匹配區約束時，調整策略是讓節點從當前位置沿著移動方向v逐點探索直到找到匹配區。若按上述方式搜索至網格邊界仍未找到匹配區，則使節點從當前位置逐點回退，運動方向為－v，直到找到匹配區。由于粒子的初始位置是在匹配區上，故回退一定能夠找到匹配區。這種調整策略能確保粒子在移動過程中的兩個“極值”對粒子運動的引導性不變。

4 試驗結果與分析

本文給出的算法在6000×6000像素的數字地形高程圖上實驗，其中，每個像素代表的實際距離是90m。實驗中，網格的大小為500×500像素，考慮匹配區限制。粒子群算法的參數設定為：粒子個數，迭代次數90次，粒子每一維的最大速度Vmax＝200，加權系數C1＝C2＝2。本文進行兩類實驗：先對同一幅初始航跡網絡圖進行三組粒子群優化實驗，然后在優化前后的航跡網絡圖上進行航跡重組的對比實驗。

圖3所示是航跡網絡圖代價的變化情況。從圖中可以看出，航跡網絡的代價是震蕩下降的，這是由優化函數值的影響因素比較復雜造成的。這也會造成算法的收斂精度不高，使得曲線最終在收斂值附近波動。迭代開始時，粒子的代價從1487.25開始快速下降，之后下降趨勢逐漸減緩，最后穩定地在1430附近波動。表明該算法能有效地優化網絡圖的代價。圖4是優化后的航跡片段網絡圖，從中可以看出網絡圖能夠比較均勻地覆蓋規劃空間，并且網絡圖中片段也很豐富。

圖3 粒子群優化代價變化

圖5是在給定同一組發射點和目標點的條件下，在經粒子群算法優化的航跡網絡和沒有優化的航跡網絡上重組出的航跡對比。從圖中可以看出，在優化過的網絡圖上重組得到的航跡比較平滑。表1記錄的是進行6次不同任務得到的航跡的長度、水平轉彎次數、垂直機動次數的對比結果。其中，任務1是圖5中這兩條航跡的相關參數的對比。

圖4 優化后的網絡圖

圖5 網絡圖優化前后重組出的航跡

表1 航跡相關參數的對比

任務1中，基于優化的網絡圖重組的航跡長度為287.726km，較基于未優化的網絡圖重組的航跡長度315.2km短。在水平機動次數上的對比是9次低于14次。在垂直機動的次數上的對比是34次低于43次。從表1可以看出，每組任務中，左邊的航跡長度均比右邊的航跡長度短，水平機動次數少。在垂直機動次數上，左邊的航跡在大多數情況下要優于右邊的航跡。在統計意義上，基于較優的網絡圖重組出的航跡要優于基于未優化的航跡網絡圖重組出的航跡。

5 結語

航跡網絡圖的優化存在優化函數值影響因素的復雜性問題。并且網絡節點通常較多，使得網絡圖的優化是一個高維復雜優化問題。實驗結果表明，本文提出的方法能生成代價較優、片段豐富的航跡網絡圖。在統計意義上，優化后航跡網絡圖重組出的航跡要優于優化前網絡圖重組出的航跡。

航跡網絡圖優化的后續研究，可以在進一步提高優化效率等方面展開。

［1］鄭昌文，嚴平，丁明躍，等.飛行器航跡規劃研究現狀與趨勢［J］.宇航學報，2007，28（6）：1441－1446.

［2］Li ShiDong，Ding Mingyue，Cai Chao.A novel path planning method based on path network［C］／／Proceedings of the SPIE 6thInternational Symposium on Multispectral Image Processing and Pattern Recognition，2009.

［3］Li S，Ding M，Cai C，et al.Fast online path planning method based on path network［C］／／Computer Application and System Modeling（ICCASM），2010International Conference on.IEEE，2010，10：V10－224－V10－227.

［4］Li S，Ding M，Cai C.Path planning using FMM with direction and curvature constrained［C］／／Sixth International Symposium on Multispectral Image Processing and Pattern Recognition.International Society for Optics and Photonics，2009：749847－749847－8.

［5］Changuien Z，Mingyue D，Chengping Z.An evolutionary real－time 3Droute planner for aircraft［J］.Systems Engineering and Electronics，Journal of，2003，14（1）：47－53.

［6］Li S，Ding M，Cai C.A new roadmap constitution method based on fividing grid and level－set［C］／／Intelligence Information Processing and Trusted Computing（IPTC），2010International Symposium on.IEEE，2010：647－650.

［7］Kavraki L E，Svestka P，Latombe J C，et al.Probabilistic roadmaps for path planning in high－dimensional configuration spaces［J］.Robotics and Automation，IEEE Transactions on，1996，12（4）：566－580.

［8］Kavraki L E，Kolountzakis M N，Latombe J C.Analysis of probabilistic roadmaps for path planning［J］.Robotics and Automation，IEEE Transactions on，1998，14（1）：166－171.

［9］Siméon T，Laumond J P，Nissoux C.Visibility－based probabilistic roadmaps for motion planning［J］.Advanced Robotics，2000，14（6）：477－493.

［10］Nissoux C，Siméon T，Laumond J P.Visibility based probabilistic roadmaps［C］／／Intelligent Robots and Systems，1999.IROS'99.Proceedings.1999IEEE／RSJ International Conference on.IEEE，1999，3：1316－1321.

［11］Lulu L，Elnagar A.A comparative study between visibility－based roadmap path planning algorithms［C］／／Intelligent Robots and Systems，2005.（IROS 2005）.2005IEEE／RSJ International Conference on.IEEE，2005：3263－3268.

［12］Kennedy J，Eberhart R C.Particle swarm optimization［C］／／Proceedings of IEEE International Conference on Neutral Networks，Perth，Australia，1995：1942－1984.

［13］Shi Y H，Eberhart R C.A modified particle swarm optimizer［C］／／IEEE International Conference of Evolutionary Computation，Anchorage，Alaska， May 1998.

［14］Shi Y H，Eberhart R C.Parameter selection in particle swarm optimization［C］／／Annual，1998.

［15］Clerc M，Kennedy J.The particle swarm－explosion，stability，and convergence in a multidimensional complex space［J］.Evolutionary Computation，IEEE Transactions on，2002，6（1）：58－73.