楊朋舉　周成平

(華中科技大學(xué)自動化學(xué)院多譜信息處理技術(shù)國家級重點(diǎn)實(shí)驗(yàn)室　武漢　430074)

?

一種復(fù)雜場景的局部實(shí)時(shí)規(guī)劃決策與方法

楊朋舉周成平

(華中科技大學(xué)自動化學(xué)院多譜信息處理技術(shù)國家級重點(diǎn)實(shí)驗(yàn)室武漢430074)

針對無人機(jī)改變飛行任務(wù)以及實(shí)際飛行航跡存在狀態(tài)差異的問題,首先分析了不同的場景,同時(shí)指出與傳統(tǒng)局部實(shí)時(shí)規(guī)劃的差異,進(jìn)而根據(jù)不同的場景進(jìn)行決策與方法分析。最后,經(jīng)過仿真實(shí)驗(yàn)驗(yàn)證,驗(yàn)證了方法的可行性與有效性。

局部實(shí)時(shí); 狀態(tài)差異; 改變?nèi)蝿?wù); 場景; 決策方法

Class NumberV249

1　引言

信息化戰(zhàn)爭中,高空長航時(shí)無人機(jī)系統(tǒng)得到了各國空前的重視。迄今為止,無人機(jī)已經(jīng)經(jīng)歷了伊拉克戰(zhàn)爭等六次的局部戰(zhàn)爭,充分顯示了偵查、打擊、空中戰(zhàn)斗等方面的巨大作用[1]。

無人機(jī)導(dǎo)航需要較高的精度,同時(shí)需要一定的魯棒性[3]。常用的導(dǎo)航方式中,慣性導(dǎo)航有隱蔽性好,實(shí)時(shí)性好等優(yōu)點(diǎn),但是也存在導(dǎo)航誤差積累的問題;GPS有全天準(zhǔn)確等優(yōu)點(diǎn),但是也有抗干擾性差等缺點(diǎn);地磁導(dǎo)航可以利用地球固有資源導(dǎo)航,但是也存在導(dǎo)航精度低、變化磁場等問題;地形匹配導(dǎo)航具有不受電子干擾、全天候等優(yōu)點(diǎn),但是對地形的依賴性也很大。因此,以慣性導(dǎo)航為主,其他導(dǎo)航輔助匹配制導(dǎo),往往會達(dá)到良好效果。無人機(jī)系統(tǒng)中,航跡規(guī)劃具有很重要的作用。其中主要有以A*算法[11～12]為代表的確定性搜索方法和遺傳算法[14]等為代表的不確定性搜索算法,并且已經(jīng)應(yīng)用于實(shí)踐中。

局部實(shí)時(shí)規(guī)劃領(lǐng)域,Qingbao Zhu[10]、Changwen Zheng[9]等研究了各種不同環(huán)境下的實(shí)時(shí)規(guī)劃,但是規(guī)劃的起點(diǎn)與結(jié)束點(diǎn)往往是確定并且已知的。T. Ishida[2]、鄭昌文[4]等研究了目標(biāo)變化的實(shí)時(shí)規(guī)劃,但是起始點(diǎn)是確定的并且類似于一邊規(guī)劃一邊飛行的情況,并且大都默認(rèn)為向著軌跡的前方飛行?，F(xiàn)在面臨的情況是起始點(diǎn)與結(jié)束點(diǎn)都是動態(tài)未知,并且有復(fù)雜的場景變化,不同于以前的局部實(shí)時(shí)規(guī)劃。表現(xiàn)為:1)無人機(jī)實(shí)際飛行時(shí),局部范圍內(nèi)出現(xiàn)新的任務(wù),并且后續(xù)的原有任務(wù)不再執(zhí)行,執(zhí)行完新任務(wù)可能還需回到偵查飛行起點(diǎn)的情況;2)實(shí)際飛行時(shí),原有的匹配區(qū)無法完成正確匹配校正的的情況。當(dāng)然無人機(jī)實(shí)際飛行時(shí)可能碰到多種情況,現(xiàn)在只針對以上兩種情況,進(jìn)行場景分析,進(jìn)而在局部范圍內(nèi)進(jìn)行決策與方法分析,完成實(shí)時(shí)調(diào)整。

