陳岳軍，王敬賢

(上海五零盛同信息科技有限公司，上海 200333)

智能化機器人擁有感知決策能力，它們可以辨識身邊的信息情況，實現(xiàn)自主控制并完成復(fù)雜的任務(wù)[1]。機器人的路徑規(guī)劃問題是智能控制領(lǐng)域中的一個關(guān)鍵問題，保證機器人在完成任務(wù)的同時提高效率[2]。路徑規(guī)劃是在起始點和目標點之間選出一條最短路徑，既能使機器人在行進過程中躲過障礙物，并且滿足特定評價標準，如行走路線距離最短、到達目標行走時間最短、自身能量消耗最小等[3-4]。目前，機器人及其路徑規(guī)劃相關(guān)問題已經(jīng)取得了許多成果，可分為傳統(tǒng)方法和智能化方法兩大類。

傳統(tǒng)路徑規(guī)劃方法主要有幾何構(gòu)造方法和人工勢場法?；趲缀螛?gòu)造的方法將機器人抽象成一個可忽略的點，同時適當擴大障礙物體積，然后構(gòu)造自由空間，并將其全部連通，最后采用圖搜索算法找出最優(yōu)路徑[5]。人工勢場法運用較為成熟，它用引力場和斥力場模型來表示機器人所工作的環(huán)境信息[6]，受力如圖1所示。該算法原理簡單，適合底層的簡單控制，其運行速度和存儲空間與其他算法相比具有優(yōu)勢。但它只解決局部空間內(nèi)的避障問題，更適用于動態(tài)環(huán)境，在實時避障方面發(fā)揮重要作用。

圖1 人工勢場法受力示意圖

智能化路徑規(guī)劃方法主要基于遺傳算法、模糊邏輯和蟻群算法。遺傳算法在全局環(huán)境中搜索最優(yōu)路徑的能力比較強，有并行計算特性，應(yīng)用較為廣泛[7]。孫樹棟等[8]實現(xiàn)了離散空間下機器人的路徑規(guī)劃，使用插入和刪除算子，使規(guī)劃出的路徑是連續(xù)的。周明等[9]提出連續(xù)空間下機器人的路徑規(guī)劃。該方法簡單可行，在執(zhí)行過程中不會產(chǎn)生無效路徑，但是對于復(fù)雜環(huán)境是不適用的。閆雪超等[10]提出一種用于機器人路徑規(guī)劃的改進遺傳算法，解決過早收斂和隨機變異等問題。模糊邏輯算法是一種常用的在線規(guī)劃路徑方法，依靠傳感器的實時反饋信息，包含了人的操作經(jīng)驗和控制策略，將這些表示成模糊條件語句并構(gòu)成一個集合[11]。該算法通過對環(huán)境信息的模糊化解決傳統(tǒng)算法中機器人定位精度高的問題。郭娜等[12]針對機器人在復(fù)雜環(huán)境的局部死鎖和路徑冗余問題,使用結(jié)合預(yù)測和模糊控制的局部路徑規(guī)劃方法。該算法隨著障礙物數(shù)目的增多，計算越來越復(fù)雜，而且在未知的動態(tài)環(huán)境中，模糊規(guī)則很難制定。

蟻群優(yōu)化(ACO)算法是一種啟發(fā)于蟻群覓食行為的智能仿生算法[13]。它利用一種稱為信息素的特殊化學(xué)物質(zhì)在個體和環(huán)境之間進行交流。劉煊琨等[14]將蟻群算法用于變電站路徑的優(yōu)化問題,。鄧新文等[15]提出了一種基于蟻群算法的航跡規(guī)劃方法，確保遠程魚雷航渡過程中避障的同時選擇最優(yōu)航行路徑?，F(xiàn)針對環(huán)境簡單、障礙物分布較少的情況，采用人工勢場法進行規(guī)劃路徑，當環(huán)境變得復(fù)雜，障礙物數(shù)量較多且較為密集時使用蟻群算法，為了驗證這個方案是否可行，進行了兩種算法的模擬實驗并得到不同障礙物環(huán)境下的實驗結(jié)果。

1 環(huán)境建模

