劉師良，杜改麗，黃武峰

（1.河南醫(yī)學(xué)高等?？茖W(xué)校，河南 鄭州 451191；2.廣西科技大學(xué)自動化學(xué)院，廣西 柳州 545616）

1 引言

路徑規(guī)劃能夠根據(jù)時間、能耗等相關(guān)要求，在障礙環(huán)境中為移動機(jī)器人規(guī)劃一條符合要求的最優(yōu)路徑，已成為機(jī)器人控制領(lǐng)域的研究熱點［1］，目前，根據(jù)環(huán)境中障礙物的已知情況，已有路徑規(guī)劃算法通常分為局部規(guī)劃和全局規(guī)劃，并取得顯著成果，如遺傳算法及其改進(jìn)、啟發(fā)搜索算法［2］、粒子群算法［3］、改進(jìn)蟻群算法［4］及各種人工勢場優(yōu)化算法［5］等。

蟻群算法是一種通過模擬螞蟻覓食過程構(gòu)建的全局搜索算法，具有較好的魯棒性和環(huán)境表達(dá)優(yōu)勢，作為一種群體智能算法，蟻群算法以其較強(qiáng)的全局搜索性能適用于存在障礙物環(huán)境下的機(jī)器人最優(yōu)路徑規(guī)劃［4］，但經(jīng)典算法效率低且易陷入“早熟”和局部最優(yōu)，為此，文獻(xiàn)［5］以粒子群算法優(yōu)化蟻群參數(shù)，并能過柵格地圖改進(jìn)蟻群算法對U型陷阱的適應(yīng)性，但算法迭代收斂時間較少；文獻(xiàn)［6］對蟻群算法的相關(guān)參數(shù)進(jìn)行自適應(yīng)優(yōu)化，以實現(xiàn)算法初期的快速收斂和后期的穩(wěn)定局部搜索能力，但仍未解決局部最優(yōu)局限；文獻(xiàn)［7］基于雙向A*啟發(fā)改進(jìn)經(jīng)典蟻群算法，有效提高算法的收斂速度和全局最優(yōu)能力，但其局部搜索能力需要進(jìn)一步提高。

人工勢場在移動機(jī)器人路徑規(guī)劃中具有較為成熟的應(yīng)用，其計算量較小且結(jié)構(gòu)簡單，可以實現(xiàn)路徑的快速計算，但在障礙物環(huán)境容易限入局部震蕩，為此，文獻(xiàn)［8］將人工勢場作用力引入到蟻群算法的狀態(tài)轉(zhuǎn)移函數(shù)中，以優(yōu)化算法的初始值設(shè)置，實驗結(jié)果驗證了改進(jìn)算法在迭代耗時、收斂速度和規(guī)劃精度上的有效性；文獻(xiàn)［9］采用快速函數(shù)改進(jìn)人工勢場，并通過虛擬引力斥力全力優(yōu)化蟻群的搜索啟發(fā)信息，以提高算法的全局搜索能力，從而避免經(jīng)典算法中啟發(fā)信息引起的局部最優(yōu)；文獻(xiàn)［10］以勢場力改進(jìn)蟻群啟發(fā)信息，避免局部最優(yōu)和障礙物停滯，構(gòu)建局部擴(kuò)散信息素，改進(jìn)蟻群算法對具有高適應(yīng)值的目標(biāo)空間的搜索能力。

在已有研究基礎(chǔ)上，提出了基于改進(jìn)人工勢場優(yōu)化蟻群算法的障礙物環(huán)境機(jī)器人路徑規(guī)劃算法，算法通過斥力改進(jìn)和虛擬力點設(shè)置改進(jìn)人工勢場算法的U 形障礙物避免能力，并通過改進(jìn)勢場優(yōu)化蟻群算法的啟發(fā)函數(shù)、信息素更新和狀態(tài)轉(zhuǎn)移函數(shù)，以調(diào)節(jié)信息素的自適應(yīng)更新，從而平衡算法的收斂速度與全局搜索能力。

