一種基于改進(jìn)人工勢(shì)場(chǎng)法的路徑規(guī)劃技術(shù)

摘 要：針對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法在路徑規(guī)劃中出現(xiàn)的局部最小值問(wèn)題和振蕩問(wèn)題，提出了引入虛擬局部目標(biāo)，修改斥力場(chǎng)函數(shù)的解決方案。為增強(qiáng)算法的實(shí)用性，提出了一種考慮障礙物體積的方案。最后文章還使用了另一種方法來(lái)優(yōu)化改進(jìn)的APF算法規(guī)劃出的路徑。在該方法中，最優(yōu)路徑由盡可能少的直線組成，節(jié)省了機(jī)器人運(yùn)動(dòng)的時(shí)間。仿真實(shí)驗(yàn)結(jié)果表明文章所提算法能夠較好的實(shí)現(xiàn)移動(dòng)機(jī)器人的路徑規(guī)劃任務(wù)。

關(guān)鍵詞：移動(dòng)機(jī)器人；路徑規(guī)劃；人工勢(shì)場(chǎng)法

1 人工勢(shì)場(chǎng)法概述

人工勢(shì)場(chǎng)法（APF）首先被Khatib提出[1]。APF可以快速地計(jì)算出一條高質(zhì)量的路徑并響應(yīng)動(dòng)態(tài)環(huán)境。然而，該算法被廣泛證明存在不可避免的缺點(diǎn)，該算法容易將機(jī)器人引入局部最小值和在障礙物前振蕩。有文獻(xiàn)提出了一種混合算法，該算法整合了環(huán)境信息的先驗(yàn)知識(shí)以便于執(zhí)行更加有效和安全的任務(wù)分配[2]。結(jié)果表明該方法能保證機(jī)器人即使在未知的動(dòng)態(tài)環(huán)境中操作，也不會(huì)陷入死鎖。盡管該方法有良好的特性，但該文獻(xiàn)所描述導(dǎo)航系統(tǒng)的典型缺點(diǎn)是系統(tǒng)依賴先驗(yàn)知識(shí)和導(dǎo)航策略。另一種改進(jìn)型APF算法也被提出，該算法使用粒子群優(yōu)化快速全局搜索和確定最佳路徑規(guī)劃[3]。為了處理傳統(tǒng)APF的局部最小值問(wèn)題，還有研究者提出了一種由機(jī)器回歸和勢(shì)場(chǎng)填充的方法[4]。類(lèi)似的方法也在其它文獻(xiàn)中提到，在計(jì)算最終的結(jié)果前，把一個(gè)對(duì)象放入勢(shì)場(chǎng)中，建立其到最近障礙物之間的連接來(lái)優(yōu)化路徑規(guī)劃[5]。其他改進(jìn)勢(shì)場(chǎng)法的方法也被研究過(guò)，比如有研究者將機(jī)器人和目標(biāo)位置之間的相對(duì)距離引入斥力函數(shù)，然后修改斥力方向確保全局最小值在目標(biāo)位置[6]。

然而上述所有的APF和它的改進(jìn)算法仍然會(huì)遇到一些缺點(diǎn)，比如在高時(shí)間復(fù)雜度和高維度情況下，有些算法能處理實(shí)時(shí)路徑規(guī)劃，有些算法無(wú)法完全解決局部最小值和振蕩問(wèn)題，使他們?cè)趯?shí)踐中效率低下。因此，上述算法下的路徑不是最優(yōu)路徑，僅僅是可行路徑。在文章中展示了一種有效的改進(jìn)APF算法，該方法能在已知環(huán)境中獲得一個(gè)沒(méi)有局部最小值問(wèn)題和振蕩問(wèn)題的全局最優(yōu)或次優(yōu)路徑。

2 傳統(tǒng)人工勢(shì)場(chǎng)法介紹

