張希聞,肖本賢

基于人工勢場法的移動機(jī)器人動態(tài)路徑規(guī)劃

張希聞1,2,肖本賢1,2

1. 合肥工業(yè)大學(xué)電氣工程與自動化學(xué)院, 安徽 合肥 230009 2. 合肥工業(yè)大學(xué)工業(yè)與裝備技術(shù)研究院, 安徽 合肥 230009

目前移動機(jī)器人越來越多地被用于物流倉庫中進(jìn)行勞動力的解放。本文采用改進(jìn)人工勢場法代替?zhèn)鹘y(tǒng)的人工勢場法進(jìn)行動態(tài)路徑規(guī)劃，其中引用了A*算法的一些思路來彌補(bǔ)傳統(tǒng)人工勢場法容易形成局部最優(yōu)解的不足。在實驗室環(huán)境下，針對動態(tài)的障礙設(shè)計出一條更為快捷的避障路徑。當(dāng)障礙存在而可能使移動機(jī)器人掉入陷阱時，采用障礙連鎖法將障礙連接，形成新的障礙，使得移動機(jī)器人順利通過陷阱。

移動機(jī)器人; 動態(tài)路徑規(guī)劃; A*算法; 人工勢場法

作為自動控制研究的一個重要方向，路徑規(guī)劃一直被我們迫切需求著。在一個障礙已知或未知的封閉區(qū)域中對機(jī)器人進(jìn)行路徑規(guī)劃是當(dāng)下的一種研究熱點，而障礙已知的環(huán)境中，障礙又分為靜態(tài)障礙和動態(tài)障礙，動態(tài)障礙使用一般的算法如：A*算法、蟻群算法、F*算法，解決的相對較為復(fù)雜。作為虛擬力場算法的代表，人工勢場法以他的最優(yōu)性、快捷性顯得尤為突出。作為一種較為完善的方法，人工勢場法能更好的躲避動態(tài)的障礙?？旖莸倪\(yùn)算、實時性的避障成為了人工勢場法的主要優(yōu)點，不過此算法也并非是盡善盡美，其主要的實時性具有一些瑕疵，比如，它只關(guān)注局部的最優(yōu)解，而并沒有視全局的最優(yōu)解。本文主要思路是使用改進(jìn)的人工勢場法來彌補(bǔ)傳統(tǒng)人工勢場法局部最優(yōu)解的缺陷，使用A*算法生成一定數(shù)量的節(jié)點，然后以人工勢場法連接節(jié)點與節(jié)點減少局部最優(yōu)解的生成。先以A*算法做靜態(tài)路徑規(guī)劃生成大量的節(jié)點，在節(jié)點與節(jié)點之間使用人工勢場法，這樣可以優(yōu)化人工勢場法目標(biāo)點過遠(yuǎn)造成的引力場過大的問題。不但可以提高運(yùn)算效率而且還能減少路徑長度。將二者結(jié)合起來更有效的進(jìn)行動態(tài)障礙規(guī)避。

當(dāng)移動機(jī)器人陷入了障礙陷阱時，即移動機(jī)器人形成了徘徊抖動狀態(tài)，本文擬用連鎖障礙法。即先對障礙進(jìn)行一次判定，然后將障礙陷阱采取障礙連鎖形成新的障礙結(jié)構(gòu)，確保改進(jìn)人工勢場法可以順利通過該處。

A*算法本身路徑不具有人工勢場法的平滑性和動態(tài)障礙的規(guī)避能力，二者取長補(bǔ)短、相得益彰。不但可以進(jìn)行動態(tài)的路徑規(guī)劃，而且可以使得路徑較為平滑并且能夠防止由于遠(yuǎn)點終點的引力場過大造成的局部最優(yōu)解的情況發(fā)生。

1 相關(guān)算法

本文采用的是改進(jìn)人工勢場法進(jìn)行動態(tài)路徑規(guī)劃。

1.1 人工勢場法

人工勢場法的思路是在建模后的倉庫中假設(shè)有虛擬的引力場和斥力場存在，二者的作用平衡使得移動機(jī)器人能夠躲避障礙。終點的引力與移動機(jī)器人和終點的距離成正比；障礙和移動機(jī)器人之間的斥力與障礙和移動機(jī)器人之間的距離成反比。在二者的綜合作用下，移動機(jī)器人會找到一個力的平衡點，從而生成一個從初始位置到終止位置的路徑規(guī)劃。這其中，引力勢場函數(shù)為：

公式中，為移動機(jī)器人現(xiàn)在的位置，X為目標(biāo)點的位置，0為路障的位置，K為引力勢場的常數(shù)，K為斥力勢場常數(shù)，0障礙造成的威脅的距離的最大值。

