基于環(huán)境建模的USV軌跡規(guī)劃技術(shù)

張國(guó)棟,陳金鑫,吳鵬飛

(1.海軍研究院,北京 100161;2.海軍工程大學(xué)兵器工程學(xué)院,湖北武漢 430033)

1 概述

隨著“斯巴達(dá)偵察兵”等水面無(wú)人艇(Unmanned Surface Vessel,簡(jiǎn)稱USV)正式裝備美海軍,同時(shí)在2003年的伊拉克戰(zhàn)爭(zhēng)中被劃到戰(zhàn)區(qū)進(jìn)行相關(guān)實(shí)驗(yàn)以來(lái),水面無(wú)人艇已經(jīng)被公認(rèn)必將在未來(lái)的海戰(zhàn)中扮演重要的角色,可執(zhí)行掃雷、反潛、電子戰(zhàn)等多種作戰(zhàn)任務(wù)。因此,深入研究水面無(wú)人艇技術(shù),盡早裝備我軍,對(duì)提高戰(zhàn)斗力有重要意義。智能化是水面無(wú)人艇研發(fā)的重要方向之一,智能化意味著在復(fù)雜的海洋環(huán)境中無(wú)人艇可以和外部海洋環(huán)境進(jìn)行自主交互,自適應(yīng)海洋環(huán)境的變化,這種交互的一個(gè)重要方面就體現(xiàn)在無(wú)人艇的軌跡規(guī)劃上。

路徑規(guī)劃是這一領(lǐng)域發(fā)展的基本階段。此時(shí),無(wú)人艇簡(jiǎn)化為一個(gè)質(zhì)點(diǎn),沒(méi)有運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)特性。這一階段,無(wú)人艇的外形和尺寸也不對(duì)路徑規(guī)劃產(chǎn)生影響,規(guī)劃路徑最短、消耗資源最少、耗時(shí)最短是規(guī)劃的目標(biāo)和限制條件?；诼肪€圖的規(guī)劃方法、基于網(wǎng)格的搜索算法以及各種具有優(yōu)化目標(biāo)的進(jìn)化算法和啟發(fā)式算法,均屬于這一階段的規(guī)劃方法。然而,通過(guò)這種方法規(guī)劃出的路徑,與無(wú)人艇的實(shí)際路徑之間存在著較大差距。在實(shí)際海上任務(wù)中,無(wú)人艇很難執(zhí)行這些路徑。在路徑規(guī)劃中加入無(wú)人艇運(yùn)動(dòng)學(xué)限制,催生了第二個(gè)階段——軌跡規(guī)劃。這一階段,無(wú)人艇不作為質(zhì)點(diǎn)出現(xiàn),而是具有合理假設(shè)的外形和尺寸。位置的一階導(dǎo)數(shù)包括平動(dòng)速度、旋轉(zhuǎn)角速度,甚至二階導(dǎo)數(shù)包括平動(dòng)加速度、角加速度等要素,限制了生成的可行軌跡集的規(guī)模。路徑的安全性、消耗少、平滑和可執(zhí)行性成為運(yùn)動(dòng)規(guī)劃的新目標(biāo),吸引大量學(xué)者展開(kāi)了對(duì)動(dòng)態(tài)路徑生成、速度窗口、路徑平滑等課題的研究。速度障礙法、動(dòng)態(tài)窗口法以及各種曲線平滑算法被提出來(lái)。第三個(gè)階段是運(yùn)動(dòng)規(guī)劃,考慮規(guī)劃的路徑是否可以被控制系統(tǒng)執(zhí)行。此時(shí),NGC(Navigation-Guidance-Control)系統(tǒng)的概念受到了關(guān)注。導(dǎo)航系統(tǒng)提供無(wú)人艇的位置、航向、航速信息,制導(dǎo)模塊規(guī)劃出可行的航跡,控制系統(tǒng)按照一定的算法跟蹤所規(guī)劃的算法。這一階段,研究的重點(diǎn)是軌跡跟蹤算法和穩(wěn)定的航行控制方法。

本文在前人資料的基礎(chǔ)上,重點(diǎn)研究了無(wú)人艇的全局路徑規(guī)劃算法。規(guī)劃算法實(shí)質(zhì)是,在給定的起始點(diǎn)和目的地之間設(shè)計(jì)一條軌跡,使得無(wú)人艇安全平穩(wěn)到達(dá)目的地。路徑規(guī)劃算法分為全局規(guī)劃算法和局部規(guī)劃算法,二者沒(méi)有本質(zhì)上的區(qū)別,局部規(guī)劃的目標(biāo)是局部的子目的地而全局規(guī)劃的目標(biāo)是最終的目的地。全局路徑規(guī)劃利用靜態(tài)環(huán)境數(shù)據(jù),進(jìn)行大范圍離線路徑規(guī)劃,由于傳感器精度和動(dòng)態(tài)環(huán)境限制,只提供宏觀的路徑指導(dǎo),即一系列離散的子路徑的組合。在進(jìn)行路徑規(guī)劃之前,需要根據(jù)使用的方法對(duì)環(huán)境進(jìn)行建模。一般有兩種方式:1)基于可視圖法或單元分解的方法,將環(huán)境地圖轉(zhuǎn)化為行車路線圖或者柵格。在此基礎(chǔ)上,利用搜索算法得到最優(yōu)路徑;2)基于“場(chǎng)”的概念,將環(huán)境地圖轉(zhuǎn)化為勢(shì)能場(chǎng)或者向量場(chǎng),在建立的場(chǎng)中進(jìn)行軌跡規(guī)劃。

2 基于可視圖法和單元分解的搜索規(guī)劃

