移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法的研究與實(shí)現(xiàn)

史 進(jìn)，董 瑤,3，白振東，崔澤晨，董永峰

(1.河北工業(yè)大學(xué) 控制科學(xué)與工程學(xué)院，天津 300401； 2. 河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401；3.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401)

移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法的研究與實(shí)現(xiàn)

史 進(jìn)1,2，董 瑤1,2,3，白振東2,3，崔澤晨2,3，董永峰2,3*

(1.河北工業(yè)大學(xué) 控制科學(xué)與工程學(xué)院，天津 300401； 2. 河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401；3.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401)

針對(duì)在未知?jiǎng)討B(tài)障礙物存在且目標(biāo)點(diǎn)移動(dòng)的環(huán)境下，采用人工勢(shì)場(chǎng)法規(guī)劃路徑時(shí)斥力影響半徑往往大于障礙物的半徑從而導(dǎo)致動(dòng)態(tài)障礙物與機(jī)器人發(fā)生碰撞的問(wèn)題，提出非完全等待策略與Morphine算法相結(jié)合的改進(jìn)人工勢(shì)場(chǎng)法動(dòng)態(tài)路徑規(guī)劃策略。當(dāng)動(dòng)態(tài)障礙物與機(jī)器人發(fā)生側(cè)面碰撞時(shí)采用非完全等待策略；當(dāng)動(dòng)態(tài)障礙物與機(jī)器人發(fā)生迎面碰撞時(shí)采用Morphine算法局部規(guī)劃路徑；同時(shí)引入滾動(dòng)窗口理論提高躲避動(dòng)態(tài)障礙物的精確度。通過(guò)仿真實(shí)驗(yàn)，與傳統(tǒng)人工勢(shì)場(chǎng)作對(duì)比，提出的改進(jìn)算法在發(fā)生側(cè)面碰撞時(shí)要縮短12步，在發(fā)生迎面碰撞時(shí)要縮短6步，由此可得提出改進(jìn)算法在路徑平滑性和規(guī)劃步數(shù)方面效果更優(yōu)。

路徑規(guī)劃；人工勢(shì)場(chǎng)；Morphine算法；非完全等待策略；滾動(dòng)窗口

0 引言

近年來(lái)，動(dòng)態(tài)路徑規(guī)劃問(wèn)題一直是機(jī)器人技術(shù)和人工智能領(lǐng)域的一個(gè)重要研究課題，同時(shí)也是機(jī)器人技術(shù)能夠更廣泛應(yīng)用到其他領(lǐng)域的一個(gè)重要前提條件。當(dāng)前常用的路徑規(guī)劃算法主要有柵格法[1]、人工勢(shì)場(chǎng)法[2]、遺傳算法[3]、神經(jīng)網(wǎng)絡(luò)[4]等，其中，人工勢(shì)場(chǎng)法是目前比較成熟且高效的一種算法，但其主要用于解決靜態(tài)環(huán)境下機(jī)器人路徑規(guī)劃問(wèn)題，而對(duì)于解決動(dòng)態(tài)環(huán)境下的運(yùn)動(dòng)路徑規(guī)劃問(wèn)題并不理想，常由于斥力影響半徑大于障礙物的半徑而導(dǎo)致動(dòng)態(tài)障礙物與機(jī)器人發(fā)生碰撞。為此本文提出了非完全等待策略與Morphine算法相結(jié)合的改進(jìn)人工勢(shì)場(chǎng)路徑規(guī)劃策略，從在單一動(dòng)態(tài)環(huán)境和復(fù)雜動(dòng)態(tài)環(huán)境下進(jìn)行的實(shí)驗(yàn)結(jié)果可以看出，本文提出的改進(jìn)策略在路徑平滑性和規(guī)劃路徑步數(shù)上更優(yōu)。

1 機(jī)器人路徑規(guī)劃方法

1.1 改進(jìn)人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法即根據(jù)地圖的障礙物、目標(biāo)點(diǎn)位置分別構(gòu)建斥力場(chǎng)和引力場(chǎng)，通過(guò)斥力和引力相互作用構(gòu)建人工虛擬勢(shì)場(chǎng)，機(jī)器人在勢(shì)場(chǎng)中規(guī)劃出一條無(wú)碰撞路徑。

