一、 歷史背景

無(wú)人機(jī)最早在20世紀(jì)20年代出現(xiàn)，當(dāng)時(shí)是作為訓(xùn)練用的靶機(jī)使用的，是一個(gè)許多國(guó)家用于描述最新一代無(wú)人駕駛飛機(jī)的術(shù)語(yǔ)。1945年，第二次世界大戰(zhàn)之后將多余或者是退役的飛機(jī)改裝成為特殊研究或者是靶機(jī)，成為近代無(wú)人機(jī)使用趨勢(shì)的先河。隨著電子技術(shù)的進(jìn)步，無(wú)人機(jī)在擔(dān)任偵查任務(wù)的角色上開(kāi)始展露他的彈性與重要性。隨著研究的深入，無(wú)人機(jī)開(kāi)始逐步扮演各種空戰(zhàn)角色，如：無(wú)人偵察機(jī)可以繞過(guò)敵方的雷達(dá)威脅區(qū)而獲得重要的軍事情報(bào)。1982年以色列航空工業(yè)公司(IAI)首創(chuàng)以無(wú)人機(jī)擔(dān)任其他角色的軍事任務(wù)。以色列國(guó)防軍主要用無(wú)人機(jī)進(jìn)行偵察，情報(bào)收集，跟蹤和通訊。20世紀(jì)90年代后，西方國(guó)家充分認(rèn)識(shí)到無(wú)人機(jī)在戰(zhàn)爭(zhēng)中的作用，競(jìng)相把高新技術(shù)應(yīng)用到無(wú)人機(jī)的研制與發(fā)展上。

早期的無(wú)人機(jī)都是按照地面任務(wù)規(guī)劃中心預(yù)先計(jì)算并設(shè)定好的航路飛行，因此一旦在既定航路段出現(xiàn)新的威脅，無(wú)人機(jī)將束手無(wú)策，無(wú)人機(jī)航路規(guī)劃無(wú)疑成為無(wú)人機(jī)導(dǎo)航任務(wù)中最重要的任務(wù)之一。

二、 研究意義

無(wú)人機(jī)航路規(guī)劃是指在特定約束條件下,尋找從起始點(diǎn)到目標(biāo)點(diǎn)并滿足無(wú)人機(jī)性能指標(biāo)的最優(yōu)或可行的航路。其問(wèn)題本質(zhì)是多約束條件下，多目標(biāo)函數(shù)求極值的優(yōu)化問(wèn)題。規(guī)劃出滿足任務(wù)要求、導(dǎo)航、安全性等約束的較優(yōu)航路，對(duì)提高無(wú)人機(jī)的武器系統(tǒng)性能有重要意義。通過(guò)對(duì)無(wú)人機(jī)航路規(guī)劃的研究，對(duì)無(wú)人機(jī)航路規(guī)劃問(wèn)題進(jìn)行了概括和總結(jié)，闡述了無(wú)人機(jī)航路規(guī)劃的框架結(jié)構(gòu)以及靜態(tài)全局規(guī)劃和動(dòng)態(tài)局部規(guī)劃方法的研究現(xiàn)狀。分析了近年來(lái)常用的幾種規(guī)劃算法，在此基礎(chǔ)上，對(duì)今后的研究方向進(jìn)行了展望。

無(wú)人機(jī)航路規(guī)劃主要包括環(huán)境信息、飛行約束、航路目標(biāo)以及航路規(guī)劃器4部分。

根據(jù)不同的任務(wù)環(huán)境，按照環(huán)境模型是否實(shí)時(shí)更新，即無(wú)人機(jī)飛行環(huán)境是否確定,航路規(guī)劃可分為靜態(tài)全局航路規(guī)劃和實(shí)時(shí)的局部航路規(guī)劃。靜態(tài)全局航路規(guī)劃根據(jù)無(wú)人機(jī)飛行環(huán)境的確定信息，在無(wú)人機(jī)離線狀態(tài)下進(jìn)行規(guī)劃設(shè)計(jì)，然后把預(yù)先規(guī)劃好的最優(yōu)路徑裝載在無(wú)人機(jī)上，無(wú)人機(jī)自動(dòng)駕駛沿預(yù)定航線飛行。這一過(guò)程一般在無(wú)人機(jī)起飛前完成,實(shí)時(shí)性要求不高,因而可以采用的規(guī)劃算法比較寬。實(shí)時(shí)局部航路規(guī)劃通過(guò)傳感器對(duì)環(huán)境變化的反饋更新后，在相應(yīng)時(shí)間內(nèi)對(duì)航路進(jìn)行規(guī)劃設(shè)計(jì)，這種規(guī)劃實(shí)時(shí)性要求高，是提高無(wú)人機(jī)的生存概率的一種最有效的手段。按照實(shí)時(shí)性要求，可分為強(qiáng)實(shí)時(shí)規(guī)劃算法和弱實(shí)時(shí)規(guī)劃算法。