2.1 環(huán)境建模方法

2.1.1 基于道路圖的可視圖法

可視圖法(Visibility Graph)[1]是由Lozano和Wesley提出的。應(yīng)用可視圖法需要將環(huán)境中的障礙物表示為多邊形數(shù)據(jù),將起始點(diǎn)s、目標(biāo)點(diǎn)g和多邊形障礙物的各頂點(diǎn)進(jìn)行組合連接。障礙物各頂點(diǎn)之間、起始點(diǎn)和障礙物各頂點(diǎn)之間、終點(diǎn)和障礙物各頂點(diǎn)之間的連線,均不能穿過(guò)障礙物。設(shè)所有的障礙物的頂點(diǎn)構(gòu)成的集合是V0,構(gòu)造可見(jiàn)圖G(V,E),點(diǎn)集V是V0和s、g的并集,E是所有可見(jiàn)邊的集合。在道路圖形成后,采用某種最優(yōu)搜索算法[2-5]在圖G中搜索從S到G的最優(yōu)路徑,即搜索從起點(diǎn)s到終點(diǎn)g經(jīng)過(guò)這些可視直線的最短距離。

可視圖法對(duì)環(huán)境變化的適應(yīng)性較弱。起始點(diǎn)和終點(diǎn)改變,或者障礙物改變,都會(huì)導(dǎo)致可視點(diǎn)的變化,導(dǎo)致全局路徑需要完全重新規(guī)劃。文獻(xiàn)[6]針對(duì)算法不適應(yīng)動(dòng)態(tài)環(huán)境的缺陷,設(shè)計(jì)了一種基于相交判斷的改進(jìn)算法,但是不能處理凹形障礙物的情況?？梢晥D法的另一個(gè)缺陷是實(shí)際路徑巡航中一旦產(chǎn)生位置誤差,極易發(fā)生碰撞。可視圖法的計(jì)算復(fù)雜度依賴于工作空間總的障礙物,當(dāng)環(huán)境中存在密集障礙物,后續(xù)的搜索算法很可能找不到最優(yōu)路徑甚至搜索失敗。文獻(xiàn)[7]利用膨脹法,將膨脹輪廓的頂點(diǎn)作為連接的頂點(diǎn),降低了碰撞危險(xiǎn)。同時(shí)僅考慮以起終點(diǎn)連線為對(duì)角線的矩形內(nèi)部的障礙物,降低了算法的計(jì)算規(guī)模,但忽略矩形外部障礙物也可能導(dǎo)致只能得到次優(yōu)路徑。文獻(xiàn)[8-9]明確了可視圖法中內(nèi)可視點(diǎn)和外可視點(diǎn)的概念,通過(guò)模擬現(xiàn)實(shí)人尋路的思想,引入凸點(diǎn)法提高了可視圖法的計(jì)算效率。

Voronoi圖法是一個(gè)關(guān)于空間劃分的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)[9],它的概念在19世紀(jì)末就被討論過(guò),之后得以廣泛研究和應(yīng)用[10]。Voronoi圖將平面劃分為多個(gè)凸多邊形形狀的Voronoi區(qū)域,每個(gè)區(qū)域?qū)?yīng)一個(gè)站點(diǎn)。在某個(gè)特定區(qū)域中,任何點(diǎn)到其中站點(diǎn)的距離都比到其他區(qū)域中點(diǎn)的距離要短。在路徑規(guī)劃領(lǐng)域,障礙物基本屬于面目標(biāo),因此不能用質(zhì)點(diǎn)來(lái)近似。廣義的Voronoi圖可以用來(lái)進(jìn)行路徑規(guī)劃,各個(gè)Voronoi區(qū)域的共有頂點(diǎn),即可視圖法的集合E中各條可見(jiàn)邊的中點(diǎn)。這樣得到的路徑是最安全的,但是犧牲了路徑[11]。

2.1.2 環(huán)境地圖的單元分解方法

柵格法是由W.E.Howden于1968年提出,他在進(jìn)行路徑規(guī)劃時(shí)采用柵格表示地圖,規(guī)劃空間被分解為一系列具有二值信息的網(wǎng)絡(luò)單元。每個(gè)網(wǎng)格的規(guī)格參考規(guī)劃對(duì)象的尺寸以及單步規(guī)劃步長(zhǎng)來(lái)確定。柵格地圖中存在自由柵格和障礙柵格,障礙柵格是環(huán)境中障礙物經(jīng)過(guò)膨脹或者腐蝕處理后填充到柵格中形成的,自由柵格是可以自由行走的柵格。柵格位置可以使用序號(hào)法和直角坐標(biāo)法兩種方法來(lái)表示[13]。

運(yùn)用最優(yōu)搜索算法進(jìn)行搜索,可以得到從起始點(diǎn)到目的地的無(wú)碰路徑。柵格法描述簡(jiǎn)單且易于實(shí)現(xiàn),可應(yīng)用于不同的算法,同時(shí)可以表示不同的障礙物,實(shí)現(xiàn)大規(guī)模的并行處理[14-15]。同時(shí)柵格法存在以下缺陷:1)分辨率難以確定。分辨率過(guò)高,增加搜索算法的運(yùn)算量;分辨率過(guò)小會(huì)導(dǎo)致路徑規(guī)劃結(jié)果粗糙,在極端情況下會(huì)造成本來(lái)分開(kāi)的障礙物連通,最終得不到有效路徑。2)柵格在被選入路徑后需要加入禁忌表,即該柵格不能再次被選入路徑中,這樣當(dāng)遇到一些U型障礙物等復(fù)雜環(huán)境會(huì)迅速地生成有效路徑。文獻(xiàn)[16]參考可視圖法和人工勢(shì)場(chǎng)思想,提出了基于有效頂點(diǎn)的柵格編碼方法,使得算法計(jì)算規(guī)模不再依賴于分辨率的設(shè)置,只與障礙物的個(gè)數(shù)相關(guān);文獻(xiàn)[17]給出了四叉樹(shù)的方法,四叉樹(shù)只需要記錄葉子節(jié)點(diǎn)的編碼而不用記錄中間的節(jié)點(diǎn)和層次關(guān)系,減少了儲(chǔ)存空間,但是計(jì)算過(guò)程引入了鄰域查找算法,增加了算法的復(fù)雜性。文獻(xiàn)[18]設(shè)計(jì)了一種扇形柵格,改進(jìn)后的柵格法更加適合處理傳感器數(shù)據(jù)。