在二維空間中設(shè)機(jī)器人的坐標(biāo)向量為X=(x,y)，目標(biāo)點(diǎn)的坐標(biāo)向量為Xd=(xd,yd)，總勢(shì)場(chǎng)Usum(X)可以表示為引力場(chǎng)函數(shù)Uatt(X)和斥力場(chǎng)函數(shù)Urep(X)之和，即：

Usum(X)=Uatt(X)+Urep(X)

(1)

傳統(tǒng)人工勢(shì)場(chǎng)法的引力場(chǎng)函數(shù)Uatt(X)和斥力場(chǎng)函數(shù)Urep(X)計(jì)算公式如下：

Uatt(X)=0.5αρ2(X,Xo)

(2)

Urep(X)=

(3)

其中：α為引力的增益系數(shù)，是正數(shù)；β為斥力的增益系數(shù)，是正數(shù)；ρ(X,Xo)為機(jī)器人與障礙物之間的最短距離;ρo是一個(gè)大于零的常數(shù)，表示障礙物影響的距離，在ρo之外的機(jī)器人便不受此障礙物的影響。

改進(jìn)人工勢(shì)場(chǎng)法[5-7]引入機(jī)器人和目標(biāo)點(diǎn)的相對(duì)位置和速度，公式如下：

Uatt(p,V)=δp‖p-pd‖2+δv‖V-Vd‖2

(4)

其中：p為機(jī)器人當(dāng)前位置，V為機(jī)器人當(dāng)前速度，δp為相對(duì)位置引力系數(shù)，pd為目標(biāo)點(diǎn)位置，Vd為目標(biāo)點(diǎn)速度，δv為相對(duì)速度引力系數(shù)，‖p-pd‖為機(jī)器人與目標(biāo)點(diǎn)之間的歐氏距離，‖V-Vd‖為機(jī)器人與目標(biāo)點(diǎn)之間的相對(duì)速度。由此得出機(jī)器人所受目標(biāo)點(diǎn)的引力，公式如下：

Fatt(p,V)=-▽Uatt(p,V)=-▽pUatt(p,V)-

▽vUatt(p,V)

(5)

改進(jìn)的斥力場(chǎng)函數(shù)可表示為：

Urep(p,V)=

(6)

其中：Rr為機(jī)器人半徑；β1與β2為可變因子；ρo為障礙物影響距離；ρro是指機(jī)器人與障礙物邊界的距離；Vro為障礙物與機(jī)器人的相對(duì)速度。由此推出斥力公式：

Frep(p,V)=

(7)

1.2 Morphine算法

Morphine算法[8]即通過(guò)機(jī)器人獲取環(huán)境信息后統(tǒng)計(jì)前方備選的多條弧線路徑信息，選出最優(yōu)通行路徑。

設(shè)已知機(jī)器人的起點(diǎn)s和目標(biāo)點(diǎn)d的坐標(biāo),機(jī)器人的方向角α(s和d的連線與x軸的夾角)、某一備選路徑弧線的半徑r,如圖1所示，要畫出備選路徑弧線必須知道該弧線的圓心c的坐標(biāo)及某一路徑點(diǎn)t的坐標(biāo)，其計(jì)算公式如式(8)～(9)所示:

(8)

(9)

其中θ為路徑點(diǎn)t的圓心角。

圖1 弧線上某點(diǎn)坐標(biāo)推導(dǎo)圖Fig. 1 Coordinates of a point on the Arc

設(shè)定機(jī)器人路徑尋優(yōu)評(píng)估函數(shù)為：

(10)

式中：Arc表示弧線，O表示障礙物，L為每條弧線路徑長(zhǎng)度；G為路徑拐點(diǎn)參數(shù)；M為路徑點(diǎn)t到目標(biāo)點(diǎn)d的歐氏距離；α1、α2、α3為各參數(shù)的權(quán)值。當(dāng)f值為無(wú)窮大時(shí)，弧線經(jīng)過(guò)障礙物，機(jī)器人與障礙物碰撞，此路徑不可取，選取f值最小的路徑為機(jī)器人運(yùn)行最優(yōu)路徑。

2 動(dòng)態(tài)環(huán)境下機(jī)器人路徑規(guī)劃

