鄧學(xué)強(qiáng)

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山東 淄博 255091)

路徑規(guī)劃是移動(dòng)機(jī)器人研究領(lǐng)域中的一個(gè)重要方向.所謂路徑規(guī)劃是指在滿足某種性能指標(biāo)最優(yōu)或者準(zhǔn)優(yōu)的前提下，尋找一條在設(shè)定區(qū)域內(nèi)從起始點(diǎn)到目標(biāo)點(diǎn)且避開(kāi)障礙物的連續(xù)路徑[1].目前，路徑規(guī)劃主要分為兩大類(lèi)：環(huán)境信息已知的全局路徑規(guī)劃和環(huán)境信息未知或部分可知的局部路徑規(guī)劃[2].常用的路徑規(guī)劃方法主要有人工勢(shì)場(chǎng)法、柵格法[3]、遺傳算法[4]、模糊邏輯[5-6]、人工神經(jīng)網(wǎng)絡(luò)[7]等，其中人工勢(shì)場(chǎng)法相對(duì)于神經(jīng)網(wǎng)絡(luò)、遺傳算法等算法具有規(guī)劃效果安全可靠、計(jì)算量小的優(yōu)點(diǎn)，是局部路徑規(guī)劃中比較成熟且高效的一種規(guī)劃方法[8].但由于該算法依據(jù)的是局部的環(huán)境信息，缺乏宏觀自我調(diào)控能力，從而可能會(huì)使機(jī)器在運(yùn)動(dòng)過(guò)程中陷入局部極小值點(diǎn)而不能到達(dá)目標(biāo)點(diǎn)，這就是目標(biāo)不可達(dá)問(wèn)題[9].目前，學(xué)者們已經(jīng)研究出多種逃出局部極小值點(diǎn)的方法，如沿墻走[10]、模擬退火算法[11]、隨機(jī)逃走法[12]和動(dòng)態(tài)步長(zhǎng)折半法[13]等.本文采用改進(jìn)斥力函數(shù)的方法來(lái)解決目標(biāo)不可達(dá)問(wèn)題，在構(gòu)造新的斥力勢(shì)場(chǎng)函數(shù)時(shí)，考慮機(jī)器人與目標(biāo)點(diǎn)的相對(duì)距離，并對(duì)障礙物的作用范圍進(jìn)行分段，在不同的分段采用不同的斥力.最后，利用Matlab軟件驗(yàn)證該方法能夠有效解決傳統(tǒng)人工勢(shì)場(chǎng)法中的目標(biāo)不可達(dá)問(wèn)題.

1 傳統(tǒng)人工勢(shì)場(chǎng)算法模型

Khatib首先提出了人工勢(shì)場(chǎng)的概念[14].人工勢(shì)場(chǎng)法的基本思想就是將機(jī)器人的運(yùn)動(dòng)環(huán)境虛擬成一種抽象的人造勢(shì)場(chǎng)，在目標(biāo)位置構(gòu)造引力勢(shì)場(chǎng)，在障礙物周?chē)鷺?gòu)造斥力勢(shì)場(chǎng)，引力場(chǎng)的引力吸引機(jī)器人朝目標(biāo)點(diǎn)方向移動(dòng)，斥力場(chǎng)的斥力阻止機(jī)器人朝障礙物方向移動(dòng)，在這兩個(gè)勢(shì)場(chǎng)力的共同作用下，機(jī)器人朝目標(biāo)點(diǎn)移動(dòng)[15].機(jī)器人受力分析如圖1所示.

圖1 機(jī)器人在多障礙物下受力分析圖

假設(shè)機(jī)器人簡(jiǎn)化為一個(gè)質(zhì)點(diǎn)并且工作空間為二維空間，機(jī)器人坐標(biāo)向量為X=(x,y)，目標(biāo)點(diǎn)的坐標(biāo)向量為Xg=(xg,yg)，總的勢(shì)場(chǎng)可表示為引力場(chǎng)和斥力場(chǎng)之和，即

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

(1)

其中：Uatt(X)為引力場(chǎng)，Urep(X)為斥力場(chǎng)，Usum(X)為合力場(chǎng).

勢(shì)場(chǎng)中機(jī)器人的合力表示為

Ftotal=Fatt+Frep

(2)

