劉硯菊，代 濤，宋建輝

改進(jìn)人工勢(shì)場(chǎng)法的路徑規(guī)劃算法研究

劉硯菊，代 濤，宋建輝

(沈陽(yáng)理工大學(xué) 自動(dòng)化與電氣工程學(xué)院，沈陽(yáng) 110159)

針對(duì)基于傳統(tǒng)人工勢(shì)場(chǎng)法的機(jī)器人路徑規(guī)劃存在局部極小點(diǎn)的問(wèn)題，提出了一種修改斥力方向和自主建立虛擬目標(biāo)牽引點(diǎn)相結(jié)合的路徑規(guī)劃算法。該算法在修改斥力方向算法中設(shè)置了一個(gè)臨界值，在機(jī)器人行走的過(guò)程中，若機(jī)器人與障礙物的距離大于臨界值，機(jī)器人路徑規(guī)劃就采用修改斥力方向的算法，當(dāng)機(jī)器人與障礙物的距離小于臨界值時(shí)，機(jī)器人路徑規(guī)劃算法就從修改斥力方向算法轉(zhuǎn)入自主建立虛擬目標(biāo)牽引點(diǎn)算法。改進(jìn)后的算法很好地解決了傳統(tǒng)人工勢(shì)場(chǎng)法的局部極小點(diǎn)問(wèn)題，仿真結(jié)果證明了改進(jìn)后算法的有效性。

人工勢(shì)場(chǎng)法；機(jī)器人路徑規(guī)劃；目標(biāo)不可達(dá)；局部極小值

隨著科學(xué)技術(shù)水平和人們生活水平的不斷提高，機(jī)器人在人們生活中的應(yīng)用[1]越來(lái)越廣泛，人們對(duì)機(jī)器人應(yīng)用的研究也越來(lái)越深入，其中機(jī)器人應(yīng)用中一個(gè)比較重要的課題就是機(jī)器人路徑規(guī)劃算法的研究。路徑規(guī)劃就是在具有障礙物的環(huán)境中，按照一定的評(píng)價(jià)標(biāo)準(zhǔn)來(lái)尋找一條從起始狀態(tài)到目標(biāo)狀態(tài)的無(wú)碰撞路徑[2]。總的來(lái)說(shuō)，機(jī)器人路徑規(guī)劃方法可以分為兩種，它們分別是全局路徑規(guī)劃[3]方法和局部路徑規(guī)劃[4]方法，全局路徑規(guī)劃方法主要包括柵格法、拓?fù)浞ā⒖梢晥D法等方法[5]，典型的路徑規(guī)劃方法主要有人工勢(shì)場(chǎng)法[6]、沿墻走算法、模糊邏輯控制算法[7]、遺傳算法[8]等。其中沿墻走算法存在路徑規(guī)劃速度慢的問(wèn)題，模糊邏輯控制算法存在很難構(gòu)造出比較全面的規(guī)則庫(kù)的問(wèn)題，若輸入量和規(guī)則不匹配，它就無(wú)所適從，不具備適應(yīng)能力，遺傳算法存在計(jì)算資源消耗大、收斂速度慢的問(wèn)題。與上述算法相比，人工勢(shì)場(chǎng)法具有計(jì)算簡(jiǎn)單、實(shí)現(xiàn)容易、實(shí)時(shí)性好、反應(yīng)速度快、規(guī)劃軌跡平滑等優(yōu)點(diǎn)，因此得到了廣泛的應(yīng)用。

本文在修改斥力函數(shù)的基礎(chǔ)上，針對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法的局部極小點(diǎn)問(wèn)題，提出了一種修改斥力方向和自主建立虛擬目標(biāo)牽引點(diǎn)相結(jié)合的算法。該算法結(jié)合了修改斥力方向和自主建立虛擬目標(biāo)牽引點(diǎn)兩種算法的優(yōu)點(diǎn)，解決了傳統(tǒng)人工勢(shì)場(chǎng)法局部極小點(diǎn)問(wèn)題。

