航跡規劃研究趨勢分析

李泓波，白勁波，程順，楊高明，黃少偉

（1.肇慶學院計算機學院軟件學院，肇慶 526061；2.肇慶學院經濟管理學院，肇慶 526061；3.安徽理工大學計算機科學與工程學院，淮南　232001）

航跡規劃研究趨勢分析

李泓波1，白勁波2，程順1，楊高明3，黃少偉1

（1.肇慶學院計算機學院軟件學院，肇慶 526061；2.肇慶學院經濟管理學院，肇慶 526061；3.安徽理工大學計算機科學與工程學院，淮南232001）

0　引言

我國擁有三百多萬平方公里的海洋國土，長達一萬八千公里的海岸線。如果將島嶼也計算在內，則我國海岸線長度達到三萬兩千多公里［1］。在?？諈f同條件下，基于突然性和隱蔽性等多方面的考慮，為飛行器提供自適應飛行提供支持的航跡規劃問題已經成為學術界研究的熱點問題。

1　航跡規劃算法分類

航跡規劃研究經歷了幾十年的發展歷程。上世紀六十年代，航跡規劃主要采用純數學的微積分方法進行研究。在其后的幾十年中，航跡規劃問題歷經了基于機器人技術、自主機動機器人技術等幾個階段。

發展至今，航跡規劃算法已經十分豐富，大致可以分為兩大類：一類是純數學的方法，典型的如參數優化法、能量狀態法、牛頓法、窮舉法，動態規劃方法、整數規劃、梯度法以及奇異攝動法等［8］。這類算法的缺點是計算量大，計算時間長，而且在約束條件比較多時很難或不能獲得最優航跡解。另一類是啟發式方法，典型的如遺傳算法、神經網絡、模擬退火算法、蟻群算法、粒子群算法等［8］。相比較而言，由于具有許多優良的特性，第二類算法越來越受到研究者的重視，并且這類算法也已廣泛應用于航跡規劃實踐中［8-15］。

2　啟發式航跡規劃算法比較分析

在啟發式航跡規劃算法中，前述幾種算法各有優缺點。

從優良特性方面來說，遺傳算法具有較好的魯棒性，變異機制使其能及時跳出局部最優解，對于目標函數沒有嚴格要求；蟻群算法具有良好的并行性，對目標函數也沒有嚴格的約束要求，無需設定前提假設；神經網絡算法也具有良好的并行性，不易出現不符實際情況的規劃結果；模擬退火算法最大優勢在于對于解空間形狀無約束，對于目標函數無需滿足光滑、最優解唯一等要求；粒子群算法具有較好的實時性，可以獲得全局最優解。

從存在的缺點方面來說，遺傳算法的取得滿意解往往需要進行多代進化，時間成本較大，并且由于遺傳變異的振蕩現象的存在，收斂速度有時會很慢；蟻群算法由于理論研究相對滯后，信息素揮發率等參數的設定帶有試驗性性質，往往會限入局部最優；神經網絡算法計算開銷較大，不易滿足實時性要求；模擬退火算法雖然從理論上來說可以獲得全局最優解，但往往需要較長的時間成本；粒子群算法需要設定的參數雖然較少，但設定的學習因子等參數也帶有試驗性性質。

3　啟發式航跡規劃算法的新發展

從前述分析來看，幾種啟發式算法各有千秋，適應范圍存在較大差異。為克服現有算法的不足，目前研究者的主要方法是引入新機制、新技術與已有算法進行混合，提出新算法。

例如，為克服遺傳算法效率不高、遺傳算子不好選擇等缺點，學者們引入了協同進化航跡規劃算法。協同進化航跡規劃算法既保持了遺傳算法的優點，又通過種間斗爭提高了算法效率。基于協同進化的航跡規劃算法，比較典型的有多飛行器協調航跡規劃方法CCRP算法（Coevolutionary Coordinative Route Planner），該方法快速有效，可用于機上實時規劃系統中。該方法的一個主要特點是不同飛行器的“潛在航跡”個體形成自己的子種群 （相對于所有飛行器的全部航跡個體形成的種群而言），而且只在各自的子種群內部進化。飛行器間的協調與合作由個體適應函數的定義來反映。CCRP設計了一種有效的規劃環境表示方法，當戰場環境發生變化時可以及時更新環境信息，同時還可以有效地利用地形高程數據，使生成的航跡能夠有效地進行地形回避和威脅回避［9］。

目前，混合算法研究保持著強大勢頭，量子遺傳算法，量子粒子群、競爭粒子群、病毒粒子群、模擬退火、A*等航跡規劃混合算法相繼被提出［16-20］。雖然不斷有新的混合算法被提出，但這些算法尚不完善，存在著一些局限性。例如，CCRP等算法在實時性和魯棒性等方面尚有較大的改進空間。

4　研究趨勢分析

從航跡規劃算法來看，當前的研究還主要集中在單機航跡規劃算法上。考慮到目前面臨的嚴峻的周邊局勢，為打破島鏈封鎖，我國迫切需要多機協同航跡規劃研究，特別是協同突防等領域的多機協同航跡規劃研究。

多機的協同突防較之單機的突防在協同感應、協同干擾、協同攻擊等許多方面都具有優勢。例如：在協同感應方面，單機上的無源雷達只能提供目標的方位角信息，而多機（三架或三架以上的飛機）則可以通過協同感應（如使用三角測量法對目標進行測量）準確地獲取目標的位置信息。在協同干擾方面，單機只能干擾敵方部分雷達輻射面，而多機協同飛行路線和干擾信號則能夠干擾敵方雷達的整個輻射面。在協同攻擊方面，單機的生存率和攻擊成功率都比較低，而多機則可以通過協調行動而大幅度地提高生存率和攻擊成功率。