其中：引力Fatt=-grad[Uatt(X)]，斥力Frep=-grad[Urep(X)]，F(xiàn)total為引力與斥力之和.

機(jī)器人在二維空間中所受到的合力即為

(3)

1.1 引力的計(jì)算

目標(biāo)點(diǎn)的引力能夠引導(dǎo)機(jī)器人向目標(biāo)點(diǎn)運(yùn)動(dòng)，具有導(dǎo)航作用.引力場(chǎng)的方向指向目標(biāo)點(diǎn)，引力的大小與機(jī)器人離目標(biāo)點(diǎn)距離的平方成反比.

X處的引力函數(shù)Uatt(X)與目標(biāo)位置Xg=(xg,yg)有關(guān)，目標(biāo)對(duì)機(jī)器人的引力勢(shì)函數(shù)為

(4)

相應(yīng)的引力Fatt(X)為目標(biāo)勢(shì)場(chǎng)的負(fù)梯度，其公式為

Fatt=-grad[Uatt(X)]=-k(X-Xg)=kpa

(5)

式中：k為引力增益系數(shù)，是正數(shù)；X為當(dāng)前機(jī)器人在二維空間中的坐標(biāo)；Xg為目標(biāo)點(diǎn)位置；pa=‖X-Xg‖為機(jī)器人與目標(biāo)點(diǎn)之間的相對(duì)距離，機(jī)器人在引力作用下可以線性收斂到目標(biāo)點(diǎn).

1.2 斥力的計(jì)算

障礙物的斥力能夠使移動(dòng)機(jī)器人避開(kāi)障礙物，斥力大小的計(jì)算應(yīng)從障礙物的邊界算起.當(dāng)機(jī)器人遇到多個(gè)障礙物時(shí)，采用迭加的方式來(lái)求得多個(gè)障礙物對(duì)機(jī)器人的斥力.

障礙物附近的斥力場(chǎng)一般采用Khatib提出的FIRAS函數(shù)[16]，斥力勢(shì)函數(shù)為

(6)

式中：m為斥力增益系數(shù)，是正數(shù)；p表示機(jī)器人與障礙物的最短距離；p0是一個(gè)大于零的常數(shù)，表示障礙物的影響距離，在p0之外的機(jī)器人不受此障礙物的影響.相應(yīng)的引力為目標(biāo)勢(shì)場(chǎng)的負(fù)梯度，其公式為

Frep=-grad[Urep(X)]=

(7)

由公式(2)可求出作用于機(jī)器人的合力Ftotal.

1.3 傳統(tǒng)人工勢(shì)場(chǎng)法存在的問(wèn)題分析

機(jī)器人的合力Ftotal決定了機(jī)器人的運(yùn)動(dòng)方向，當(dāng)目標(biāo)點(diǎn)在障礙物的影響范圍之內(nèi)時(shí)，隨著機(jī)器人接近目標(biāo)點(diǎn)，吸引力越來(lái)越小，而斥力越來(lái)越大，由于斥力過(guò)大而引力過(guò)小，最終兩者達(dá)到平衡，形成局部極小值點(diǎn)，因而總的勢(shì)場(chǎng)力在目標(biāo)點(diǎn)達(dá)不到全局最小，此時(shí)，機(jī)器人停滯，不能到達(dá)目標(biāo)點(diǎn)，產(chǎn)生了目標(biāo)不可達(dá)問(wèn)題.

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

為了解決傳統(tǒng)人工勢(shì)法中的目標(biāo)不可達(dá)問(wèn)題，本文對(duì)傳統(tǒng)人工勢(shì)場(chǎng)中的斥力函數(shù)進(jìn)行改進(jìn)，在改進(jìn)的斥力勢(shì)場(chǎng)函數(shù)中通過(guò)引入機(jī)器人與目標(biāo)點(diǎn)的相對(duì)距離，將原來(lái)的斥力函數(shù)乘以一個(gè)調(diào)節(jié)因子(X-Xg)n，并對(duì)障礙物的作用范圍進(jìn)行分段，在不同的分段采用不同的斥力，使得目標(biāo)點(diǎn)位置的斥力為零，機(jī)器人在目標(biāo)點(diǎn)位置總的勢(shì)場(chǎng)力為全局最小.