1 人工勢(shì)場(chǎng)法原理

人工勢(shì)場(chǎng)法是由Khatib提出來(lái)的一種虛擬力法[9]，它是根據(jù)電荷間相互作用規(guī)律的理論演變而來(lái)的。人工勢(shì)場(chǎng)法的實(shí)質(zhì)就是對(duì)機(jī)器人的運(yùn)行環(huán)境人為建立一個(gè)抽象的勢(shì)場(chǎng)，機(jī)器人在這個(gè)人工勢(shì)場(chǎng)中將會(huì)受到來(lái)自障礙物的斥力場(chǎng)和來(lái)自目標(biāo)點(diǎn)的引力場(chǎng)的作用，在引力場(chǎng)和斥力場(chǎng)的作用下，機(jī)器人將受到引力和斥力的作用，在斥力和引力的共同作用下，機(jī)器人將會(huì)向目標(biāo)點(diǎn)移動(dòng)并最終到達(dá)目標(biāo)點(diǎn)。傳統(tǒng)人工勢(shì)場(chǎng)法的定義如下:

若機(jī)器人的當(dāng)前位置坐標(biāo)向量為X=(x,y)，目標(biāo)點(diǎn)的坐標(biāo)向量為Xg=(xg,yg)，則定義引力勢(shì)場(chǎng)函數(shù)如公式(1):

(1)

式中:k為大于零的引力場(chǎng)的系數(shù)常量；機(jī)器人到目標(biāo)點(diǎn)的距離為ρ(X,Xg)=‖X-Xg‖，引力為引力勢(shì)場(chǎng)函數(shù)的負(fù)梯度，則定義引力如公式(2):

F1(X)=-▽(U1(X))=k(Xg-X)

(2)

(3)

式中:m為大于零的斥力場(chǎng)系數(shù)常量；Xo為障礙物的位置坐標(biāo)向量；機(jī)器人到障礙物的距離為ρ(X,Xo)=‖X-Xo‖；ρ0為障礙物的最大影響范圍，則定義斥力如公式(4):

F2(X)=-▽(U2(X))

(4)

針對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法存在的目標(biāo)不可達(dá)問(wèn)題，現(xiàn)在一般采用較為普遍的改進(jìn)斥力函數(shù)的方法，在斥力函數(shù)中引入機(jī)器人和目標(biāo)點(diǎn)之間的相對(duì)距離，其實(shí)現(xiàn)如下:

若機(jī)器人的當(dāng)前位置為X=(x,y)，目標(biāo)點(diǎn)的位置為Xg=(xg,yg)，則定義改進(jìn)后的斥力勢(shì)場(chǎng)函數(shù)如公式(5):

(5)

(6)

式中，

(7)

(8)

在實(shí)際應(yīng)用中普遍采用它們各自的簡(jiǎn)化形式，形如公式(9)和公式(10):

(9)

(10)

式中δ(X-Xg)n-1=|(x-xg)n-1|+|(y-yg)n-1|。

2 修改斥力方向和自主建立虛擬目標(biāo)牽引點(diǎn)的混合算法

2.1 修改斥力方向的方法

圖1 改進(jìn)斥力函數(shù)及修改斥力方向受力分析圖

圖2 修改斥力函數(shù)仿真效果圖

2.2 自主建立虛擬目標(biāo)牽引點(diǎn)的方法

自主建立虛擬目標(biāo)牽引點(diǎn)的方法是在檢測(cè)到機(jī)器人陷入傳統(tǒng)人工勢(shì)場(chǎng)的局部極小點(diǎn)時(shí)，通過(guò)自主建立虛擬目標(biāo)牽引點(diǎn)并對(duì)原有目標(biāo)點(diǎn)進(jìn)行隔離的方法牽引機(jī)器人逐步走出局部極小點(diǎn)，其實(shí)現(xiàn)主要包括局部極小值點(diǎn)的檢測(cè)、自主虛擬目標(biāo)牽引點(diǎn)的建立和對(duì)原有目標(biāo)點(diǎn)的隔離兩個(gè)部分。