APF的基本思路是假設(shè)機(jī)器人是抽象的人造勢(shì)場(chǎng)范圍中一個(gè)移動(dòng)的質(zhì)點(diǎn)。環(huán)境中的人工勢(shì)場(chǎng)由目標(biāo)產(chǎn)生的引力勢(shì)場(chǎng)和障礙物產(chǎn)生的斥力勢(shì)場(chǎng)組成。引力勢(shì)場(chǎng)由目標(biāo)產(chǎn)生，方向指向目標(biāo)點(diǎn)，斥力場(chǎng)由不同障礙物共同產(chǎn)生，方向?yàn)檫h(yuǎn)離障礙物點(diǎn)。因此，勢(shì)場(chǎng)函數(shù)（1）就是機(jī)器人的APF算法，該函數(shù)的結(jié)果為引力勢(shì)場(chǎng)和斥力勢(shì)場(chǎng)相加。機(jī)器人沿著APF的方向控制其運(yùn)動(dòng)到目標(biāo)點(diǎn)。在APF算法下，機(jī)器人能通過(guò)搜索沿勢(shì)場(chǎng)函數(shù)方向下降的路線找到一條無(wú)碰撞的路徑。

機(jī)器人的坐標(biāo)是q=（x，y）T，因此APF定義為：

盡管傳統(tǒng)的APF算法能規(guī)劃出一條光滑的路徑，但其仍存在一些問(wèn)題。在機(jī)器人向目標(biāo)位置移動(dòng)的過(guò)程中，當(dāng)引力和斥力相等或幾乎相等，且互為反向時(shí)，機(jī)器人勢(shì)場(chǎng)力為0，這將會(huì)導(dǎo)致陷入局部最小值和在障礙物前振蕩。當(dāng)目標(biāo)的位置與障礙物十分接近時(shí)，機(jī)器人可能會(huì)出現(xiàn)目標(biāo)不可達(dá)。

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

機(jī)器人與目標(biāo)之間引力勢(shì)場(chǎng)的值取決于？籽goal（q）的距離，如式（3）。當(dāng)？籽（q）非常大時(shí)，引力同樣也很大，容易導(dǎo)致機(jī)器人移動(dòng)時(shí)離障礙物太近。為避免碰撞，當(dāng)機(jī)器人與障礙物的距離小于一定值時(shí)，讓斥力顯著增加，斥力函數(shù)修改如式（10）。

其中，系數(shù)d是斥力函數(shù)的影響因子，為指數(shù)形式，在下一節(jié)中給出。

對(duì)于上一節(jié)提到的局部最小值問(wèn)題，通過(guò)引入虛擬局部目標(biāo)來(lái)指導(dǎo)機(jī)器人逃離局部最小值，該方法也能解決振蕩問(wèn)題。此外，利用函數(shù)（11）和（12）來(lái)解決機(jī)器人目標(biāo)不可達(dá)的問(wèn)題，我們稱其為斥力抵消法。一旦機(jī)器人探測(cè)到目標(biāo)和障礙物之間的距離小于dob，目標(biāo)和機(jī)器人的距離小于dgr，機(jī)器人就僅沿著引力勢(shì)場(chǎng)前進(jìn)，不考慮引力勢(shì)場(chǎng)和斥力勢(shì)場(chǎng)的疊加。

U（q）=Uatt（q）+Urep（q） ，otherwisedUatt（q） ，？籽（q）？燮dob and ？籽goal？燮dgr （11）

F（q）=Fatt（q）+Frep（q） ，otherwiseFatt（q） ，||qg-qc||？燮dob and ||q-qg||？燮dgr （12）

前面提到的APF算法和改進(jìn)的APF算法都沒(méi)有明確定義多邊形障礙物的斥力場(chǎng)。在傳統(tǒng)APF的描述中，將人工勢(shì)場(chǎng)源看做質(zhì)點(diǎn)，即將目標(biāo)、障礙物和移動(dòng)機(jī)器人都看做質(zhì)點(diǎn)。若障礙物的體積過(guò)大，有可能導(dǎo)致APF算法規(guī)劃出的路徑穿過(guò)障礙物內(nèi)部，這樣機(jī)器人在沿著規(guī)劃好的路徑運(yùn)動(dòng)過(guò)程中會(huì)與障礙物發(fā)生碰撞。如圖1，虛線圓是障礙物的實(shí)際邊界，按照傳統(tǒng)的勢(shì)場(chǎng)法，機(jī)器人沿著路徑行走會(huì)穿過(guò)障礙物，這顯然是不合理的。因此，為增強(qiáng)APF算法的實(shí)用性，文章針對(duì)此問(wèn)題提出了改進(jìn)措施。