2　兩種具體問題的介紹

2.1匹配區(qū)的匹配失敗

預(yù)規(guī)劃的航跡采用導(dǎo)航點(diǎn)鏈的形式進(jìn)行存儲,導(dǎo)航點(diǎn)形式有起始點(diǎn),直飛段(兩個(gè)端點(diǎn)),弧線段(轉(zhuǎn)彎起始點(diǎn),轉(zhuǎn)彎中心點(diǎn),轉(zhuǎn)彎結(jié)束點(diǎn)),匹配區(qū)(具有寬度與方向的匹配區(qū),簡化為中心匹配點(diǎn)),任務(wù)區(qū)(簡化為中心任務(wù)點(diǎn))構(gòu)成。

在預(yù)規(guī)劃的任務(wù)鏈上存在很多匹配區(qū),在每個(gè)匹配區(qū)處進(jìn)行輔助匹配校正,減小慣導(dǎo)誤差。如圖1,但是實(shí)際飛行的過程中,存在某個(gè)匹配區(qū)無法進(jìn)行匹配的情況。一旦匹配區(qū)無法輔助匹配校正,無人機(jī)就可能沿著誤差曲線漂移的越來越遠(yuǎn),無法完成后續(xù)的飛行任務(wù)。為了改變這種狀況,需要在匹配失敗信息出現(xiàn)時(shí),以失敗匹配點(diǎn)所在位置選定局部區(qū)域,進(jìn)而在所在場景內(nèi)確定局部規(guī)劃起點(diǎn)與結(jié)束點(diǎn),進(jìn)行局部實(shí)時(shí)調(diào)整,不影響后續(xù)的任務(wù)執(zhí)行。出現(xiàn)匹配失敗時(shí),多是結(jié)束點(diǎn)在原規(guī)劃航跡前方的情況,分別采用A*算法,改進(jìn)稀疏A*算法,遺傳算法進(jìn)行實(shí)現(xiàn),分析幾種算法在此場景中的適應(yīng)性。

圖1　匹配區(qū)匹配失敗示意圖

2.2任務(wù)改變的情況

如圖2,無人機(jī)從最初的起飛點(diǎn)Fs開始飛行,飛到當(dāng)前位置S,突然需要改變?nèi)蝿?wù)。具體分為兩種:第一,出現(xiàn)新的任務(wù)區(qū)N,但是后面的任務(wù)不再執(zhí)行,執(zhí)行過程就是S—N的規(guī)劃;第二,在新任務(wù)N執(zhí)行后,需要回到無人機(jī)的最起始位置Fs,當(dāng)然過程中可能需要添加許多臨時(shí)規(guī)劃點(diǎn)Pi,執(zhí)行過程就是S—N—P1—P2…Pi…Fs。這兩種情況,預(yù)規(guī)劃的航跡與任務(wù)都不再滿足,需規(guī)劃新的軌跡。對于規(guī)劃方向差異過大的情況,楊杰[13]提出了在任務(wù)點(diǎn)周圍反向規(guī)劃設(shè)置引導(dǎo)點(diǎn)的決策,宋文兵[15]等也提出有向圓的思想在任務(wù)添加時(shí)解決規(guī)劃距離過近與規(guī)劃方向差異過大的情況,但是跟本文的場景都存在一定的差異。

經(jīng)過分析,在有向圓思想解決位置關(guān)系與方向關(guān)系問題的基礎(chǔ)上,進(jìn)一步探討有向圓在任務(wù)改變中的應(yīng)用。同時(shí)對于有向圓的定義與位置關(guān)系如何分類進(jìn)行簡化處理與實(shí)現(xiàn),對于任務(wù)改變需要回到原始起點(diǎn)的復(fù)雜場景進(jìn)行分析與決策,對于多次規(guī)劃中臨時(shí)結(jié)束點(diǎn)可能陷入禁飛區(qū)的情況進(jìn)行處理,同時(shí)對于不同的場景實(shí)現(xiàn)連續(xù)模擬與局部調(diào)整,使得場景模擬更加接近真實(shí)場景,仿真實(shí)驗(yàn)更加方便快捷。

圖2　無人機(jī)改變?nèi)蝿?wù)示意圖

3　局部實(shí)時(shí)規(guī)劃的規(guī)劃決策與方法

