趙炳巍，賈 峰，曹 巖，孫 瑜，劉一鴻

(西安工業(yè)大學(xué)機(jī)電工程學(xué)院，陜西 西安 710021)

1 引言

近幾年，得益于傳感器技術(shù)、計(jì)算機(jī)科學(xué)和人工智能技術(shù)的快速發(fā)展，移動機(jī)器人在各個(gè)領(lǐng)域已受到廣泛研究，并取得了巨大的進(jìn)展。移動機(jī)器人對不同環(huán)境導(dǎo)航技術(shù)提出了更多的要求[1-3]。路徑規(guī)劃是移動機(jī)器人自主移動的核心技術(shù)之一。現(xiàn)有的路徑規(guī)劃方法主要分為傳統(tǒng)規(guī)劃方法和智能規(guī)劃方法。傳統(tǒng)規(guī)劃方法主要有人工勢場法和A*算法[4]等。智能規(guī)劃方法主要包括遺傳算法、粒子群算法、模糊控制法和神經(jīng)網(wǎng)絡(luò)等。其中，人工勢場法有反應(yīng)速度快、計(jì)算量小、便于實(shí)時(shí)控制和生成的路徑平滑等優(yōu)點(diǎn)，因此得到廣泛應(yīng)用[5]。

人工勢場法原理是假設(shè)工作環(huán)境中存在虛擬勢場力，目標(biāo)點(diǎn)對移動機(jī)器人具有吸引力，而障礙物對其具有排斥力，這2種力的合力控制著移動機(jī)器人的運(yùn)動。但是，人工勢場法存在局部極小點(diǎn)的問題。為了解決此問題，國內(nèi)外學(xué)者進(jìn)行了大量的研究，Abadlla等[6]提出了一種改進(jìn)的人工勢場法與模糊邏輯法相結(jié)合的新方法。該方法克服了傳統(tǒng)人工勢場法局部極小點(diǎn)問題，提高了復(fù)雜環(huán)境下的導(dǎo)航性能,但未能完全克服機(jī)器人劇烈震蕩問題。Mabrouk 等[7]引入移動機(jī)器人內(nèi)部運(yùn)動學(xué)主體狀態(tài)方程，以解決傳統(tǒng)人工勢場方法的局部極小點(diǎn)問題。陳金鑫[8，9]等基于改進(jìn)的勢場函數(shù)，使用了增加控制力的方法來使機(jī)器人移出局部極小點(diǎn)區(qū)域，新的斥力勢場函數(shù)把機(jī)器人與目標(biāo)之間的相對距離也考慮進(jìn)去，從而使目標(biāo)點(diǎn)為整個(gè)勢場的全局最小值點(diǎn)。Fazli等[10]采用沿墻避障算法來解決局部極小點(diǎn)問題，但是會相應(yīng)地增加路徑長度。程志等[11]引入機(jī)器人前進(jìn)的方向向量，對斥力的生成和計(jì)算機(jī)制進(jìn)行了調(diào)整，以解決其處于局部極小點(diǎn)情況下無法繼續(xù)規(guī)劃路徑的問題。

針對傳統(tǒng)人工勢場法在路徑規(guī)劃中存在局部極小點(diǎn)，使得移動機(jī)器人無法達(dá)到目標(biāo)點(diǎn)的問題,本文提出一種基于模擬退火法的人工勢場法，利用模擬退火法在當(dāng)前局部極小點(diǎn)的位置附近增設(shè)隨機(jī)目標(biāo)點(diǎn)，使移動機(jī)器人逐漸逃離出局部極小點(diǎn)區(qū)域。在Matlab上的仿真結(jié)果表明，此方法能夠幫助移動機(jī)器人有效逃離局部極小點(diǎn)區(qū)域，達(dá)到目標(biāo)點(diǎn)位置。

2 路徑規(guī)劃總體設(shè)計(jì)

路徑規(guī)劃是移動機(jī)器人執(zhí)行導(dǎo)航和其他復(fù)雜任務(wù)的基礎(chǔ)，其含義為查找從初始點(diǎn)到目標(biāo)點(diǎn)的路徑，并避免碰撞所有障礙物[12]。路徑規(guī)劃總體結(jié)構(gòu)如圖1所示。

Figure 1 Overall structure of path planning

移動機(jī)器人通過傳感器采集系統(tǒng)，得出障礙物距離信息?；谡系K物信息，本文選用的路徑規(guī)劃方法為人工勢場法，但其存在容易陷入局部極小點(diǎn)問題。因此，本文利用模擬退火算法，在局部極小點(diǎn)的位置附近，增設(shè)隨機(jī)目標(biāo)點(diǎn)，引導(dǎo)移動機(jī)器人逐漸逃離出局部極小點(diǎn)區(qū)域?；谀M退火算法的人工勢場法路徑規(guī)劃整體思路如圖2所示。

