改進的蟻群算法在無人機航路規劃中的應用

郝延軍，羅 軍，陳治平，何佑明，孫彥飛

(解放軍陸軍軍官學院，安徽合肥230031)

0 引言

航路規劃(Path Planning)［1，2］是指在目標點與起始點之間，為運動物體尋找滿足某種性能指標和某些約束的線路、路徑。在制定無人機部(分)隊作戰計劃時，首先要進行合理的航路規劃，以期在種種約束條件之下無人機能夠順利地往返可疑目標點(有時是多個目標點)，并能對目標點發揮無人機最大的作戰效能。

1 無人機航路規劃的基本步驟

1.1 確定航路規劃的主要指標

航路規劃時選擇的主要指標包括:有效飛行時間、目標價值指數和航路總長等。

有效飛行時間Teffective是無人機作用目標的時間。若無人機等速飛行，則無人機的有效飛行時間也就可以轉變為有效飛行距離，可記為Leffective。

目標價值指數是指目標的重要程度。在對不同的目標執行任務時，對于價值較高的目標通常需要有效作用的時間長，而對于價值相對較低的目標，則可以壓縮作用時間。

航路總長是指在遂行了一定的任務之后，總的航路長度，這里指路程，而不是位移。

1.2 確定目標位置

目標對無人機的吸引程度由目標的軍事價值、無人機性能和任務決定。敵方的目標一般以點目標較多，但當目標為明顯的面目標時，則選擇其中心點作為目標點位置。

1.3 確定主要威脅位置

敵方對無人機的主要威脅有:敵方雷達陣地和敵方防空武器陣地等。在航路規劃時，在不影響作用效果或者影響效果不大的情況下盡可能遠離或規避這些區域。

1.4 選擇無人機發射回收陣地

在盡可能安全的前提下，無人機盡量抵近第一個目標點發射，以保證在航程一定的情況下能經過盡可能多的目標點。回收通常與發射是同一陣地，有時為增強抗毀性也可分開。

1.5 優化航路

航路的獲得是通過計算機按一定選優算法仿真實現的，具體地說:首先構建目標點及威脅點的坐標系。將上述各目標點及威脅點用坐標系來表示，將主要威脅點換算到平面直角坐標系中。然后有針對性地規劃多條航路，這些航路不是最終航路，需要最優化處理，本文采用改進的蟻群算法和MATLAB二維仿真運算實現尋優過程。

1.6 后期處理航路

航路的后期處理通常是指航路的光順。該過程包括:初始航路的離散化、鏈路動力學處理和最佳通過點附近的修正。

2 蟻群算法的基本原理

航路優化方法［3-11］有很多，蟻群算法在這些方法中具有較好的魯棒性，在螞蟻數量不多時收斂速度快，無人機航路優化尤其適合用蟻群算法來求解。

蟻群算法(Ant Colony Algorithm)［12，13］是一種仿真蟻群覓食過程的新型概率搜索算法。其原理在于，一只螞蟻在行動中感知其他螞蟻留下的氣味，并在路網中散布自己的生物信息激素，而后到者會受前者信息激素影響，并很可能會對原有的信息激素進行加強，如此循環下去。這樣，經過螞蟻越多的路徑，被后到螞蟻選中的可能性就越大。通常越短的路徑會被越多的螞蟻訪問，因而積累的信息激素也就越多，在下一個時間內被其他螞蟻選中的可能性也就越大。這個過程會一直持續到幾乎所有的螞蟻都走最短的那一條路徑為止，那么這條路徑也就是蟻群選擇的距離最短的(有時是能量消耗最小的)最優路徑。

3 改進的蟻群算法

3.1 原蟻群算法的不足

上述蟻群算法運用于無人機航路規劃時有其不足之處:

①蟻群在尋找食源時，它們的目標是不定的，而無人機的作戰目標是預先確定的。