2 虛擬引力優(yōu)化人工勢場

人工勢場（APF）以引力場和斥力場組成的虛擬勢“場”的形式模擬障礙環(huán)境，移動機(jī)器人根據(jù)目標(biāo)點生成的引力場逐漸移向目標(biāo)，同時根據(jù)障礙物生成的斥力場避開障礙物，從而獲得到達(dá)既定目標(biāo)的最優(yōu)路徑。

但傳統(tǒng)人工勢場算法通常存在較多局限，（1）當(dāng)障礙中的目標(biāo)點與障礙物在互相影響范圍之內(nèi)時，引力與斥力作用會使用機(jī)器人在目標(biāo)點附近徘徊而無法抵達(dá)目標(biāo)點；（2）在目標(biāo)點引力作用方向上同時存在相反方向的障礙物斥力，易造成引力與斥力相互抵消而停止前移，為此，需要對傳統(tǒng)人工勢場算法進(jìn)行改進(jìn)。

針對目標(biāo)不可達(dá)問題，由機(jī)器人當(dāng)前位置X和目標(biāo)位置Xa可得兩者之間的歐氏距離da，將其引入到斥力函數(shù)中得：

式中：db—機(jī)器人與障礙物之間距離；dm—障礙物影響半徑；d0—障礙物安全距離，式（1）在db≤dm條件下，當(dāng)db＞dm時，取值Ur=0；t—da對斥力的影響系數(shù)。

當(dāng)機(jī)器人靠近目標(biāo)時，此時，為減少障礙物斥力影響，將式（1）進(jìn)一步分解為障礙物指向機(jī)器人及機(jī)器人指向目標(biāo)，兩個斥力分量Fr1和Fr2，其計算式為：

當(dāng)在障礙物附近時，F(xiàn)r1使機(jī)器人遠(yuǎn)離障礙物，而Fr2使機(jī)器人同時向目標(biāo)方向運(yùn)動，當(dāng)目標(biāo)點在某障礙物影響半徑內(nèi)造成移動機(jī)器人震蕩時，根據(jù)式（3），目標(biāo)在移動向目標(biāo)點時，da逐漸減少，則障礙物斥力被強(qiáng)制減少，而機(jī)器人與目標(biāo)之間的引力逐漸增大，從而避免出現(xiàn)在目標(biāo)點附近震蕩。

2.1 有效障礙物識別

當(dāng)初始規(guī)劃路徑即機(jī)器人與目標(biāo)點之間的連線上存在障礙物時，該障礙物即為影響路徑規(guī)劃的有效障礙，在路徑優(yōu)化時，需要對其進(jìn)行避碰處理，以第一個有效障礙物中心點作為臨時目標(biāo)點，當(dāng)障礙物為U形區(qū)域時，機(jī)器人易陷入局部極小值而無法跳出障礙物區(qū)域，如圖1所示。障礙物影響半徑設(shè)置為r，其中，心坐標(biāo)為(a1，a2)，機(jī)器人中心坐標(biāo)為(x0，y0)，其與障礙物影響圓之間的切點坐標(biāo)為(x1，y1)，(x，y)為虛擬牽引力點，其位于切線延長線且與切點之間的距離為d，虛擬牽引力點用于在機(jī)器人遇到U形障礙物時，將機(jī)器人向自身位置索引，當(dāng)機(jī)器人到達(dá)(x，y)位置后，虛擬力點及其牽引力自動取消，機(jī)器人引力受力情況變換為原有引力。

圖1 U形障礙物內(nèi)受力分析Fig.1 Analysis of Internal Forces in U-shaped Obstacles

根據(jù)圖1所示三角關(guān)系，切點坐標(biāo)(x1，y1)可以表示為：

由切點坐標(biāo)(x1，y1)和機(jī)器人當(dāng)前位置(x0，y0)可建立求解虛擬牽引力點位置坐標(biāo)(x，y)的方程為：