室內(nèi)環(huán)境復(fù)雜多變，具有動(dòng)態(tài)不確定性，移動(dòng)機(jī)器人如何有效避障是完成路徑規(guī)劃的重點(diǎn)。本文在局部路徑規(guī)劃中采用滾動(dòng)窗口預(yù)測(cè)障礙物，分析碰撞類型，分別采取不同避障策略，最終完成動(dòng)態(tài)路徑規(guī)劃。

2.1 滾動(dòng)窗口碰撞預(yù)測(cè)

機(jī)器人在運(yùn)動(dòng)過(guò)程中采用滾動(dòng)窗口[9]對(duì)周圍的環(huán)境信息進(jìn)行探測(cè)，預(yù)測(cè)在其規(guī)劃好的全局路徑中是否有障礙物出現(xiàn); 若存在動(dòng)態(tài)障礙物，則測(cè)定其速度與方向，預(yù)測(cè)其運(yùn)動(dòng)軌跡，制定有效的避碰策略。滾動(dòng)窗口碰撞預(yù)測(cè)的流程如圖2所示，具體步驟如下：

1)場(chǎng)景預(yù)測(cè)。機(jī)器人開(kāi)始運(yùn)動(dòng)時(shí)，采用啟發(fā)式方法，將傳感器所探測(cè)到的局部環(huán)境信息轉(zhuǎn)化為局部子目標(biāo)[10]，同時(shí)預(yù)測(cè)動(dòng)態(tài)障礙物的運(yùn)動(dòng)軌跡，設(shè)定機(jī)器人每走一步用時(shí)Δt，通過(guò)預(yù)測(cè)Δt時(shí)間內(nèi)機(jī)器人與動(dòng)態(tài)障礙物兩條運(yùn)動(dòng)軌跡之間的相對(duì)位置來(lái)預(yù)測(cè)二者是否會(huì)發(fā)生碰撞。

2)滾動(dòng)窗口更新優(yōu)化。按照滾動(dòng)窗口預(yù)測(cè)結(jié)果和環(huán)境信息，進(jìn)行子目標(biāo)的局部路徑規(guī)劃，采取相應(yīng)策略有效避障，重新更新滾動(dòng)窗口。

3)反饋初始化。在新的滾動(dòng)窗口范圍內(nèi)，根據(jù)此時(shí)傳感器采集的信息，重新更新窗口內(nèi)障礙物的運(yùn)動(dòng)狀況和環(huán)境信息，以此循環(huán)預(yù)測(cè)。

圖2 滾動(dòng)窗口碰撞預(yù)測(cè)流程Fig. 2 Collision prediction flow by rolling window

2.2 動(dòng)態(tài)避障策略

根據(jù)滾動(dòng)窗口預(yù)測(cè)結(jié)果，分析機(jī)器人與動(dòng)態(tài)障礙物運(yùn)動(dòng)軌跡是否存在交集，即是否存在碰撞，如圖3所示。機(jī)器人與動(dòng)態(tài)障礙物相對(duì)運(yùn)動(dòng)的3種典型情況如下：

1)無(wú)碰撞。若兩條運(yùn)動(dòng)軌跡不存在交集，如圖3(a)、(b)、(e)所示，此時(shí)機(jī)器人與障礙物在Δt范圍內(nèi)不會(huì)發(fā)生碰撞。

2)側(cè)面碰撞。若兩條運(yùn)動(dòng)軌跡之間存在交集，如圖3(c)、(d)所示，機(jī)器人與動(dòng)態(tài)障礙物將在Δt范圍內(nèi)發(fā)生側(cè)面碰撞，此時(shí)機(jī)器人采取非完全等待策略[11]。假設(shè)障礙物的半徑為R，障礙物斥力影響半徑為r，當(dāng)機(jī)器人在r范圍內(nèi)則開(kāi)始等待，大于r則繼續(xù)前進(jìn)，稱其為“完全等待”；但若機(jī)器人未等障礙物完全經(jīng)過(guò)(還在影響半徑r范圍內(nèi))就繼續(xù)前進(jìn)，稱其為“非完全等待”。

