水面無(wú)人艇冗余路徑點(diǎn)約減方法研究
——基于最優(yōu)路徑代價(jià)估計(jì)

溫乃峰，劉冠群，于海洋，張汝波

(大連民族大學(xué) a.機(jī)電工程學(xué)院；b.智能感知與先進(jìn)控制國(guó)家民委重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116605)

水面無(wú)人艇冗余路徑點(diǎn)約減方法研究
——基于最優(yōu)路徑代價(jià)估計(jì)

溫乃峰a,b，劉冠群a,b，于海洋a,b，張汝波a,b

(大連民族大學(xué) a.機(jī)電工程學(xué)院；b.智能感知與先進(jìn)控制國(guó)家民委重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116605)

針對(duì)復(fù)雜海洋環(huán)境下USV在線路徑規(guī)劃問(wèn)題，提出一種順序-隨機(jī)兩模式的冗余路徑點(diǎn)約減方法。利用估計(jì)通過(guò)路徑點(diǎn)的最優(yōu)路徑來(lái)制定其被約減的概率，并通過(guò)概率值的自適應(yīng)變化考慮更多路徑點(diǎn)的組合方案。采用順序方法控制隨機(jī)約減范圍，快速發(fā)現(xiàn)潛在的優(yōu)化路徑。在約減過(guò)程中考慮海流等復(fù)雜海況對(duì)USV運(yùn)動(dòng)的影響，從而降低USV的碰撞概率。實(shí)驗(yàn)結(jié)果表明，本文方法可有效地簡(jiǎn)化并優(yōu)化USV路徑。

水面無(wú)人艇；路徑簡(jiǎn)化；冗余路徑點(diǎn)約減；海流信息處理；隨機(jī)化方法

Abstract:To solve the online USV path planning problem in complex ocean environment, we propose a two-mode redundant waypoints pruning method containing the sequential and probabilistic pruning modes. Regarding the problems of the path simplification as well as path optimization, an estimation method of the optimal path passing through a waypoint is raised to calculate the pruned probabilities of waypoints. At the same time, the pruned probabilities are changed adaptively to consider more waypoints combinations of a path to find a potentially better path. To reduce the pruning time, the scale of the probabilistic pruning process is constrained by the sequential pruning process. The influence caused by the complex sea state, such as current, is considered during the pruning process to decrease the collision probability of USV. The experimental results show that our method is better than the traditional methods in simplifying and optimizing USV paths.

Keywords:unmanned surface vehicle(USV); path simplification; redundant waypoints pruning; current information processing; randomized method

海洋環(huán)境瞬息多變，水面無(wú)人艇( Unmanned Surface Vehicle, USV)必須具有在線路徑規(guī)劃能力。由于時(shí)間有限，通常采用啟發(fā)式快速路徑規(guī)劃方法，造成路徑上冗余路徑點(diǎn)和拐點(diǎn)較多，路徑較曲折[1]。為了提高路徑的平順度，減少路徑上的拐點(diǎn)，以進(jìn)一步提高路徑的優(yōu)化性并降低跟蹤的難度，需要對(duì)局部路徑進(jìn)行后期簡(jiǎn)化處理，在線約減冗余路徑點(diǎn)[2-3]。USV的運(yùn)動(dòng)能力和載荷能力有限[4]，此時(shí)冗余路徑點(diǎn)的約減對(duì)提高任務(wù)執(zhí)行的效率和成功率非常重要。在線時(shí)間有限，要求冗余路徑點(diǎn)約減方法必須高效。在約減過(guò)程中需要綜合考慮路徑執(zhí)行時(shí)間、能耗以及路徑與海流、障礙物、渦流區(qū)的關(guān)系，以保證路徑的優(yōu)化性和USV運(yùn)動(dòng)的安全性。約減結(jié)果不應(yīng)與原始路徑差異過(guò)大，以免過(guò)多丟失原始路徑的優(yōu)點(diǎn)。

1 研究現(xiàn)狀