人工勢(shì)場(chǎng)法局部極小值的檢測(cè)一般采用一定間隔內(nèi)機(jī)器人所走的距離和閥值進(jìn)行比較的方法。該方法首先根據(jù)機(jī)器人移動(dòng)的步長(zhǎng)和障礙物影響范圍的大小來(lái)設(shè)置一個(gè)閥值T，然后每隔一定的間隔檢測(cè)一次這段間隔內(nèi)機(jī)器人所走的距離并和這個(gè)閥值T進(jìn)行比較。若這段間隔內(nèi)機(jī)器人所走的距離小于閥值T，可以認(rèn)為機(jī)器人陷入了局部極小點(diǎn)，反之，則沒(méi)有陷入局部極小點(diǎn)。

當(dāng)檢測(cè)到機(jī)器人陷入人工勢(shì)場(chǎng)法的局部極小點(diǎn)時(shí)，在與經(jīng)過(guò)機(jī)器人、障礙物的直線相垂直的直線上偏移一小段距離的地方設(shè)置一個(gè)虛擬目標(biāo)牽引點(diǎn)，并將機(jī)器人的目標(biāo)點(diǎn)從原有目標(biāo)點(diǎn)切換到這個(gè)虛擬目標(biāo)牽引點(diǎn)，進(jìn)而機(jī)器人將在這個(gè)虛擬目標(biāo)牽引點(diǎn)的牽引下移動(dòng)一小段距離。當(dāng)機(jī)器人到達(dá)這個(gè)虛擬目標(biāo)牽引點(diǎn)時(shí)，將機(jī)器人的目標(biāo)點(diǎn)從虛擬目標(biāo)牽引點(diǎn)再切換到原有的目標(biāo)點(diǎn)。如果一個(gè)虛擬目標(biāo)牽引點(diǎn)不能把機(jī)器人牽引出局部極小點(diǎn)，可以重復(fù)上述步驟繼續(xù)設(shè)置更多的虛擬目標(biāo)牽引點(diǎn)，直到把機(jī)器人牽引出局部極小點(diǎn)為止。

在Matlab平臺(tái)上對(duì)自主建立虛擬目標(biāo)牽引點(diǎn)的方法進(jìn)行了仿真，各參數(shù)設(shè)置如下:引力場(chǎng)系數(shù)k為200,斥力場(chǎng)系數(shù)m為200,機(jī)器人移動(dòng)步長(zhǎng)l為0.1m，障礙物的最大影響范圍為2m，閥值T為0.15m，仿真結(jié)果如圖3所示。通過(guò)仿真結(jié)果可以看出當(dāng)機(jī)器人進(jìn)入凹形槽的影響范圍且陷入局部極小點(diǎn)時(shí)，自主建立虛擬目標(biāo)牽引點(diǎn)的方法使其順利地繞開(kāi)了障礙物并到達(dá)了目標(biāo)點(diǎn)。

2.3 改進(jìn)算法

