勢場改進蟻群算法優(yōu)化機器人路徑規(guī)劃

劉師良，杜改麗，黃武峰

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2.1 有效障礙物識別

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

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

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

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

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

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

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

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

3.1 自適應啟發(fā)信息的改進

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

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

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

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

3.2 信息素更新方法的改進

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

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

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

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

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

4 仿真實驗驗證及分析

為驗證文中所提算法的最優(yōu)路徑規(guī)劃有效性，構(gòu)建圖2所示的（20×20）的復雜柵格障礙環(huán)境作為機器人路徑規(guī)劃實驗仿真環(huán)境，采用已有文獻中的勢場改進自適應蟻群算法［10］作為實驗比較算法。針對環(huán)境中的U形障礙物，兩種算法的實驗仿真結(jié)果，如圖2所示。可以看出，勢場改進自適應蟻群算法雖然也采用人工勢場對蟻群算法進行改進，但沒有針對U 形障礙物進行跳出操作，因而路徑規(guī)劃進，機器人在U形障礙物內(nèi)多次徘徊，而文中算法通過虛擬牽引力點的設置，較好的避免移動機器人在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 所示。可以看出，復雜格柵環(huán)境中，勢場改進自適應蟻群算法的最優(yōu)路徑仍陷入局部最優(yōu)，而文中算法較好的避免了局部最優(yōu)并取得全局最優(yōu)路徑，且文中算法通過構(gòu)建迭代相關的信息素負反饋通道，有效緩解迭代波動，從而提高收斂速度。

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

5 總結(jié)

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