2.2 啟發(fā)式路徑搜索算法

啟發(fā)式算法一般用來(lái)解決“NP-Hard”問(wèn)題,借助某種直觀判斷或試探的方法,以求得問(wèn)題的次優(yōu)解或以一定概率求得最優(yōu)解。在規(guī)劃環(huán)境稀疏時(shí),使用深度優(yōu)先搜索(DFS)、廣度優(yōu)先搜索(BFS)、Dijkstra[19]算法等精確算法,可以在離散的路徑中準(zhǔn)確高效地找到全局最短路徑。而隨著規(guī)劃環(huán)境的規(guī)模和復(fù)雜度增大,求解全局最優(yōu)路徑的計(jì)算量會(huì)急劇增加。此時(shí)精確算法難以在要求的時(shí)間內(nèi)得到滿意解,啟發(fā)式算法犧牲求解質(zhì)量換取求解速度,可以以一定概率在較短時(shí)間內(nèi)得到最優(yōu)解。用在路徑規(guī)劃領(lǐng)域的啟發(fā)式算法,主要包括A*算法及其變種算法[20-28]、快速進(jìn)行法(FM)[22]、隨機(jī)路圖法(PRM)[29]、快速擴(kuò)展隨機(jī)樹(shù)法(RRT)[30-39]等。

A*算法是比較經(jīng)典的啟發(fā)式尋路算法,是在Dijkstra算法基礎(chǔ)演化而來(lái)。Dijkstra算法在搜索下一個(gè)路徑點(diǎn)時(shí),僅僅考慮了該路徑點(diǎn)到起點(diǎn)的路徑最短,直到遍歷整個(gè)路徑網(wǎng)絡(luò),屬于盲目、遍歷式的搜索。A*算法加入了目標(biāo)點(diǎn)到當(dāng)前路徑點(diǎn)的距離估價(jià)代價(jià),綜合考慮從起點(diǎn)到當(dāng)前路徑點(diǎn)的距離G以及經(jīng)過(guò)該路徑點(diǎn)到達(dá)終點(diǎn)的距離H,以此來(lái)決定搜索的方向。A*算法中最關(guān)鍵部分是當(dāng)前路徑點(diǎn)到終點(diǎn)的距離估價(jià)代價(jià)函數(shù)H的設(shè)置,由于當(dāng)前路徑點(diǎn)到終點(diǎn)的路徑是未知的,因此該距離估計(jì)是有誤差的。當(dāng)H小于實(shí)際距離時(shí),A*算法可以通過(guò)搜索找到問(wèn)題最優(yōu)解,但是會(huì)搜索較多無(wú)用的節(jié)點(diǎn),H為0時(shí)類似于BPS算法;當(dāng)H大于實(shí)際距離時(shí),A*算法可以快速找到可行解,但有可能不是最優(yōu)解。A*算法的路徑尋優(yōu)能力和收斂速度是相互矛盾的。A*算法主要用于靜態(tài)柵格地圖的最優(yōu)路徑搜索,其改進(jìn)主要集中在兩個(gè)方面:提高搜索速度以及提高規(guī)劃路徑的可行性。目前提高搜索速度的方法有:使用曼哈頓距離和對(duì)角線距離作為代價(jià)函數(shù)H,引入決勝法來(lái)處理評(píng)價(jià)值相等的情況,以采樣的方式進(jìn)行跳躍點(diǎn)搜索,引入權(quán)值到距離估價(jià)函數(shù),雙向搜索等提高了搜索速度。

