人工勢(shì)場(chǎng)法路徑規(guī)劃的差分進(jìn)化參數(shù)優(yōu)化研究

趙文瑜，彭程,2

（1.華北科技學(xué)院電子信息工程學(xué)院，三河 065201；2.應(yīng)急管理部煤炭安全監(jiān)測(cè)監(jiān)控技術(shù)安全生產(chǎn)重點(diǎn)實(shí)驗(yàn)室，三河 065201）

0 引言

路徑規(guī)劃是移動(dòng)機(jī)器人的重要研究領(lǐng)域，是移動(dòng)機(jī)器人導(dǎo)航的基本環(huán)節(jié)之一，它的目的是找到一條從起始位置到目標(biāo)位置的無(wú)碰撞路徑[1]。近來(lái)研究人員提出了多種路徑規(guī)劃算法，例如Dijkstra、A*、遺傳算法、模擬退火、粒子群優(yōu)化和人工勢(shì)場(chǎng)法等[2-6]。人工勢(shì)場(chǎng)法是一種應(yīng)用廣泛的路徑規(guī)劃方法。其優(yōu)點(diǎn)是數(shù)學(xué)表達(dá)式簡(jiǎn)潔明了、反應(yīng)速度快、實(shí)時(shí)性好且物理意義明確[5]。但是人工勢(shì)場(chǎng)法也有一定的局限性，本文研究分析傳統(tǒng)人工勢(shì)場(chǎng)中參數(shù)的設(shè)置對(duì)最終路徑規(guī)劃結(jié)果的影響，并使用差分進(jìn)化算法優(yōu)化人工勢(shì)場(chǎng)法的主要參數(shù)，以期規(guī)劃出距離短且平滑性更好的路徑。

1 傳統(tǒng)人工勢(shì)場(chǎng)算法的路徑規(guī)劃

人工勢(shì)場(chǎng)法的主要基本思想是假定機(jī)器人在一個(gè)虛擬的人工受力場(chǎng)中，目標(biāo)點(diǎn)產(chǎn)生對(duì)移動(dòng)機(jī)器人的吸引力，而在場(chǎng)內(nèi)的障礙物產(chǎn)生對(duì)機(jī)器人的排斥力，吸引與排斥這兩種力的合力作為機(jī)器人的驅(qū)動(dòng)力，引導(dǎo)機(jī)器人從起始點(diǎn)向目標(biāo)點(diǎn)運(yùn)動(dòng)，反映在數(shù)學(xué)模型上則是引力場(chǎng)與斥力場(chǎng)的模型建立。

在勢(shì)場(chǎng)中，機(jī)器人距離障礙物越近排斥力越大，方向是由障礙物指向機(jī)器人，當(dāng)機(jī)器人與障礙物的間距大于一定值時(shí)，障礙物對(duì)機(jī)器人的排斥力可以忽略不計(jì)。因此可取斥力勢(shì)場(chǎng)函數(shù)：

式中Ur（q）是斥力勢(shì)場(chǎng)函數(shù)，q表示機(jī)器人當(dāng)前所在位置，Kr斥力場(chǎng)函數(shù)的增益系數(shù)，ρ（q）為機(jī)器人到障礙物的間距，ρ0為障礙物能夠影響機(jī)器人的最大距離，即超出這個(gè)距離障礙物對(duì)機(jī)器人的排斥力可以忽略不計(jì)。因此可得到機(jī)器人在虛擬勢(shì)場(chǎng)中受到的排斥力：

式中Fr（q）是排斥力，qo是障礙物的位置。

在勢(shì)場(chǎng)中，移動(dòng)機(jī)器人受到目標(biāo)點(diǎn)的吸引的作用。當(dāng)移動(dòng)機(jī)器人間距越遠(yuǎn)時(shí)，目標(biāo)點(diǎn)對(duì)移動(dòng)機(jī)器人的吸引力越大，當(dāng)機(jī)器人與目標(biāo)點(diǎn)的間距越近時(shí)吸引力越小，當(dāng)機(jī)器人與目標(biāo)點(diǎn)的間距為零時(shí)，機(jī)器人的勢(shì)能為0，這樣機(jī)器人就到達(dá)了目標(biāo)點(diǎn)。虛擬的勢(shì)場(chǎng)中的性質(zhì)類似于彈性勢(shì)場(chǎng)，彈性勢(shì)場(chǎng)中的勢(shì)能與距離成正比，即可得到引力勢(shì)場(chǎng)中引力勢(shì)場(chǎng)函數(shù)：

式中Ua（q）是吸引勢(shì)位，Ka為正比例系數(shù)，ρg（q）是移動(dòng)機(jī)器人與目標(biāo)點(diǎn)之間的間距。因此可以得到吸引力：

全局勢(shì)場(chǎng)U（q）由吸引勢(shì)場(chǎng)與排斥勢(shì)場(chǎng)的和而得來(lái)，即：

與之相對(duì)應(yīng)，合力F（q）為：

2 人工勢(shì)場(chǎng)法參數(shù)優(yōu)化

通過(guò)仿真實(shí)驗(yàn)發(fā)現(xiàn)人為設(shè)置的參數(shù)對(duì)人工勢(shì)場(chǎng)法規(guī)劃的路徑有很大影響，其中引力場(chǎng)正比例增益系數(shù)Ka、斥力場(chǎng)的增益系數(shù)Kr，障礙物的影響距離ρ0這三個(gè)參數(shù)的設(shè)置不當(dāng)對(duì)路徑規(guī)劃的影響最為明顯，具體可見(jiàn)下一節(jié)仿真實(shí)驗(yàn)結(jié)果。在確定了傳統(tǒng)人工勢(shì)場(chǎng)的模型后，為了得到一條更平滑的路徑，通過(guò)差分進(jìn)化算法對(duì) Ka、Kr、ρ0這三個(gè)參數(shù)進(jìn)行優(yōu)化，其優(yōu)化的目標(biāo)是規(guī)劃得到的路徑長(zhǎng)度最短。