3)迎面碰撞。若兩條運(yùn)動(dòng)軌跡之間有交集，如圖3(f)所示，在Δt時(shí)間內(nèi)機(jī)器人與動(dòng)態(tài)障礙物發(fā)生迎面碰撞，則此時(shí)機(jī)器人采用Morphin算法作局部路徑規(guī)劃，當(dāng)機(jī)器人不在動(dòng)態(tài)障礙物影響半徑r范圍內(nèi)時(shí)再用改進(jìn)人工勢(shì)場(chǎng)法作全局路徑規(guī)劃。

圖3 機(jī)器人與動(dòng)態(tài)障礙物碰撞的幾種典型情況Fig. 3 Several typical cases of collision between robot and dynamic obstacle

由于室內(nèi)環(huán)境復(fù)雜多變，傳統(tǒng)人工勢(shì)場(chǎng)法存在障礙物附近目標(biāo)不可達(dá)、易發(fā)生碰撞、狹窄通道等問(wèn)題，本文提出采用改進(jìn)人工勢(shì)場(chǎng)法進(jìn)行全局路徑規(guī)劃，當(dāng)遇到狹窄通道時(shí)，采用Morphine算法進(jìn)行局部路徑規(guī)劃。

2.3 動(dòng)態(tài)路徑規(guī)劃

機(jī)器人動(dòng)態(tài)路徑規(guī)劃流程具體步驟如下。

步驟1 構(gòu)建室內(nèi)環(huán)境地圖。

步驟2 采用改進(jìn)人工勢(shì)場(chǎng)法進(jìn)行全局路徑規(guī)劃，且其目標(biāo)點(diǎn)即機(jī)器人的勢(shì)場(chǎng)全局最小點(diǎn)。

步驟3 機(jī)器人沿全局規(guī)劃路徑行走。

步驟4 通過(guò)滾動(dòng)窗口預(yù)測(cè)動(dòng)態(tài)障礙物，判斷此障礙物是否會(huì)產(chǎn)生影響：若無(wú)影響，轉(zhuǎn)步驟5；有影響，則轉(zhuǎn)步驟6。

步驟5 判斷是否到達(dá)目標(biāo)點(diǎn)：若到達(dá)目標(biāo)點(diǎn)路徑規(guī)劃結(jié)束；反之，返回步驟2。

步驟6 判斷動(dòng)態(tài)障礙物的運(yùn)動(dòng)方向和狀態(tài)，采用相應(yīng)的避障策略。

步驟7 判斷是否避障成功：若成功返回步驟3；反之，返回步驟2。

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

本文采用上述動(dòng)態(tài)路徑規(guī)劃方法，分別設(shè)計(jì)單一和復(fù)雜兩種動(dòng)態(tài)障礙物環(huán)境進(jìn)行20組實(shí)驗(yàn)驗(yàn)證，每類實(shí)驗(yàn)舉一例說(shuō)明。

3.1 單一環(huán)境動(dòng)態(tài)路徑規(guī)劃

3.1.1 側(cè)面碰撞

假設(shè)機(jī)器人與動(dòng)態(tài)障礙物發(fā)生側(cè)面碰撞，其參數(shù)設(shè)定如表1所示。

表1 側(cè)面碰撞參數(shù)列表Tab. 1 Parameter list of side collision

1) 機(jī)器人采取“完全等待”策略。

機(jī)器人采取“完全等待”策略的動(dòng)態(tài)路徑規(guī)劃結(jié)果如圖4所示，機(jī)器人到達(dá)目標(biāo)點(diǎn)步數(shù)為144步，且路徑非常平滑。

圖4 完全等待動(dòng)態(tài)路徑規(guī)劃Fig. 4 Completely waiting for dynamic path planning

2) 機(jī)器人采取“非完全等待 ”策略。

機(jī)器人采取“非完全等待”策略的動(dòng)態(tài)路徑規(guī)劃結(jié)果如圖5所示，采取“非完全等待”策略的規(guī)劃路徑雖沒(méi)有“完全等待”平滑，但機(jī)器人到達(dá)目標(biāo)點(diǎn)步數(shù)為123步，小于“完全等待”規(guī)劃步數(shù)。

圖5 非完全等待動(dòng)態(tài)路徑規(guī)劃Fig. 5 Non-completely waiting for dynamic path panning

