侯遠韶

（河南工業(yè)貿易職業(yè)學院機電工程系，鄭州451191）

機器人導航方式主要有視覺導航、電磁導航和慣性導航[1]。視覺導航技術以路徑規(guī)劃作為主要研究對象，根據各種已知信息尋找最佳路徑的搜索問題，進而完成自主移動。路徑規(guī)劃方式根據所掌握環(huán)境信息量的不同可以分為局部路徑規(guī)劃（環(huán)境未知或部分未知）和全局路徑規(guī)劃（環(huán)境完全已知），同時環(huán)境又有動態(tài)和靜態(tài)之分。因此，對路徑規(guī)劃的研究具體分為：在全局和局部路徑規(guī)劃的基礎上又分為靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃。具體的代表算法有：粒子群算法、遺傳算法、模糊邏輯算法和人工勢場法；A*算法、柵格法、構型空間法和自由空間法[2]。蟻群算法（ACO）又稱螞蟻算法，是基于模擬蟻群覓食行為尋找優(yōu)化路徑的一種自然估算算法，是意大利人Marco Dorigo在1992年首次提出的一種具有啟發(fā)式的仿生智能優(yōu)化搜索算法。ACO有著正反饋性、簡單性和并行性等特點，在機器人路徑規(guī)劃中有著非常重要的作用，但是蟻群算法收斂速度慢，容易陷入局部最優(yōu)進而導致死鎖現(xiàn)象[3]。而遺傳算法有利于尋找全局最優(yōu)點，具有極強的容錯能力，可以求解非線性復雜組合的優(yōu)化問題[4]。因此，本文為了克服蟻群算法存在的缺陷，減少算法的迭代次數(shù)進而加快收斂速度，在基礎蟻群算法的原理上融合遺傳算法的優(yōu)勢。

1 最優(yōu)化問題

1.1 最優(yōu)化問題的定義

根據已知條件，對數(shù)據參數(shù)和方案進行設計，進而得到滿意的答案，稱之為最優(yōu)化問題。最優(yōu)化的數(shù)學表示為：

式（1）中，f(x)為目標函數(shù)，gi(x)和hi(x)為等式約束條件和不等式約束條件（其中x∈S），S為目標可行域。求解最優(yōu)化的問題可以轉化為在目標可行域S中為了得到符合目標函數(shù)f(x)極大值x的數(shù)據集，同時滿足其約束條件，其中極大值問題也可以根據極小值進行計算maxf(x)=f(x)-minf(x)。

1.2 蟻群優(yōu)化原理及數(shù)學模型

式（2）中，α為信息啟發(fā)式因子，β為期望啟發(fā)式因子，ηij為小鎮(zhèn)i到小鎮(zhèn)j的能見度。為了避免啟發(fā)信息被過多的殘留信息所覆蓋，需要及時將殘留信息替換為新的信息，替換后t+n時間點道路(i,j)信息素總量為：

式（3）中，ρ∈[0 , 1]為殘留信息素揮發(fā)系數(shù)，Δτij為新的信息素增量。

蟻群對路徑優(yōu)化步驟如圖1所示：

圖1 蟻群算法求解最優(yōu)路徑流程

2 機器人路徑優(yōu)化問題

2.1 障礙物檢測算法

移動簡單的物體是容易的，而路徑搜索是復雜的。障礙物檢測算法用于對機器人移動路徑障礙物進行檢測，進而規(guī)劃合理的路徑[5]。該算法的原理為：在機器人起點和終點之間搭建一條直線，繼而沿直線從起點到終點進行檢測，如果發(fā)現(xiàn)障礙物進行標記，并計算障礙物到起點和終點的距離，得到兩個極值，然后利用兩個極值點得到路徑中間點，最終根據中間點對機器人進行路徑規(guī)劃[6]。障礙物檢測算法數(shù)學模型為：假設起點坐標用Xs=[xs,ys]T表示，終點坐標用XD=[xd,yd]T表示，那么機器人初始位置和終點位置的線性方程為：

2.2 機器人路徑規(guī)劃

機器人路徑規(guī)劃是利用某些指標進行有規(guī)則的移動，進而得到路徑規(guī)劃的最優(yōu)化效果。當目標可行區(qū)域內存在障礙物，起點到終點無碰撞、消耗時間短則為最優(yōu)路徑[7]。指標的尋找則需要通過算法對不同路徑實驗得到，包括路徑尋找過程中能量的消耗、路徑的距離、尋找路徑所消耗的時間成本等[8]。路徑規(guī)劃問題和流程如圖2所示。

圖2 路徑規(guī)劃的問題和流程

在多個條件限制情況下，對機器人移動路徑進行求解最優(yōu)化的問題即為路徑規(guī)劃。在已知自身位置的前提下，根據已得到的環(huán)境信息，實現(xiàn)移動過程中的避障。因此，根據所掌握環(huán)境信息量的不同，可以將機器人路徑規(guī)劃劃分為全局路徑規(guī)劃和局部路徑規(guī)劃[9]。全局路徑規(guī)劃是指機器人在目標可行域內對障礙可知，障礙不隨機器人的運動而運動，屬于靜態(tài)規(guī)劃，主要算法有蟻群優(yōu)化算法、柵格法、神經網絡法等；局部路徑規(guī)劃是指機器人在目標可行域內每次移動前，通過各種傳感器不間斷收集環(huán)境信息，繼而根據自身定位和障礙物環(huán)境信息，進行路徑選擇屬于動態(tài)規(guī)劃，主要算法有模糊邏輯控制法、人工勢場法和遺傳算法。根據具體情況全局路徑規(guī)劃和局部路徑規(guī)劃有各自的適應范圍，因此為了避免死鎖現(xiàn)象的發(fā)生和加快收斂速度，可以將算法混合進而改善算法性能，實現(xiàn)機器人自主避障[10]。