事實(shí)上，修改斥力方向方法程序的執(zhí)行效率較傳統(tǒng)人工勢(shì)場(chǎng)法更高，規(guī)劃出的路徑也較平滑，具有很多突出的優(yōu)點(diǎn)，是一種很高效的算法，但在有凹形槽障礙物的環(huán)境中進(jìn)行路徑規(guī)劃時(shí)該方法存在一定的局限性，如圖2b所示。為解決傳統(tǒng)人工勢(shì)場(chǎng)法局部極小值的問(wèn)題，本文在修改斥力函數(shù)的基礎(chǔ)上，提出了一種修改斥力方向和自主建立虛擬目標(biāo)牽引點(diǎn)相結(jié)合的算法。該算法的原理是在修改斥力方向算法中設(shè)置一個(gè)避免機(jī)器人和障礙物直接相碰撞的臨界值T1，用這個(gè)臨界值T1代替自主建立虛擬目標(biāo)牽引點(diǎn)方法中的檢測(cè)機(jī)器人是否陷入局部極小點(diǎn)的閾值T，若機(jī)器人與障礙物之間的距離始終保持大于臨界值T1，機(jī)器人采用修改斥力方向的算法規(guī)劃行走路徑；若機(jī)器人在行走的過(guò)程中遇到機(jī)器人與障礙物之間的距離小于臨界值T1的時(shí)候，機(jī)器人路徑規(guī)劃算法就從修改斥力方向的算法切換到自主建立虛擬目標(biāo)牽引點(diǎn)的算法，采用自主建立虛擬目標(biāo)牽引點(diǎn)的算法規(guī)劃?rùn)C(jī)器人前進(jìn)的路徑，其流程圖如圖4所示。

圖3 自主建立虛擬目標(biāo)牽引點(diǎn)仿真結(jié)果圖

圖4 改進(jìn)后算法流程圖

3 改進(jìn)算法的仿真實(shí)驗(yàn)結(jié)果及分析

本文對(duì)改進(jìn)后的算法在Matlab平臺(tái)上進(jìn)行了仿真，仿真在全局靜態(tài)環(huán)境下進(jìn)行，機(jī)器人在外界環(huán)境中是很小的，可以抽象成一個(gè)質(zhì)點(diǎn)，把障礙物尺寸考慮進(jìn)來(lái)折合成被外接圓包裹的圓形，圖5中(0,0)是起始點(diǎn)，目標(biāo)點(diǎn)為(28,30)，小實(shí)線圓表示包圍障礙物的外接圓，虛線圓表示障礙物的最大影響范圍，長(zhǎng)線條表示機(jī)器人的前進(jìn)路徑，各仿真參數(shù)設(shè)置如下:引力場(chǎng)系數(shù)k為200；斥力場(chǎng)系數(shù)m為300；障礙物的最大影響范圍為2m；機(jī)器人移動(dòng)的步長(zhǎng)l為0.1m；避免機(jī)器人和障礙物直接相碰撞的臨界值T1為1.5m，仿真操作界面和仿真結(jié)果如圖5所示。圖5a為Matlab平臺(tái)上的仿真操作界面，圖5b和圖5c為改進(jìn)后算法的仿真結(jié)果。

圖5 混合修改斥力方向和自主建立虛擬目標(biāo)牽引點(diǎn)算法的仿真結(jié)果圖

實(shí)驗(yàn)結(jié)果分析:圖5中起始點(diǎn)為(0,0)，目標(biāo)點(diǎn)為(28,30)，按照傳統(tǒng)人工勢(shì)場(chǎng)法進(jìn)行路徑規(guī)劃，在遇到位置為(7,7.5)障礙物時(shí)，機(jī)器人必將陷入局部極小點(diǎn)而無(wú)法到達(dá)目標(biāo)點(diǎn)，但通過(guò)圖5b和圖5c仿真結(jié)果可以看出，修改斥力方向的算法使機(jī)器人順利走出了傳統(tǒng)人工勢(shì)場(chǎng)法的局部極小點(diǎn)。在進(jìn)入凹形槽區(qū)域時(shí)，檢測(cè)到機(jī)器人和障礙物的距離小于設(shè)定的臨界值T1，機(jī)器人路徑規(guī)劃算法就從修改斥力方向的算法自動(dòng)切換到自主建立虛擬目標(biāo)牽引點(diǎn)的算法，在虛擬目標(biāo)牽引點(diǎn)的作用下，避免了修改斥力方向算法中機(jī)器人撞上凹形槽的情況，使機(jī)器人順利地繞過(guò)了凹形槽并到達(dá)了目標(biāo)點(diǎn)。本文改進(jìn)的算法可以把機(jī)器人從凹形槽的不同方向牽引出來(lái)，如圖5b和5c所示，然后進(jìn)行比較選擇一條較好的路徑作為機(jī)器人的前進(jìn)路徑。通過(guò)比較可以發(fā)現(xiàn)，圖5c的前進(jìn)路徑更加光滑，是一條較好的前進(jìn)路徑。綜合上述分析可知，本文對(duì)基于人工勢(shì)場(chǎng)法的路徑規(guī)劃算法的改進(jìn)方法是可行的。

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