同時(shí)在設(shè)定機(jī)器人步長(zhǎng)為1的情況下選取3組實(shí)驗(yàn)數(shù)據(jù)作對(duì)比，結(jié)果如表2所示，采取“非完全等待”策略在規(guī)劃步數(shù)，即運(yùn)動(dòng)時(shí)間上要遠(yuǎn)小于“完全等待”策略。

表2 兩種等待策略步數(shù)對(duì)比Tab. 2 Comparison of steps by two waiting strategies

為再次證明“非完全等待”策略的有效性，本文與文獻(xiàn)[12]方法作對(duì)比，實(shí)驗(yàn)環(huán)境不變，參數(shù)設(shè)定如表1所示，實(shí)驗(yàn)結(jié)果如圖6所示，其中圖6(a)是采用文獻(xiàn)[12]中的未采用等待策略的路徑規(guī)劃，圖6(b)是采用“非完全等待”策略的路徑規(guī)劃，圖6(c)是兩種路徑規(guī)劃方法的局部避障放大對(duì)比圖，由圖6(c)可以看出本文提出的非完全等待避障策略不會(huì)使機(jī)器人在受到巨大斥力情況下倒退行走，避障效果更優(yōu)。

3.1.2 迎面碰撞

假設(shè)機(jī)器人與動(dòng)態(tài)障礙物發(fā)生迎面碰撞，采取Morphine算法進(jìn)行避障。為證明本文算法優(yōu)越性，與文獻(xiàn)[12]算法作對(duì)比，其參數(shù)設(shè)定如表3所示，步長(zhǎng)為1。

表3 迎面碰撞參數(shù)列表Tab. 3 Parameter list of face-to-face collision

動(dòng)態(tài)路徑規(guī)劃結(jié)果如圖7所示，其中圖7(a)為采用文獻(xiàn)[12]人工勢(shì)場(chǎng)算法的路徑規(guī)劃，圖7(b)為采用Morphine算法的路徑規(guī)劃，圖7(c)為兩種方法局部避障放大對(duì)比圖。不難看出未使用 Morphine 算法的機(jī)器人在遇到障礙物后會(huì)出現(xiàn)倒退現(xiàn)象，其運(yùn)動(dòng)到目標(biāo)點(diǎn)的步數(shù)為169 步，使用 Morphine算法的機(jī)器人運(yùn)動(dòng)步數(shù)為159 步。因此，本文算法在避障效果和路徑規(guī)劃步數(shù)上更優(yōu)。

圖6 在一個(gè)障礙物的情形下側(cè)面碰撞路徑規(guī)劃對(duì)比Fig. 6 Comparison of side collision path planning with one obstacle

圖7 在一個(gè)障礙物的情形下迎面碰撞路徑規(guī)劃圖Fig. 7 Comparison of face-to-face collision path planning with one obstacle

3.2 復(fù)雜環(huán)境動(dòng)態(tài)路徑規(guī)劃

建立復(fù)雜環(huán)境，在120×100的環(huán)境地圖中設(shè)定8個(gè)靜態(tài)障礙物和1個(gè)動(dòng)態(tài)障礙物，機(jī)器人起始點(diǎn)坐標(biāo)為(0,0)，目標(biāo)點(diǎn)坐標(biāo)為(100,100)，步長(zhǎng)為1。

3.2.1 側(cè)面碰撞

設(shè)定動(dòng)態(tài)障礙物起始點(diǎn)坐標(biāo)為(69,54)，并向左下方運(yùn)動(dòng)，其半徑為3，影響半徑為6，采用傳統(tǒng)人工勢(shì)場(chǎng)法進(jìn)行路徑規(guī)劃，如圖8所示，機(jī)器人整個(gè)動(dòng)態(tài)避障的步數(shù)為45。

圖8 傳統(tǒng)人工勢(shì)場(chǎng)法避免側(cè)面碰撞Fig. 8 Side collision avoidance by traditional artificial potential field method

采用滾動(dòng)窗口預(yù)測(cè)到機(jī)器人行至(65,44)時(shí)將與動(dòng)態(tài)障礙物發(fā)生側(cè)面碰撞，于是采用本文提出的非完全等待進(jìn)行避障，其動(dòng)態(tài)路徑規(guī)劃如圖9所示，機(jī)器人整個(gè)動(dòng)態(tài)避障的步數(shù)為33，可以明顯看出采用非完全等待的避障策略的行進(jìn)路徑比傳統(tǒng)避障方法的路徑更平滑，所用步數(shù)更少。