3 基于改進蟻群算法的路徑優(yōu)化

3.1 算法對比

為了避免算法開始階段缺少信息素而導致蟻群盲目搜索，進而帶來迭代次數(shù)多、收斂速度慢的問題，需要對算法進行改進。已有的機器人路徑規(guī)劃算法主要有基于柵格法的環(huán)境建模、基于神經網絡算法的建模和對蟻群算法進行各種融合改進的全局最優(yōu)路徑規(guī)劃。

柵格法是將移動機器人的目標可行域離散為多個柵格，通過棋盤理念將柵格分為兩大類，即障礙物柵格和可通行柵格，障礙物的柵格化主要通過數(shù)學形態(tài)學中的膨脹法和腐蝕法算子來實現(xiàn)，如圖3所示。

圖3 障礙物柵格化前后的形態(tài)

人工勢場算法是局部路徑規(guī)劃的典型應用，利用了人工力場原理。我們可以認為目標點對機器人運動具有引力作用，障礙物對機器人運動有斥力作用，在引力和斥力的影響下機器人做路徑規(guī)劃運動，機器人的加速力則是引力和斥力相互作用的結果。機器人在目標可行域內初始定位為X=[x,y]T，目標定位為XM=[xm,ym]T，斥力和引力可以通過相應的數(shù)學公式表示，稱為勢場函數(shù)：

式（6）中，K0為目標可行域內斥力增益系數(shù)，ξ為障礙物邊緣到機器人初始定位的最小直線路程，ξ0為機器人受障礙物影響的最大界限。式（7）中，Kg為目標可行域內引力增益系數(shù)，K0，Kg均大于零。

3.2 路徑優(yōu)化算法的實現(xiàn)

蟻群算法初始階段缺少信息素導致收斂速度慢，同時隨著路徑搜索規(guī)模的擴大，搜索時間也隨之大幅提升，在迭代搜索過程中遺傳算法的快速性是其他算法無法比擬的，因此在基礎蟻群算法的原理上融合遺傳算法的優(yōu)勢，最終實現(xiàn)路徑優(yōu)化。算法思路為：首先對組合優(yōu)化問題求解較優(yōu)解，然后利用得到的較優(yōu)解進行改進，作為蟻群進行全局最優(yōu)解的初始信息素，最后通過并行機制和反饋機制得到全局最優(yōu)路徑規(guī)劃的實現(xiàn)，即全局最優(yōu)解。算法具體流程為：

（1）選擇合適的遺傳基因、蟻群數(shù)量、蟻群循環(huán)迭代次數(shù)和螞蟻信息量的各種參數(shù)，如信息素常量、揮發(fā)系數(shù)、啟發(fā)因子等；

（2）求解組合優(yōu)化問題，通過遺傳算法循環(huán)迭代搜索，得到染色體種群矩陣信息；

（3）將步驟（2）中得到染色體種群矩陣信息作為蟻群進行初始路徑搜尋的信息素分布矩陣；

（4）蟻群算法改進后，對組合優(yōu)化問題求解最優(yōu)解；

（5）分析全部最優(yōu)解，得到最終全局最優(yōu)解。

4 實驗仿真

本文采用Matlab 7.0實驗平臺進行仿真，電腦操作系統(tǒng)為win 7，內存32 G，CPU為Intel I7處理器，數(shù)據庫采用TSP30作為實驗例子，實驗結果采用20次實驗的平均值，實驗數(shù)據如表1和表2所示。

表1 傳統(tǒng)蟻群算法實驗結果

表2 改進蟻群算法實驗結果

為了驗證算法具有普遍適應性，實驗給定相同的信息啟發(fā)因子和期望啟發(fā)因子，使其具有同等仿真環(huán)境，同時信息素揮發(fā)系數(shù)設為定值，避免不同外部因素對實驗帶來的影響。通過實驗仿真結果可知，在基礎蟻群算法的原理上融合遺傳算法具有尋找全局最優(yōu)點的特征，雖然蟻群尋址最短路徑基本一致，但迭代次數(shù)大大減少，同時避免了死鎖現(xiàn)象的存在，使其在時效性以及穩(wěn)定性上具有一定的優(yōu)勢。

5 結語

本文通過最優(yōu)化定義引出了機器人路徑規(guī)劃作為視覺導航存在的問題，分析了蟻群優(yōu)化原理與數(shù)學模型，以及現(xiàn)有機器人路徑規(guī)劃算法對障礙物檢測存在的不足之處。繼而通過全局規(guī)劃和局部規(guī)劃，得出機器人路徑規(guī)劃所需要考慮的問題。最后通過比較柵格法、人工勢場算法和基礎蟻群算法的核心思想及各自的應用范圍，提出了一種改進的蟻群優(yōu)化算法，即在基礎蟻群算法的原理上融合遺傳算法的優(yōu)勢，同時保留傳統(tǒng)蟻群算法的隨機、并行特點和遺傳算法具有全局快速搜索的優(yōu)勢。通過實驗仿真可知，優(yōu)化后的算法迭代次數(shù)大大減少，收斂速度得到了提高，同時避免死鎖現(xiàn)象的發(fā)生，具有一定的應用價值。