3.1約束條件

1) 機(jī)動約束:最大爬升角度/俯沖角度,最大爬升距離/下降距離,最小轉(zhuǎn)彎半徑,無人機(jī)最大轉(zhuǎn)彎角度等;

2) 環(huán)境約束:地形、戰(zhàn)術(shù)、氣象等禁飛區(qū)與威脅區(qū)的約束,匹配區(qū)的選擇與方向約束,規(guī)劃需要的時(shí)間,規(guī)劃航跡的航程等。

3.2匹配失敗

3.2.1場景分析

無人機(jī)實(shí)際飛行時(shí),預(yù)規(guī)劃航跡上有很多匹配區(qū)來進(jìn)行匹配,以校正慣性導(dǎo)航的時(shí)間積累誤差。但是實(shí)際飛行時(shí),可能出現(xiàn)某種狀況,使得無人機(jī)無法進(jìn)行匹配區(qū)校正。此時(shí),需要確定調(diào)整起點(diǎn)、局部區(qū)域、調(diào)整結(jié)束點(diǎn)進(jìn)行局部實(shí)時(shí)的調(diào)整。匹配失敗的匹配區(qū)的出區(qū)位置作為調(diào)整起點(diǎn),根據(jù)調(diào)整起點(diǎn)為中心確定局部調(diào)整區(qū)域。對于可能出現(xiàn)各種導(dǎo)航點(diǎn)與匹配區(qū)、任務(wù)區(qū)組合出現(xiàn)的復(fù)雜場景進(jìn)行簡化處理,把局部區(qū)域內(nèi)是否存在任務(wù)點(diǎn)來作為不同場景的唯一分類標(biāo)準(zhǔn),場景圖如圖3,具體過程如下:

1) 在局部調(diào)整區(qū)域內(nèi)的所在航跡上,若存在任務(wù)點(diǎn),此時(shí)可以把最近的任務(wù)點(diǎn)T作為局部調(diào)整的調(diào)整結(jié)束點(diǎn);

2) 若在局部調(diào)整區(qū)域內(nèi)的所在航跡上,搜索不存在任務(wù)點(diǎn),此時(shí)可以把原規(guī)劃航跡與局部局域的邊界的相交點(diǎn)C作為調(diào)整結(jié)束點(diǎn);

其中調(diào)整結(jié)束點(diǎn)的確定特別重要,求調(diào)整結(jié)束點(diǎn)的步驟為(1)確定匹配失敗情況的起點(diǎn)S;

(2)以起始點(diǎn)作為中心點(diǎn),確定具體的矩形調(diào)整區(qū)域;

(3)在矩形區(qū)域內(nèi)搜索原航跡的向前導(dǎo)航點(diǎn),如果存在任務(wù)點(diǎn)T,則把最近任務(wù)點(diǎn)作為局部調(diào)整結(jié)束點(diǎn),否則轉(zhuǎn)下一步;

(4)搜索到原航跡與局部區(qū)域相交的前后兩個(gè)導(dǎo)航點(diǎn)A與B,如果是直線段,直接求直線段與四條邊界線段交點(diǎn)作為調(diào)整結(jié)束點(diǎn);否則是弧段,則采用二分法求得弧線段與邊界的交點(diǎn),作為調(diào)整結(jié)束點(diǎn)。

圖3　匹配失敗某種場景示意圖

3.2.2方法分析

1) A*算法是一種常用的確定性航跡搜索算法。優(yōu)點(diǎn)是針對具體場景,若設(shè)計(jì)合適,能較好地完成航跡規(guī)劃,找到最優(yōu)解或者近似最優(yōu)解,且解能重復(fù);缺點(diǎn)是搜索時(shí)間不能確定,因?yàn)锳*算法是基于遍歷收斂的。但是傳統(tǒng)的A*算法容易出現(xiàn)組合爆炸的問題,不滿足局部實(shí)時(shí)規(guī)劃。Robert J[5,8]關(guān)于稀疏A*算法的提出,減少了搜索的區(qū)域,也可以得到最優(yōu)或者次優(yōu)的結(jié)果。

