潘 洲，萬(wàn) 衡，王凱凱，胡中華

PAN Zhou, WAN Heng, WANG Kai-kai, HU Zhong-hua

（上海應(yīng)用技術(shù)學(xué)院 電氣與電子工程學(xué)院，上海 201418）

0 引言

隨著智能技術(shù)的不斷發(fā)展，自主移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的研究也成為了各國(guó)學(xué)者研究的熱點(diǎn)。研究路徑規(guī)劃的意義是想讓機(jī)器人擁有感知、規(guī)劃和控制等高等技能，其基本思想是旨在按照某一評(píng)估準(zhǔn)則（像移動(dòng)耗費(fèi)最小、路徑最短、時(shí)間最少等），在存在障礙物的室內(nèi)復(fù)雜場(chǎng)景下，搜尋一條從起點(diǎn)到目標(biāo)點(diǎn)的無(wú)碰撞的路徑[1]。目前常用的路徑規(guī)劃方法主要有人工勢(shì)場(chǎng)法[2]、模糊邏輯算法[3]，可視圖法[4]，柵格法[5]，蟻群算法[6]，神經(jīng)網(wǎng)絡(luò)法[7]等。由于人工勢(shì)場(chǎng)法相對(duì)于其它算法來(lái)說(shuō)具有反應(yīng)快速、計(jì)算簡(jiǎn)單以及實(shí)時(shí)性強(qiáng)等優(yōu)點(diǎn)，因而獲得了廣泛的應(yīng)用。

雖然人工勢(shì)場(chǎng)法有很多優(yōu)點(diǎn)，但也存在固有的缺陷：局部極小問(wèn)題。文獻(xiàn)[8]提出了一種基于虛擬障礙點(diǎn)（Virtual Obstacle Point）的方法來(lái)處理局部極小問(wèn)題。該方法在一定程度上解決了局部極小問(wèn)題，但還存在一定的缺陷：第一，在某種特殊情況下會(huì)反復(fù)陷入局部極小點(diǎn)，無(wú)法到達(dá)目標(biāo)點(diǎn)；第二，盲目的放置虛擬障礙點(diǎn)的位置，未考慮路徑規(guī)劃的效率問(wèn)題。本文在此基礎(chǔ)上，提出了一種改進(jìn)的虛擬障礙點(diǎn)法（Improved Virtual Obstacle Point），改進(jìn)后的算法可以很好的解決文獻(xiàn)[8]中所存在的問(wèn)題。仿真結(jié)果表明，APF-IVOP算法更具優(yōu)越性。

1 傳統(tǒng)人工勢(shì)場(chǎng)法原理

人工勢(shì)場(chǎng)法是由Khatib[9]提出的一種方法。其基本思想是設(shè)計(jì)出一種抽象的虛擬力場(chǎng)來(lái)處理機(jī)器人的運(yùn)動(dòng)，目標(biāo)對(duì)機(jī)器人產(chǎn)生“引力”，障礙物對(duì)機(jī)器人產(chǎn)生“斥力”，再利用它們的合力來(lái)控制機(jī)器人的動(dòng)作。在勢(shì)場(chǎng)中包含有斥力極和引力極，障礙物區(qū)域?qū)儆诔饬O，目標(biāo)區(qū)域?yàn)橐O。引力極和斥力極周?chē)a(chǎn)生相應(yīng)的勢(shì)場(chǎng)。移動(dòng)機(jī)器人在虛擬勢(shì)場(chǎng)中獲得一定的抽象力，推動(dòng)移動(dòng)機(jī)器人避開(kāi)障礙物，朝目標(biāo)運(yùn)動(dòng)。

勢(shì)場(chǎng)函數(shù)包含引力場(chǎng)函數(shù)和斥力場(chǎng)函數(shù)。在勢(shì)場(chǎng)中，障礙物O（Obstacle）對(duì)機(jī)器人R（Robot）產(chǎn)生排斥力，且距離越近，排斥力就越大，反之就越?。荒繕?biāo)點(diǎn)G（Goal）對(duì)機(jī)器人R產(chǎn)生引力，且距離越近，引力就越小，反之就越大。最后用引力與斥力的合力來(lái)牽引移動(dòng)機(jī)器人運(yùn)動(dòng)，構(gòu)造的勢(shì)場(chǎng)函數(shù)表示為：

式中，U為總勢(shì)場(chǎng)，UO為斥力場(chǎng)，Ug為引力場(chǎng)。勢(shì)場(chǎng)中的合力為：

式中，F(xiàn)為合力，決定了移動(dòng)機(jī)器人的運(yùn)動(dòng)；Fg為引力，F(xiàn)O為斥力。

在勢(shì)場(chǎng)中移動(dòng)機(jī)器人的受力分析圖如圖1所示。

2 APF-IVOP算法對(duì)局部極小問(wèn)題的優(yōu)化

