基于模擬退火算法的人工勢場法路徑規劃研究*

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

(西安工業大學機電工程學院，陜西 西安 710021)

1 引言

近幾年，得益于傳感器技術、計算機科學和人工智能技術的快速發展，移動機器人在各個領域已受到廣泛研究，并取得了巨大的進展。移動機器人對不同環境導航技術提出了更多的要求[1-3]。路徑規劃是移動機器人自主移動的核心技術之一。現有的路徑規劃方法主要分為傳統規劃方法和智能規劃方法。傳統規劃方法主要有人工勢場法和A*算法[4]等。智能規劃方法主要包括遺傳算法、粒子群算法、模糊控制法和神經網絡等。其中，人工勢場法有反應速度快、計算量小、便于實時控制和生成的路徑平滑等優點，因此得到廣泛應用[5]。

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

針對傳統人工勢場法在路徑規劃中存在局部極小點，使得移動機器人無法達到目標點的問題,本文提出一種基于模擬退火法的人工勢場法，利用模擬退火法在當前局部極小點的位置附近增設隨機目標點，使移動機器人逐漸逃離出局部極小點區域。在Matlab上的仿真結果表明，此方法能夠幫助移動機器人有效逃離局部極小點區域，達到目標點位置。

2 路徑規劃總體設計

路徑規劃是移動機器人執行導航和其他復雜任務的基礎，其含義為查找從初始點到目標點的路徑，并避免碰撞所有障礙物[12]。路徑規劃總體結構如圖1所示。

Figure 1 Overall structure of path planning

移動機器人通過傳感器采集系統，得出障礙物距離信息。基于障礙物信息，本文選用的路徑規劃方法為人工勢場法，但其存在容易陷入局部極小點問題。因此，本文利用模擬退火算法，在局部極小點的位置附近，增設隨機目標點，引導移動機器人逐漸逃離出局部極小點區域。基于模擬退火算法的人工勢場法路徑規劃整體思路如圖2所示。

Figure 2 Overall idea of path planning

3 傳統人工勢場法

3.1 基本原理

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

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

(1)

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

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

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

(2)

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

Figure 3 Schematic diagram of artificial potential field method

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

(3)

其中,Kat為引力增益常數，Xg為目標點的位置向量。吸引力為引力場的負梯度，根據式(3)可得出：

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

(4)

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

(5)

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

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

(6)

3.2 存在的主要問題

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

Figure 4 Occurrence of local minima

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

4.1 基本原理

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

Figure 5 增設隨機目標點受力分析

增設隨機目標點后，受到的合力如式(7)所示：

F=Fat+Fre+Fr≠0

(7)

其中,Fr為增設隨機目標點對移動機器人的引力。

4.2 增設隨機目標點

本文設置隨機目標點的原則是在移動機器人當前點關于障礙物取右對稱點，距離為所設定一個步長值，如圖6所示，增設的目標點的引力會引導機器人向著障礙物組外側移動直至脫離其影響范圍。

Figure 6 Adding random target point

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

(8)

其中，Xn為后一時刻；Xo為前一時刻；E(Xn)為Xn時刻的內能；E(Xo)為Xo時刻的內能；T代表當前時刻溫度。

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

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

(9)

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

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

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

4.3 具體步驟

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

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

步驟2設置x=S(S為局部極小點)。

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

步驟4根據隨機目標點設置原則產生一個隨機點x1=x+Δx(Δx為x一個步長)。

步驟5計算點x1處的勢能U(x1)。

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

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

Figure 8 Flow chart of method in this paper

5 實驗仿真結果

為了驗證基于模擬退火算法的改進人工勢場法路徑規劃的可行性，通過 Matlab R2018a分別對傳統人工勢場法和本文所設計的方法在局部極小點情況下的路徑規劃結果進行對比，初始參數設置如表1所示。

Table 1 Simulation initial parameter setting

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

Figure 9 Not reaching the target point

Figure 10 U-shaped obstacle

從圖9可以看出，當目標點靠近障礙物并且在障礙物的影響范圍內時，移動機器人陷入局部極小點導致無法到達目標點。從圖10可以看出，當環境中存在U形障礙物時，移動機器人無法從U形障礙物中逃脫。

利用本文所設計方法進行仿真實驗。針對圖9所示情況，目標點離障礙物很近，未能達到目標點，仿真結果如圖11所示；在針對圖10所示情況，出現U型障礙物，移動機器人未能逃離U型障礙物，仿真結果如圖12所示。

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

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

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

Figure 13 Path planning with different Kre

本文選取文獻[9]中改進勢場函數方法與本文方法進行對比，實驗參數設定如表2所示。圖14所示為未達到目標點時對比情況(情況1)，圖15為出現U型障礙物時對比情況(情況2)。

Table 2 Experimental parameters setting

Figure 14 Comparison of case 1

Figure 15 Comparison of case 2

本文方法和文獻[9]方法在情況1與情況2時所用時間如表3和表4所示。

Table 3 Time comparison of case 1

Table 4 Time comparison of case 2

根據圖14和圖15、表3和表4可以看出，本文提出的基于模擬退火算法的人工勢場法，所規劃路徑的平滑性優于文獻[9]方法的，并且用時較短，能夠成功讓移動機器人到達目標點位置。

6 結束語

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