根據(jù)傳統(tǒng)的三維規(guī)劃A*算法出現(xiàn)的問題,本文在匹配失敗具體場景中運(yùn)用幾種策略,改進(jìn)A*算法:(1)采用稀疏A*算法,在一定的角度內(nèi)進(jìn)行變步長搜索,代替全空間遍歷;(2)三維高度規(guī)劃過程中,采用先平面規(guī)劃,選擇合適的平面規(guī)劃路徑再進(jìn)行高度規(guī)劃;(3)對于匹配區(qū)地圖,把地圖稀疏化,不同的分辨率進(jìn)行搜索,先低分辨率大區(qū)域搜索,搜索不到則減小區(qū)域增大分辨率搜索,直到搜索到合適的匹配區(qū)。

2) 遺傳算法是一種隨機(jī)性的搜索方法。通過交叉、變異、選擇復(fù)制幾種基本算子,從而具有強(qiáng)大的搜索能力,可找到次優(yōu)解或者滿意解[14]。現(xiàn)在遺傳算法在航跡規(guī)劃中,已是一種比較成熟的算法,同時(shí)要考慮航跡如何編碼以及代價(jià)函數(shù)的設(shè)置。在本文中,航跡個(gè)體采用導(dǎo)航點(diǎn)鏈來表示,同時(shí)任務(wù)區(qū)和輔助匹配區(qū)也可以由中心點(diǎn)代替表示。航跡代價(jià)同時(shí)有幾部分構(gòu)成,有機(jī)動代價(jià)、威脅區(qū)禁飛區(qū)代價(jià)、航跡長度代價(jià),同時(shí)代價(jià)與各項(xiàng)約束有很大的關(guān)系。

3) 優(yōu)化指標(biāo)

(1)可行解:要搜索到滿足各種約束并且總體適合的航跡,應(yīng)該得到可行解或者次優(yōu)解;

(2)時(shí)間合理:對于匹配失敗的局部實(shí)時(shí)航跡規(guī)劃,對于時(shí)間的要求還是比較高的,滿足實(shí)時(shí)性的要求;

(3)成功率高:對于規(guī)劃時(shí)間一定的情況下,成功率的高低也直接影響了整體的規(guī)劃效果。

3.2.3實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)的編程環(huán)境為Visual Studio 2005與Qt4.6.3,運(yùn)行在Intel雙核 E7400、2.8GHz處理器,內(nèi)存為2.0G,系統(tǒng)為WIN7 32位機(jī)系統(tǒng),實(shí)驗(yàn)地圖分辨率為100m×100m,局部環(huán)境是以當(dāng)前點(diǎn)為中心的上下前后各100km范圍內(nèi)。

匹配失敗的場景,隨機(jī)選取不同航跡的不同的匹配失敗點(diǎn),分為A*算法,改進(jìn)稀疏A*算法(如圖4)與遺傳算法(如圖5)進(jìn)行實(shí)驗(yàn),圖6是高度規(guī)劃圖,統(tǒng)計(jì)了四條航跡的56個(gè)匹配失敗點(diǎn),記錄數(shù)據(jù)如表1所示。

圖4　改進(jìn)稀疏A*算法規(guī)劃結(jié)果

不同算法平均時(shí)間(s)最長時(shí)間(s)處理成功率A*算法39.015978.6%改進(jìn)稀疏A*算法3.4998.2%遺傳算法2.2793%

圖5　遺傳算法的匹配失敗規(guī)劃結(jié)果

圖6　高度規(guī)劃規(guī)劃結(jié)果

通過實(shí)驗(yàn)結(jié)果可知,傳統(tǒng)A*算法平均時(shí)間較長,處理成功率也比較低。改進(jìn)的稀疏A*算法搜索的效率與時(shí)間明顯高于一般A*算法,同時(shí)基于遍歷的原理也使改進(jìn)稀疏A*算法的時(shí)間稍長于遺傳算法,但是成功率也略高。因此,對于匹配失敗的情況,改進(jìn)的稀疏A*算法與遺傳算法都能滿足規(guī)劃時(shí)間小于10s的高成功率的實(shí)時(shí)規(guī)劃要求,相比之下,遺傳算法在規(guī)劃時(shí)間上稍有優(yōu)勢,改進(jìn)的稀疏A*算法在規(guī)劃成功率上稍有優(yōu)勢。

3.3任務(wù)改變