所謂局部極小，就是在多障礙物環(huán)境中，當(dāng)機(jī)器人、障礙物、目標(biāo)點(diǎn)在同一條線上，并且障礙物在機(jī)器人和目標(biāo)點(diǎn)之間，在機(jī)器人尚未到達(dá)目標(biāo)點(diǎn)時(shí)，由于障礙物的位置因素，機(jī)器人在某一點(diǎn)受力平衡，機(jī)器人所受到的引力和斥力恰好大小相同方向相反，此時(shí)的合力為0，從而導(dǎo)致該點(diǎn)的勢(shì)場(chǎng)全局最小，致使機(jī)器人在此處停止不前或者徘徊，不知道下一步的運(yùn)動(dòng)方向，造成機(jī)器人無(wú)法到達(dá)目標(biāo)點(diǎn)，這就是人工勢(shì)場(chǎng)法的局部極小值問(wèn)題。為了讓機(jī)器人逃出局部極小值，研究學(xué)者們提出了很多的方法[10,11]，比如虛擬目標(biāo)點(diǎn)法、沿墻走、隨機(jī)逃走法等。

圖1 機(jī)器人受力分析圖

本文首先對(duì)文獻(xiàn)[8]中所提到的算法進(jìn)行敘述并分析其所存在的缺陷，然后再針對(duì)其存在的缺陷提出改進(jìn)方法。

文獻(xiàn)[8]中的方法如下：

1）如圖2所示，首先連接局部極小點(diǎn)R和目標(biāo)點(diǎn)G。

2）在RG上選擇一點(diǎn)V，使RV=dv，該點(diǎn)就是虛擬障礙點(diǎn)的位置。

3）根據(jù)下式得到V點(diǎn)的坐標(biāo)值，并記錄到虛擬障礙點(diǎn)的信息表中。

式中，(xr,yr)、(xv,yv)、(xg,yg)分別是R、V、G的坐標(biāo)值；atan2(yg-yr，xg-xr)為直線RV與X軸的夾角，加入的隨機(jī)數(shù)，避免機(jī)器人、虛擬障礙點(diǎn)、目標(biāo)點(diǎn)在同一條直線上時(shí)，消除一個(gè)局部極小點(diǎn)后又產(chǎn)生一個(gè)新的局部極小點(diǎn)，如此反復(fù)，使得機(jī)器人無(wú)法擺脫局部極小點(diǎn)。

4）在計(jì)算虛擬力時(shí)，虛擬障礙點(diǎn)的斥力計(jì)算和普通障礙物一樣。

圖2 文獻(xiàn)[8]中虛擬障礙點(diǎn)位置選擇

從本質(zhì)上說(shuō)，原文獻(xiàn)中設(shè)置虛擬障礙點(diǎn)的方法就是隨機(jī)在機(jī)器人附近添加一個(gè)虛擬障礙點(diǎn)，這樣做是有缺陷的：

2）文獻(xiàn)[8]并沒(méi)有判斷機(jī)器人所處位置與障礙物之間的關(guān)系，這樣盲目的添加虛擬障礙點(diǎn)，很有可能使得機(jī)器人多走很多彎路，不僅增加了機(jī)器人的規(guī)劃時(shí)間，降低了規(guī)劃的效率，而且完成路徑規(guī)劃的代價(jià)也增多。

本文中的做法是：

1）如圖3所示，首先連接局部極小點(diǎn)R和目標(biāo)點(diǎn)G，取dv為一個(gè)適當(dāng)?shù)某?shù)。

2）其次判斷機(jī)器人、障礙物、目標(biāo)點(diǎn)間的位置關(guān)系：首先通過(guò)傳感器獲取周?chē)系K物的信息，計(jì)算出障礙物兩邊與連線間的夾角判斷的大小。

計(jì)算公式如下：

式中，(xr,yr)、(xv,yv)、(xg,yg)分別是R、V、G的坐標(biāo)值；atan2(yg-yr,xg-xr)為直線RG與X軸的夾角，

6）在計(jì)算虛擬力時(shí)，虛擬障礙點(diǎn)的斥力計(jì)算和普通障礙物一樣。

圖3 本文虛擬障礙點(diǎn)位置選擇

利用APF-IVOP算法進(jìn)行路徑規(guī)劃的過(guò)程如下：

1）初始化起點(diǎn)和目標(biāo)點(diǎn)。

2）判斷機(jī)器人是否到達(dá)目標(biāo)點(diǎn)，如果是，則成功找到路徑，路徑規(guī)劃結(jié)束；如果否，則轉(zhuǎn)3）。

3）判斷機(jī)器人是否陷入局部極小，如果是，則添加一個(gè)虛擬障礙點(diǎn)后轉(zhuǎn)4）；如果否，直接轉(zhuǎn)4）。

4）根據(jù)勢(shì)場(chǎng)模型，計(jì)算當(dāng)前位置的合力。

5）計(jì)算機(jī)器人下一步位置，將機(jī)器人由當(dāng)前位置移至下一位置，轉(zhuǎn)2）。

APF-IVOP算法流程如圖4所示。

圖4 算法流程圖

3 仿真實(shí)驗(yàn)與結(jié)果