對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法的原理、實(shí)現(xiàn)方法進(jìn)行了分析，并對(duì)改進(jìn)傳統(tǒng)人工勢(shì)場(chǎng)法的修改斥力方向方法和自主建立虛擬目標(biāo)牽引點(diǎn)方法進(jìn)行了研究，提出了一種修改斥力方向和自主建立虛擬目標(biāo)牽引點(diǎn)相混合的算法，該算法很好地解決了傳統(tǒng)人工勢(shì)場(chǎng)法的局部極小值問(wèn)題，仿真結(jié)果證明了改進(jìn)后算法的有效性。

[1]廖爽,許勇,王善超.智能汽車(chē)自動(dòng)駕駛的控制算法研究[J].計(jì)算機(jī)測(cè)量與控制,2014,22(8):2472-2474.

[2]石為人,黃興華,周偉.基于改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用,2010,30(8):2021-2023.

[3]黃靜,陳漢偉.移動(dòng)機(jī)器人全局路徑規(guī)劃算法的研究[J].儀表技術(shù)與傳感器,2014(12):80-83.

[4]黃炳強(qiáng),曹廣益.基于人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(27):26-28.

[5]Park M G,Jeon J H,Lee M C.Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing[J].IEEE International Symposium on Industrial Electronics,2001,3(6):1530-1535.

[6]吳正平,唐念,陳永亮,等.基于改進(jìn)人工勢(shì)場(chǎng)法的AUV路徑規(guī)劃[J].化工自動(dòng)化及儀表,2014,41(12):1421-1423.

[7]潘洲,萬(wàn)衡,李嘉琦.基于模糊人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].制造業(yè)自動(dòng)化,2015,37(7):4-8.

[8]曲志堅(jiān),張先偉,曹雁鋒,等.基于自適應(yīng)機(jī)制的遺傳算法研究[J].計(jì)算機(jī)應(yīng)用研究,2015,32(11):176-182.

[9]KHATIB O.Real-Time obstacle avoidance for manipulators and mobile robots[J].The International Journal Robotics Research,1986,5(1):90-98.

(責(zé)任編輯:馬金發(fā))

Research of Path Planning Algorithm Based on Improved Artificial Potential Field

LIU Yanju,DAI Tao,SONG Jianhui

(Shenyang Ligong University,Shenyang 110159,China)

In path planning of the mobile robot,the problem of local minimum points exists based on the traditional artificial potential field method.A path planning algorithm is proposed,which is based on combination of modifying the repulsive force direction and determines the virtual target point.In this algorithm,a critical value is set in the modified repulsion direction algorithm.In the process of the robot moving,when the distance between the robot and the obstacle is larger than the critical value,the path planning of the robot turns to the modified repulsive direction algorithm.When the distance between the robot and the obstacle is less than the critical value,the robot path planning algorithm is transferred from the modified repulsive direction algorithm to the autonomous virtual target traction point algorithm.The improved algorithm solves the problem of local minimum points,and the effectiveness of the improved algorithm is verified by simulation.

artificial potential field;robot path planning;goal non-reachable;local minimum point

2016-05-05

劉硯菊(1965—)，女，教授，博士，研究方向:多傳感器信息融合、目標(biāo)識(shí)別、智能檢測(cè)技術(shù)。

1003-1251(2017)01-0061-05

TP391.9

A