差分進(jìn)化算法（Different Evolution，DE）是由Storn和Price在1995年提出的[7]。差分進(jìn)化算法是一種啟發(fā)式尋求最優(yōu)解的智能算法，與遺傳算法類似，該算法也包含變異、交叉、選擇等過(guò)程。差分進(jìn)化算法的特點(diǎn)是結(jié)構(gòu)簡(jiǎn)單，便于理解與實(shí)現(xiàn)，且具有很好的魯棒性和收斂性。差分進(jìn)化算法的相關(guān)公式可參考文獻(xiàn)[7-8]，這里不再贅述。差分進(jìn)化算法的流程如下：

（1）設(shè)置差分進(jìn)化算法的控制參數(shù)。控制參數(shù)包括種群的大小NP，縮放因子F，交叉概率CR，最大迭代代數(shù)G；

（2）隨機(jī)產(chǎn)生初始種群；

（3）計(jì)算種群中個(gè)體的目標(biāo)函數(shù)值，找出種群中的最優(yōu)個(gè)體；

（4）對(duì)種群中的每個(gè)個(gè)體重復(fù)步驟（5）～（8）；

（5）變異操作，生成變異向量；

（6）邊界條件處理；

（7）交叉操作，對(duì)目標(biāo)向量和變異向量進(jìn)行交叉操作，生成試驗(yàn)向量；

（8）選擇，計(jì)算試驗(yàn)向量的目標(biāo)函數(shù)值，進(jìn)行貪婪選擇操作；

（9）迭代代數(shù)加1，若沒(méi)有達(dá)到最大代數(shù)G返回（4），否則結(jié)束輸出最優(yōu)個(gè)體及其對(duì)應(yīng)的目標(biāo)函數(shù)值。

3 仿真實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證本文提出算法的有效性，使用MATLAB軟件進(jìn)行仿真實(shí)驗(yàn)。移動(dòng)機(jī)器人在10 m×10 m的有障礙環(huán)境中運(yùn)動(dòng)，將障礙物膨脹為圓[9]，起始點(diǎn)坐標(biāo)和目標(biāo)點(diǎn)坐標(biāo)分別設(shè)置為（0.5,0.5）和（9.5,9.5）。在傳統(tǒng)人工勢(shì)場(chǎng)法規(guī)劃路徑時(shí)設(shè)置兩組不同參數(shù)，比較不同參數(shù)設(shè)置對(duì)最終路徑的影響，并用差分進(jìn)化算法優(yōu)化人工勢(shì)場(chǎng)法的三個(gè)參數(shù)，得出最優(yōu)路徑。

3.1 人工勢(shì)場(chǎng)法的路徑規(guī)劃仿真結(jié)果

人工設(shè)置的兩組參數(shù)如表1所示。在第一組參數(shù)設(shè)置下規(guī)劃出的路徑見(jiàn)圖1，此時(shí)移動(dòng)機(jī)器人出現(xiàn)目標(biāo)不可達(dá)的問(wèn)題；在第二組參數(shù)設(shè)置下規(guī)劃出的路徑見(jiàn)圖2，此種情況下路徑存在明顯的鋸齒，其規(guī)劃出的路徑距離長(zhǎng)度20.076 m。

表1 人工勢(shì)場(chǎng)法模型的相關(guān)參數(shù)

圖1 第一組參數(shù)下的路徑規(guī)劃仿真結(jié)果

圖2 第二組參數(shù)下的路徑規(guī)劃仿真結(jié)果

3.2 差分進(jìn)化算法優(yōu)化后路徑規(guī)劃仿真結(jié)果

差分進(jìn)化算法相關(guān)設(shè)置如下：初始種群大小設(shè)置為10，最大迭代數(shù)為30，交叉概率CR和縮放因子F分別設(shè)置為0.1和0.4。差分進(jìn)化算法優(yōu)化人工勢(shì)場(chǎng)法中三個(gè)參數(shù)后的路徑規(guī)劃結(jié)果如圖3所示，其規(guī)劃出的路徑不再有鋸齒狀，很好地提升了移動(dòng)機(jī)器人路徑的平滑性。優(yōu)化后的人工勢(shì)場(chǎng)參數(shù)如表2所示，路徑為14.947 m，相較于前述第二組參數(shù)時(shí)得到的結(jié)果，得到了長(zhǎng)度更短、平滑性更好的路徑，同時(shí)也解決了因參數(shù)設(shè)置不當(dāng)出現(xiàn)的目標(biāo)不可達(dá)問(wèn)題。

表2 優(yōu)化后的人工勢(shì)場(chǎng)法的相關(guān)參數(shù)

圖3 差分進(jìn)化算法優(yōu)化后的路徑規(guī)劃仿真結(jié)果

4 結(jié)語(yǔ)

本文針對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法存在的缺陷，將傳統(tǒng)人工勢(shì)場(chǎng)法與差分進(jìn)化算法相結(jié)合，以減小路徑長(zhǎng)度為目標(biāo)，對(duì)人工勢(shì)場(chǎng)法的三個(gè)參數(shù)：引力場(chǎng)正比例增益系數(shù)、斥力場(chǎng)增益系數(shù)以及障礙物的影響距離進(jìn)行優(yōu)化，仿真結(jié)果表明參數(shù)優(yōu)化可以顯著改善人工勢(shì)場(chǎng)法的性能。