部分學(xué)者給出了很多代價(jià)函數(shù)H的設(shè)置方法,使用動(dòng)態(tài)加權(quán)方法,為代價(jià)函數(shù)H設(shè)置一個(gè)權(quán)值,當(dāng)不斷接近目標(biāo)位置時(shí),權(quán)值也不斷降低,這樣路徑實(shí)際代價(jià)的重要性相對(duì)提高,啟發(fā)式函數(shù)的不確定性相對(duì)降低。還有部分專家學(xué)者引入帶寬搜索的概念,限定了評(píng)價(jià)值的取值范圍,當(dāng)搜索點(diǎn)的評(píng)價(jià)值超出該取值范圍,那么該搜索點(diǎn)一定不在最優(yōu)路徑上,這樣加快了算法的搜索速度。文獻(xiàn)[20]設(shè)計(jì)了雙向搜索的A*算法,通過(guò)計(jì)算正向搜索點(diǎn)的G值、反向搜索點(diǎn)的G值以及兩個(gè)方向搜索點(diǎn)的距離估值H的和,可以確定最佳的搜索方向,直至兩個(gè)方向的搜索在中途相遇,即評(píng)價(jià)值不再增加。A*搜索算法一般和柵格法結(jié)合運(yùn)用,常見(jiàn)的A*算法變體在四宮格、九宮格或者十六宮格內(nèi)進(jìn)行搜索,路徑的平滑度和使用的搜索宮格的格子數(shù)量相關(guān),格子越多,搜索出來(lái)的路徑就越平滑。文獻(xiàn)[27]提出了Theta*算法,和原始的A*算法中頂點(diǎn)的父節(jié)點(diǎn)必須是相鄰頂點(diǎn)不同,它允許頂點(diǎn)的父節(jié)點(diǎn)是任意頂點(diǎn),從而擺脫了搜索宮格對(duì)路線平滑度的限制。Theta*算法需要完成大量的頂點(diǎn)是否相互可視的檢查工作,降低了搜索效率,后來(lái)部分學(xué)者又提出了Lazy Theta*算法,減少了頂點(diǎn)相互可視的檢查次數(shù)。由于動(dòng)態(tài)地圖環(huán)境建模導(dǎo)致節(jié)點(diǎn)發(fā)生變化,A*算法一般用于靜態(tài)地圖的搜索?；贏*算法的改進(jìn)動(dòng)態(tài)搜索算法D*算法[24]可以適應(yīng)動(dòng)態(tài)變化的地圖,進(jìn)一步地終身規(guī)劃A*算法可以重復(fù)利用之前的A*計(jì)算來(lái)產(chǎn)生新的路徑,但是兩種算法需要一定的計(jì)算儲(chǔ)存空間的支持。

快速擴(kuò)展隨機(jī)樹(shù)法應(yīng)用也較為廣泛,是一種常見(jiàn)的用于運(yùn)動(dòng)規(guī)劃的方法,由LaValle在1998年提出[30-31]。其基本原理是在工作空間中存在一個(gè)起始點(diǎn),先在工作空間中隨機(jī)選定一個(gè)點(diǎn)并連接起始點(diǎn)和隨機(jī)點(diǎn),若連線與障礙物不相交,那么該連線確定一個(gè)可行方向,機(jī)動(dòng)平臺(tái)可以沿著該方向前進(jìn)一步,到達(dá)一個(gè)新的位置點(diǎn)。那么,這個(gè)新的位置點(diǎn)和初始點(diǎn)以及其連線構(gòu)成了一棵簡(jiǎn)單的樹(shù)。在這棵樹(shù)的基礎(chǔ)上,繼續(xù)在工作空間中隨機(jī)選定一個(gè)點(diǎn),然后在已經(jīng)確定的樹(shù)上找到距離該隨機(jī)點(diǎn)最近的點(diǎn)并將二者連線。若連線不與障礙物相交,那么該連線確定了下一步的可行方向,機(jī)動(dòng)平臺(tái)沿著可行方向到達(dá)新的位置,該位置可以被添加到已經(jīng)確定的樹(shù)上,以此類推,直到目標(biāo)點(diǎn)被添加到樹(shù)上。

隨機(jī)性和運(yùn)算的復(fù)雜性是制約該算法應(yīng)用的兩個(gè)主要問(wèn)題。工作空間中選點(diǎn)的隨機(jī)性導(dǎo)致相同環(huán)境下規(guī)劃結(jié)果的不同。該算法是概率完備的,但是由于選點(diǎn)是隨機(jī)的,在起點(diǎn)和目標(biāo)點(diǎn)之間確定一條可行路線的時(shí)間是不確定的,這給算法的實(shí)際應(yīng)用帶來(lái)困難。影響RRT算法性能的主要因素有:隨機(jī)節(jié)點(diǎn)個(gè)數(shù),樹(shù)擴(kuò)展的軌跡段長(zhǎng)度,隨機(jī)節(jié)點(diǎn)產(chǎn)生的概率分布擴(kuò)展樹(shù)的個(gè)數(shù)。已經(jīng)有專家學(xué)者對(duì)算法進(jìn)行改進(jìn),形成了一些改進(jìn)版本的RRT算法。文獻(xiàn)[32-33]提出了帶有目標(biāo)偏向思想的RRT算法,通過(guò)隨機(jī)函數(shù)加參數(shù)來(lái)生成局部目標(biāo)點(diǎn),以一定概率用目標(biāo)點(diǎn)作為牽引點(diǎn),解決原始RRT算法中擴(kuò)展節(jié)點(diǎn)方式過(guò)于平均、隨機(jī)性大的問(wèn)題。文獻(xiàn)[34]提出了雙向搜索的改進(jìn)RRT算法,分別以初始點(diǎn)和目標(biāo)點(diǎn)作為根節(jié)點(diǎn)進(jìn)行擴(kuò)展,直到兩棵樹(shù)連接在一起,提高了搜索效率。文獻(xiàn)[35]和文獻(xiàn)[36]分別通過(guò)限制采樣概率和采樣節(jié)點(diǎn)提高工作空間中采點(diǎn)的質(zhì)量。文獻(xiàn)[37]將RRT算法和Parti-game方法結(jié)合起來(lái),在例如障礙物附件等需要的地方細(xì)化搜索,以便能更快速地給出規(guī)劃方案。文獻(xiàn)[38]則將Theta*算法和RRT算法結(jié)合,使用路徑優(yōu)化和智能采樣相結(jié)合的方式來(lái)加快RRT算法的收斂速率。文獻(xiàn)[39]則將A*算法和RRT算法相結(jié)合,在第一層使用A*算法進(jìn)行大尺度的規(guī)劃,然后在第二層使用RRT算法進(jìn)行小尺度規(guī)劃,將啟發(fā)式思想引入到RRT算法中改善規(guī)劃的效果。

