周祖坤

(昆明冶金高等?？茖W(xué)校，云南 昆明　650033)

0　前　言

移動機(jī)器人的路徑規(guī)劃屬于機(jī)器人研究領(lǐng)域中的重要技術(shù)，其是基于障礙物環(huán)境，之后根據(jù)某個性能指標(biāo)找尋能夠從起始狀態(tài)最優(yōu)或者近似最優(yōu)的，沒有碰撞的路徑。目前傳統(tǒng)移動機(jī)器人路徑規(guī)劃的方法主要包括人工勢場法及柵格法，柵格法能夠在全局路徑規(guī)劃過程中使用，在環(huán)境空間擴(kuò)大的時候，需要的存儲內(nèi)存比較大，并且計算的效率比較低，沒有良好的決策實時性[1]。人工勢場法屬于機(jī)器人局部路徑規(guī)劃過程中比較成熟的方法，能夠使用到實時控制中，但是此種方法容易出現(xiàn)死鎖或者陷入局部最優(yōu)的問題中[2]。在環(huán)境系統(tǒng)越來越復(fù)雜，并且不斷增加任務(wù)難度的過程中，以數(shù)學(xué)模型為基礎(chǔ)的傳統(tǒng)路徑規(guī)劃方法無法得到良好的效果，所以就出現(xiàn)了部分仿生智能優(yōu)化算法，比如人工魚群、免疫、粒子群、遺傳算法等，但是此種算法的搜索空間比較大，并且無法確定參數(shù)，算法較為復(fù)雜，降低了搜索效率，并且還有可能無法實現(xiàn)可行路徑的搜索。所以，在復(fù)雜環(huán)境中，就要尋找高效移動機(jī)器人路徑規(guī)劃方法。蟻群算法屬于隨機(jī)搜索的最優(yōu)方法，其屬于全局優(yōu)化算法，具有較廣的應(yīng)用領(lǐng)域，其能夠?qū)崿F(xiàn)全局最優(yōu)路徑的尋找[3]?；诖耍疚木腿嫜芯炕趧輬鱿伻核惴ǖ亩鄼C(jī)器人編隊。

1　人工勢場概述

1.1　人工勢場原理

簡單來說，人工勢場就是實現(xiàn)移動機(jī)器人運(yùn)行環(huán)境抽象勢場的虛擬。此勢場主要包括兩個分場：第1部分屬于目標(biāo)位置引力場，第2部分為在已知環(huán)境中形成的障礙斥力場。人工勢場的引力場及斥力場都是矢量，斥力場的矢量方向和障礙物背對，引力場的矢量方向和目標(biāo)位置相對[4]，人工勢場見圖1。

圖1　人工勢場

人工勢場可以通過多種勢場函數(shù)進(jìn)行表示，不同函數(shù)意義也各有不同，對于移動機(jī)器人的編隊，一般使用梯度勢場法實現(xiàn)。也就是將機(jī)器人在環(huán)境中的勢力場作為基礎(chǔ)，使其在移動機(jī)器人虛擬力中作用，目標(biāo)位置對于移動機(jī)器人出現(xiàn)引力Fatt，障礙物對于移動機(jī)器人在運(yùn)動過程中產(chǎn)生斥力Frep，兩者合力就是移動機(jī)器人對目標(biāo)點進(jìn)行運(yùn)動的加速度[5]，圖2為人工勢力場的受力。

圖2　人工勢力場的受力

1.2　人工勢場中的問題

人工勢場能夠有效實現(xiàn)移動機(jī)器人的路徑規(guī)劃，其理論研究較為成熟，并且被廣泛應(yīng)用到工業(yè)中。人工勢場法能夠?qū)⒁苿訖C(jī)器人運(yùn)動空間拓?fù)浣Y(jié)構(gòu)充分的反映出來，并且及時獲得已知環(huán)境障礙物的形狀位置及分布情況，將此信息在移動機(jī)器人運(yùn)行環(huán)境中的勢場值中使用，機(jī)器人合力大小在勢場變化過程中而變化。其和其他的路徑規(guī)劃算法相比計算量比較小，并且具有較快的反應(yīng)速度及較強(qiáng)的實時性。但是，傳統(tǒng)人工勢場法在使用過程中還是具有一定的局限性，比如目標(biāo)不可達(dá)及局部穩(wěn)定[6]。

