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

張希聞,肖本賢

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

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

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

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

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

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

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

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

1 相關(guān)算法

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

1.1 人工勢場法

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

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

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

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

1.2 A*算法

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

1.3 連鎖障礙法

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

圖 1 障礙陷阱

圖 2 連鎖障礙

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

2.1 倉庫建模

圖 3 倉庫

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

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

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

圖 4 流程圖

3 仿真與實(shí)驗(yàn)

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

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

圖 5 原算法結(jié)果

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

移動(dòng)機(jī)器人實(shí)驗(yàn)如圖7所示。

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

圖 7 移動(dòng)機(jī)器人

4 結(jié)束語

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

[1] 何雨楓,曾慶化,王云舒,等.室內(nèi)微型飛行器實(shí)時(shí)路徑規(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的集群實(shí)時(shí)定位系統(tǒng)設(shè)計(jì)[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ì)算機(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] 劉建華,楊建國,劉華平,等.基于勢場蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2015,46(9):18-27

[8] 王殿君.基于改進(jìn)A*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃[J].清華大學(xué)學(xué)報(bào):自然科學(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é)基金資助項(xiàng)目:基于采樣控制的非光滑控制系統(tǒng)分析與綜合(61304007)

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