式中，相關(guān)變量值，如圖1所示。根據(jù)式（5）可以計算虛擬牽引力點坐標(biāo)(x，y)的值。在虛擬引力值作用下，機(jī)器人可以加速向虛擬點移動并跳出U形障礙物范圍，為快速增加虛擬力值以提高跳出障礙物作用范圍的效率，改進(jìn)虛擬引力值為：

式中：c、d—虛擬力點坐標(biāo)值與機(jī)器人當(dāng)前坐標(biāo)，由式（5）計算，a1＞1—指數(shù)函數(shù)系數(shù)；f(t)—開關(guān)函數(shù)，當(dāng)?l≤S時，f(t)=1，反之，f(t)=0，?l—機(jī)器人受牽引力作用下的移動速度，S—預(yù)測閾值。

改進(jìn)算法通過中間目標(biāo)點優(yōu)化各局部路徑的規(guī)劃，由于經(jīng)過有效障礙物搜索，中間目標(biāo)點內(nèi)無新障礙物和中間點存在，因而有效避免經(jīng)典算法的死鎖現(xiàn)象，同時，由于不考慮接近時斥力，機(jī)器人可緊貼近障礙物移動，使得局部路徑更優(yōu)。

3 改進(jìn)蟻群全局規(guī)劃算法

3.1 自適應(yīng)啟發(fā)信息的改進(jìn)

傳統(tǒng)算法的路徑搜索通常需要對節(jié)點進(jìn)行遍歷，而在算法初期，信息素在各節(jié)點的濃度較為均勻，原始啟發(fā)函數(shù)無法引導(dǎo)蟻群進(jìn)入下一個節(jié)點。通常在路徑規(guī)劃時，以當(dāng)前節(jié)點到終點的直線作為最短的路徑，因此可以將改進(jìn)人工勢場法引入到算法的啟發(fā)函數(shù)中，改進(jìn)后的啟發(fā)函數(shù)為：

式中：ξ∈(0，1]—誘導(dǎo)因子，用以削弱啟發(fā)函數(shù)在算法的迭代后期所民揮的作用。

當(dāng)機(jī)器人所處的障礙環(huán)境規(guī)模較大時，改進(jìn)后的式（10）的值在不同柵格下的差值較小，因而仍存在較大的隨機(jī)初始路徑選擇，另一方面，在目標(biāo)點附近，式（10）的值在不同柵格下的差值又較大，使得機(jī)器人在該區(qū)域內(nèi)的路徑選擇較為單一，為此，引入改進(jìn)人工勢場計算的當(dāng)前位置與目標(biāo)位置的距離值，設(shè)計參數(shù)自適應(yīng)啟發(fā)函數(shù)，即：

可以看出，改進(jìn)后的啟發(fā)函數(shù)，不會隨著機(jī)器人的位置變化而出現(xiàn)較大的變化值，從而避免算法迭代前期的選擇隨機(jī)性和后期選擇的單一性。

3.2 信息素更新方法的改進(jìn)

傳統(tǒng)算法的最小螞蟻信息素更新策略會產(chǎn)生誤導(dǎo)，為平衡在收斂與搜索上的性能優(yōu)勢，這里采用自適應(yīng)部分信息素更新策略，即在一次迭代完成后，對路徑進(jìn)行排序，僅對排序靠前的路徑對應(yīng)的螞蟻進(jìn)行信息系自適應(yīng)更新，設(shè)這些螞蟻的信息素變化量為，則有：

式中：lgbest—全局最優(yōu)值；lbest、lworst—當(dāng)前迭代搜索到的最優(yōu)與最差值；ε=k/Kmax—進(jìn)化率；k、Kmax—當(dāng)前迭代值與最大迭代次數(shù)。為增加算法后期搜索能力，需要對信息素更新策略進(jìn)行擾動，當(dāng)連續(xù)多次未產(chǎn)生新路徑時，對各路徑對應(yīng)的信息素增加揮發(fā)系數(shù)，即：

3.3 改進(jìn)轉(zhuǎn)移函數(shù)