在機(jī)器人運(yùn)行過程中空間受到的勢場屬于斥力場及引力場相互疊加斥力及引力大小通過機(jī)器人和目標(biāo)位置距離相關(guān)。在障礙物與目標(biāo)位置越來越接近的時候，基于引力朝著目標(biāo)位置進(jìn)行運(yùn)動，在距離越來越短的時候，斥力就會提高，那么如果機(jī)器人斥力較大，就不能夠朝著目標(biāo)位置進(jìn)行移動，所以無法達(dá)到目標(biāo)[7]。圖3為目標(biāo)不可達(dá)的示意圖。

圖3　目標(biāo)不可達(dá)

人工勢場法的局部穩(wěn)定是在實現(xiàn)路徑規(guī)劃時候，因為障礙物位置的不同，移動機(jī)器人在運(yùn)行路徑過程中目標(biāo)位置障礙物斥力和引力相互抵消為0，那么移動機(jī)器人就沒有牽引作用，從而出現(xiàn)局部穩(wěn)定。圖4為拒不穩(wěn)定的示意圖。

圖4　拒不穩(wěn)定

2　勢場蟻群算法

2.1　環(huán)境的建模

機(jī)器人在工作過程中的環(huán)境屬于二維空間，其中的障礙物靜止。根據(jù)柵格化實現(xiàn)工作環(huán)境的劃分，柵格劃分的尺寸和機(jī)器人大小具有密切的聯(lián)系，無障礙物柵格屬于可行柵格，如果存在障礙物柵格屬于不可行柵格[8]，圖5為迷失的蟻群和交叉的路徑。

圖5　迷失的蟻群和交叉的路徑

2.2　目標(biāo)函數(shù)

基于柵格描述的背景下，假如機(jī)器人的起始位置屬于P(1,1)，目標(biāo)位置屬于P(M,N)，機(jī)器人從t步進(jìn)行運(yùn)動，通過T步運(yùn)動到目的位置，本文機(jī)器人的路徑規(guī)劃目標(biāo)函數(shù)是通過起始點到目標(biāo)點沒有障礙路徑的總長度L是最短的[9]，也就是：

圖6　蟻群算法中信息素的擴(kuò)散方向

3　基于勢場蟻群算法的算法

3.1　蟻群算法的搜索

假如蟻群中的螞蟻數(shù)量為m，第k只螞蟻在走了t步時的位置為P(t)=r，到下個位置P(t+1)=s概率為：

在第k只螞蟻下一步的位置使用集合表示，路徑搜索過程中的螞蟻能夠出現(xiàn)環(huán)路，在集合為空的時候，機(jī)器人就要后退。螞蟻k在路徑搜索時候走過的邊使用以下幾步規(guī)則實現(xiàn)信息素的更新：

t(t+1)=(1-q)t(t)+q△t(t)

利用相鄰的啟發(fā)規(guī)則路徑長度，其屬于信息素蒸發(fā)過程，主要目的就是降低已經(jīng)走過邊的其他螞蟻還要走，提高螞蟻對于其他能夠?qū)崿F(xiàn)路徑搜索的挖掘。在螞蟻走完所有路徑之后，就要尋找螞蟻的最短路徑，并且使用全局更新規(guī)則實現(xiàn)信息素的更新[10]，圖7為簡化之后的信息素擴(kuò)散模型。

圖7　簡化之后的信息素擴(kuò)散模型

3.2　算法的步驟

以上屬于算法具體的設(shè)計，以下就是本文所提出基于勢場蟻群算法的步驟：

1)實現(xiàn)參數(shù)的初始化。在此步驟中，主要包括柵格單獨長度的創(chuàng)建，人工勢場基本的參數(shù)，比如障礙物的斥力半徑，斥力系數(shù)和引力系數(shù)，還有蟻群搜索過程中的迭代次數(shù)、螞蟻數(shù)量等一系列的參數(shù)；

2)使用柵格化實現(xiàn)機(jī)器人運(yùn)動過程中環(huán)境的離散化，實現(xiàn)各個柵格位置坐標(biāo)的確定，并且實現(xiàn)機(jī)器人的起始柵格、目標(biāo)柵格和障礙物柵格的有效確定[11]；