基于最優(yōu)化方法的冗余路徑點(diǎn)約減過(guò)程復(fù)雜度高，收斂慢，不能滿足復(fù)雜運(yùn)動(dòng)的約束條件，難以應(yīng)用于在線路徑規(guī)劃。針對(duì)這個(gè)問(wèn)題，有研究人員提出了增量式快速約減方法(Incrementally Fast Pruning，IFP)、順序約減方法(Sequential Pruning，SP)[5]和捷徑法(Shortcut)[6]等典型快速約減方法。

傳統(tǒng)SP方法順序執(zhí)行約減過(guò)程，初始條件下，將原始路徑點(diǎn)集{n1,n2,…,nN}按順序排列，令約減結(jié)果Np=Φ，當(dāng)前約減路徑點(diǎn)下標(biāo)j=1。循環(huán)執(zhí)行如下過(guò)程：將nj移入路徑點(diǎn)集合Sp，令i=j+2，若nj與ni間存在無(wú)碰撞路徑，且該路徑段滿足USV運(yùn)動(dòng)約束條件，則繼續(xù)當(dāng)前約減循環(huán)，i=i+1；否則，令j=i-1并重新開(kāi)始約減循環(huán)；順序約減直至路徑末端點(diǎn)。

Shortcut方法在全路徑范圍內(nèi)隨機(jī)選擇路徑點(diǎn)對(duì)，并嘗試用點(diǎn)對(duì)間直線路徑代替原路徑。隨機(jī)選取過(guò)程可以保持約減過(guò)程的隨機(jī)性和多樣性，有助于找到SP方法無(wú)法發(fā)現(xiàn)的潛在的更優(yōu)結(jié)果。但Shortcut方法路徑點(diǎn)對(duì)的選擇過(guò)程完全隨機(jī)，難以全面地考慮路徑的可行性和易行性，因此一些學(xué)者采用啟發(fā)式方法選擇點(diǎn)對(duì)，從而在約減過(guò)程中降低路徑代價(jià)，本文借用這種思想設(shè)計(jì)隨機(jī)約減過(guò)程。

為了提高USV的安全性，需要考慮海流對(duì)USV運(yùn)動(dòng)造成的偏差。通常采用障礙物膨脹法、誤差走廊法及幾何化方法，通過(guò)擴(kuò)大路徑與障礙物的間隔來(lái)降低碰撞概率。在環(huán)境建模過(guò)程中，向外擴(kuò)充障礙物邊界，或?yàn)槁窂皆O(shè)定寬度值，寬度值根據(jù)USV運(yùn)動(dòng)特性和實(shí)時(shí)參數(shù)設(shè)定[7]。也有文獻(xiàn)對(duì)規(guī)劃環(huán)境進(jìn)行幾何化處理，并在無(wú)碰空間的中軸線上規(guī)劃路徑，以追求路徑與障礙物間隔最大化的目標(biāo)，其中典型的方法包括泰森多邊形方法和回退法。

泰森多邊形方法需要對(duì)障礙物進(jìn)行幾何化預(yù)處理，為障礙物頂點(diǎn)劃分泰森多邊形，然后在各泰森多邊形頂點(diǎn)處尋找路徑點(diǎn)。但對(duì)空間預(yù)處理需要已知的環(huán)境信息且構(gòu)建泰森多邊形的時(shí)空復(fù)雜度高[8]，不適合在線路徑規(guī)劃問(wèn)題?；赝朔╗9]的流程：尋找路徑點(diǎn)ni與障礙物距離最近的點(diǎn)oi；沿nioi矢量方向移動(dòng)ni，直到oi與其它障礙物更近。

2 運(yùn)動(dòng)偏差處理