在一般的家庭環(huán)境中，障礙物形狀多樣，給路徑規(guī)劃帶來(lái)一定難度。文章提出了將障礙物邊界離散化的方法，即根據(jù)障礙物的實(shí)際形狀，在其邊界上離散的取若干個(gè)點(diǎn)，使用若干個(gè)點(diǎn)的勢(shì)場(chǎng)代替原先將障礙物看做質(zhì)點(diǎn)時(shí)的勢(shì)場(chǎng)，如圖2所示。上述改進(jìn)有效的解決了穿過(guò)障礙物的問(wèn)題。然而在某些情況下，改進(jìn)的勢(shì)場(chǎng)法規(guī)劃出的路徑仍然會(huì)出現(xiàn)穿過(guò)障礙物的情況，此時(shí)邊界上的點(diǎn)會(huì)對(duì)障礙物產(chǎn)生斥力，方向指向障礙物中心，這會(huì)導(dǎo)致機(jī)器人向著障礙物行走。如圖3所示，A點(diǎn)是機(jī)器人的下一步路徑點(diǎn)，由于目標(biāo)對(duì)障礙物的引力太大導(dǎo)致A點(diǎn)在障礙物內(nèi)部，此時(shí)由于障礙物邊界點(diǎn)對(duì)其存在斥力，導(dǎo)致機(jī)器人進(jìn)一步進(jìn)入障礙物，即B點(diǎn)。這是因?yàn)樗惴ㄖ胁介L(zhǎng)參數(shù)太大，導(dǎo)致所規(guī)劃的路徑一步就跨入障礙物內(nèi)部，因此障礙物邊界點(diǎn)間距的設(shè)定應(yīng)小于機(jī)器人的步長(zhǎng)。上述方法雖然增加了計(jì)算量，但能有效解決某些情況下與障礙物發(fā)生碰撞的問(wèn)題。

盡管上述改進(jìn)的APF能成功的解決局部最小值問(wèn)題和振蕩問(wèn)題，但仍不能規(guī)劃出一條在實(shí)際應(yīng)用中最優(yōu)或次優(yōu)的路徑。APF算法為路徑規(guī)劃設(shè)置了步長(zhǎng)，即APF算法會(huì)根據(jù)給定的步長(zhǎng)計(jì)算下一個(gè)路徑點(diǎn)，直到下一個(gè)路徑點(diǎn)為目標(biāo)點(diǎn)。在這種情況下，APF算法所規(guī)劃出來(lái)的路徑會(huì)有很多不必要的彎曲，這會(huì)使得機(jī)器人頻繁調(diào)整方向?qū)е聲r(shí)間的浪費(fèi)和能耗的增加。文章使用了另一種方法來(lái)優(yōu)化改進(jìn)的APF算法規(guī)劃出的路徑。在該方法中，最優(yōu)路徑由盡可能少的直線組成，節(jié)省了機(jī)器人運(yùn)動(dòng)的時(shí)間。

改進(jìn)的方法如下：從機(jī)器人的當(dāng)前位置到目標(biāo)位置，起始點(diǎn)連接了其后的路徑點(diǎn)成為一條直線。如果這條直線沒(méi)有穿過(guò)任何障礙物，起始點(diǎn)將重新連接下一個(gè)路徑點(diǎn)成為新的直線，直到這條線穿過(guò)障礙物，或這條線離障礙物的距離小于D0。將這條線保存為機(jī)器人的局部最優(yōu)路徑。然后系統(tǒng)將上一條直線的終點(diǎn)作為下一條直線的起點(diǎn)，使用同樣的方法生成新的直線。