2.3 智能搜索算法

智能算法是在自然規(guī)律的啟發(fā)下,根據(jù)其原理模擬求解問(wèn)題的算法,也稱元啟發(fā)式算法。元啟發(fā)式算法結(jié)合了啟發(fā)式算法和隨機(jī)算法,其解決問(wèn)題的思路一般是:1)生成一組候選解;2)設(shè)置適應(yīng)性函數(shù)計(jì)算這些候選解的適應(yīng)度;3)根據(jù)適應(yīng)度閾值保留符合條件的候選解;4)對(duì)保留的候選解進(jìn)行操作以生成一組新的候選解。這方面內(nèi)容有很多,如禁忌搜索算法、模擬退火算法、人工免疫算法、人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法、粒子群算法、人工魚(yú)群、人工蜂群等。由于具有全局尋優(yōu)能力,這些智能算法被廣泛用于路徑規(guī)劃領(lǐng)域。

遺傳算法是應(yīng)用最廣泛的智能搜索算法,算法將候選解看作染色體,對(duì)染色體進(jìn)行交叉、變異、選擇等操作,經(jīng)過(guò)有限次的遺傳得到符合條件的染色體，即問(wèn)題的解。粒子群算法[40]同遺傳算法類似,初始化粒子群隨機(jī)解,通過(guò)迭代尋找最優(yōu)值,但是沒(méi)有交叉變異等操作,而是在解空間中追尋最優(yōu)解。同時(shí),粒子群算法由于不像遺傳染色體那樣粒子之間共享信息,只有全局最優(yōu)粒子發(fā)布信息給其他粒子,因此收斂速度要優(yōu)于遺傳算法。

遺傳算法的優(yōu)點(diǎn)是具有強(qiáng)大的自組織學(xué)習(xí)能力、容錯(cuò)能力以及隱含的并行性,遺傳進(jìn)程以適應(yīng)度為導(dǎo)向,對(duì)問(wèn)題的依賴性較弱[41]。同時(shí),遺傳算法存在運(yùn)算規(guī)模大、前期易陷入局部極小,后期收斂速度慢等問(wèn)題[42]。遺傳算法的改進(jìn)一般著眼于種群初始化、染色體編碼方式、適應(yīng)度函數(shù)結(jié)構(gòu)、遺傳算子結(jié)構(gòu)等四個(gè)方面。劉佳男[43]使用浮點(diǎn)數(shù)編碼代替常用的二進(jìn)制編碼,提高了運(yùn)算精度和效率。針對(duì)傳統(tǒng)遺傳算法隨機(jī)初始化種群導(dǎo)致路徑質(zhì)量不高的問(wèn)題,文獻(xiàn)[41]引入勢(shì)場(chǎng)力的思想為遺傳算法初始化種群,文獻(xiàn)[43-44]采用了啟發(fā)式方法降低種群初始化的隨機(jī)性。文獻(xiàn)[45]在種群初始化時(shí),事先將障礙物從規(guī)劃空間中剔除,提高了算法的全局收斂速度。趙媛[45]根據(jù)動(dòng)靜態(tài)路徑規(guī)劃的不同分別設(shè)計(jì)了動(dòng)態(tài)和靜態(tài)適應(yīng)度函數(shù),張毅等[46]在設(shè)計(jì)適應(yīng)度函數(shù)考慮了路徑最短和障礙物規(guī)避兩個(gè)要求,文獻(xiàn)[44,47]進(jìn)一步考慮了路徑平滑度這一因素。遺傳算子的改進(jìn)傾向于自適應(yīng)函數(shù)的設(shè)計(jì),使其能和種群適應(yīng)度交互,降低陷入局部極小的概率,提高全局收斂能力。文獻(xiàn)[43,45-46]在傳統(tǒng)遺傳算子的基礎(chǔ)上引入了刪除、平滑和插入(修復(fù))算子,文獻(xiàn)[41]則提出了種群熵的概念以及染色體自適應(yīng)度排序分組的策略,設(shè)計(jì)了自適應(yīng)的選擇、交叉和變異算子,提高了規(guī)劃路徑的質(zhì)量。

另一種比較常用的智能算法是蟻群算法,它模擬螞蟻覓食的過(guò)程,是一個(gè)群體性行為。螞蟻在尋找食物時(shí),會(huì)在道路上釋放一種信息素,而且可以感受到其余螞蟻釋放的信息素。信息素濃度大小代表著距離的遠(yuǎn)近,信息素濃度越高,表示距離越近。通常螞蟻以較大的概率優(yōu)先選擇信息素濃度較大的路徑,并且釋放信息素以提高該路徑上的信息素濃度,由此形成一個(gè)正反饋。最終,螞蟻找到一條從巢穴到食物的最短路徑。將蟻群思想應(yīng)用于路徑規(guī)劃,即用螞蟻的行走路徑作為待優(yōu)化問(wèn)題的可行解,整個(gè)螞蟻群體的所有路徑構(gòu)成待優(yōu)化問(wèn)題的解空間。按照螞蟻覓食的思想,最終得到一條從起始點(diǎn)到目的地的最短路徑。蟻群算法的缺陷是:1)前期各條路徑上信息素分布為固定值,導(dǎo)致搜索具有盲目性;2)后期各條路徑上信息索的積累,導(dǎo)致后續(xù)搜索路徑不一定是全局最優(yōu)路徑。文獻(xiàn)[48]將勢(shì)場(chǎng)概念引入信息素?cái)U(kuò)散模型,提高了算法的動(dòng)態(tài)規(guī)劃能力。文獻(xiàn)[49-50]對(duì)比了遺傳算法和蟻群算法的收斂性,利用遺傳算法初始種群隨機(jī)性強(qiáng)的特點(diǎn),為蟻群算法的生成初始信息素分布,降低蟻群算法前期搜索的盲目性。文獻(xiàn)[50-51]將遺傳算子引入蟻群算法,抑制蟻群算法后期陷入局部極小。