用m來(lái)表示斥力增益系數(shù)，m為正數(shù)；用p來(lái)表示機(jī)器人與障礙物的最短距離；用p0來(lái)表示障礙物的影響距離，在p0之外的機(jī)器人不受此障礙物的影響，p0是一個(gè)大于零的常數(shù)；用p1來(lái)對(duì)p0進(jìn)行分段：p1≤p≤p0的區(qū)域?yàn)榭煽貐^(qū)，機(jī)器人在可控區(qū)受到的障礙物的斥力大小為p的線性收斂；p

(8)

斥力為斥力勢(shì)場(chǎng)的負(fù)梯度，由式(8)進(jìn)而得到斥力，其公式為

Frep=-grad[Urep(X)]=

(9)

1)當(dāng)p1≤p≤p0時(shí)，

(10)

2)當(dāng)p

(11)

式中：pa=‖X-Xg‖，表示機(jī)器人與目標(biāo)點(diǎn)之間的相對(duì)距離，n為大于零的任意實(shí)數(shù)，其中Frep1和Frep2是Frep的兩個(gè)分力.改進(jìn)的人工勢(shì)場(chǎng)法中，當(dāng)機(jī)器人接近目標(biāo)點(diǎn)時(shí)，引力勢(shì)場(chǎng)增加時(shí)，斥力勢(shì)場(chǎng)隨著減小，在目標(biāo)點(diǎn)處斥力達(dá)到0，當(dāng)且僅當(dāng)X=Xg時(shí)，總的勢(shì)場(chǎng)力可達(dá)到全局最小值0.通過(guò)適當(dāng)選取k、m、n的值，可以有效解決目標(biāo)不可達(dá)問(wèn)題.

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

3.1 仿真實(shí)驗(yàn)步驟

根據(jù)上述算法設(shè)計(jì)，利用Matlab軟件開(kāi)發(fā)平臺(tái)進(jìn)行算法仿真實(shí)驗(yàn)，具體步驟如下：

1)設(shè)置機(jī)器人的工作環(huán)境為一個(gè)50×50的二維空間，引力增益系數(shù)k為15，斥力增益系數(shù)m為25，機(jī)器人步長(zhǎng)l為0.5，障礙物的影響距離p0為1(注：k、m、p0的值與機(jī)器人的規(guī)劃路徑有直接關(guān)系，可進(jìn)行適當(dāng)調(diào)整).

2)隨機(jī)設(shè)置機(jī)器人起始位置、目標(biāo)點(diǎn)位置、障礙物的位置及個(gè)數(shù).

3)根據(jù)機(jī)器人當(dāng)前位置信息計(jì)算引力和斥力.

4)由合力決定機(jī)器人下一步的動(dòng)作，更新機(jī)器人與目標(biāo)、與障礙物的角度，更新機(jī)器人的坐標(biāo)位置，記錄機(jī)器人所經(jīng)過(guò)的點(diǎn).

5)判斷機(jī)器人是否到過(guò)目標(biāo)點(diǎn)，到達(dá)則終止，否則轉(zhuǎn)入步驟3).

3.2 實(shí)驗(yàn)結(jié)果

仿真實(shí)驗(yàn)利用Matlab軟件，在二維環(huán)境下應(yīng)用本文提出的算法進(jìn)行模擬仿真.在仿真實(shí)驗(yàn)中，設(shè)置起始點(diǎn)為五星，目標(biāo)點(diǎn)為十字，機(jī)器人為圓點(diǎn)，障礙物為圓圈，仿真結(jié)果如圖2所示.

仿真實(shí)驗(yàn)中，隨機(jī)生成起始點(diǎn)位置、目標(biāo)點(diǎn)位置，隨機(jī)分布障礙物的位置、生成障礙物的個(gè)數(shù).機(jī)器人從起點(diǎn)出發(fā)，利用本文的算法，避開(kāi)了障礙物，到達(dá)了目標(biāo)點(diǎn)，實(shí)驗(yàn)成功.

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