目前，雖然對多機協同規劃算法有所涉及，但研究數量相對較少，且遠未達到實際應用水平。因此，為應對我國萬里海疆上存在著的客觀的和潛在的威脅、保護海上石油等自然資源的開發、促進祖國統一，充分展開多機協同航跡規劃研究，特別是掠海突防等多機協同航跡規劃研究將是未來研究的新方向和新熱點。

5　結語

航跡規劃算法先后經歷了基于數學的純數學方法和基于人工智能的啟發式兩大階段。啟發式航跡規劃算法不斷得到發展和完善，融合多種技術的新一代啟發式算法——混合航跡規劃算法正在蓬勃發展。依據前述分析，多機協同航跡規劃將是未來的研究方向。

［1］杜朝平.島鏈對中國海軍的影響有多大［J］.中國海軍，2004（5）：37-40.

［2］王羽綸.沖破太平洋三大島鏈［J］.大科技，2007（6）：42-44.

［3］李杰.捆綁中國的“島鏈”［J］.現代船舶，2001（7）：35-37.

［4］李濟然.美暗布“第一島鏈預警帶”［J］.當代軍事文摘，2006（7）：35-37.

［5］李泉.美國舊“島鏈戰略”指向新目標［J］.社會觀察，2012（8）：36-37.

［6］海盾.三重島鏈做長纓 妄想縛住中國龍——中國周邊的美國航母基地［J］.艦載武器，2004（10）：44-45.

［7］于開金，李光所，曹永恒.島鏈淺析［J］.船舶，2006（5）：13-15.

［8］屈耀紅.小型無人機航跡規劃及組合導航關鍵技術研究［D］.西北工業大學博士論文，2006.

［9］鄭昌文，丁明躍，周成平，等.一種飛行器在線航跡重規劃算法［J］.華中科技大學學報（自然科學版），2003（2）：90-92，113.

［10］M.B.Pellazar.Vehicle route planning with constraints using genetic algorithms［C］.Proceedings of the IEEE 1994 National Aerospace and Electronic Conference，1994：111-119.

［11］王棟.低空突防航跡規劃、航跡控制的工程實現［D］.南京航空航天大學博士論文，1999.

［12］李春華.一種三維航跡快速搜索方法［J］.宇航學報，2002（3）：13-17.

［13］Robert J Szczerba.Robust algorithm for real-time route planning［J］.IEEE Transactions on Aerospace and Electronic Systems，2000 （3）：869-878.

［14］胡昱，高金源.應用模糊變權的啟發式搜索進行飛行軌跡優化［J］.飛行力學，1998（2）：46-50.

［15］Scott A.Bortoff.Path-planning for unmanned air vehicles［C］.Proceedings of the American Control Conference，2000：364-368.

［16］李婷，張金生，王仕成，等.量子粒子群算法在地磁匹配航跡規劃中的應用［J］.電光與控制，2015（7）：43-47.

［17］吳天愛，吳云玉，別曉峰.采用病毒粒子群優化算法的飛行器航跡規劃［J］.電光與控制，2014（8）：102-105.

［18］嚴浙平，鄧超，孫海濤.競爭粒子群算法及其在UUV航跡規劃中的應用［J］.北京理工大學學報，2014（8）：813-818.

［19］王瑞，白曉濤，等.基于A*算法的無人機跟蹤目標的航跡規劃［J］.計算機仿真，2015（1）：153-156.

［20］張玉廣，謝文俊，趙曉林.基于改進粒子群算法的無人作戰飛機航跡規劃［J］.現代計算機（專業版），2015（3）：14-18.

Route Planning；Research Trend

Research Trend Analysis of Route Planning
LI Hong-bo1，BAI Jin-bo2，CHENG Shui1，YANG Gao-ming3，HUANG Shao-wei1

（1.School of Computer/School of Software，Zhaoqing University，Zhaoqing 526161；
2.College of Economics&Management，Zhaoqing University，Zhaoqing 526161；3.College of Computer Science and Engineering，Anhui University of Science&Technology，Huainan 232001）

安徽省高校自然科學基金（No.KJ2014A061）、安徽省博士后基金（No.2014B021）、中國民航信息技術科研基地開放課題基金（No.CAAC-ITRB-201404）、創新強校專項基金（No.504-20000112）、基于物聯網技術的信息化協同中心（No.CQ2014013）

1007-1423（2015）31-0049-03

10.3969/j.issn.1007-1423.2015.31.013

李泓波（1971-），男，遼寧法庫人，博士，講師，研究方向為社會計算、數據挖掘等

白勁波（1971-），女，博士，副教授，研究領域為群體智能等，E-mail：hljbjb@126.com

程順（1968-），男，博士，副教授，研究方向為自動化控制、大數據等

楊高明（1974-），男，博士，副教授，研究方向為隱私保護、機器學習等

黃少偉（1979-），男，博士，副教授，研究方向為數據挖掘、移動電子商務等

2015-09-29

2015-10-20

航跡規劃是指在一定約束條件下，尋找運動體從初始點到目標點滿足某種性能指標最優的運動軌跡。在對現有航跡規劃算法進行分類、比較和闡釋其新近研究動向的基礎上，結合我國面臨的實際情況，分析航跡規劃研究的趨勢和方向。

航跡規劃；研究趨勢

Route planning is pointed in a certain constraint conditions，looks for body moving optimal trajectory from the initial point to the target point to meet a certain performance index.On the basis of classifying and comparing of the existing route planning algorithms，and interpreting the new status of them，combining the actual situation that China is facing，analyzes the research trends of route planning.