融合智能算法也表現(xiàn)出不錯(cuò)的性能,如文獻(xiàn)[44]將遺傳算法和柵格法結(jié)合,便于根據(jù)實(shí)際位置坐標(biāo)進(jìn)行染色體編碼;文獻(xiàn)[40,52]將遺傳算子分別引入粒子群算法和蟻群算法,降低兩種算法陷入局部極小的概率;文獻(xiàn)[53]將遺傳算法和B樣條曲線函數(shù)結(jié)合,提高規(guī)劃路線的平滑度和可行性;文獻(xiàn)[54]將人工免疫算法分別引入遺傳算法和蟻群算法,抑制算法“早熟”等。

3 基于場(chǎng)建模的軌跡規(guī)劃

3.1 人工勢(shì)場(chǎng)法

基于場(chǎng)建模的軌跡規(guī)劃是將無(wú)人艇工作空間的障礙物轉(zhuǎn)化為“場(chǎng)”,一般通過(guò)研究無(wú)人艇在這些場(chǎng)中的受力情況來(lái)規(guī)劃航向。Khatib在1986年提出了人工勢(shì)場(chǎng)法[55],它的基本思想是在機(jī)器人周圍設(shè)計(jì)一種類似于電場(chǎng)的勢(shì)場(chǎng),機(jī)器人的運(yùn)動(dòng)依靠勢(shì)場(chǎng)力進(jìn)行驅(qū)動(dòng)。障礙物對(duì)機(jī)器人產(chǎn)生“斥力”,目標(biāo)對(duì)機(jī)器人產(chǎn)生“引力”,障礙物斥力和目標(biāo)引力的矢量和是機(jī)器人所受的合力,合力的方向即機(jī)器人下一步的運(yùn)動(dòng)方向。該方法由于數(shù)學(xué)原理簡(jiǎn)單、計(jì)算速度快、硬件要求低,被廣泛應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃。

人工勢(shì)場(chǎng)法將局部環(huán)境轉(zhuǎn)化為勢(shì)場(chǎng),雖然勢(shì)場(chǎng)函數(shù)是連續(xù)的,但是由于環(huán)境中障礙物的不確定性,無(wú)人艇受到的勢(shì)場(chǎng)力變化是不連續(xù)的。同時(shí)由于勢(shì)場(chǎng)中引力和斥力同時(shí)作用于無(wú)人艇,勢(shì)場(chǎng)中可能存在受力平衡點(diǎn),此時(shí)算法無(wú)法給出無(wú)人艇的下一步規(guī)劃航向。因此人工勢(shì)場(chǎng)法主要存在以下四方面缺陷。

1)受力平衡問(wèn)題

當(dāng)無(wú)人艇靠近障礙物時(shí),受到障礙物斥力勢(shì)場(chǎng)的作用,且距離障礙物越近受到的勢(shì)場(chǎng)斥力越大。同時(shí),無(wú)人艇還受到目標(biāo)點(diǎn)的引力作用,且距離目標(biāo)點(diǎn)越遠(yuǎn),受到的引力越強(qiáng)。當(dāng)引斥力的合力與引力的夾角為斥角時(shí),無(wú)人艇規(guī)劃的航向有較大角度的變化。當(dāng)引力和斥力二者共線且合力為0時(shí),無(wú)人艇所在位置稱為全局極小點(diǎn),在該點(diǎn)處算法無(wú)法給出規(guī)劃航向,無(wú)人艇提前停車或者航向“震蕩”。

針對(duì)全局極小問(wèn)題,前面的研究者給出了很多改進(jìn)方法[56-60]。第一類方法是從算法層面進(jìn)行改進(jìn),基本原理是根據(jù)全局極小點(diǎn)的特征判定無(wú)人艇陷入全局極小,然后利用其他方法引導(dǎo)無(wú)人艇離開(kāi)全局極小點(diǎn),當(dāng)判定無(wú)人艇已經(jīng)脫離全局極小點(diǎn)后繼續(xù)利用人工勢(shì)場(chǎng)法進(jìn)行規(guī)劃。無(wú)人艇隨機(jī)行走、目標(biāo)點(diǎn)在一定范圍內(nèi)隨機(jī)生成、水流法、斥力偏轉(zhuǎn)、沿墻走、和其他方法結(jié)合設(shè)置子目標(biāo)點(diǎn)(VFH、A*、遺傳算法、隨機(jī)路圖法PRM、快速擴(kuò)展隨機(jī)樹(shù)法RRT等)。顯然,這些方法僅僅是在局部層面上進(jìn)行算法的改進(jìn),其應(yīng)用范圍是有限的。系統(tǒng)輸入的信息規(guī)模沒(méi)有改變,當(dāng)無(wú)人艇遇到的障礙物尺寸大于無(wú)人艇局部工作空間的尺寸時(shí),這些算法不能給出有效的解決方案。第二類方法是引入全局信息,改變系統(tǒng)輸入的信息規(guī)模。相比局部規(guī)劃的實(shí)時(shí)性,全局規(guī)劃時(shí)生成路徑的安全性和最優(yōu)性是首要考慮的目標(biāo)。因此將人工勢(shì)場(chǎng)法應(yīng)用于無(wú)人艇任務(wù)起點(diǎn)和終點(diǎn)之間的矩形區(qū)域,可以提前確定全局極小點(diǎn)的位置并進(jìn)行規(guī)避。在進(jìn)行局部規(guī)劃時(shí),根據(jù)全局規(guī)劃信息的指導(dǎo),無(wú)人艇可以成功避開(kāi)這些全局極小點(diǎn)。