約減過(guò)程中海流對(duì)USV的運(yùn)動(dòng)產(chǎn)生影響，由于在線規(guī)劃時(shí)間有限，對(duì)運(yùn)動(dòng)偏差處理方法的效率要求較高。幾何化方法要求對(duì)環(huán)境精確建模，使得它的計(jì)算較復(fù)雜，水下先驗(yàn)環(huán)境信息通常帶有未知性和動(dòng)態(tài)性，難以預(yù)先構(gòu)建精確環(huán)境模型。而且?guī)缀位椒ㄖ皇菃渭兊脑黾勇窂脚c障礙物的間隔，未考慮海流信息，可能會(huì)造成間隔不合理。不僅額外增加了路徑長(zhǎng)度，還可能使路徑距海流流向上的障礙物更近，增加了碰撞概率。

本文由啟發(fā)式快速擴(kuò)展隨機(jī)樹(shù)方法規(guī)劃初始路徑，通過(guò)碰撞檢測(cè)技術(shù)避免對(duì)環(huán)境的精確建模，采用誤差走廊法增加路徑與障礙物間距離。估計(jì)海流造成的運(yùn)動(dòng)偏差距離為σt·Vc·sinαy，其中，σt為USV控制的時(shí)間節(jié)拍，Vc為海流流速，αy為海流方向與路徑方向或USV運(yùn)動(dòng)方向的夾角。這里，USV的運(yùn)動(dòng)方向主要指它的偏航方向。

利用線性二次型高斯運(yùn)動(dòng)規(guī)劃方法[10]近似地估計(jì)USV在路徑上無(wú)碰撞的概率下限值pc。假設(shè)USV的位置服從n元高斯分布，那么，USV在某一路徑點(diǎn)qi處無(wú)碰概率可近似為：Γ (n/2,Cq2/2) ，Γ為標(biāo)準(zhǔn)伽瑪分布函數(shù)，Cq是根據(jù)USV與障礙物間最近距離和由海流造成的USV位置偏差的標(biāo)準(zhǔn)差δq計(jì)算得出的USV可偏離路徑且無(wú)碰的位置分布標(biāo)準(zhǔn)差。

定義路徑質(zhì)量如下：路徑段π的質(zhì)量Q(π)為USV跟蹤π時(shí)的無(wú)碰概率，它等于USV在π上所有的nw個(gè)路徑點(diǎn)處的pc值的乘積，nw=10，如式(1)。通過(guò)在路徑規(guī)劃和簡(jiǎn)化過(guò)程中保證結(jié)果路徑段的質(zhì)量大于某閾值，來(lái)考慮USV自身的運(yùn)動(dòng)偏差和海流造成的偏差。

(1)

3 基于最優(yōu)路徑代價(jià)估計(jì)的冗余路徑點(diǎn)約減

為了快速地約減冗余路徑點(diǎn)并進(jìn)一步優(yōu)化路徑，本文結(jié)合SP方法和Shortcut法，提出基于估計(jì)最優(yōu)路徑代價(jià)的冗余路徑點(diǎn)約減方法(Optimal Path Cost Estimation based Redundant Waypoints Pruning Method，CEP)。CEP方法參照Shortcut方法制定了一種啟發(fā)式隨機(jī)約減方式，為了在隨機(jī)約減過(guò)程中考慮路徑的代價(jià)和易行性問(wèn)題，估計(jì)通過(guò)路徑點(diǎn)的最優(yōu)路徑代價(jià)，并根據(jù)代價(jià)計(jì)算約減路徑點(diǎn)的概率，同時(shí)根據(jù)中間路徑結(jié)果的代價(jià)自適應(yīng)改變各路徑點(diǎn)被約減概率。規(guī)定只有當(dāng)路徑代價(jià)由于約減而降低時(shí)，約減才會(huì)發(fā)生，以此保證結(jié)果路徑收斂于更優(yōu)的結(jié)果。為了彌補(bǔ)Shortcut方法收斂慢的缺點(diǎn)，CEP方法基于SP方法的順序約減過(guò)程來(lái)縮小隨機(jī)約減規(guī)模，只在前次順序約減的終點(diǎn)之后到路徑末端點(diǎn)的范圍內(nèi)進(jìn)行隨機(jī)約減。