Figure 2 Overall idea of path planning

3 傳統(tǒng)人工勢場法

3.1 基本原理

人工勢場法是于1986年由Khatib首次提出的[13]。該方法將物理學(xué)中場的概念引入到路徑規(guī)劃中，其基本原理是將移動機(jī)器人假設(shè)成一個(gè)點(diǎn)，該點(diǎn)在一個(gè)虛擬力場中運(yùn)動，虛擬力場由目標(biāo)點(diǎn)對移動機(jī)器人的引力場和障礙物對移動機(jī)器人的斥力場組成。人工勢場法的勢場函數(shù)定義為引力場與斥力場的和，如式(1)所示：

U(X)=Uat(X)+Ure(X)

(1)

其中,X=(x,y)T為移動機(jī)器人的位置向量，Uat(X)為引力場，Ure(X)為斥力場。

勢場函數(shù)的負(fù)梯度定義為人工力，其由引力和斥力組成。因此，移動機(jī)器人在勢場中所受的力為引力和斥力的合力，如式(2)所示：

F(X)=Fat(X)+Fre(X)

(2)

其中,F(X)為所受合力;Fat(X)為引力，引導(dǎo)移動機(jī)器人走向目標(biāo)點(diǎn);Fre(X)為斥力，使移動機(jī)器人遠(yuǎn)離障礙物。其受力圖如圖3所示。

Figure 3 Schematic diagram of artificial potential field method

引力場的計(jì)算公式如式(3)所示：

(3)

其中,Kat為引力增益常數(shù)，Xg為目標(biāo)點(diǎn)的位置向量。吸引力為引力場的負(fù)梯度，根據(jù)式(3)可得出：

Fat(X)=-Kat(X-Xg)

(4)

斥力場的計(jì)算公式如式(5)所示：

(5)

其中,Kre為斥力增益常數(shù)，pobs(X)=X-Xobs為移動機(jī)器人與障礙物的最短距離，Xobs為障礙物的位置向量，p0為單個(gè)障礙物最大影響距離。

斥力的計(jì)算公式如式(6)所示：

(6)

3.2 存在的主要問題

傳統(tǒng)人工勢場法存在的主要問題是局部極小點(diǎn)問題，其含義為移動機(jī)器人運(yùn)動到某一點(diǎn)，其所受斥力等于引力，使得自身合力為零，從而導(dǎo)致移動機(jī)器人誤以為已經(jīng)達(dá)到目標(biāo)點(diǎn)，停止運(yùn)動[14]。具體局部極小點(diǎn)出現(xiàn)情況如圖4所示，其中圖4a表示當(dāng)移動機(jī)器人移動時(shí)，障礙物和目標(biāo)點(diǎn)在同一條線上，并且障礙物在機(jī)器人和目標(biāo)點(diǎn)的中間。在這種情況下，斥力和引力大小相等，方向相反，導(dǎo)致作用在移動機(jī)器人上的合力為零，移動機(jī)器人停止移動。圖4b為當(dāng)目標(biāo)點(diǎn)在障礙物的作用區(qū)域內(nèi)時(shí)，障礙物的斥力將移動機(jī)器人推離目標(biāo)點(diǎn)。當(dāng)移動機(jī)器人遇到包含復(fù)雜形狀障礙物的環(huán)境情況如U型障礙時(shí)，如圖4c所示，機(jī)器人被困在該區(qū)域內(nèi)。

Figure 4 Occurrence of local minima

4 基于模擬退火算法的人工勢場法

4.1 基本原理

移動機(jī)器人在陷入局部極小點(diǎn)時(shí)，本文在原來所設(shè)定目標(biāo)點(diǎn)附近位置添加隨機(jī)目標(biāo)點(diǎn)，通過在移動機(jī)器人上施加額外的力，打破原有的力平衡，從而使移動機(jī)器人在障礙物、目標(biāo)點(diǎn)和隨機(jī)目標(biāo)點(diǎn)的共同作用下從局部極小點(diǎn)區(qū)域中逃脫，并繼續(xù)向目標(biāo)點(diǎn)移動。設(shè)置隨機(jī)目標(biāo)點(diǎn)受力如圖5所示。

Figure 5 增設(shè)隨機(jī)目標(biāo)點(diǎn)受力分析

增設(shè)隨機(jī)目標(biāo)點(diǎn)后，受到的合力如式(7)所示：

F=Fat+Fre+Fr≠0

(7)

其中,Fr為增設(shè)隨機(jī)目標(biāo)點(diǎn)對移動機(jī)器人的引力。

