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

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

航跡規(guī)劃研究趨勢分析

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

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

0　引言

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

1　航跡規(guī)劃算法分類

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

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

2　啟發(fā)式航跡規(guī)劃算法比較分析

在啟發(fā)式航跡規(guī)劃算法中，前述幾種算法各有優(yōu)缺點。

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

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

3　啟發(fā)式航跡規(guī)劃算法的新發(fā)展

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

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

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

4　研究趨勢分析

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

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

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

5　結語

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

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

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

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

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

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

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

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

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

［9］鄭昌文，丁明躍，周成平，等.一種飛行器在線航跡重規(guī)劃算法［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］王棟.低空突防航跡規(guī)劃、航跡控制的工程實現(xiàn)［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］胡昱，高金源.應用模糊變權的啟發(fā)式搜索進行飛行軌跡優(yōu)化［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］李婷，張金生，王仕成，等.量子粒子群算法在地磁匹配航跡規(guī)劃中的應用［J］.電光與控制，2015（7）：43-47.

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

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

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

［20］張玉廣，謝文俊，趙曉林.基于改進粒子群算法的無人作戰(zhàn)飛機航跡規(guī)劃［J］.現(xiàn)代計算機（專業(yè)版），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）、創(chuàng)新強校專項基金（No.504-20000112）、基于物聯(lián)網技術的信息化協(xié)同中心（No.CQ2014013）

1007-1423（2015）31-0049-03

10.3969/j.issn.1007-1423.2015.31.013

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

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

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

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

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

2015-09-29

2015-10-20

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

航跡規(guī)劃；研究趨勢

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.