定義路徑點(diǎn)間的代價(jià)距離(Cost Distance，CD)：

CD(qi,qj)=Dγ1·D(qi,qj)+Dγ2·Ya-Dγ3·Vc·cosαy+Dγ4·Vc·sinαy+Dγ5·Tt。

(2)

式中，權(quán)值Dγ1+Dγ2+Dγ3+Dγ4+Dγ5=1；Vc為海流速度；αy∈[0,π]為海流方向與路徑方向夾角。Vc·cosαy為逆流能耗指示變量，當(dāng)αy<π/2時(shí)，海流對(duì)USV運(yùn)動(dòng)具有推動(dòng)作用；當(dāng)π/2<αy≤π時(shí)，逆向海流增加USV能耗。Vc·sinαy反應(yīng)海流造成的運(yùn)動(dòng)偏差，當(dāng)αy=π/2時(shí)，橫向海流造成的偏差最大。CD用于啟發(fā)CEP算法生成順流且偏差較小的路徑。Ya為USV由qi到達(dá)qj的偏航角的絕對(duì)弧度值。Tt為渦流對(duì)USV的威脅，令Tt=cos[(π·Rt)/(2·Rmax)]，Rt表示qi和qj與其最近的渦流區(qū)中心的距離之和，Rmax為渦流區(qū)的威脅半徑，Rt≤Rmax。

定義通過(guò)路徑點(diǎn)(qi)的估計(jì)最優(yōu)路徑的代價(jià):

Cp(qi)=pγ·cost(qi)+(1-pγ)·CD(qi,Goal) 。

(3)

式中，pγ為權(quán)值;Goal為路徑終點(diǎn);CD(qi,Goal)是qi與Goal間的估計(jì)最優(yōu)路徑的代價(jià)。cost(qi)為從路徑起始點(diǎn)到達(dá)qi的所有路徑段的CD之和。

本文根據(jù)Metropolis準(zhǔn)則[11]定義路徑點(diǎn)被約減的概率如式(4)，該準(zhǔn)則來(lái)源于模擬退火算法，

pp=1-exp[-Cp(qi)/(kp·Tem)]。

(4)

式中，Tem類似模擬退火算法中的溫度參數(shù)，它負(fù)責(zé)控制約減過(guò)程路徑點(diǎn)間競(jìng)爭(zhēng)的激烈程度，在開(kāi)始階段，令Tem為較小值，此時(shí)，路徑點(diǎn)間競(jìng)爭(zhēng)較小。將路徑點(diǎn)的pp值歸一化后，Cp值較高的路徑點(diǎn)的pp值明顯高于Cp值較低的路徑點(diǎn)的pp值，此時(shí)，競(jìng)爭(zhēng)的激烈程度較弱，Cp值較大的路徑點(diǎn)更容易被約減，而Cp值較小的路徑點(diǎn)競(jìng)爭(zhēng)力較弱。CEP算法保證約減后的路徑代價(jià)低于原始路徑代價(jià)，隨著路徑代價(jià)值下降，提高Tem值，增加競(jìng)爭(zhēng)激烈程度，所有路徑點(diǎn)pp值下降，而Cp值較大的路徑點(diǎn)的pp值降低得更快，此時(shí)，路徑點(diǎn)間的pp值差距變小，Cp值較低的路徑點(diǎn)競(jìng)爭(zhēng)力增加，被約減的可能性增加。約減過(guò)程的多樣性增加，更有助于尋找潛在的低代價(jià)路徑。

式(4)中kp的作用是限定函數(shù)的值域，令kp=(PCmax-PCmin)/2，PCmax為路徑估計(jì)最大代價(jià)，令其為原始路徑代價(jià)值，PCmin為路徑估計(jì)最低代價(jià)，令其為路徑起始端點(diǎn)間的CD值。令Tem隨著路徑代價(jià)的降低而線性增加，定義Tem函數(shù)：

Tem=-Kt·(PC-PCmax)+Temmin。