圖9 非完全等待避障策略避免側(cè)面碰撞Fig. 9 Side collision avoidance by non-completely waiting strategy

3.2.2 迎面碰撞

設(shè)定動(dòng)態(tài)障礙物的起始點(diǎn)坐標(biāo)為(89,78)，并向左下方運(yùn)動(dòng)，其半徑為3，影響半徑為6，如圖10所示。采用常規(guī)避障方法，整個(gè)動(dòng)態(tài)避障過(guò)程需要46步。

圖10 傳統(tǒng)人工勢(shì)場(chǎng)法避免迎面碰撞Fig. 10 Face-to-face collision avoidance by traditional artificial potential field method

而在相同環(huán)境下，采用滾動(dòng)窗口預(yù)測(cè)到機(jī)器人行至(74,59)時(shí)將與動(dòng)態(tài)障礙物發(fā)生迎面碰撞，采取Morphine算法進(jìn)行局部避障，如圖11所示，實(shí)線為動(dòng)態(tài)避障過(guò)程，整個(gè)動(dòng)態(tài)避障過(guò)程需要40步，效果要優(yōu)于傳統(tǒng)人工勢(shì)場(chǎng)法。

圖11 Morphine算法避免迎面碰撞Fig. 11 Face-to-face collision avoidance by Morphine algorithm

4 結(jié)語(yǔ)

本文在動(dòng)態(tài)環(huán)境下提出非完全等待策略與Morphine算法相結(jié)合的改進(jìn)人工勢(shì)場(chǎng)法路徑規(guī)劃，并引入滾動(dòng)窗口理論，對(duì)未知?jiǎng)討B(tài)障礙物進(jìn)行碰撞預(yù)測(cè)，分析碰撞模型進(jìn)而采取相應(yīng)的避障策略。通過(guò)對(duì)比實(shí)驗(yàn)可知，本文提出的改進(jìn)策略具有更高的避障性能，且規(guī)劃步數(shù)更少。

References)

[1] WANG X, JIN Y, DING Z. A path planning algorithm of raster maps based on artificial potential field[C]// Proceedings of the 2015 Chinese Automation Congress. Piscataway, NJ: IEEE, 2015:627-632.

[2] YE B, ZHAO M, WANG Y. Research of path planning method for mobile robot based on artificial potential field[C]// Proceedings of the 2011 International Conference on Multimedia Technology. Piscataway, NJ: IEEE, 2011: 3192-3195.

[3] OZDIKIS O. Genetic algorithms with random coordinates for route planning on a 3D terrain[C]// Proceedings of the 2011 5th International Conference on Genetic and Evolutionary Computing. Washington, DC: IEEE Computer Society, 2011:146-149.

[4] JIANG M, YU Y, LIU X, et al. Fuzzy neural network based dynamic path planning[C]// Proceedings of the 2012 International Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE, 2012: 326-330.

[5] CHEN L, LIU C, SHI H, et al. New robot planning algorithm based on improved artificial potential field[C]// Proceedings of the 3rd International Conference on Instrumentation, Measurement, Computer, Communication and Control. Washington, DC: IEEE Computer Society, 2013:228-232.

[6] 羅勝華,劉國(guó)榮,蔣燕.一種基于改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 微計(jì)算機(jī)信息, 2009, 25(29):188-190.(LUO S H, LIU G R, JIANG Y. A path planning of mobile robot based on improved artificial potential field method[J]. Microcomputer Information, 2009, 25(29):188-190.)

[7] 羅乾又, 張華, 王姮, 等.改進(jìn)人工勢(shì)場(chǎng)法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì), 2011, 32(4):1411-1413.(LUO Q Y, ZHANG H, WANG H, et al. Application of improved artificial potential field approach in local path planning for mobile robot[J]. Computer Engineering and Design, 2011, 32(4):1411-1413.)