4.2 增設(shè)隨機(jī)目標(biāo)點(diǎn)

本文設(shè)置隨機(jī)目標(biāo)點(diǎn)的原則是在移動機(jī)器人當(dāng)前點(diǎn)關(guān)于障礙物取右對稱點(diǎn)，距離為所設(shè)定一個(gè)步長值，如圖6所示，增設(shè)的目標(biāo)點(diǎn)的引力會引導(dǎo)機(jī)器人向著障礙物組外側(cè)移動直至脫離其影響范圍。

Figure 6 Adding random target point

模擬退火算法是一種基于蒙特卡洛的近似求最優(yōu)解優(yōu)化算法。算法運(yùn)算過程中通常有2層循環(huán)，外部循環(huán)和內(nèi)部循環(huán)，其中外部循環(huán)代表溫度的連續(xù)下降，內(nèi)部循環(huán)是在此溫度下的多重干擾而產(chǎn)生的不同的態(tài)。內(nèi)部循環(huán)是按Metropolis 準(zhǔn)則接受新狀態(tài)，粒子在溫度T時(shí)趨于平衡的概率為exp(-ΔE/(kT))，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變數(shù),k為Boltzmann常數(shù)[15]。Metropolis準(zhǔn)則常表示如式(8)所示：

(8)

其中，Xn為后一時(shí)刻；Xo為前一時(shí)刻；E(Xn)為Xn時(shí)刻的內(nèi)能；E(Xo)為Xo時(shí)刻的內(nèi)能；T代表當(dāng)前時(shí)刻溫度。

模擬退火算法中溫度T以一定的方式減小，如式(9)所示:

T(t)=αT(t-1)

(9)

其中,α為略小于1的正常數(shù)，其取值為0.85<α<1，t為迭代次數(shù)。

基于模擬退火算法的人工勢場法逃離局部極小點(diǎn)區(qū)域的具體過程為，在當(dāng)前處于局部極小點(diǎn)x處選擇一個(gè)隨機(jī)點(diǎn)x1,然后根據(jù)式(1)分別計(jì)算出點(diǎn)x與點(diǎn)x1處的勢場U(x)和U(x1),如果滿足U(x1)≤U(x),則接受點(diǎn)x1作為下一個(gè)點(diǎn)；如果滿足U(x1)>U(x),則以概率p接受該點(diǎn)作為下一個(gè)點(diǎn)?；谀M退火算法的人工勢場法整體流程如圖7所示。

Figure 7 Whole process of artificial potential field method based on simulated annealing algorithm

4.3 具體步驟

本文方法具體流程圖如8所示，其具體步驟如下所示：

步驟1判斷是否陷入局部極小點(diǎn)，即判斷移動機(jī)器人所受合力是否為0。若是則陷入局部極小點(diǎn)，否則無。

步驟2設(shè)置x=S(S為局部極小點(diǎn))。

步驟3設(shè)置模擬退火算法溫度初始值T0和終止值Tf。

步驟4根據(jù)隨機(jī)目標(biāo)點(diǎn)設(shè)置原則產(chǎn)生一個(gè)隨機(jī)點(diǎn)x1=x+Δx(Δx為x一個(gè)步長)。

步驟5計(jì)算點(diǎn)x1處的勢能U(x1)。

步驟6計(jì)算Δ=U(x1)-U(x)。

步驟8如果U(x1)≤U(S)，則成功逃離局部極小點(diǎn)區(qū)域。否則判斷T≤Tf,如果成立則結(jié)束，代表本次逃離局部極小點(diǎn)失??；如果不成立，令T(t)=αT(t-1)，跳至步驟3，直至逃離局部極小點(diǎn)。

Figure 8 Flow chart of method in this paper

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

為了驗(yàn)證基于模擬退火算法的改進(jìn)人工勢場法路徑規(guī)劃的可行性，通過 Matlab R2018a分別對傳統(tǒng)人工勢場法和本文所設(shè)計(jì)的方法在局部極小點(diǎn)情況下的路徑規(guī)劃結(jié)果進(jìn)行對比，初始參數(shù)設(shè)置如表1所示。

Table 1 Simulation initial parameter setting

首先，只利用傳統(tǒng)人工勢場法進(jìn)行仿真。圓形表示為障礙物，虛線表示為障礙物的影響范圍。黑色線段表示移動機(jī)器人的運(yùn)動軌跡。本文主要針對2種情況進(jìn)行仿真：第1種情況，當(dāng)目標(biāo)點(diǎn)距障礙物很近，移動機(jī)器人的起點(diǎn)坐標(biāo)為(0,0)，終點(diǎn)坐標(biāo)為(8,7)，仿真結(jié)果如圖9所示。第2種情況，當(dāng)環(huán)境中出現(xiàn)U型障礙物，移動機(jī)器人的起點(diǎn)坐標(biāo)為(0,0)，終點(diǎn)坐標(biāo)為(10,9)，仿真結(jié)果如圖10所示。