3.3.1場景分析

無人機(jī)實(shí)際飛行中,突然接到新的任務(wù)命令,并且舊的任務(wù)不再執(zhí)行。有不同的情況,第一是執(zhí)行完新任務(wù)就結(jié)束,第二是執(zhí)行完任務(wù)需要回到原始起飛點(diǎn)。新任務(wù)執(zhí)行時(shí),考慮到新任務(wù)的距離和方向的多變性,例如起點(diǎn)與結(jié)束點(diǎn)的方向偏差比較大的情況,或者起點(diǎn)與結(jié)束點(diǎn)的距離過近時(shí),可通過改進(jìn)的有方向圓來處理這個(gè)問題。對于不需要回到起點(diǎn)的情況,確定好規(guī)劃起點(diǎn)與結(jié)束點(diǎn),局部區(qū)域,采用有向圓算法進(jìn)行航跡規(guī)劃。

1) 起點(diǎn):出現(xiàn)新任務(wù)的時(shí)刻,無人機(jī)所在點(diǎn)作為起始點(diǎn);

2) 局部區(qū)域:以起始點(diǎn)為中心,建立矩形區(qū)域作為局部調(diào)整區(qū)域;

3) 結(jié)束點(diǎn):新任務(wù)點(diǎn)作為調(diào)整結(jié)束點(diǎn)。

對需要回到起始點(diǎn)的情況,可能需要較長時(shí)間,采用選定臨時(shí)規(guī)劃點(diǎn),多次局部規(guī)劃的辦法,具體操作步驟為

1) 出現(xiàn)新任務(wù)時(shí)刻的無人機(jī)所在位置作為調(diào)整起始點(diǎn);

2) 新任務(wù)所在位置作為臨時(shí)調(diào)整結(jié)束點(diǎn),并且調(diào)用第一種情況下的算法進(jìn)行局部調(diào)整,轉(zhuǎn)下一步;

3) 檢測整條航跡的原始起始點(diǎn)是否在規(guī)劃區(qū)域內(nèi),如果在,則把更改任務(wù)作為起始點(diǎn),原始起點(diǎn)作為結(jié)束點(diǎn)進(jìn)行規(guī)劃,規(guī)劃結(jié)束;否則轉(zhuǎn)下一步;

4) 原始起點(diǎn)不在規(guī)劃區(qū)域內(nèi),則把前一次的規(guī)劃結(jié)束點(diǎn)作為本次規(guī)劃起始點(diǎn),本次規(guī)劃起始點(diǎn)與任務(wù)鏈起始點(diǎn)的連線與局部邊界的交點(diǎn)作為本次規(guī)劃的結(jié)束點(diǎn);

5) 最終每一段都規(guī)劃成功,則連接回到原始起點(diǎn)的多段規(guī)劃航跡,但是此時(shí)可能要多次局部規(guī)劃,就需要比較長的時(shí)間,因此這種情況的主要衡量指標(biāo)為任務(wù)執(zhí)行的成功率,多段執(zhí)行成功回到起始點(diǎn)。

3.3.2方法分析

對于改變?nèi)蝿?wù)的出現(xiàn)的位置與方向的多樣性,復(fù)雜的場景構(gòu)成,回到原始起點(diǎn)時(shí)生成的臨時(shí)規(guī)劃點(diǎn)可能落入禁飛區(qū)的情況,準(zhǔn)備在有向圓的有關(guān)概念的基礎(chǔ)上進(jìn)一步改進(jìn)并且應(yīng)用于改變?nèi)蝿?wù)中。

1) 有向圓定義與可行公切線概念介紹

在初等數(shù)學(xué)上平面圓有如下概念:在一個(gè)平面內(nèi),線段OB繞它固定的一個(gè)端點(diǎn)O旋轉(zhuǎn)一周,另一個(gè)端點(diǎn)B旋轉(zhuǎn)生成的圖形叫做圓[6]。我們約定,在一個(gè)平面內(nèi)線段OB繞它的圓心旋轉(zhuǎn)時(shí),有順時(shí)針和逆時(shí)針的兩個(gè)旋轉(zhuǎn)方向,順時(shí)針旋轉(zhuǎn)生成的圓叫做順時(shí)針圓,逆時(shí)針旋轉(zhuǎn)生成的圓叫做逆時(shí)針圓,順時(shí)針圓和逆時(shí)針圓合成有向圓。