2)目標(biāo)不可達(dá)問(wèn)題

目標(biāo)不可達(dá)問(wèn)題實(shí)質(zhì)上也是一類受力平衡問(wèn)題[58]。當(dāng)目標(biāo)點(diǎn)周圍有障礙物時(shí),障礙物處的斥力勢(shì)場(chǎng)值較高,而目標(biāo)點(diǎn)處的引力勢(shì)場(chǎng)值較低,經(jīng)過(guò)勢(shì)場(chǎng)疊加后在目標(biāo)點(diǎn)周圍存在勢(shì)場(chǎng)值高點(diǎn)。無(wú)人艇需要跨越這些勢(shì)場(chǎng)高點(diǎn)才能到達(dá)目標(biāo)點(diǎn)。按照勢(shì)場(chǎng)梯度下降的規(guī)劃原理,無(wú)人艇無(wú)法到達(dá)目標(biāo)點(diǎn)。

針對(duì)目標(biāo)不可達(dá)問(wèn)題,比較常見(jiàn)的改進(jìn)方法是修改勢(shì)場(chǎng)函數(shù)。部分專家學(xué)者將無(wú)人艇和目標(biāo)點(diǎn)的距離引入到斥力勢(shì)場(chǎng)函數(shù)中,斥力隨著機(jī)器人到目標(biāo)點(diǎn)距離縮小而減小,同時(shí)增加了一個(gè)由機(jī)器人指向目標(biāo)點(diǎn)的分力,該模型理論上可以解決目標(biāo)點(diǎn)不可達(dá)的問(wèn)題。

3)狹窄通道內(nèi)航向抖動(dòng)問(wèn)題

當(dāng)無(wú)人艇在較為狹窄的通道內(nèi)航行時(shí),周圍障礙物和無(wú)人艇的距離較近,因此斥力的方向變化對(duì)障礙物的位置改變比較敏感。尤其是在狹窄通道內(nèi)側(cè)邊緣不平滑的情況下,無(wú)人艇受到的勢(shì)場(chǎng)斥力的方向變化較為劇烈,導(dǎo)致最終規(guī)劃的航向抖動(dòng)比較明顯。顯然,這種頻繁大角度變化的規(guī)劃航向,對(duì)機(jī)動(dòng)性相對(duì)較差的無(wú)人平臺(tái)而言,是難以執(zhí)行的[60]。

針對(duì)狹窄通道內(nèi)航向抖動(dòng)的問(wèn)題,可以對(duì)算法規(guī)劃的航向進(jìn)行濾波,減小算法輸出的航向抖動(dòng)的幅度;部分學(xué)者將人工勢(shì)場(chǎng)法和向量場(chǎng)直方圖法結(jié)合,當(dāng)無(wú)人艇當(dāng)前航向被障礙物遮擋時(shí)調(diào)整航向至可行方向,當(dāng)無(wú)人艇當(dāng)前航向不受障礙物遮擋時(shí)減小航向的調(diào)整幅度。還有的學(xué)者從障礙物入手,在進(jìn)行障礙物建模的時(shí)候利用圖形學(xué),使狹窄通道內(nèi)側(cè)更平滑,有利于算法輸出小幅度變化的航向。

打擊侵權(quán)假冒工作是一個(gè)系統(tǒng)工程，涉及部門(mén)多、工作面廣，需要高位統(tǒng)籌，做好頂層規(guī)劃和制度設(shè)計(jì)，理順工作體制機(jī)制，突出司法威懾作用，借助大數(shù)據(jù)網(wǎng)絡(luò)技術(shù)，構(gòu)建協(xié)同共治新局面。

4)復(fù)雜環(huán)境中不能確定有效通道問(wèn)題

人工勢(shì)場(chǎng)法計(jì)算無(wú)人艇受到的總斥力時(shí),考慮到每個(gè)障礙物與無(wú)人艇之間的距離信息以及障礙物與無(wú)人艇之間的相對(duì)位置關(guān)系。但是在計(jì)算總斥力時(shí),算法給出的只是障礙物的一般趨向,即障礙物少的方向,這個(gè)趨向程度是由斥力增益系數(shù)決定的。當(dāng)環(huán)境中的障礙物分布較為復(fù)雜時(shí),尤其是有效通道較為狹窄且隱藏在障礙物群中時(shí),人工勢(shì)場(chǎng)法通常不能發(fā)現(xiàn)有效通道[61]。

針對(duì)復(fù)雜環(huán)境中尋找有限通道的問(wèn)題,部分學(xué)者使用了啟發(fā)式的算法,如A*、Theta*等算法來(lái)搜索可行路徑;部分學(xué)者利用快速擴(kuò)展隨機(jī)樹(shù)法(RRT)來(lái)尋找有效路徑,該方法不需要進(jìn)行環(huán)境建模,且搜索的速度較快。

3.2 流函數(shù)法