[8] 萬(wàn)曉風(fēng),胡偉,鄭博嘉,等.基于改進(jìn)蟻群算法與Morphin算法的機(jī)器人路徑規(guī)劃方法[J].科技導(dǎo)報(bào), 2015,33(3): 84-89.(WAN X F,HU W,ZHENG B J, et al. Robot path planning method based on improved ant colony algorithm and Morphin algorithm[J].Science & Technology Review, 2015,33(3):88-89.)

[9] 叢巖峰, 基于滾動(dòng)優(yōu)化原理的路徑規(guī)劃方法研究[D].長(zhǎng)春: 吉林大學(xué),2007.(CONG Y F, The path planning method research based on rolling optimization theory [D]. Changchun: Jilin University, 2007.)

[10] LI X, XU H, LI M. A memory-based complete local search method with variable neighborhood structures for no-wait job shops[J]. International Journal of Advanced Manufacturing Technology, 2013,87(5/6/7/8):1401-1408.

[11] BRANKE J, RGEN, MIDDENDORF M, et al. Waiting strategies for dynamic vehicle routing [J]. Transportation Science, 2005, 39(3): 298-312.

[12] LIU Z X, YANG L X, WANG J G. Soccer robot path planning based on evolutionary artificial field[J].Advanced Materials Research, 2012, 568(8): 955-958.

This work is partially supported by the Tianjin Natural Science Foundation Project (14JCYBJC18500), the Tianjin Application Foundation and Frontier Technology Research Program (13JCQNJC00200).

SHIJin, born in 1981, Ph. D. candidate, lecturer. His research interests include artificial intelligence, robot positioning navigation.

DONGYao, born in 1982, Ph. D. candidate, experimentalist. Her research interests include intelligent information processing, artificial intelligence.

BAIZhendong, born in 1989, M. S. candidate. His research interests include robot positioning navigation, artificial intelligence.

CUIZechen, born in 1989, M. S. candidate. His research interests include robot positioning navigation.

DONGYongfeng, born in 1977, Ph. D., professor. His research interests include intelligent information processing.

Researchandimplementationofmobilerobotpathplanningmethod

SHI Jin1,2, DONG Yao1,2,3, BAI Zhendong2,3, CUI Zechen2,3,DONG Yongfeng2,3*

(1.SchoolofControlScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China;2.SchoolofComputerScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China;3.HebeiProvinceKeyLaboratoryofBigDataCalculation,Tianjin300401,China)

In the environment with unknown dynamic obstacle moving and target point, the radius of the repulsive force is often larger than the radius of the obstacle when the path is planned by the artificial potential field method, which leads to the collision of the dynamic obstacle with the robot. An improved dynamic path planning strategy of artificial potential field based on Morphine algorithm and non-completely waiting strategy was proposed. The non-completely waiting strategy was adopted when the dynamic obstacle collided with the robot on a side. The Morphine algorithm was used to localize the path when the dynamic obstacle collided with the robot face to face. Moreover, the rolling window theory was introduced to improve the accuracy of avoiding dynamic obstacles. Through the simulation tests, compared with the traditional artificial potential field, the proposed algorithm is shortened by 12 steps in the event of a side collision and 6 steps in the event of a face-to-face collision. Therefore, the improved algorithm is more effective in path smoothness and planning steps.

path planning; artificial potential field; Morphine algorithm; non-completely waiting strategy; rolling window

2017- 05- 16;

2017- 06- 08。

天津市自然科學(xué)基金資助項(xiàng)目(14JCYBJC18500); 天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目(13JCQNJC00200)。

史進(jìn) (1981—)，男，河北張家口人，講師，博士研究生，主要研究方向：人工智能、機(jī)器人定位導(dǎo)航； 董瑤(1982—)，女，河北石家莊人，實(shí)驗(yàn)師，博士研究生，主要研究方向：智能信息處理、人工智能； 白振東(1989—)，男，河北邯鄲人，碩士研究生，主要研究方向：機(jī)器人定位導(dǎo)航、人工智能; 崔澤晨(1989—),男，北京人，碩士研究生，主要研究方向：機(jī)器人定位導(dǎo)航; 董永峰(1987—),男，河北定州人，教授，博士，主要研究方向：智能信息處理。

1001- 9081(2017)11- 3119- 05

10.11772/j.issn.1001- 9081.2017.11.3119

(*通信作者電子郵箱dongyongfeng@scse.hebut.edu.cn)

TP399

A