假設(shè)有起點(diǎn)有向圓S與結(jié)束點(diǎn)有向圓T相離,則兩圓有四條公切線,有且僅有一條合適公切線。合適公切線滿足起點(diǎn)有向圓S與結(jié)束點(diǎn)有向圓T與公切線的方向一致?？梢酝ㄟ^起始圓與目標(biāo)圓的不同方向進(jìn)行組合,有四種情況,每種情況都有且僅有一條合適公切線,再選擇最優(yōu)的公切線。

2) 兩圓位置關(guān)系分類簡化處理

常見的兩圓的位置關(guān)系分為五種,分別為外離、相交、外切、內(nèi)切、內(nèi)含,針對不同的位置關(guān)系進(jìn)行分別處理,十分繁瑣[7]。為了進(jìn)一步簡化處理,如果假設(shè)起點(diǎn)圓為有向圓S,終點(diǎn)圓為有向圓T。有向圓對可以看做一個(gè)平面上的集合,w1(s(x,y)|x2+y2≤r2),w2(T(x,y)|x2+y2≤r2)。根據(jù)集合w1與集合W2交集是否為空,把兩有向圓的位置關(guān)系簡化為兩種:第一種為兩個(gè)集合無交集,即兩個(gè)圓相離的情況,可以做四條公切線;第二種,是兩個(gè)集合有交集,可能是除了外離之外的任何一個(gè),此時(shí)沒有必要進(jìn)行細(xì)分,只需要在兩個(gè)圓心的中垂線上選擇合適的第三個(gè)點(diǎn),再構(gòu)造臨時(shí)有向圓P,構(gòu)成起點(diǎn)圓S與臨時(shí)有向圓P、臨時(shí)有向圓P與終點(diǎn)圓T的兩對集合無交集的相離圓對。

3) 臨時(shí)調(diào)整點(diǎn)落入禁飛區(qū)或者威脅區(qū)的處理

改變?nèi)蝿?wù)回到原始起點(diǎn)的過程,把新任務(wù)與規(guī)劃原始起點(diǎn)的連線和局部邊界的交點(diǎn)作為臨時(shí)調(diào)整點(diǎn),同時(shí)回到起始點(diǎn)的過程中也可能有多個(gè)臨時(shí)調(diào)整點(diǎn)。但是臨時(shí)調(diào)整點(diǎn)存在可能落入禁飛區(qū)的情況。這個(gè)情況跟匹配失敗的過程不同,因?yàn)槠ヅ涫∵^程選定的調(diào)整結(jié)束點(diǎn)都在預(yù)規(guī)劃航跡上,滿足禁飛區(qū)與威脅區(qū)的約束。因此具體處理如下:

(1)根據(jù)新任務(wù)與規(guī)劃原始起點(diǎn)的連線和局部邊界的交點(diǎn)作為臨時(shí)調(diào)整點(diǎn);

(2)檢測臨時(shí)調(diào)整結(jié)束點(diǎn)是否在禁飛區(qū)或者威脅區(qū)內(nèi);

(3)如果不在禁飛區(qū)或者威脅區(qū)內(nèi),則把臨時(shí)調(diào)整點(diǎn)作為臨時(shí)調(diào)整結(jié)束點(diǎn);

(4)假若在相關(guān)區(qū)域,需要設(shè)置一定的角度與距離進(jìn)行多次擾動,同時(shí)轉(zhuǎn)2);

(5)如果擾動達(dá)到最大次數(shù)或者擾動后此點(diǎn)不在禁飛區(qū)或者威脅區(qū)內(nèi),轉(zhuǎn)3)。

4) 有向圓解決方向偏差大與距離近的問題

本文采用有向圓,采用前后弧段無人機(jī)機(jī)動飛行,中間切線遺傳算法規(guī)劃的方法,可以有效地解決規(guī)劃起點(diǎn)S到規(guī)劃終點(diǎn)T方向偏差大的問題。如圖7,前弧段S-M和后弧段N-T機(jī)動轉(zhuǎn)彎飛行,切線段M-N進(jìn)行遺傳算法規(guī)劃。