經(jīng)典蟻群算法的初始信息素濃度可能會較低，從而導(dǎo)致初始迭代收斂速度較慢，從而影響整個算法的收斂速度，為此，將改進(jìn)的人工勢場虛擬合力引入到算法的狀態(tài)轉(zhuǎn)移函數(shù)中，以提高路徑規(guī)劃初期的信息素濃度。虛擬合力主要用于判斷蟻群最優(yōu)路徑的方向，引導(dǎo)蟻群算法的初始階段快速收斂，為避免其對后期算法的影響，還需要對其進(jìn)行約束，加入勢場合力的狀態(tài)轉(zhuǎn)移函數(shù)修正為：

式中：ηij，d—兩節(jié)點之間的距離，γ—勢場啟發(fā)因子；ε—以目標(biāo)點為參考的引力系數(shù)；k、kmax—當(dāng)前迭代次數(shù)及最大迭代次數(shù)；f—勢場的虛擬合力；α＞1—某調(diào)節(jié)函數(shù)；θ—單虛擬力值與合力之間的夾角，θ值越小相對較大，從而使得蟻群向夾角小的路徑偏移。

4 仿真實驗驗證及分析

為驗證文中所提算法的最優(yōu)路徑規(guī)劃有效性，構(gòu)建圖2所示的（20×20）的復(fù)雜柵格障礙環(huán)境作為機(jī)器人路徑規(guī)劃實驗仿真環(huán)境，采用已有文獻(xiàn)中的勢場改進(jìn)自適應(yīng)蟻群算法［10］作為實驗比較算法。針對環(huán)境中的U形障礙物，兩種算法的實驗仿真結(jié)果，如圖2所示?？梢钥闯觯瑒輬龈倪M(jìn)自適應(yīng)蟻群算法雖然也采用人工勢場對蟻群算法進(jìn)行改進(jìn)，但沒有針對U 形障礙物進(jìn)行跳出操作，因而路徑規(guī)劃進(jìn)，機(jī)器人在U形障礙物內(nèi)多次徘徊，而文中算法通過虛擬牽引力點的設(shè)置，較好的避免移動機(jī)器人在U形障礙物內(nèi)的徘徊，從而取得最優(yōu)的路徑規(guī)劃結(jié)果。

圖2 對U形障礙物處理實驗結(jié)果Fig.2 Experimental Results on the Treatment of U-Shaped Obstacles

兩種算法的最優(yōu)路徑規(guī)劃實驗結(jié)果，如圖3 所示?？梢钥闯?，復(fù)雜格柵環(huán)境中，勢場改進(jìn)自適應(yīng)蟻群算法的最優(yōu)路徑仍陷入局部最優(yōu)，而文中算法較好的避免了局部最優(yōu)并取得全局最優(yōu)路徑，且文中算法通過構(gòu)建迭代相關(guān)的信息素負(fù)反饋通道，有效緩解迭代波動，從而提高收斂速度。

圖3 簡單實驗環(huán)境實驗結(jié)果Fig.3 Experimental Results in Complex Simple Experimental Environment

5 總結(jié)

針對傳統(tǒng)蟻群算法易陷入局部最優(yōu)、收斂較慢等問題，提出了基于改進(jìn)人工勢場優(yōu)化蟻群算法的障礙物環(huán)境機(jī)器人路徑規(guī)劃算法，算法通過斥力改進(jìn)和虛擬力點設(shè)置改進(jìn)人工勢場算法的U 形障礙物避免能力，并通過改進(jìn)勢場優(yōu)化蟻群算法的啟發(fā)函數(shù)、信息素更新和狀態(tài)轉(zhuǎn)移函數(shù)，以調(diào)節(jié)信息素的自適應(yīng)更新，從而平衡算法的收斂速度與全局搜索能力。仿真實驗結(jié)果表明，所提算法具有較好的全局搜索能力和對U形障礙物的規(guī)避能力，收斂速度和搜索能力優(yōu)于實驗采用的已有改進(jìn)蟻群算法。