②算法不滿足無人機航路選擇的要求。無人機對航路選擇要求有2點:航路盡可能安全(主要防敵打擊和電磁干擾);航路盡量短(為減少路途飛行時間，增加執行任務時間，有時也為減少油耗)。在這2個要求需要同時抉擇時，應該首先滿足前者。但蟻群算法解決后者比較理想，解決前者卻略顯不足。

③第一只螞蟻對蟻群路徑選擇影響大，容易消耗蟻群正確選擇路徑的時間。如開始時第一只螞蟻在探索路徑中(假設是較次的路徑)散布自己的生物信息激素，而后到者會受這只螞蟻信息激素影響，并很可能會加強信息激素，如此惡性循環下去，則這只螞蟻會極大地消耗正確選擇路徑的時間，在仿真實現中會占用計算機資源。

④無人機的路徑選擇過程對信息內容要求較嚴，因為蟻群選擇路徑時一般是靜態的，需要考慮的因素少，而無人機選擇路徑是動態的，要隨戰場變化實時調整的。

3.2 改進的蟻群算法

通過分析上述算法不足，本文提出新的改進算法。首先，在算法中設定具體目標和可能經過的威脅點;其次，在信息激素中除了有距離信息還需要增加威脅度信息，并將威脅度設為權重較高的參數指標;再次，在航路規劃仿真開始階段，同時發送多個探路人工蟻。探路人工蟻是專門探路的專職人工蟻，其探路行動各自獨立，也可以按人工預定線路探路，到達目標返回后，報告所行路徑的安全度和行程距離。探路人工蟻的數量可根據計算機處理能力設定，一般至少5個。由探路人工蟻探測出通往目標的可能路徑和相關指標后，再根據要求初選出幾條較好路徑，然后再由人工蟻群算法確定最優路徑。最后，信息激素中的信息是隨時更新，以便于適應戰場動態變化。

在新算法使用中，有些時候探路人工蟻可能得不出無人機通往目標的航路路徑，這很可能因為威脅點過多，或有的威脅度過高，此時，可以通過改變一個或幾個威脅點的危險度，再由算法得出可能的航路。這為我部隊通過戰法或其他手段，降低其威脅度提供依據。當目標本身威脅度很高時，則合理采用無人機戰法來解決，如采用“復眼”和“蜂群”戰法［14］，這里與航路規劃無關，不詳細討論。

3.2.1 改進的蟻群算法的基本假設

改進的蟻群算法基于以下基本假設:

①在航路規劃仿真開始階段。探路人工蟻按制約條件獨自向目標方向行動，返回后，報告其所行路徑的安全度和行程距離，給出初選的幾條航路。

②蟻群選優仿真階段。第一，人工蟻之間通過環境進行通信。通信內容具有安全信息，這樣使安全度高的路徑與信息激素高的路徑趨于一致。第二，每只人工蟻僅根據其周圍的局部環境做出反應，也僅對其周圍的局部環境產生影響。人工蟻之間通過激素相互影響，并趨向于選擇信息激素濃度高的方向。人工蟻對環境的反應由其內部模式決定。第三，在個體水平上，每只人工蟻僅根據環境做出獨立選擇。在群體水平上，單只人工蟻的行為是隨機的，但蟻群通過自組織過程形成高度有序的群體行為。

以上基本假設構成了改進蟻群算法，基于以上基本假設的螞蟻系統，實際上是一類多主體系統。在人工螞蟻系統中，人工蟻設計成反應型主體，它包括一個感知器、一個反應器和一個內部執行系統。感知器收集環境信息如收集其他人工蟻的信息、紀錄當地威脅度信息及所行航程;內部執行系統具有分析收集的環境信息，選擇下一步路徑(選擇人工蟻較多的路徑);反應器則在執行系統處理后，散布自身信息。反應型主體的執行系統是一組“條件—處理—動作”規則，將主體的感知器與效應器連接起來。