使用圖4來(lái)舉例說(shuō)明改進(jìn)的APF算法。假設(shè)Ti∈{T1，T2，T3，...，Ti，Ti+1，...，Tn}是一系列由人工勢(shì)場(chǎng)法規(guī)劃出的路徑點(diǎn)，機(jī)器人沿著這些路徑點(diǎn)移動(dòng)就能無(wú)碰撞的到達(dá)目標(biāo)點(diǎn)。首先，初始點(diǎn)T1作為開(kāi)始點(diǎn)連接下一個(gè)點(diǎn)T2，成為直線L1-2。然后判斷L1-2是否已經(jīng)越過(guò)障礙物，或其與障礙物的最短距離D是否小于D0。如果L1-2沒(méi)有越過(guò)障礙物，或D大于D0，則重新連接T1和T3成為直線L1-3。重復(fù)前面的步驟，直到L1-i穿過(guò)障礙物，那么可行的局部最優(yōu)路徑是L1-i，即Ti是該直線的終點(diǎn)。因?yàn)門(mén)i+1不是目標(biāo)點(diǎn)，所以下一個(gè)初始點(diǎn)是Ti，類(lèi)似的連接Ti+1。因此在這個(gè)例子中，最優(yōu)路徑是L1-i和Li-n。換句話說(shuō)，機(jī)器人沿著L1-i和Li-n行走將最大化節(jié)省時(shí)間，并且距離最短。

綜合前面幾項(xiàng)改進(jìn)，完整的改進(jìn)APF算法如下：

（1）計(jì)算機(jī)器人當(dāng)前坐標(biāo)與各障礙物點(diǎn)之間的距離；（2）計(jì)算引力：根據(jù)式（4）計(jì)算引力；（3）計(jì)算斥力：根據(jù)式（7），若當(dāng)前坐標(biāo)與障礙物距離？籽（q）小于？籽0，計(jì)算斥力。否則忽略該障礙物斥力，即將斥力置為0。根據(jù)式（12），若目標(biāo)和障礙物的距離小于dob，目標(biāo)和機(jī)器人的距離小于dgr，將斥力置為0；（4）計(jì)算機(jī)器人所受的合力；（5）根據(jù)設(shè)定的步長(zhǎng)，使用合力計(jì)算下一步坐標(biāo)點(diǎn)；（6）將坐標(biāo)保存為T(mén)i；（7）重復(fù)前兩步，直到到達(dá)目標(biāo)；（8）依次搜索Ti；（9）連接初始點(diǎn)Ti到Tj，作為直線Li-j；（10）如果Li-j不符合條件，則連接Ti和Tj+1；（11）否則保存Li-j，然后將點(diǎn)Tj作為下一條直線的初始點(diǎn)；（12）返回第六步直到找到最后的目標(biāo)點(diǎn)；（13）獲取最優(yōu)路徑，機(jī)器人按照該路徑移動(dòng)。

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

仿真實(shí)驗(yàn)表明：文章所提出的改進(jìn)APF算法克服了傳統(tǒng)APF算法局部最小值和在障礙物前振蕩的缺點(diǎn)，在算法中考慮障礙物的體積使其實(shí)用性更強(qiáng)，最后對(duì)路徑進(jìn)行了優(yōu)化使得算法規(guī)劃出的路徑在路程長(zhǎng)度和機(jī)器人轉(zhuǎn)向時(shí)間上都有縮短。綜上文章所提出的改進(jìn)APF算法能夠較好的實(shí)現(xiàn)移動(dòng)機(jī)器人的路徑規(guī)劃任務(wù)。

參考文獻(xiàn)

[1]Khatib O. Real-time Obstacle Avoidance for Manipu-lators and Mobile Robots[J].International Journal of Robotics Research，1985，1（5）：500-505.

[2]Sgorbissa A，Zaccaria R. Planning and Obstacle Avoidance in Mobile Robotics[J].Robotics Autonomous Systems，2012，60（4）： 628-638.

[4]Zhang H，Yang L，Gao Z， et al. The Dynamic Path Planning Research for Mobile Robot Based on Artificial Potential Field[C]//Consumer Electronics， Communications and Networks （cecnet），2011 International Conference on， [S.l.]： [s.n.]，2011：2736-2739.

[4]Qi N，Ma B，Liu X， et al. A Modified Artificial Potential Field Algorithm for Mobile Robot Path Planning[J].World Congress on Intelligent Control Automation， 2008：2603-2607.

[5]Automation SOMEA，University TP，Tianjin， et al. An Optimized Method for Path Planning Based on Artificial Potential Field[C]//Null， [S.l.]： [s.n.]，2006：35-39.

[6]He B，Liu G，Gao J， et al. A Route Planning Method Based on Improved Artificial Potential Field Algorithm[C]//Communication Software and Networks （iccsn），2011 Ieee 3rd International Conference on， [S.l.]： [s.n.]，2011：550-554.