為了使計算機能夠辨識所要規(guī)劃的環(huán)境，必須經(jīng)過環(huán)境建模這一重要環(huán)節(jié)。環(huán)境建模選用的方法關(guān)系到整個路徑規(guī)劃的難易程度以及精確程度，合理的建模方式能使路徑搜索量減少。機器人所處的環(huán)境因素以及障礙物信息情況等都是影響規(guī)劃建模方法的因素。要做的工作就是將機器人所在的物理空間映射為算法可以處理的數(shù)學(xué)矩陣，最后再用環(huán)境模型將規(guī)劃的結(jié)果表達出來。

1.1 柵格法環(huán)境建模

柵格法是目前在各領(lǐng)域應(yīng)用都較成功的建模方法[16]。采用此方法是為了得到一張數(shù)字地圖，起止點和障礙物信息都存儲在這張地圖中，最后規(guī)劃出的路徑也會展示在這張地圖上。

該方法將一個二維工作平面劃分成大小相同的柵格，每個柵格都具有一個0或1表示的二值信息。柵格大小選取是影響機器人運行性能的重要因素之一，它與環(huán)境信息的表達程度關(guān)系密切，也會對規(guī)劃時間產(chǎn)生影響。柵格越小，環(huán)境信息描述越準確，但存儲空間會相應(yīng)加大，算法搜索范圍也會加大，導(dǎo)致路徑搜索時間變長。柵格越大，環(huán)境信息的表達誤差越大，雖然決策速度變快，但路徑規(guī)劃不精確，可能會出現(xiàn)摩擦甚至碰撞障礙物的情形。因此在選擇柵格大小時，應(yīng)考慮到工作環(huán)境、障礙物信息以及實驗結(jié)果精確度等多個問題。

在進行柵格法建模前，需要對環(huán)境信息預(yù)處理，在此遵循以下原則：①如果相鄰的兩個障礙物挨得特別近，則將它們看作一個障礙物處理；②工作空間靜態(tài)障礙物數(shù)量大小已知，當障礙物不規(guī)則時，即邊界不足一個柵格大小時，按一個柵格處理，這樣做都是為了避免發(fā)生和障礙物的摩擦。

1.2 柵格環(huán)境轉(zhuǎn)換為數(shù)學(xué)矩陣

將機器人工作的二維平面分成大小相等的柵格，綜合考慮空間和障礙物數(shù)量兩方面，取20×20空間大小。使用直角坐標系表示整個柵格平面，將柵格陣左下角的點作為原點，水平向右為橫軸正方向，豎直向上為縱軸正方向。此時平面中每一個交叉點都能用坐標系中的對應(yīng)坐標來表示，從(0，0)到(20,20)。

在機器人工作平面上，每個柵格有兩種狀態(tài)，障礙物空間和機器人自由行走空間，把涂黑的柵格表示為障礙物空間，把空白區(qū)域看作機器人可自由行走的空間。然后對柵格環(huán)境進行編碼，采用二值編碼方法，用1表示障礙物空間，用0表示自由空間，這樣每一個柵格都能對應(yīng)0或1。用此方法，當環(huán)境情況突變時只要改變數(shù)學(xué)矩陣中的值即可。此時，工作空間用數(shù)學(xué)矩陣的形式表示出來，工作環(huán)境的柵格模型和矩陣如圖2所示。

圖2 工作環(huán)境柵格模型和矩陣表示

2 人工勢場法和蟻群算法實現(xiàn)

2.1 人工勢場法的實現(xiàn)

人工勢場法是一種人為設(shè)定的模擬虛擬力的算法，使機器人在由目標位置和障礙物組成的抽象勢場中受到合力作用而運動。將目標位置視為引力場，其方向指向目標點，而障礙物視為斥力場，其方向指向遠離障礙物的方向，兩個場共同作用構(gòu)造人工勢場。在構(gòu)建的人工勢場中，機器人可以沿合成的勢場運動，避開障礙物，向目標位置前進，從而走出一條無碰路徑。

設(shè)機器人所在位置為qrobot=[x,y]T，目標位置為qgoal=[x1,y1]T，第i個障礙物的位置為qzhang(i)=[x2,y2]T。則機器人所在位置的引力勢場為

(1)

引力為

Fyin=kyin(qrobot-qgogal)

(2)