(5)

式中，KT=(Tmax-Tmin)/(PCmax-PCmin)；Tmax=0.8，Tmin=0.2分別為溫度的最大值和最小值；PC為實(shí)時(shí)路徑的代價(jià)值，由式(2)計(jì)算可得。

本文提出的冗余路徑點(diǎn)約減算法CEP將約減過(guò)程分為Shortcut約減模式和SP約減模式，流程如下：

(1) 生成[0,1]間隨機(jī)數(shù)Rand，若Rand大于Shortcut約減閾值Pr，根據(jù)SP算法選擇順序約減的起止點(diǎn)，若SP約減模式未完成全路徑的順序約減，執(zhí)行步驟(2)，否則算法結(jié)束；

(2) 找到上一輪SP約減的終點(diǎn)，將其作為Shortcut約減的起點(diǎn)，為該起點(diǎn)到達(dá)路徑末端點(diǎn)間所有路徑點(diǎn)qi計(jì)算通過(guò)它的路徑的估計(jì)最優(yōu)代價(jià)Cp(qi)和其被約減概率PP，并根據(jù)PP值，使用輪盤(pán)賭方法選取擬被約減的路徑點(diǎn)，該路徑點(diǎn)的前后路徑點(diǎn)作為此次Shortcut約減的起止節(jié)點(diǎn)；

(3) 執(zhí)行約減流程，SP模式和Shortcut模式的約減過(guò)程一致，首先檢查約減起止點(diǎn)間直線路徑代價(jià)是否小于起止點(diǎn)間原始路徑代價(jià)，若是，則繼續(xù)檢測(cè)起止點(diǎn)間直線路徑是否滿足USV的運(yùn)動(dòng)約束條件且無(wú)碰撞，以及路徑段質(zhì)量是否大于閾值0.1，若滿足條件，則用起止點(diǎn)間直線路徑代替起止點(diǎn)間原始路徑。

本文CEP算法的平均時(shí)間復(fù)雜度為O(n2)。

4 實(shí)驗(yàn)結(jié)果和分析

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

(6)

式中，B(t)=b+e·cos(ω·t+θ)，令b=1.2，c=0.12，k=0.84，ω=0.4，e=0.3，θ=π/2。海流的速度場(chǎng)是一個(gè)向量場(chǎng)，可以由ψ(x,y,t)得到：U(x,y,t)=?ψ/?y，V(x,y,t)= ?ψ/?x，U(x,y,t)和V(x,y,t)分別為t時(shí)刻海流沿X軸和Y軸方向的速度分量。

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

CEP方法和傳統(tǒng)順序方法的約減結(jié)果如圖1。陰影區(qū)為渦流區(qū)，隨著區(qū)域遠(yuǎn)離渦流中心，渦流危險(xiǎn)性降低，實(shí)體為障礙物。

(a) CEP的一個(gè)約減結(jié)果 (b) CEP與SP的約減結(jié)果比較

圖1(a)為CEP的一個(gè)約減結(jié)果，實(shí)線表示結(jié)果路徑，虛線集CEP的中間結(jié)果，由于CEP在執(zhí)行過(guò)程中考慮了路徑優(yōu)化和渦流區(qū)躲避問(wèn)題，因此CEP逐步收斂于代價(jià)更優(yōu)、危險(xiǎn)性更低且更易行的路徑，傾向于將路徑向海流干擾較小、路徑平順度較高的方向調(diào)整。

圖1(b)為CEP與SP方法的約減結(jié)果，原始路徑用十字符號(hào)表示，而CEP與SP的結(jié)果路徑分別用實(shí)線和虛線展示。CEP的結(jié)果路徑距離原始路徑較近，而SP方法偏離原始路徑較大。這是因?yàn)镾P方法持續(xù)約減路徑點(diǎn)，直到新生成的直線路徑不滿足約束條件。CEP方法的結(jié)果路徑能更多地保留原始路徑的優(yōu)點(diǎn)，安全性更高，而SP方法的結(jié)果路徑存在距離渦流中心和障礙物較近的部分，且路徑上存在較急的轉(zhuǎn)彎部分，USV難以跟蹤路徑。本文CEP方法的拐點(diǎn)較少，路徑較平順，說(shuō)明CEP方法在約減過(guò)程中考慮路徑代價(jià)是有效的。