近年來(lái)，無(wú)人機(jī)實(shí)時(shí)航路規(guī)劃技術(shù)的研究在國(guó)內(nèi)明顯加強(qiáng)，但距實(shí)時(shí)規(guī)劃要求還有較大的差距。

三、 無(wú)人機(jī)航路規(guī)劃建模

3.1 圖形環(huán)境模型

基于圖形的航路規(guī)劃方法中,首先根據(jù)一定的規(guī)則將飛行環(huán)境表示成由一系列飛行航路組成的網(wǎng)絡(luò)圖，然后根據(jù)特定的評(píng)價(jià)函數(shù)對(duì)網(wǎng)絡(luò)圖進(jìn)行航路搜索，最后得到連接起始點(diǎn)和目標(biāo)點(diǎn)的“最優(yōu)”航路。構(gòu)造可飛航路的方法有多種,其中典型的方法有切線圖法、Voronoi圖法和PRM(Probabilistic RoadmapPlanner)法。切線圖法是用威脅的切線表示可飛航路，構(gòu)造出的可飛航路圖是最短航路圖。這種方法構(gòu)造出來(lái)的航路幾乎接近威脅，其缺點(diǎn)是在無(wú)人機(jī)飛行過(guò)程中出現(xiàn)位置偏差就很易被敵方發(fā)現(xiàn)。Voronoi圖則是根據(jù)地面威脅的分布情況依次做出相鄰兩威脅的中垂線，垂線可以根據(jù)威脅等級(jí)適當(dāng)?shù)南虻偷燃?jí)威脅靠近，從而形成圍繞各威脅的多邊形，多邊形的邊就是所有可飛的航路，其寬度可以適當(dāng)選取從而形成所謂的安全走廊。然后通過(guò)搜索算法，得到“最優(yōu)”的飛行航路。當(dāng)威脅分布均勻時(shí)這種方法顯得非常有效。PRM(Probabilistic Roadmap Planner)法的優(yōu)點(diǎn)是可以針對(duì)不同的環(huán)境特征采用不同的采樣方式，在航路質(zhì)量和構(gòu)造時(shí)間上可以權(quán)衡，構(gòu)造的時(shí)間越長(zhǎng)得到最優(yōu)的航路的可能性越大。當(dāng)飛行環(huán)境變化時(shí)，PRM方法需要重新對(duì)環(huán)境進(jìn)行采樣分析，實(shí)時(shí)性不強(qiáng)，一般不用于實(shí)時(shí)的局部航路規(guī)劃。在實(shí)時(shí)航路規(guī)劃時(shí)，這幾種方法都需要重新構(gòu)造航路圖。

3.2 柵格環(huán)境模型

柵格法將無(wú)人機(jī)的飛行環(huán)境分為一系列具有二值信息的大小相同或不同的單元格，其中的一些單元格為不可飛單元，其他的為可飛單元。每個(gè)柵格的信息可以用結(jié)構(gòu)體類型定義。這一方法的關(guān)鍵在于柵格大小的選取，柵格大小直接影響信息的存儲(chǔ)量的大小和規(guī)劃時(shí)間的長(zhǎng)短。柵格大,信息存儲(chǔ)量減小，規(guī)劃時(shí)間短，但是航路質(zhì)量下降。柵格小，信息存儲(chǔ)量大，規(guī)劃時(shí)間長(zhǎng)，航路質(zhì)量高。針對(duì)這一問(wèn)題，往往對(duì)威脅密集的環(huán)境進(jìn)行單元格細(xì)分，而對(duì)稀疏環(huán)境單元格大小適當(dāng)放大。柵格法的實(shí)現(xiàn)簡(jiǎn)單，當(dāng)環(huán)境更新時(shí)能夠做出快速的對(duì)局部柵格信息進(jìn)行更新以滿足實(shí)時(shí)規(guī)劃要求，近來(lái)被廣泛采用。

3.3 威脅模型