機器人所在位置的斥力勢場為

(3)

斥力為

Fchi=-Uchi

(4)

式中：kyin表示引力的比例系數(shù);kchi表示斥力的比例系數(shù);(qrobot-qgogal)表示機器人當前所在位置與目標點的距離;p(q)表示機器人與障礙物的最短距離。

具體實現(xiàn)步驟如下：

1)參數(shù)初始化，給定位置信息和各系數(shù)。

2)循環(huán)執(zhí)行人工勢場法的主功能。依次調(diào)用計算角度的子功能、計算引力的子功能、計算斥力的子功能，進行各個關(guān)鍵量的計算。

3)計算機器人的下一步位置并保存。

4)循環(huán)執(zhí)行以上步驟，直至機器人到達目標點，并用變量K記錄迭代的次數(shù)。

2.2 蟻群算法的工作原理

蟻群算法是通過模擬自然界中螞蟻群體的覓食過程而得出的。當螞蟻遇到一個不曾走過的路口時，隨機選擇一條路徑前進，同時留下供交流的信息素，螞蟻所走路徑越短且走過數(shù)量越多，釋放信息素會越多，作為后續(xù)螞蟻選擇路徑的依據(jù)。哪條路徑最優(yōu)，選擇的螞蟻會越多，此路徑信息量越大，即信息正反饋現(xiàn)象。而其他路信息素會隨時間而揮發(fā)，循環(huán)執(zhí)行得到一個最優(yōu)解。

如圖3所示，AE之間可以有兩條路徑供選擇，其中AB=DE=HD=HB=1，BC=CD=0.5，假設(shè)原路不存在信息素，每只螞蟻前進速度一樣，單位時間內(nèi)走長度為1，且釋放相等濃度的信息素。當t=0時，從A、E兩點各有30只螞蟻同時出發(fā)。當t=1時，螞蟻從A到B，這時BH與BC信息素濃度相等，則螞蟻隨機二選一前進，會有一半螞蟻選擇BH較長路徑，另一半選擇BC較短路徑。同時，從E點螞蟻走到D點，各一半螞蟻分別選擇DH和DC。當t=2 時，選擇BC與DC的螞蟻分別通過BCD和DCB，可選擇BH與DH的螞蟻此時只走到H。此時BCD走過的螞蟻數(shù)量是BHD的兩倍，則路徑BCD上總信息素濃度相比于BHD是它的兩倍，以后若再有螞蟻在路口選擇時，就會向信息素濃度高的路徑前進。這個過程循環(huán)進行，選擇短路徑的螞蟻數(shù)量越來越多，此路徑信息素濃度也增大，最終趨于最優(yōu)解。

圖3 蟻群算法原理示意圖

2.3 蟻群算法的數(shù)學(xué)抽象

1)對螞蟻個體的抽象。每只螞蟻看作一個簡單智能體，可根據(jù)局部環(huán)境構(gòu)造候選解，也能進行信息交流。

2)尋找路徑的抽象。用柵格兩頂點作為螞蟻巢穴(起始點)和食物所在地(目標點)，螞蟻覓食過程看作算法求解過程，圖軌跡作為信息素信息，比較相鄰節(jié)點軌跡濃度來決定下一步走向。

3)信息素揮發(fā)的抽象。將信息素揮發(fā)過程離散化，規(guī)定經(jīng)過一個單位時間信息素揮發(fā)一次，若用ρ表示信息素揮發(fā)系數(shù)，則1-ρ表示信息素殘留因子，在每時刻記錄各條路徑的信息素情況。

4)啟發(fā)因子的引入。螞蟻行走路徑的概率問題是一個隨機搜索過程，引入啟發(fā)因子表示螞蟻從一個節(jié)點轉(zhuǎn)移到另一節(jié)點的期望概率，有引導(dǎo)作用，使尋優(yōu)路徑時間變短，增加時效性。

通過以上抽象可以將蟻群覓食問題轉(zhuǎn)化為數(shù)學(xué)模型。螞蟻個體是算法基本對象，所選路徑取決于擁有的知識，而知識來源于信息交流及環(huán)境感知，具有自學(xué)習(xí)能力，可根據(jù)環(huán)境變化和以往經(jīng)驗對知識結(jié)構(gòu)更新，實現(xiàn)算法逐步優(yōu)化。該算法流程如圖4所示。