3.2.2 編程實現探路人工蟻對航路的初選

因為航路初選不是簡單的類旅行商(TSP)問題，更不是簡單的尋求最短路徑的行為，因此在編程時，必須考慮約束條件。螞蟻系統的主體——環境模型如圖1所示。

圖1 螞蟻系統的主體——環境模型

威脅量不能超過指揮員的許可范圍，即無人機的被毀殲概率不能超過某一特定的數值。無人機的總路徑長度不能超過無人機的航程。一旦兩者不能達成，則程序需要跳出循環，提示要求的任務是無法完成的。

由于該優化不便于用傳統的優化論的方法求解，因此需要采取一定的人工智能求解最優路線，進而得出最優的目標函數值。

4 案例分析

假設無人機的作戰目標是M1、M2和M3，發射回收陣地在X市，途經威脅點有M地、J地和W地，目標附近威脅點有T地、H地和Z地。利用MATLAB仿真運算，得出最優航路如圖2所示，圖中坐標系為虛擬平面直角坐標系，單位為km，每小格為20 km×20 km。

圖2 蟻群算法改進前后對比

圖2中單線是改進前航路，雙線是改進后航路。由圖2可見，改進前蟻群算法規劃的航路雖然路程少但經過的威脅點多;而改進后的航路，盡量避開了威脅點，雖然路程遠，但在無人機航程內，這損失與取得的戰果相比是值得的。而且在仿真過程中由于采用探路人工蟻，改進后的算法在選擇最優航路過程中需要的時間遠遠小于改進前時間。

5 結束語

上述提出了一種改進的蟻群算法實現無人機航路規劃。改進的蟻群算法克服了傳統蟻群算法的缺陷，充分考慮了無人機飛行中的威脅，更加符合無人機航路規劃中的實戰要求。仿真中由于人工探路工蟻的采用，大大縮短了仿真時間，優化效率更高。

［1］ 霍得森.中程無人機在島嶼進攻戰役中的航路規劃研究［D］.合肥:解放軍炮兵學院，2006:18-22

［2］ 沈延安.美軍無人機作戰運用問題研究［D］.宣化:炮兵指揮學院，2006:8-9.

［3］ 崔麥會.無人機航跡優化研究［D］.合肥:解放軍炮兵學院，2001:15-16.

［4］ 柳長安.無人機協同偵察航路規劃［J］.火力指揮與控制，2004，27(1):27-29.

［5］ 樊曉軍，羅 熊.復雜環境下基于蟻群優化算法的機器人路徑規劃［J］.控制與決策，2004，35(2):35-37.

［6］ 葉 文，廉華耕，漆云海，等.無人機航路規劃算法研究［J］.電光與控制，2011，18(2):8-11.

［7］ 任 博，馬 吉，于洪洋.威脅環境下無人機偵察航路規劃方法及仿真研究［J］.吉林工程技術師范學院學報，2011，27(10):75-77.

［8］ EMILIO F.Real-time Motion Planning for Agile Autonomous Vehicles.［J］.Journal of Guidance，Control and Dynamics，2002，25(1):9-16.

［9］ Unmanned Aerial Vehicles(UAVs)［R］.Washington DC:Headquarters Department of the Army，2005:34-40.

［10］ Unmanned Aircraft Systems Roadmap 2000 ～2025［R］.Washington DC:Office of the Secretary of Defense，2000:4-8.

［11］ Unmanned Aircraft Systems Roadmap 2005 ～2030［R］.Washington DC:Office of the Secretary of Defense，2005:2-5.

［12］李士勇.蟻群算法及其應用［M］.哈爾濱:哈爾濱工業大學出版社，2004:8-87.

［13］高 攀.飛行器低空突防中的航線優化技術研究［J］.宇航學報，2003，13(2):18-20.

［14］王 碩，康樂興.美軍無人機戰術的創新［J］.外國軍事學術，2004，38(7):14-15.