Figure 9 Not reaching the target point

Figure 10 U-shaped obstacle

從圖9可以看出，當(dāng)目標(biāo)點(diǎn)靠近障礙物并且在障礙物的影響范圍內(nèi)時(shí)，移動機(jī)器人陷入局部極小點(diǎn)導(dǎo)致無法到達(dá)目標(biāo)點(diǎn)。從圖10可以看出，當(dāng)環(huán)境中存在U形障礙物時(shí)，移動機(jī)器人無法從U形障礙物中逃脫。

利用本文所設(shè)計(jì)方法進(jìn)行仿真實(shí)驗(yàn)。針對圖9所示情況，目標(biāo)點(diǎn)離障礙物很近，未能達(dá)到目標(biāo)點(diǎn)，仿真結(jié)果如圖11所示；在針對圖10所示情況，出現(xiàn)U型障礙物，移動機(jī)器人未能逃離U型障礙物，仿真結(jié)果如圖12所示。

通過對比可以看出，對于第1種情況，當(dāng)目標(biāo)點(diǎn)距障礙物很近時(shí)，本文所設(shè)計(jì)的方法能成功到達(dá)目標(biāo)點(diǎn)，其中點(diǎn)狀部分為模擬退火算法增設(shè)隨機(jī)目標(biāo)點(diǎn)過程；對于第2種情況，當(dāng)環(huán)境中存在U形障礙物時(shí)，使用本文方法能成功避開U型障礙物，最終快速到達(dá)目標(biāo)點(diǎn)。

Figure 11 Path planning of our method when not reaching the target point

Figure 12 Path planning of our method when U-shaped obstacle appeared

斥力增益常數(shù)Kre取值過大，會使移動機(jī)器人在運(yùn)動過程路徑產(chǎn)生震蕩問題，因此將斥力增益常數(shù)Kre取值為30與取值為18這2種情況進(jìn)行對比，如圖13所示。通過對比可以看出Kre取值為30時(shí)，利用本文算法規(guī)劃移動機(jī)器人運(yùn)動路徑并未出現(xiàn)震蕩問題，但是路徑長度有所增加。

Figure 13 Path planning with different Kre

本文選取文獻(xiàn)[9]中改進(jìn)勢場函數(shù)方法與本文方法進(jìn)行對比，實(shí)驗(yàn)參數(shù)設(shè)定如表2所示。圖14所示為未達(dá)到目標(biāo)點(diǎn)時(shí)對比情況(情況1)，圖15為出現(xiàn)U型障礙物時(shí)對比情況(情況2)。

Table 2 Experimental parameters setting

Figure 14 Comparison of case 1

Figure 15 Comparison of case 2

本文方法和文獻(xiàn)[9]方法在情況1與情況2時(shí)所用時(shí)間如表3和表4所示。

Table 3 Time comparison of case 1

Table 4 Time comparison of case 2

根據(jù)圖14和圖15、表3和表4可以看出，本文提出的基于模擬退火算法的人工勢場法，所規(guī)劃路徑的平滑性優(yōu)于文獻(xiàn)[9]方法的，并且用時(shí)較短，能夠成功讓移動機(jī)器人到達(dá)目標(biāo)點(diǎn)位置。

6 結(jié)束語

傳統(tǒng)人工勢場法容易在路徑規(guī)劃中陷入局部極小點(diǎn)，使得移動機(jī)器人無法運(yùn)動到目標(biāo)點(diǎn)。本文首先闡述了路徑規(guī)劃的整體思路，其次論述了傳統(tǒng)人工勢場法的基本原理，對傳統(tǒng)人工勢場法中存在局部極小點(diǎn)問題進(jìn)行詳細(xì)分析。針對此問題，本文提出一種基于模擬退火算法的人工勢場法，利用模擬退火算法在當(dāng)前局部極小點(diǎn)的位置附近，增設(shè)隨機(jī)目標(biāo)點(diǎn)，引導(dǎo)移動機(jī)器人逐漸逃出局部極小點(diǎn)區(qū)域。最后通過Matlab仿真表明，本文所設(shè)計(jì)的基于模擬退火算法的人工勢場法能使得移動機(jī)器人逃離局部極小點(diǎn)位置，成功到達(dá)目標(biāo)點(diǎn)位置，且用時(shí)較短。在后續(xù)的工作中，將考慮更多復(fù)雜環(huán)境且對移動機(jī)器人路徑的最優(yōu)性進(jìn)行更進(jìn)一步分析。