圖4 蟻群算法流程圖

2.4 蟻群算法模擬流程

1)工作環(huán)境用0和1組成的矩陣表示。

2)輸入初始信息素信息，選擇起止點。在本算法設(shè)計時，要設(shè)置各種參數(shù)如表1所示。初始狀態(tài)螞蟻在出發(fā)點S，需將初始點放到禁忌表中。

表1 算法基本參數(shù)設(shè)置

3)選擇下一步節(jié)點時，各節(jié)點的概率由該節(jié)點的信息素求出，計算公式如式(5)所示。其中，πij(t)為圖中弧(i,j)上殘留的信息素濃度；ηij為與弧(i,j)相關(guān)的啟發(fā)式信息；α、β分別為πij(t)、ηij的權(quán)重參數(shù)。

(5)

當螞蟻轉(zhuǎn)移時，總按理論計算結(jié)果進行容易很快陷入收斂。為避免此問題，引入輪盤算法[17]，選擇節(jié)點j并將其加入禁忌表即可。輪盤賭算法將圓盤分成n份，每個扇形面積不同，轉(zhuǎn)動圓盤并穩(wěn)定后，選擇參照點所在扇形即可。當扇形所占的面積越大，則參照點落入其區(qū)域概率越大，在蟻群算法中相當于設(shè)定該節(jié)點被選擇的概率也越大。

4)更新路徑以及路程長度并實時記錄。

5)重復(fù)3)、4)過程，直到到達目的地。

6)重復(fù)3)、5)，直到某一代螞蟻迭代結(jié)束。

7)更新信息素矩陣，經(jīng)過時間Δt后，各條路徑上的信息素按式(6)進行調(diào)整。

πij(t+1)=(1-ρ)πij(t)+Δπij

(6)

式中：ρ為信息素揮發(fā)系數(shù)；1-ρ為信息素殘留的系數(shù)；ρ?[0,1)使信息素不至于無限積累；Δπij(t)表示在時間的增量中，螞蟻所走路徑上信息素的增加量，初始時刻Δπij(0)=0，求解公式為

(7)

根據(jù)信息素更新方式的差別，有

(8)

式中：Q為信息素強度；Lk表示第k只螞蟻所走路徑長度。想要一波螞蟻到達目標點后，才更新路徑上的信息素濃度，而這個模型利用的正是整體信息，因此在本文中采用此模型。

8)迭代3)～7)到n代螞蟻迭代全部結(jié)束。

3 模擬實驗與結(jié)果

3.1 實驗說明

為對兩種算法進行比較，并在不同環(huán)境中驗證算法有效性，進行路徑規(guī)劃模擬實驗。

1)人工勢場法模擬。主函數(shù)功能為迭代過程的主體。計算斥力的子功能可計算出斥力在x、y方向的數(shù)組分量。計算角度的子功能用于計算車、障礙物和目標之間的與X軸之間的夾角。計算引力的子功能可計算出目標對車的引力在x、y方向的兩個分量值。

2)蟻群算法模擬。首先要建立柵格環(huán)境，然后模擬蟻群算法的完整過程，在這個算法內(nèi)部包含覓食規(guī)則、選擇節(jié)點規(guī)則、避障規(guī)則、信息素更新規(guī)則等。

3.2 人工勢場法的仿真及結(jié)果

在這個實驗中，主要改變障礙物個數(shù)和位置分布，通過在幾種不同障礙物環(huán)境的模擬結(jié)果分析人工勢場法優(yōu)點和局限性以及適用環(huán)境。

1)當空間有一個障礙物時，結(jié)果如圖5所示，兩種環(huán)境中的迭代次數(shù)分別為K=107和K=114。

圖5 障礙物個數(shù)n=1時仿真結(jié)果

從圖5可看出，當環(huán)境中有一個障礙物時，機器人可通過構(gòu)造的人工勢場躲避障礙物，并沿最短路徑尋找目標，即使改變障礙物位置，依然可得到良好結(jié)果，因此人工勢場法用于簡單環(huán)境是可靠的。

2)當空間中有兩個障礙物時，結(jié)果如圖6所示，迭代次數(shù)均為K=109。