航路規(guī)劃中的關(guān)鍵問(wèn)題在于地形信息和威脅源信息的獲取與處理，這些信息的獲取及處理的準(zhǔn)確度直接決定了航路規(guī)劃的質(zhì)量。這類信息一般通過(guò)衛(wèi)星遙感技術(shù)和其他情報(bào)手段獲得。由于航路規(guī)劃大部分工作由計(jì)算機(jī)自動(dòng)完成，對(duì)于地形信息，需要建立數(shù)字地形數(shù)據(jù)庫(kù)，即電子地圖的形式來(lái)表示地形。航路規(guī)劃系統(tǒng)必須對(duì)地形特征做出分析，根據(jù)地形數(shù)據(jù)來(lái)確定無(wú)人機(jī)的可飛區(qū)及飛行高度。同時(shí)需要從威脅源信息中分析出敵方防御系統(tǒng)的雷達(dá)探測(cè)區(qū)、火力殺傷范圍和相應(yīng)的地形遮蔽區(qū)，并將其填入地形數(shù)據(jù)庫(kù)中。威脅模型分為地形威脅模型、雷達(dá)威脅模型以及大氣威脅模型。

四、 無(wú)人機(jī)航路規(guī)劃算法

航路規(guī)劃算法可以分為傳統(tǒng)經(jīng)典算法和現(xiàn)代智能算法兩大類。其中，前者主要包括動(dòng)態(tài)規(guī)劃法、導(dǎo)數(shù)相關(guān)法、最優(yōu)控制法;后者主要包括啟發(fā)式尋優(yōu)搜索、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、群體智能(主要包括蟻群算法、粒子群算法、蜂群算法)等。上述這些方法所要解決的問(wèn)題都是大范圍航路規(guī)劃過(guò)程中巨大的信息存儲(chǔ)量和全局最優(yōu)之間的矛盾,現(xiàn)在這方面仍然還有許多工作要做。

4.1 動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃是分階段決策過(guò)程的最優(yōu)化的一種數(shù)學(xué)方法。使用這種方法的無(wú)人機(jī)航路規(guī)劃要求構(gòu)造的航路圖分為各級(jí)的連接,并最終歸結(jié)于目標(biāo)點(diǎn)。每一級(jí)的航路代價(jià)由特定的評(píng)價(jià)函數(shù)給出，然后按照分階段決策規(guī)則尋找最優(yōu)的航路。這種方法在無(wú)人機(jī)高空作業(yè)并且威脅單一的情況下得到了良好的效果。

4.2 啟發(fā)式算法

啟發(fā)式方法是指通過(guò)尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，找到問(wèn)題的一個(gè)最優(yōu)解或近似最優(yōu)解。該方法求解問(wèn)題的效率較高，但是對(duì)每一個(gè)所求的問(wèn)題必須找到特有的啟發(fā)式規(guī)則，啟發(fā)式規(guī)則沒(méi)有通用性。這一方法的典型有A*法，以及各種改進(jìn)A*算法。A*算法是利用問(wèn)題擁有的啟發(fā)信息來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的。

無(wú)人機(jī)航路規(guī)劃問(wèn)題應(yīng)用中，啟發(fā)式項(xiàng)采用當(dāng)前節(jié)點(diǎn)于目標(biāo)節(jié)點(diǎn)的歐式距離能夠得到較好的效果。啟發(fā)式項(xiàng)在滿足小于實(shí)際的耗費(fèi)值的前提,越接近實(shí)際耗費(fèi)值越能提高搜索效率。傳統(tǒng)的A*算法存在搜索速度慢和耗內(nèi)存空間大的缺陷。曾佳等人通過(guò)結(jié)合無(wú)人機(jī)的飛行約束,將前項(xiàng)搜索點(diǎn)限制在一定的范圍，提出了基于五叉樹(shù)的A*搜索算法。Szczerba等人為了加快搜索過(guò)程和節(jié)省內(nèi)存空間，通過(guò)分區(qū)搜索并結(jié)合飛行約束削減搜索節(jié)點(diǎn)，提出了稀疏A*算法。Bander為提高A*算法的搜索速度，引入了經(jīng)驗(yàn)知識(shí)和人工干預(yù)，提出了自適應(yīng)A*算法。S.Al-Hasan等采用柵格的形式構(gòu)造飛行環(huán)境，采用A*算法進(jìn)行搜索，評(píng)價(jià)函數(shù)由威脅、距離、機(jī)動(dòng)能力的加權(quán)和以及啟發(fā)式項(xiàng)構(gòu)成。并且評(píng)價(jià)函數(shù)中使用了人工智能的模糊技術(shù)，針對(duì)環(huán)境的變化可以調(diào)整權(quán)系數(shù)，對(duì)動(dòng)態(tài)環(huán)境有較高的適應(yīng)性。