3)對環(huán)境自由位置勢場合力方向及大小的計算，包括合力和可行方向夾角；

4)在起始的柵格中放入m只螞蟻，螞蟻k從以上分析中的式子啟發(fā)信息中選擇允許運(yùn)行的邊進(jìn)入到另外柵格中，之后在此柵格位置中實現(xiàn)螞蟻k創(chuàng)建路徑表的存儲，在所有螞蟻到達(dá)另外位置之后，實現(xiàn)走過邊信息素的優(yōu)化，如果螞蟻路徑表柵格位置不屬于目標(biāo)位置，那么就要繼續(xù)進(jìn)行搜索[12]；

5)所有螞蟻都在目標(biāo)位置之后，對螞蟻搜索路徑長度進(jìn)行計算，尋找目前搜索最短可行的路徑，并且根據(jù)相應(yīng)的公式實現(xiàn)信息素全局的搜索，對螞蟻路徑存儲表進(jìn)行清空；

6)對算法是否能夠停止進(jìn)行判斷，如果可以，那么就要停止計算，并且將最短的可行路徑進(jìn)行輸出。如果不可以，那么就要繼續(xù)進(jìn)行第四步[13]。

4　仿真對比

本文使用仿真平臺實現(xiàn)仿真，在仿真過程中，螞蟻的數(shù)量會影響到搜索路徑能力和收斂的速度，螞蟻數(shù)量越大，表示隨機(jī)搜索的機(jī)率就越高，所以就會降低收斂的速度。如果螞蟻數(shù)量較小，就會導(dǎo)致早熟的現(xiàn)象出現(xiàn)，停止搜索。圖8為優(yōu)化之后的螞蟻算法流程。

在柵格環(huán)境中，左上角柵格就是蟻群起始的柵格，黑色的柵格屬于障礙，白色的柵格屬于自由柵格。對蟻群算法初始的參數(shù)進(jìn)行設(shè)置，其中的啟發(fā)信息因子、信息素濃度因子和信息素濃度揮發(fā)因子對搜索過程速度及隨機(jī)性有一定的決定性作用[14]。

實現(xiàn)兩種柵格環(huán)境的設(shè)置，對于傳統(tǒng)蟻群算法及本文所提出的基于勢場蟻群算法實現(xiàn)實驗。在簡單環(huán)境中簡單分布障礙物，但是要避開L型的障礙，搜索路徑通過折線進(jìn)行表示[15]。圖9為簡單環(huán)境中算法改進(jìn)之前的路徑規(guī)劃結(jié)果，圖10為簡單環(huán)境中改進(jìn)算法的路徑規(guī)劃結(jié)果。

圖8　優(yōu)化之后的螞蟻算法流程

a 簡單環(huán)境中最短路徑　　　　　　　　　　　　　　　　b 簡單環(huán)境中最短路徑收斂曲線

a 簡單環(huán)境中最短路徑　　　　　　　　　　　　　　　　　b 簡單環(huán)境中最短路徑收斂曲線

通過上圖就可以看出來，本文所提出的算法能夠搜索路徑和傳統(tǒng)蟻群算法的搜索路徑較為平滑，并且路徑比較短。通過多次連續(xù)實驗表示，本文所研究的基于勢場蟻群算法實現(xiàn)路徑規(guī)劃，具有較高的收斂速度[16]。

5　結(jié)　語

在移動機(jī)器人技術(shù)研究過程中，對于路徑規(guī)劃問題的研究較為重要。首先，路徑規(guī)劃能夠?qū)C(jī)器人的導(dǎo)航效果造成影響，其主要為移動機(jī)器人導(dǎo)航過程中的重要環(huán)節(jié)。另外，路徑規(guī)劃和多門學(xué)科技術(shù)具有密切的聯(lián)系，尋找最優(yōu)的運(yùn)動路徑，其能夠在運(yùn)動過程中尋找高效、安全及沒有障礙的運(yùn)動。通過本文研究表示，基于勢場的蟻群算法機(jī)器人具有可行性，并且能夠提高收斂速度，比傳統(tǒng)算法要有效。