圖6 障礙物個數(shù)n=2時的仿真結(jié)果

從圖6可看出，當存在兩個障礙物時，機器人可通過合力作用成功躲避障礙物，并沿最短路徑到達目標點，改變障礙物的位置結(jié)果依然滿意。

3)當空間中有3個障礙物時，結(jié)果如圖7所示，迭代次數(shù)分別為K=110和K=52。

從圖7可看出，一種情況機器人連續(xù)躲避了兩個障礙物，然后沿最短路徑向目標點前進；第二種情況，機器人從兩障礙物之間穿過，也取得不錯效果。3個障礙物環(huán)境人工勢場法可完成規(guī)劃任務(wù)。

圖7 障礙物個數(shù)n=3時的仿真結(jié)果

4)當空間中有4個障礙物時，結(jié)果如圖8所示，迭代次數(shù)分別為K=56和K=51。

圖8 障礙物個數(shù)n=4時仿真結(jié)果

這種情況和3個障礙物環(huán)境中的仿真結(jié)果相似，均能躲避障礙物。但此時可觀察到兩種環(huán)境下規(guī)劃的路徑顯然已不是最短路徑，這是合力方向不當造成的。

5)當空間中有5個障礙物時，結(jié)果如圖9所示，迭代次數(shù)分別為K=121、K=113和K=52。

圖9 n=5時兩種不同情況仿真結(jié)果

從圖9(a)看確實避開了障礙物，但最后機器人不能到達目標點，這是由于障礙物和目標點距離較近，目標在障礙物影響范圍之內(nèi)，這時斥力大于引力，停止點位置兩者相等造成的。從圖9(b)在機器人行進過程中，躲避第4個障礙物時出現(xiàn)問題。觀察這個位置特征，可看出這是個特殊位置，此時，機器人、障礙物和目標點在同一條直線上，這時合力也是沿著這條直線，才導(dǎo)致了這個問題。因此在這種情況下，人工勢場法已不能完成基本規(guī)劃任務(wù)。

通過比較這5種不同障礙物環(huán)境下的仿真可以發(fā)現(xiàn)，當障礙物數(shù)量較少且分散時，人工勢場法可規(guī)劃出滿意路徑，且該路徑為平滑曲線。當障礙物數(shù)量較多時，特別是障礙物分布在目標點周圍或出現(xiàn)機器人、障礙物和目標點三者在同一條直線上的情況，該算法已不能規(guī)劃出較優(yōu)路徑?；谶@種局限性，須使用智能化算法中的蟻群算法進行復(fù)雜環(huán)境中的路徑規(guī)劃。

3.3 蟻群算法的仿真及結(jié)果

3.3.1 參數(shù)的設(shè)置及初始化

蟻群算法中各參數(shù)值會影響算法的性能，研究下列參數(shù)最佳組合是有必要的。①M：螞蟻數(shù)，即每波有M只螞蟻覓食；②ρ：信息素蒸發(fā)系數(shù)；③β：表征啟發(fā)式因子的重要程度。

3.3.1.1 蟻群規(guī)模的設(shè)置

一只螞蟻所走路徑為整體解集中的一個，M只螞蟻在一次迭代過程中所走路徑為整體解集中一個子集。蟻群數(shù)量適當增多可使規(guī)劃出來的路徑結(jié)果更穩(wěn)定和更準確，但螞蟻數(shù)量過大時，算法需要耗費過長時間；反之，當螞蟻數(shù)量過少時，會降低算法的隨機性，導(dǎo)致過快收斂，計算結(jié)果不可靠。以下通過在不同數(shù)量螞蟻的情況下進行實驗，通過實驗結(jié)果來直接得到算法中螞蟻數(shù)量的最佳設(shè)置值。M=10、30、50、70、90時，路徑規(guī)劃和收斂曲線如圖10所示。

圖10 改變螞蟻數(shù)量時的仿真圖像

對比圖10可知，當螞蟻數(shù)量M=50時，路徑長度最短，也不至于陷入過早收斂，因此將螞蟻數(shù)量設(shè)為M=50。

3.3.1.2 信息素蒸發(fā)系數(shù)ρ的取值