圖7　方向偏差大的有向圓方法的示意圖

兩個(gè)圓之間有多種位置關(guān)系,如果相離,一定存在合適的滿足方向的公切線,如果是非相離的距離過近的情況,都可以在兩圓的中垂線上選擇新任務(wù)點(diǎn),進(jìn)行兩段規(guī)劃即可,每一段都參照方向偏差大的具體過程。方向偏差大與距離過近的具體步驟如圖8所示。

圖8　方向偏差過大與距離過近的有向圓

處理流程圖

5) 一條航跡實(shí)現(xiàn)多次模擬與局部調(diào)整

針對匹配失敗與任務(wù)改變的情況,設(shè)計(jì)之初,是針對每一種情況進(jìn)行單獨(dú)處理,不利于連續(xù)多場景的演示與仿真,在保持各種情況的單獨(dú)處理外,設(shè)置一個(gè)綜合接口,使得規(guī)劃方法能夠?qū)τ趶?fù)雜場景與不同情況進(jìn)行連續(xù)模擬與處理,循環(huán)呈現(xiàn)。

3.3.3實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)環(huán)境同3.2.3節(jié),改變?nèi)蝿?wù)分為兩種,一種是改變后回到起始點(diǎn)的實(shí)驗(yàn)如圖9,另一種改變后結(jié)束,不需要回到起始點(diǎn)。采用改進(jìn)的有向圓方法進(jìn)行處理,選取四條航跡50次試驗(yàn)記錄數(shù)據(jù),統(tǒng)計(jì)結(jié)果如表2所示。

圖9　任務(wù)改變回到起始點(diǎn)實(shí)驗(yàn)結(jié)果圖

改變?nèi)蝿?wù)平均時(shí)間(s)最長時(shí)間處理成功率不回起始點(diǎn)1297.5%需回起始點(diǎn)XX95%

對于改變?nèi)蝿?wù),容易出現(xiàn)規(guī)劃起點(diǎn)與結(jié)束點(diǎn)方向差別大與距離過近的情況。實(shí)驗(yàn)驗(yàn)證,采用本文方法,不需要回到原始起點(diǎn)的任務(wù)改變的規(guī)劃平均時(shí)間為1s,成功率高達(dá)97.5%;需要回到起始點(diǎn)的任務(wù)改變情況由于需要不斷滑動窗口多次規(guī)劃,規(guī)劃時(shí)間跟與原始起點(diǎn)的距離有很大關(guān)系,同時(shí)本算法對于臨時(shí)結(jié)束點(diǎn)可能陷入禁飛區(qū)的處理也使算法魯棒性更高,有很高的處理成功率。

4　結(jié)語

本文針對無人機(jī)出現(xiàn)的匹配失敗無法完成匹配的問題,經(jīng)過改進(jìn)的A*算法與遺傳算法都能完成局部實(shí)時(shí)的規(guī)劃。針對任務(wù)改變的情況,采用經(jīng)過處理的有向圓的局部規(guī)劃算法,很好地解決了改變?nèi)蝿?wù)回到起始點(diǎn)的問題。因此,本文對這兩種問題的算法解決是可行的,同時(shí)對于多無人機(jī)的局部規(guī)劃具有借鑒作用。

[1] 秦博,王蕾.無人機(jī)發(fā)展綜述[J].飛航導(dǎo)彈,2008(8):2-5.

QIN Bo, WANG Lei. Unmanned aerial vehicle (uav) development review[J]. Journal of Maneuverable Missile,2008(8):2-5.

