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

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

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

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

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

4　研究趨勢分析

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

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

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

5　結(jié)語

航跡規(guī)劃算法先后經(jīng)歷了基于數(shù)學(xué)的純數(shù)學(xué)方法和基于人工智能的啟發(fā)式兩大階段。啟發(fā)式航跡規(guī)劃算法不斷得到發(fā)展和完善，融合多種技術(shù)的新一代啟發(fā)式算法——混合航跡規(guī)劃算法正在蓬勃發(fā)展。依據(jù)前述分析，多機(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ì)然.美暗布“第一島鏈預(yù)警帶”［J］.當(dāng)代軍事文摘，2006（7）：35-37.

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

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

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

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

［9］鄭昌文，丁明躍，周成平，等.一種飛行器在線航跡重規(guī)劃算法［J］.華中科技大學(xué)學(xué)報（自然科學(xué)版），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ī)劃、航跡控制的工程實(shí)現(xiàn)［D］.南京航空航天大學(xué)博士論文，1999.

［12］李春華.一種三維航跡快速搜索方法［J］.宇航學(xué)報，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］胡昱，高金源.應(yīng)用模糊變權(quán)的啟發(fā)式搜索進(jìn)行飛行軌跡優(yōu)化［J］.飛行力學(xué)，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ī)劃中的應(yīng)用［J］.電光與控制，2015（7）：43-47.

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

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

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

［20］張玉廣，謝文俊，趙曉林.基于改進(jìn)粒子群算法的無人作戰(zhàn)飛機(jī)航跡規(guī)劃［J］.現(xiàn)代計算機(jī)（專業(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）

安徽省高校自然科學(xué)基金（No.KJ2014A061）、安徽省博士后基金（No.2014B021）、中國民航信息技術(shù)科研基地開放課題基金（No.CAAC-ITRB-201404）、創(chuàng)新強(qiáng)校專項(xiàng)基金（No.504-20000112）、基于物聯(lián)網(wǎng)技術(shù)的信息化協(xié)同中心（No.CQ2014013）

1007-1423（2015）31-0049-03

10.3969/j.issn.1007-1423.2015.31.013

李泓波（1971-），男，遼寧法庫人，博士，講師，研究方向?yàn)樯鐣嬎恪?shù)據(jù)挖掘等

白勁波（1971-），女，博士，副教授，研究領(lǐng)域?yàn)槿后w智能等，E-mail：hljbjb@126.com

程順（1968-），男，博士，副教授，研究方向?yàn)樽詣踊刂啤⒋髷?shù)據(jù)等

楊高明（1974-），男，博士，副教授，研究方向?yàn)殡[私保護(hù)、機(jī)器學(xué)習(xí)等

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

2015-09-29

2015-10-20

航跡規(guī)劃是指在一定約束條件下，尋找運(yùn)動體從初始點(diǎn)到目標(biāo)點(diǎn)滿足某種性能指標(biāo)最優(yōu)的運(yùn)動軌跡。在對現(xiàn)有航跡規(guī)劃算法進(jìn)行分類、比較和闡釋其新近研究動向的基礎(chǔ)上，結(jié)合我國面臨的實(shí)際情況，分析航跡規(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.