針對(duì)上文提到的部分問(wèn)題進(jìn)行了MATLAB仿真，仿真結(jié)果如圖5、圖6所示。從圖5中可以看出，當(dāng)RV與X軸夾角為0時(shí)，文獻(xiàn)中的算法會(huì)使得機(jī)器人無(wú)限陷入局部極小點(diǎn)，無(wú)法到達(dá)目標(biāo)點(diǎn)，本文中的算法有效的解決了這個(gè)問(wèn)題。從圖6中可以看出，在機(jī)器人陷入局部極小值時(shí)，當(dāng)RV與X軸夾角不為0時(shí)，原文獻(xiàn)中的算法在沒(méi)有對(duì)環(huán)境進(jìn)行判斷的情況下隨機(jī)選取了較差的路徑，連續(xù)兩次陷入局部極小點(diǎn)，耗費(fèi)了大量的時(shí)間，完成路徑規(guī)劃所花費(fèi)的代價(jià)較高，規(guī)劃出的路徑也較長(zhǎng)，規(guī)劃路徑的效率偏低；經(jīng)過(guò)判斷后的路徑，即用本文中算法規(guī)劃的路徑，其效果要明顯好于未經(jīng)過(guò)判斷的路徑，大大縮短了規(guī)劃的時(shí)間，規(guī)劃的效率明顯提升，完成路徑規(guī)劃所消耗的代價(jià)明顯降低，規(guī)劃出的路徑也更短更優(yōu)。通過(guò)以上仿真可以看出，APF-IVOP算法具有一定的優(yōu)越性和有效性。

圖5 RV與X軸夾角為0時(shí)

圖6 RV與X軸夾角不為0時(shí)

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

人工勢(shì)場(chǎng)法因其結(jié)構(gòu)簡(jiǎn)單、容易實(shí)現(xiàn)、能夠平滑路徑等優(yōu)點(diǎn)，而得到了廣泛的重視。本文針對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法存在的局部極小問(wèn)題，提出了一種改進(jìn)的人工勢(shì)場(chǎng)法，即APF-IVOP算法。該算法可以對(duì)周?chē)h(huán)境進(jìn)行探測(cè)并能夠動(dòng)態(tài)設(shè)置虛擬障礙點(diǎn)的位置，同時(shí)能夠有效處理不同位置關(guān)系下的局部極小問(wèn)題，該算法具有簡(jiǎn)單且易于實(shí)現(xiàn)、計(jì)算速度快、實(shí)時(shí)性好等優(yōu)點(diǎn)?；贏PFIVOP算法下的路徑規(guī)劃，所規(guī)劃出來(lái)的路徑更優(yōu)，消耗的代價(jià)更低，路徑規(guī)劃的效率也更高。最后通過(guò)MATLAB仿真驗(yàn)證了APF-IVOP算法的有效性。另外，對(duì)于路徑的平滑度和震蕩問(wèn)題的改進(jìn)可以采用文獻(xiàn)[12]中提到的采用模糊邏輯算法來(lái)進(jìn)行改進(jìn)。

[1] 李磊,葉濤,譚民,等.移動(dòng)機(jī)器人技術(shù)研究現(xiàn)狀與未來(lái)[J].機(jī)器人,2002,24(5)：475-480．

[2] 盧恩超,張鄧斕,寧雅男,等.改進(jìn)人工勢(shì)場(chǎng)法的機(jī)器人路徑規(guī)劃[J].西北大學(xué)學(xué)報(bào)：自然科學(xué)版,2012,42(5)：735-738.

[3] Yang S X, Luo C. A neural network approach to complete coveragepathplanning[J].IEEE Transactions on Syatems,Man and Cybernetics：Part B,2004,34(1)：718-724.

[4] GoerzenC,KongZ,Mettler B. A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance[J].Journal of Intelligentand Robotic Systems,2010, 57(1-4)：65-100.

[5] 董宇欣.移動(dòng)機(jī)器人路徑規(guī)劃方法研究[J].信息技術(shù),2006,30(6)：108-111.

[6] ColorniA,Dorigo M,ManiezzoV.Distributed Optimization by Ant Cnlnnies[A].Proceedings of the First European Conference 0nArtifial Life[C].1991：134-142.

[7] 王仲民.移動(dòng)機(jī)器人路徑規(guī)劃與軌跡跟蹤[M].北京：兵器工業(yè)出版社,2008.

[8] 黃健生.移動(dòng)機(jī)器人的路徑規(guī)劃研究[D].浙江：浙江大學(xué),2008.

[9] Khatib O. Real-time Obstacle Avoidance for Manipulators and MobileRobots[J].The International Journal of Robotics Research, 1986,5(1)：90-98．

[10] KoeingS,LikhachevM.Inproved fast replanningfor robot navigation in unknownterrain[A].2002 IEEE International Conf. on Robotics andAutomation,Washington[C].2002：968-975.

[11] Ke Liang, Zhiye Li,Dongyue Chen. Improved Artificial Potential Field for Unknown NarrowEnvironments[A].Proceeding of the 2004 IEEE International Conference on Robotics andBiomimetics, August[C].22-26,2004,688-692.

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