為了檢驗(yàn)CEP方法的Shortcut約減模式的有效性，將CEP方法與它的SP約減模式的結(jié)果進(jìn)行比較，而為了說(shuō)明CEP的SP約減模式對(duì)提高算法收斂速度的有效性，將CEP方法與它的Shortcut約減模式的結(jié)果相比較，當(dāng)單獨(dú)執(zhí)行Shortcut約減模式時(shí)，規(guī)定當(dāng)路徑代價(jià)的變化穩(wěn)定且變化率小于10%時(shí)，算法結(jié)束。單獨(dú)執(zhí)行Shortcut約減模式時(shí)，算法執(zhí)行時(shí)間超過(guò)CEP算法的10倍，代價(jià)降低率卻只比CEP算法高了不到2%，這說(shuō)明CEP方法比Shortcut約減方法更適用于約減時(shí)間有限的在線規(guī)劃問(wèn)題，CEP方法的SP約減模式具有有效性。CEP方法比單獨(dú)使用SP約減模式多用了大約8%(0.2 s)的時(shí)間，但是其結(jié)果的代價(jià)降低率卻比SP模式提高了5%，說(shuō)明CEP方法中增加Shortcut約減模式的有效性。由于在約減過(guò)程中考慮了路徑質(zhì)量因素，因此，所有方法的結(jié)果路徑均能保證碰撞概率在一定閾值范圍內(nèi)，且路徑滿足USV的運(yùn)動(dòng)約束條件。

在半實(shí)物仿真平臺(tái)上規(guī)劃出一次完整的路徑，如圖2。規(guī)劃目標(biāo)點(diǎn)成五角星形狀分布在環(huán)境邊緣。在線規(guī)劃過(guò)程中集成了局部CEP方法，在每一控制時(shí)鐘節(jié)拍，搜索出一條多步局部路徑后，采用CEP方法對(duì)路徑進(jìn)行簡(jiǎn)化。

(a)海流強(qiáng)度較小時(shí)的路徑約簡(jiǎn)結(jié)果 (b)海流強(qiáng)度較大時(shí)的路徑約簡(jiǎn)結(jié)果

圖2(a)所示為海流強(qiáng)度較小的時(shí)候的路徑約簡(jiǎn)結(jié)果，從左上角的視圖可以看出，結(jié)果路徑比較平順，拐點(diǎn)較少，路徑能較直接地到達(dá)各個(gè)目標(biāo)點(diǎn)，說(shuō)明CEP方法能夠有效地約減冗余路徑點(diǎn)，并得到與目標(biāo)點(diǎn)距離較近的路徑，海流對(duì)約減過(guò)程影響相對(duì)較小。

圖2(b)所示為海流強(qiáng)度較大的情況下的路徑約簡(jiǎn)結(jié)果，約簡(jiǎn)算法在距離障礙物較遠(yuǎn)的外圍尋路，說(shuō)明海流對(duì)約簡(jiǎn)結(jié)果影響較大，這是因?yàn)楹Ａ饕蛩卦诼窂近c(diǎn)代價(jià)計(jì)算過(guò)程中占據(jù)更大比重，算法更多地考慮了橫向海流影響，以降低USV發(fā)生碰撞的概率，這同時(shí)表明算法在約簡(jiǎn)過(guò)程中海流因素發(fā)揮的作用，說(shuō)明了約簡(jiǎn)過(guò)程中考慮海流因素的有效性，也表明本文約簡(jiǎn)算法的一種趨勢(shì)，隨著海流強(qiáng)度的增加，算法保留距離障礙物更遠(yuǎn)的路徑。