ρ取值會對算法搜索能力和收斂速度產(chǎn)生影響，ρ太小，信息素蒸發(fā)少殘留多，結(jié)果不具隨機性；ρ增大，結(jié)果具有普遍性，但算法收斂慢，時效性較差。以下通過實驗驗證算法中ρ的最佳設(shè)置值。

當ρ=0.1、0.2、0.3、0.4、0.5時，螞蟻的最短路徑圖和收斂曲線如圖11所示。

圖11 改變信息素蒸發(fā)系數(shù)時的仿真圖像

可以看出，ρ=0.3時，路徑長度最短，最終穩(wěn)定時的迭代次數(shù)也最小，因此取信息素蒸發(fā)系數(shù)ρ=0.3。

3.3.1.3 啟發(fā)式因子重要程度β的設(shè)置

啟發(fā)式因子β表示螞蟻在尋找路徑過程中所積累的信息量是對于它作出選擇的重要程度，值越大，會越多重復(fù)以前選擇，失去隨機性，使結(jié)果過早收斂。通過在β不同取值情況下實驗結(jié)果來直接得到算法中β的最佳設(shè)置值。

當β=1、3、5、7、9時，螞蟻的最短路徑圖和收斂曲線如圖12所示。

圖12 改變啟發(fā)式因子時的仿真圖像

從圖12可以看出，當啟發(fā)式因子很小時，不能找到最優(yōu)路徑，當啟發(fā)式因子逐漸增大時，路徑長度逐漸變小，迭代次數(shù)變小，但當啟發(fā)式因子過大時，螞蟻在路徑選擇上可能會過早陷入收斂。因此當啟發(fā)式因子β=7時，可規(guī)劃出最有路徑。

3.3.2 不同障礙物空間的仿真結(jié)果

在3.3.1節(jié)中可以看到，當螞蟻數(shù)量M=50、信息素蒸發(fā)系數(shù)ρ=0.3、啟發(fā)式因子β=7時，可規(guī)劃出最優(yōu)路徑。只有在不同障礙物環(huán)境下都能規(guī)劃出滿意結(jié)果才能說明算法的有效性和參數(shù)選擇合理性。

1)障礙物環(huán)境1仿真如圖13所示。從圖13中可以看出螞蟻行走的路徑為無碰路徑，由螞蟻路徑規(guī)劃的收斂曲線可以得知當?shù)螖?shù)為52時可得到收斂解，路徑長度已趨于穩(wěn)定值且為最小值。

圖13 障礙物環(huán)境1中最優(yōu)路徑和收斂曲線

2)障礙物環(huán)境2中仿真如圖14所示。由螞蟻爬行過程中所經(jīng)過的最短路徑圖可看出，顯然為無碰路徑，由螞蟻路徑規(guī)劃的收斂曲線可以得知到第52代螞蟻可得到穩(wěn)定解。

圖14 障礙物環(huán)境2中最優(yōu)路徑和收斂曲線

4 結(jié)論

通過不同障礙物、不同參數(shù)下的實驗得出：

1)當障礙物數(shù)量較少且分散時，人工勢場法可以規(guī)劃出滿意的路徑，且該路徑為平滑的曲線。該算法所占空間少，運行速度和路徑的收斂速度都較快，但有它的局限性，容易使系統(tǒng)陷入局部極值。當障礙物數(shù)量較多時，特別是障礙物分布在目標點周圍或出現(xiàn)機器人、障礙物和目標點三者在同一條直線上的情況，使用簡單的人工勢場法已不能規(guī)劃出較優(yōu)路徑。

2)基于人工勢場法的這種局限性，使用蟻群算法在復(fù)雜障礙物環(huán)境中的實驗結(jié)果表明，將蟻群算法用于復(fù)雜環(huán)境下的路徑規(guī)劃問題是可行的且本文參數(shù)的選取是合理的。此外，在仿真過程中研究螞蟻數(shù)量M、信息素蒸發(fā)系數(shù)ρ和啟發(fā)式因子重要程度β等參數(shù)的最佳組合是很重要的，這些參數(shù)會影響規(guī)劃路徑的長度和收斂速度，通過多次模擬結(jié)果的對比實驗來決定算法中的最佳參數(shù)設(shè)置能得到更為優(yōu)化的結(jié)果。