4.3 遺傳算法

遺傳算法是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來(lái)的隨機(jī)全局搜索和優(yōu)化方法，可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法。強(qiáng)調(diào)利用概率轉(zhuǎn)換規(guī)則來(lái)引導(dǎo)搜索過(guò)程。遺傳算法通過(guò)染色體的復(fù)制、交叉、變異得到新的個(gè)體，并對(duì)個(gè)體性能進(jìn)行評(píng)估，從而得到最優(yōu)的符合要求的個(gè)體。但是由于無(wú)人機(jī)航路規(guī)劃存在時(shí)間上和計(jì)算機(jī)資源的約束，遺傳算法會(huì)出現(xiàn)早熟現(xiàn)象，得不到全局的最優(yōu)解。JurisVagners等通過(guò)采用多種群并發(fā)計(jì)算,通過(guò)競(jìng)爭(zhēng)機(jī)制優(yōu)選的思想來(lái)解決遺傳算法的早熟現(xiàn)象。遺傳算法的關(guān)鍵在于對(duì)群體的編碼，Michalewicz經(jīng)過(guò)大量的實(shí)驗(yàn)表明使用浮點(diǎn)數(shù)編碼比二進(jìn)制編碼在CPU計(jì)算時(shí)間上更加有效。初始群體的選取應(yīng)具有多樣性，使得規(guī)劃空間的每一個(gè)體都有機(jī)會(huì)參與進(jìn)化。Changwen Zheng等用導(dǎo)航點(diǎn)的坐標(biāo)信息以及一位校驗(yàn)位對(duì)航路進(jìn)行實(shí)值編碼，結(jié)合航路的約束條件以及評(píng)價(jià)函數(shù)對(duì)航路群體進(jìn)行分析,然后采用自設(shè)定的幾種遺傳算子對(duì)群體進(jìn)行操作，得到了較好的結(jié)果。蟻群算法則是一種由于受自然界生物的行為啟發(fā)而產(chǎn)生的“自然”算法，通過(guò)跟蹤螞蟻的生物信息激素來(lái)決定后續(xù)行為的算法,根據(jù)信息素的強(qiáng)弱決定航路的優(yōu)劣。此方法關(guān)鍵在于信息素的調(diào)整。

4.4 元胞螞蟻算法

蟻群算法是受自然界中真實(shí)蟻群的集體覓食行為的啟發(fā)而發(fā)展起來(lái)的一種基于群體的模擬進(jìn)化算法，屬于隨機(jī)搜索算法。蟻群算法是最新發(fā)展的一種模擬昆蟲(chóng)王國(guó)中螞蟻群體智能行為的仿生優(yōu)化算法，該算法利用生物信息素作為螞蟻選擇后續(xù)行為的依據(jù)，并通過(guò)螞蟻的協(xié)同來(lái)完成尋優(yōu)過(guò)程。蟻群算法具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其他方法相結(jié)合等優(yōu)點(diǎn)。

五、 未來(lái)與展望

無(wú)人機(jī)的任務(wù)規(guī)劃系統(tǒng)給無(wú)人機(jī)制定飛行計(jì)劃,分配飛行任務(wù)。對(duì)使用無(wú)人機(jī)完成預(yù)定任務(wù)計(jì)劃具有十分重要的作用。而任務(wù)規(guī)劃系統(tǒng)中最重要的一部分就是航路規(guī)劃。任務(wù)規(guī)劃系統(tǒng)制定無(wú)人機(jī)的任務(wù)，航路規(guī)劃系統(tǒng)引導(dǎo)無(wú)人機(jī)如何選擇合適的航路去完成任務(wù)。因此航路規(guī)劃的研究對(duì)于提高無(wú)人機(jī)的執(zhí)行任務(wù)的效率有重要的意義。

隨著無(wú)人機(jī)所要執(zhí)行任務(wù)越來(lái)越復(fù)雜，環(huán)境的不確定性，對(duì)航路規(guī)劃的要求也將越來(lái)越高。不確定環(huán)境下的實(shí)時(shí)航路規(guī)劃將是未來(lái)的研究重點(diǎn)，首要解決弱實(shí)時(shí)的航路規(guī)劃，其次要解決戰(zhàn)術(shù)級(jí)的強(qiáng)實(shí)時(shí)的航路規(guī)劃問(wèn)題。當(dāng)一種方法無(wú)法滿足航路規(guī)劃要求時(shí)，高效的全局搜索方法和局部搜索方法的混合使用將是一種趨勢(shì)。