[2] T. Ishida, R. E. Korf. Moving-target search: a real-time search for changing goals[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence,1995,17(6):609-69.

[3] 周姜濱,袁建平,羅建軍,等.高空長航時(shí)無人機(jī)導(dǎo)航系統(tǒng)研究[J].西北工業(yè)大學(xué)學(xué)報(bào),2008,26(11):463-466.

ZHOU Jiangbin, YUAN Jianping, LUO Jianjun, et al. High-altitude long-endurance uav navigation system research[J]. Journal of Northwestern Polytechnical University,2008,26(11):463-463.

[4] 鄭昌文.飛行器航跡規(guī)劃方法研究[D].武漢:華中科技大學(xué),2003.

ZHENG Changwen. Research of UAV route planning method[D]. Wuhan: Huazhong University of Science and Technology,2003.

[5] Robert J Szczerba, Peggy Galkowski Ira S C lickstein, Noah Ternullo. Robust A lgorithm for A lgorithm for Real-time Route Planning[J]. IEEE Trans. on Aerospace and Elec-ronic System,2000,36(3):869-878.

[6] 李金明.二維文本條形碼識別系統(tǒng)關(guān)鍵算法的設(shè)計(jì)及實(shí)現(xiàn)[D].廣州:華南理工大學(xué),2013:32.

LI Jinming. Two-dimensional bar code text recognition system design and realization of the key algorithm[D]. Guangzhou: South China University of Technology,2003:32.

[7] 章建躍.構(gòu)建邏輯連貫的學(xué)習(xí)過程使學(xué)生學(xué)會思考[J].數(shù)學(xué)通報(bào),2013,52(6):6-7.ZHANG Jianyue. Build the logic coherence of the learning process to make the students learn to think[J]. Bulletin des Sciences Mathematics,2013,52(6):6-7.

[8] Szczerba Robert J. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic Systems,2000,36(3):869-878.

[9] Changwen Zheng, Mingyue Ding, Chengping Zhou. Real-time route planning for unmanned air vihicle with an evonutionary algorithm[J]. International Journal of Pattern Recognition and Artificial Intelligence,2003,17(1):63-81.

[10] hu, Jun Hu, Wenbin Cai, Larry Henschen. A new robot navigation algorithm for dynamic unknown environments based on dynamic path re-computation and an improved scout ant algorithm[J]. Applied Soft Computing,2011,11(8):4667-4676.

[11] Robert J S, Peggy G I S. Clickstein, Noah Ternul-lo. Robust algorithm for algorithm for real-time routeplanning[J]. IEEE Trans. on Aerospace and Electronic System,2000,36(3):869-878.

[12] 李春華,鄭昌文,周成平,等.一種三維航跡快速搜索方法[J].宇航學(xué)報(bào),2002,23(3):13-17.

LI Chunhua, ZHENG Changwen, ZHOU Chengping, et al. A three-dimensional track fast search method[J]. Acta Astronautica,2002,23(3):13-17.

[13] 楊杰.具有端點(diǎn)方向約束的快速航跡規(guī)劃法研究[D].武漢:華中科技大學(xué),2013.

YANG Jie. The fast route planning method to adapt to the directional endpoint constraints[D]. Wuhan: Huazhong University of Science and Technology,2013.

[14] 張鈴,張鈸.遺傳算法機(jī)理的研究[J].軟件學(xué)報(bào),2000,11(7):945-952.

ZHANG Ling, ZHANG Bo. The researches on the mechanism of the genetic algorithm[J]. Journal of Software,2000,11(7):945-952.

[15] 宋文兵,周成平.一種基于超差信息的局部實(shí)時(shí)航跡規(guī)劃方法[J].計(jì)算機(jī)與數(shù)字工程,2015(12):2159-2163.

SONG Wenbing, ZHOU Chengping. A Local real-time path Planning Method based on the flight error[J]. Computer & Digital Engineering,2015(12):2159-2163.

A Local Real-time Route Planning Decision and Method Based on Complex Scene
YANG PengjuZHOU Chengping
(National Key-Laboratory for Multi-Spectral Information Processing Technology,

School of Automation, Huazhong University of Science and Technology, Wuhan430074)

Aiming at the problems of changing the target point and the actual flight status different from original planning paths for the UAV(Unmanned Aerial Vehicle), this paper first analyzes the complicated scene and context, then introduces the differences from the traditional local real-time route planning. Furthermore ,according to the multifarious scene, a strategic decision is made and the corresponding algorithms are realized. Finally, through simulation experiment, the feasibility and effectiveness of the method is validated.

local real-time, status differences, changing target, scene and context, strategic decision

2016年2月4日,

2016年3月11日

楊朋舉,男,碩士研究生,研究方向:任務(wù)規(guī)劃,優(yōu)化算法。周成平,男,副教授,研究方向:圖像處理,任務(wù)規(guī)劃,計(jì)算機(jī)視覺。

V249

10.3969/j.issn.1672-9722.2016.08.007