由引力勢場公式和斥力勢場公式的負(fù)梯度延伸出引力勢場函數(shù)和斥力勢場函數(shù)公式如下：

人工勢場法在較為簡單的環(huán)境中具有不錯的路徑規(guī)劃能力，從初始點到終止點的無碰撞路徑可以簡單快捷的生成。但是一旦環(huán)境變得復(fù)雜，人工勢場法馬上會出現(xiàn)相應(yīng)的問題，諸如極限值點造成的局部最優(yōu)解問題，原理也較容易理解，即為局部障礙物過多從而引力斥力抵消造成了移動機(jī)器人判定為此時合力為0，生成局部最優(yōu)解。

1.2 A*算法

A*算法是啟發(fā)性避障的路徑規(guī)劃算法，可以在航空，游戲，物流等多種領(lǐng)域發(fā)揮重要的作用。普通的情況下，A*算法的下一次行動方向由八種可能所構(gòu)成，即：左、上、右、下、左上、右上、左下、右下。采用估價函數(shù)法對A*算法進(jìn)行一種雙重估價，即：()=()+()

1.3 連鎖障礙法

人工勢場法對每個障礙處理是分開，即每個障礙的均被視為有單獨的斥力場，但是有限障礙存在一種類似于陷阱的結(jié)構(gòu)，即當(dāng)移動機(jī)器人移動至此位置時會形成多個障礙的斥力場與引力場構(gòu)成的力平衡，從而無法進(jìn)行下一步的移動，即掉入陷阱狀態(tài)，反復(fù)徘徊抖動停滯不前。判定掉入陷阱狀態(tài)，本文取閾值，當(dāng)一個障礙物周圍存在至少兩個距離它的距離小于閾值的障礙物時，本文即視為此處為障礙陷阱，此時本文擬用障礙陷阱連鎖法，將陷阱周圍的障礙之間的可行走區(qū)域進(jìn)行連接，從而生成一個新的“障礙”。再從節(jié)點向下一個節(jié)點出發(fā)。如圖1和圖2所示

圖 1 障礙陷阱

圖 2 連鎖障礙

2 改進(jìn)人工勢場法

2.1 倉庫建模

圖 3 倉庫

2.2 改進(jìn)人工勢場法

針對人工勢場法在障礙較多時出現(xiàn)的局部最優(yōu)解問題，本文擬采用先使用A*算法生成節(jié)點，然后在節(jié)點間使用人工勢場法的方法，來優(yōu)化局部最優(yōu)解的問題，即先將動態(tài)障礙固定使用A*算法進(jìn)行全局路徑規(guī)劃，A*算法在全局路徑規(guī)劃后會生成一定數(shù)量的節(jié)點，作為根據(jù)，保留這些節(jié)點，用人工勢場法在節(jié)點間分別進(jìn)行路徑規(guī)劃，不但可以改進(jìn)人工勢場法距離目標(biāo)點過遠(yuǎn)造成的引力場過大而且還可以改進(jìn)A*算法不可進(jìn)行動態(tài)路徑規(guī)劃和路徑不夠平滑的缺點。結(jié)合二者的優(yōu)勢形成改進(jìn)人工勢場法。

與此同時，本文針對人工勢場法的移動機(jī)器人遇陷阱徘徊抖動問題采用障礙連鎖法，當(dāng)一個障礙周圍至少存在兩個障礙與其距離小于閾值，本文即視為此處存在障礙陷阱，易使移動機(jī)器人陷入徘徊抖動狀態(tài)，采取將障礙連鎖形成新的障礙的方法可以有效的避免障礙陷阱的威脅，使得移動機(jī)器人更好的利用改進(jìn)人工勢場法進(jìn)行動態(tài)路徑規(guī)劃。方法流程圖如圖4所示。

圖 4 流程圖

3 仿真與實驗

為了證明本文思路，本文分別進(jìn)行了傳統(tǒng)人工勢場法的路徑規(guī)劃和本文改進(jìn)后的人工勢場法進(jìn)行路徑規(guī)劃，對比了路徑長度、障礙陷阱躲避等方面。本文在15乘15柵格中的倉庫中進(jìn)行路徑規(guī)劃，使用的計算機(jī)設(shè)備：Window10操作系統(tǒng)。CPU為i7-7200U，內(nèi)存為4 G。

圖5和圖6為15乘15仿真實驗，其中線條左下起始點為路徑起始點，線條右上終止點為路徑終點，黑色方格為靜態(tài)障礙，綠色方格為動態(tài)障礙，藍(lán)色為A*算法生成的節(jié)點。線為規(guī)劃出的路徑，圖中可以看出，改進(jìn)人工勢場法對于障礙陷阱有更為合理的處理，并且規(guī)劃出的路徑較原人工勢場法更為合理。路徑更為平滑，且可以合理規(guī)避障礙。二者對比結(jié)果如表1所示。