針對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法中的目標(biāo)不可達(dá)問(wèn)題，本文提出了新的斥力改進(jìn)函數(shù)，在改進(jìn)的斥力函數(shù)中考慮了機(jī)器人與目標(biāo)點(diǎn)的相對(duì)距離，并對(duì)障礙物的作用范圍進(jìn)行分段，在不同的分段采用不同的斥力來(lái)解決目標(biāo)不可達(dá)問(wèn)題.將此算法應(yīng)用于移動(dòng)機(jī)器人的局部路徑規(guī)劃，通過(guò)對(duì)人造勢(shì)場(chǎng)中引力與斥力合力的計(jì)算，機(jī)器人能夠從起始點(diǎn)無(wú)碰撞地繞開(kāi)所有障礙物到達(dá)目標(biāo)點(diǎn).利用Matlab對(duì)機(jī)器人運(yùn)動(dòng)仿真的結(jié)果表明該算法有效，畫(huà)出了機(jī)器人運(yùn)動(dòng)的軌跡，找出了一種比較好的路徑規(guī)劃方案.但是機(jī)器人所處現(xiàn)實(shí)的環(huán)境是復(fù)雜多變的，假如機(jī)器人所處的環(huán)境是動(dòng)態(tài)時(shí)，還要合理地引入機(jī)器人和障礙的移動(dòng)速度等信息，只有通過(guò)不斷地修改完善勢(shì)場(chǎng)函數(shù)，路徑規(guī)劃才能更為合理，這是下一步研究的重點(diǎn)問(wèn)題.

(a)起始點(diǎn)與目標(biāo)點(diǎn)距離較遠(yuǎn)，障礙物密集

(b)起始點(diǎn)與目標(biāo)點(diǎn)距離較近，障礙物密集圖2 仿真實(shí)驗(yàn)結(jié)果

[1] 謝斌，劉士榮，俞金壽.基于在線圖搜索的移動(dòng)機(jī)器人遍歷運(yùn)動(dòng)規(guī)劃[J].華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，33(4)：551-552.

[2] 王帥，連翠玲，趙旭.基于勢(shì)場(chǎng)的運(yùn)動(dòng)路徑規(guī)劃研究[J].河北省科學(xué)院學(xué)報(bào)，2011，28(4)：64-66.

[3] 楊杰，賀利樂(lè)，李榮麗，等.基于改進(jìn)勢(shì)場(chǎng)柵格法的移動(dòng)機(jī)器人路徑規(guī)劃[J].煤礦機(jī)械， 2012，33(8)：74-76.

[4] 劉彩虹，胡吉全，齊曉寧.基于混合遺傳算法的連續(xù)空間下機(jī)器人的路徑規(guī)劃[J].武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2003，27(6)：819-821.

[5] Yang S X，Meng M.Neural network approaches to dynamic collision-free trajectory generation[J]．IEEE Transactions on Systems，Man and Cybernetics：Part B，2001，31(3)：302-317.

[6] Yang S X，Luo C．A neural network approach to complete coveragepath planning[J]．IEEE Transactions on Systems，Man and Cybernetics：Part B，2004，34(1)：718-724.

[7] 顧永超.一種基于藍(lán)牙技術(shù)的室內(nèi)定位子系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京：北京大學(xué)，2009.

[8]張建英，劉暾.基于人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人最優(yōu)路徑規(guī)劃[J].航空學(xué)報(bào)，2007，28(8)：183-188.

[9]吳喬喬，曾虹，張翔.一種人工勢(shì)場(chǎng)路徑規(guī)劃改進(jìn)算法的研究[J].杭州電子科技大學(xué)學(xué)報(bào)，2008，28(3)：43-46.

[10] Ge S S，Lai X C，Mamun A A．Boundary following and globally convergent path planning using instant goals[J]．IEEE Transactions on Systems，Man and Cybernetics:Part B，2005，35(2)：240-254.

[11]張培艷，呂恬生.基于模擬退火—人工勢(shì)場(chǎng)法的足球機(jī)器人路徑規(guī)劃研究[J].杭州科學(xué)與技術(shù)，2003，22(4)：547-548.

[12]于振中，閆繼宏，趙杰，等.改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2011，43(1)：50-55.

[13]李曉麗，謝敬，傅衛(wèi)平.一種改進(jìn)勢(shì)場(chǎng)法在多機(jī)器人避碰規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(17)：56-58.

[14] Khatib O. Real- time obstacle avoidance for maipulators and mobile robots[J].The International Journal of Robotics Research，1986，5(1)：90-98.

[15] 申魁華，譚躍剛.關(guān)于人工勢(shì)場(chǎng)法局部最小問(wèn)題的一種解決方法[J].武漢理工大學(xué)學(xué)報(bào)，2005，27(8)：77-79.

[16] 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):1 530-1 535.