將流體力學(xué)中的理想流體概念引入路徑規(guī)劃中的流函數(shù)法,是近些年出現(xiàn)的新算法。流函數(shù)法是基于流函數(shù)給出一條平滑的規(guī)劃航線,和人工勢(shì)場(chǎng)法類似,也是基于障礙物位置的規(guī)劃方法。在無(wú)人艇的工作空間中引入某種流場(chǎng),根據(jù)流體力學(xué)的知識(shí)可以得到其勢(shì)函數(shù),之后在初始流場(chǎng)中加入障礙物,通過(guò)建立障礙物的流場(chǎng)并與原勢(shì)場(chǎng)疊加即可得到總的流場(chǎng),對(duì)勢(shì)函數(shù)求導(dǎo)即得流場(chǎng)中各處的流速,對(duì)流速積分所得流體的流線就是為無(wú)人艇規(guī)劃出的航路,如圖1所示。

圖1 圓柱無(wú)環(huán)量繞流示意圖

流函數(shù)法解決了人工勢(shì)場(chǎng)法中的全局極小問(wèn)題,規(guī)劃出的路線符合流體原理,因此航向變化相對(duì)平滑。但是流函數(shù)法也有缺陷,即引入了“滯點(diǎn)”問(wèn)題,如圖1中的點(diǎn)A和點(diǎn)B。在這兩個(gè)點(diǎn)處,流函數(shù)法無(wú)法給出正確的航向。文獻(xiàn)[62]研究了雙障礙物重疊引起的“滯點(diǎn)”問(wèn)題,并提出了虛擬目標(biāo)法繞過(guò)“滯點(diǎn)”;同時(shí),將無(wú)人艇的性能引入流函數(shù)法模型中,提高了繞行“滯點(diǎn)”的規(guī)劃路線的可行性。文獻(xiàn)[63]分別引入了均勻流和sink流,推導(dǎo)了無(wú)人艇的軌跡方程;同時(shí),利用沿墻走的方法解決“滯點(diǎn)”問(wèn)題,并將流函數(shù)法應(yīng)用在多障礙物的避碰規(guī)劃中。文獻(xiàn)[64]在研究編隊(duì)運(yùn)動(dòng)控制時(shí),引入了流函數(shù)法,解決了編隊(duì)中機(jī)器人之間的相互避碰問(wèn)題。

4 軌跡規(guī)劃未來(lái)發(fā)展方向

路徑規(guī)劃領(lǐng)域的一些主流算法提出時(shí)間如表1所示。

表1 算法發(fā)展脈絡(luò)

可以看出,自從遺傳算法提出以來(lái),對(duì)于群智能算法的探索從未停止,這些算法大都受到自然界的生物群繁衍的啟發(fā)。這些新的算法在解決問(wèn)題的維度、求解效率、解的完備性等方面不斷改進(jìn)。對(duì)于啟發(fā)式算法A*算法和RRT算法的探測(cè)和改進(jìn)也從未停止,由于啟發(fā)式算法能夠犧牲較小的時(shí)間消耗快速得到較優(yōu)解,對(duì)于解決大型復(fù)雜靜態(tài)問(wèn)題效果會(huì)更加突出。

1)全局路徑規(guī)劃和局部路徑規(guī)劃相結(jié)合

全局路徑規(guī)劃提供粗線條的規(guī)劃,局部路徑規(guī)劃提供更為精確的避碰規(guī)劃,一定程度上降低了全局規(guī)劃的計(jì)算復(fù)雜度,同時(shí)解決了局部規(guī)劃固有的局部極小問(wèn)題。

2)多種智能算法的融合

根據(jù)前文分析可知,每一種算法的基本模型都是在一定的假設(shè)情況下提出的,隨著應(yīng)用環(huán)境的改變,算法的不足就會(huì)凸顯出來(lái)。單一算法很難使解決問(wèn)題的某一項(xiàng)指標(biāo)有質(zhì)的變化,而多種算法之間卻可以揚(yáng)長(zhǎng)避短、優(yōu)勢(shì)互補(bǔ),最終達(dá)到理想的效果。

3)規(guī)劃路徑時(shí),考慮環(huán)境信息的影響

目前對(duì)于軌跡規(guī)劃的研究,大多仍停留在算法階段,能否經(jīng)得起實(shí)際平臺(tái)的檢驗(yàn)是未知的。因此在研究無(wú)人艇路徑規(guī)劃時(shí),有必要同時(shí)研究海上環(huán)境信息的變化。風(fēng)、浪、流等天氣氣候信息的變化規(guī)律,以及它們是如何影響船的航向航速的,這都是需要深入探討的問(wèn)題。

4)從控制的角度,研究規(guī)劃路徑的可行性,形成反饋

同第三點(diǎn)類似,現(xiàn)在的算法規(guī)劃出的路線過(guò)于理想,實(shí)際海上航行時(shí)這些路線很可能無(wú)法被無(wú)人艇執(zhí)行,導(dǎo)致規(guī)劃失敗。根本原因是,算法并未將無(wú)人艇的機(jī)動(dòng)性能和控制系統(tǒng)調(diào)節(jié)能力考慮進(jìn)去,算法如何和控制系統(tǒng)聯(lián)結(jié)起來(lái)并形成反饋控制也需要深入研究。

5 結(jié)束語(yǔ)

軌跡規(guī)劃問(wèn)題的研究,是無(wú)人艇海上平臺(tái)研究的一個(gè)重要課題,對(duì)于無(wú)人艇的智能無(wú)人駕駛至關(guān)重要。本文從基于可視圖法和單元分解的搜索規(guī)劃、基于場(chǎng)建模的軌跡規(guī)劃兩大方面,對(duì)應(yīng)用到軌跡規(guī)劃問(wèn)題中的算法技術(shù)以及其未來(lái)的發(fā)展進(jìn)行了系統(tǒng)的總結(jié)和評(píng)價(jià),對(duì)當(dāng)前無(wú)人艇海上航行路徑規(guī)劃的研究與發(fā)展具有一定的參考價(jià)值。