5 結(jié) 論

本文針對(duì)USV在線路徑規(guī)劃過(guò)程中的路徑簡(jiǎn)化問(wèn)題，提出了一種最優(yōu)路徑代價(jià)估計(jì)方法和路徑點(diǎn)被約減概率的計(jì)算方法，以及概率值的自適應(yīng)變化方法，改進(jìn)了傳統(tǒng)的SP約減方法和Shortcut法。仿真結(jié)果表明，本文方法能夠快速發(fā)現(xiàn)比傳統(tǒng)方法更優(yōu)的簡(jiǎn)化USV路徑。在約減過(guò)程中考慮海流造成的運(yùn)動(dòng)偏差和渦流區(qū)威脅，降低了USV發(fā)生碰撞的概率。

[1] LAVALLE S M. Planning Algorithms[M]. Cambridge：University of Cambridge, 2006: 482-580.

[2] SEKHAVAT S, SVESTKA P, LAUMOND J P. Multilevel path planning for nonholonomic robots using semiholonomic subsystems[J]. The international journal of robotics research, 1998, 17(8): 840-857.

[3] CHEN P C, HWANG Y K. SANDROS: A dynamic graph search algorithm for motion planning[J]. IEEE Transactions on Robotics and Automation, 1998, 14(3): 390-403.

[4] ZHENG Z，SAMMUT K，LAMMAS A，et al. Efficient path re-planning for USVs operating in spatiotemporal currents[J]. Journal of Intelligent and Robotic Systems, 2015, 79(1): 135-153.

[5] NASIR J, ISLAM F, MALIK U, et al. RRT*-SMART: A rapid convergence implementation of RRT*[J]. International Journal of Advanced Robotic Systems, 2013, 10(4):299.

[6] GERAERTS R, OVERMARS M H. Creating high-quality paths for motion planning[J]. The International Journal of Robotics Research, 2007, 26(8): 845-863.

[7] CONNORS J, ELKAIM G. Analysis of a spline based, obstacle avoiding path planning algorithm[C]. 65th Vehicular Technology Conference, Dublin, Ireland, IEEE, 2007: 2565-2569.

[8] CHOSET H, BURDICK J. Sensor-based exploration: The hierarchical generalized voronoi graph[J]. The International Journal of Robotics Research, 2000, 19(2): 96-125.

[9] LIEN J M, THOMAS S L, AMATO N M. A general framework for sampling on the medial axis of the free space[C]. International Conference on Robotics and Automation, Taipei, Taiwan, IEEE, 2003, 3: 4439-4444.

[10] VAN B J, ABBEEL P, GOLDBERG K. LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information[J]. The International Journal of Robotics Research, 2011, 30(7): 895 - 913.

[11] JAILLET L, CORTéS J, SIMON T. Sampling-based path planning on configuration-space costmaps[J]. IEEE Transactions on Robotics, 2010, 26(4): 635-646.

(責(zé)任編輯 趙環(huán)宇)

AnUSVRedundantWaypointsPruningMethodbasedonOptimalPathCostEstimation

WENNai-fenga,b,LIUGuan-quna,b,YUHai-yanga,b,ZHANGRu-boa,b

(a.School of Electormechanical engineering; b.Key Laboratory of Intelligent Perception and Advanced Control of State Ethnic Affairs Commission, Dalian Minzu University, Dalian Liaoning 116605, China)

TP311.5

A

2017-04-05；

2017-08-14

國(guó)家自然科學(xué)基金資助項(xiàng)目(61673084)；遼寧省自然科學(xué)基金項(xiàng)目(201602204)；中央高校自主科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(DC201502010304)；遼寧省教育廳科學(xué)研究項(xiàng)目(L2014542)。

溫乃峰(1981-)，男，遼寧葫蘆島人，講師，博士，主要從事無(wú)人系統(tǒng)的路徑規(guī)劃技術(shù)、信息融合與人工智能研究。

2096-1383(2017)05-0461-05