圖 5 原算法結(jié)果

圖 6 改進(jìn)算法結(jié)果

移動機(jī)器人實驗如圖7所示。

為了驗證本文改進(jìn)后的算法產(chǎn)生的結(jié)論，實驗建立在機(jī)器人操作系統(tǒng)上進(jìn)行。移動機(jī)器人具有通過相機(jī)采集外界數(shù)據(jù)功能，可以準(zhǔn)確的獲取環(huán)境因素和障礙因素。經(jīng)過計算生成一種具有三個維度的點云數(shù)據(jù)，然后轉(zhuǎn)化為激光模擬的數(shù)據(jù)，依靠和模塊建模二維地圖柵格。接下來使用_里面的以及共同協(xié)作完成全局和部分路徑生成。

圖 7 移動機(jī)器人

4 結(jié)束語

綜合上面的實驗、數(shù)據(jù)和大量的理論知識，本文改進(jìn)后的人工勢場法相較原來的人工勢場法能更好的進(jìn)行全局的路徑規(guī)劃，而不是形成局部極小值，從而陷入局部最優(yōu)解的尷尬境地，這個辦法對A*算法取長補(bǔ)短，多個節(jié)點的提取使得引力場和斥力場的作用更為合理，取得了一定的效果。但是也有一些不足，比如需要A*法來生成節(jié)點，后續(xù)工作希望找到一種可以替代A*算法生成節(jié)點的算法，對于人工勢場法做更好的補(bǔ)充。

[1] 何雨楓,曾慶化,王云舒,等.室內(nèi)微型飛行器實時路徑規(guī)劃算法研究[J].電子測量技術(shù),2014,37(2):23-27

[2] Ahmed SU, Akhter A, Kunwar F. Cellular automata based real time path planning for mobile robots[C]. IEEE:12th International Conference on Control Automation Robotics ＆ Vision (ICARCV), 2012:142-147

[3] 丁琳,管小衛(wèi),朱霞.基于RSSI的集群實時定位系統(tǒng)設(shè)計[J].國外電子測量技術(shù),2014,33(12):69-73

[4] Jeddisaravi K, Alitappeh RJ, Pimenta LCA,. Multi-objective approach for robot motion planning in search tasks[J]. Applied Intelligence, 2016,45(2):305-321

[5] 張殿富,劉福.基于人工勢場法的路徑規(guī)劃方法研究及展望[J].計算機(jī)工程與科學(xué),2013,35(6):88-95

[6] Bakdi A, Hentout A, Boutami H,. Optimal path planning and execution for mobile robots using genetic algorithm and adaptive fuzzy-logic control[J]. Robotics and Autonomous Systems, 2017,89(1):95-109

[7] 劉建華,楊建國,劉華平,等.基于勢場蟻群算法的移動機(jī)器人全局路徑規(guī)劃方法[J].農(nóng)業(yè)機(jī)械學(xué)報,2015,46(9):18-27

[8] 王殿君.基于改進(jìn)A*算法的室內(nèi)移動機(jī)器人路徑規(guī)劃[J].清華大學(xué)學(xué)報:自然科學(xué)版,2012,52(8):1085-1089

[9] Zhou ZP, Nie YF, Gao M. Enhanced ant colony optimization algorithm for global path planning of mobile robots[C]. IEEE: International Conference on Computational and Information Sciences, 2013:698-701

[10] Ardiyanto I, Miura J. Real-time navigation using randomized kino dynamic planning with arrival time field[J]. Robotics and Autonomous Systems, 2012,60(12):1579-1591

The Planning for Dynamic Path of a Mobile Robot Based on Artificial Potential Field Method

ZHANG Xi-wen1,2, XIAO Ben-xian1,2

1.230009,2.230009,

At present,more and more mobile robots are used in a logistics warehouse to liberate the labor force. In this paper, the artificial potential field method was used to replace the traditional artificial potential field method for dynamic path planning. Some ideas of the A* algorithm were cited to make up for the traditional artificial potential field method in order to easily form a local optimal solution. In the laboratory environment, a faster approach to avoiding obstacles was designed aiming to dynamic obstacles. When there were obstacles to able to make robots fall into a trap, obstacles were connected to make some new ones to make the mobile robot successfully pass the trap.

Mobile robots; dynamic path planning; A* algorithm; artificial potential field method

TP242.6

A

1000-2324(2018)06-0937-04

10.3969/j.issn.1000-2324.2018.06.007

2018-03-14

2018-04-06

國家自然科學(xué)基金資助項目:基于采樣控制的非光滑控制系統(tǒng)分析與綜合(61304007)

張希聞(1992-),男,碩士研究生,研究方向:自動控制科學(xué)與工程. E-mail:zhangxiwen_zxw@sohu.com