基于轉(zhuǎn)角約束的改進蟻群優(yōu)化算法路徑規(guī)劃

李開榮，劉 爽，胡倩倩，唐亦媛

（揚州大學(xué)信息工程學(xué)院，江蘇揚州 225127）

（*通信作者電子郵箱973279727@qq.com）

0 引言

隨著智能化時代的到來，移動機器人越來越普及，其中一項重要的研究工作即移動機器人的路徑規(guī)劃問題。移動機器人的工作環(huán)境中往往存在著一定數(shù)量的障礙物，需要從初始點準(zhǔn)確且快速地尋找一條能夠避開所有障礙物到達目標(biāo)點的最優(yōu)路徑［1］。傳統(tǒng)的路徑規(guī)劃算法有柵格法、人工勢場法等［2］。柵格法屬于全局路徑規(guī)劃算法，用于構(gòu)建移動環(huán)境，將機器人的路徑轉(zhuǎn)換為網(wǎng)格之間的連接，算法簡單易實現(xiàn)；但是當(dāng)移動環(huán)境變大時，網(wǎng)格數(shù)量急劇增加，數(shù)據(jù)存儲空間大，計算速度慢。人工勢場法是一種局部路徑規(guī)劃算法，實時性強、計算量小，對硬件平臺的要求低；但是其存在的局部最小點問題很容易引起路徑規(guī)劃的失敗。因此，隨著移動環(huán)境復(fù)雜度和任務(wù)難度的增加，傳統(tǒng)的路徑規(guī)劃算法無法達到預(yù)期的效果。隨著人工智能的發(fā)展，例如遺傳算法［3］、蟻群優(yōu)化（Ant Colony Optimization，ACO）算法［4］、煙花算法［5］、粒子群算法［6］等智能算法也被應(yīng)用到路徑規(guī)劃領(lǐng)域中，并且取得了豐富的成果。

在上述路徑規(guī)劃方法中，蟻群優(yōu)化算法［7］具有較強的魯棒性和搜索能力，作為一種啟發(fā)式算法，對螞蟻群體的覓食過程進行學(xué)習(xí)模擬，得出螞蟻們共同規(guī)劃的解路徑，具有正反饋、并行計算以及易融合等特點，但也存在迭代次數(shù)多和易忽略全局最優(yōu)解等問題。針對這些問題，許多國內(nèi)外學(xué)者進行了探索與改進，文獻［8］針對傳統(tǒng)蟻群優(yōu)化算法易陷入局部最優(yōu)、初期搜索能力差等問題，采用改進的頭尾搜索機制，引入獎懲因子與信息素最大最小閾值，添加遺傳算法變異因子，使規(guī)劃出來的路徑得到了進一步的優(yōu)化。文獻［9］為避免初期尋優(yōu)的盲目性，在柵格地圖中劃定優(yōu)選區(qū)域，設(shè)置新的初始信息素濃度模型，提高了算法的收斂速度。文獻［10］使用偽隨機狀態(tài)轉(zhuǎn)移規(guī)則選擇路徑，根據(jù)當(dāng)前最優(yōu)解和迭代次數(shù)計算狀態(tài)轉(zhuǎn)移概率，自適應(yīng)地調(diào)整確定選擇和隨機選擇的比例，引入最優(yōu)解和最差解改進全局信息素更新方法，仿真實驗結(jié)果表明，改進后的蟻群優(yōu)化算法收斂速度更快、全局搜索能力更強。文獻［11］在蟻群優(yōu)化算法中融合免疫算法，大大緩解了抗體種群的“早熟”問題。文獻［12］將蟻群優(yōu)化算法生成的路徑進行平滑操作，減少了轉(zhuǎn)彎次數(shù)。

以上改進蟻群優(yōu)化算法大多致力于優(yōu)化路徑長度以及提高尋路效率，很少有學(xué)者在尋找下一步移動節(jié)點時就考慮到轉(zhuǎn)彎角度次數(shù)過多導(dǎo)致機器人運行時間增長、能耗增加的問題，部分學(xué)者在路徑規(guī)劃出來后對其進行平滑操作，但這種方式增加了算法的復(fù)雜性，且最終路徑未必就是全局最優(yōu)路徑。鑒于此，本文提出了一種基于轉(zhuǎn)角約束的改進蟻群優(yōu)化算法，用于移動機器人路徑規(guī)劃。為降低搜索初期的盲目性，該算法首先增加起始點與終止點之間的初始信息素濃度；并且在啟發(fā)函數(shù)中加入A*算法的估價函數(shù)和轉(zhuǎn)彎角度因子，使搜索到的路徑是綜合路徑長度和累計轉(zhuǎn)角最小的最優(yōu)路徑，有利于減少移動機器人損失的能耗，防止出現(xiàn)局部最優(yōu)的情況；在信息素更新公式中，引進狼群算法的獵物分配原則，同時借鑒最大最小蟻群（Max and Min Ant System，MMAS）算法給路徑上的信息素規(guī)定上限和下限，進一步提高收斂速度，便于快速搜索到一條綜合指標(biāo)最優(yōu)的路徑。

1 基本蟻群優(yōu)化算法

蟻群優(yōu)化算法即螞蟻種群從起始點出發(fā)，至目標(biāo)位置獲取食物的過程，螞蟻的信息素會被留在其走過的路徑上，它們利用信息素相互通信，當(dāng)某一條路徑上通過的螞蟻越來越多時，該路徑的信息素濃度就會越高，其他螞蟻就有更大的概率選擇這條路徑，起到正反饋作用，然而也容易導(dǎo)致局部最優(yōu)或死鎖情況的出現(xiàn)［13］。

通過對信息素濃度、啟發(fā)因子、路徑方向等因素進行綜合判斷選擇下一步移動的柵格，并利用輪盤賭法計算當(dāng)前節(jié)點到下一節(jié)點的概率［14］，如式（1）～（3）所示。

其中：τij是網(wǎng)格i到網(wǎng)格j的信息素值；ηij是網(wǎng)格i到網(wǎng)格j的啟發(fā)式信息；α為信息素激勵因子，代表信息素值對路徑選擇的影響程度，α越大則信息素對于路徑選擇的影響越大，大多數(shù)螞蟻走過的路徑將有更大幾率被選中；β是期望啟發(fā)式因子，代表啟發(fā)信息對螞蟻選擇路徑的影響程度，β與影響程度之間是正相關(guān)關(guān)系；dij代表節(jié)點i與節(jié)點j之間的歐幾里得距離。（xi，y）i和（xj，y）j是網(wǎng)格i與網(wǎng)格j的坐標(biāo)；allowedk中存放網(wǎng)格i中螞蟻此時能夠選擇的網(wǎng)格集合。

經(jīng)過t時刻，當(dāng)每只螞蟻都進行了一次路徑規(guī)劃后，計算所有順利到達目標(biāo)點的螞蟻走過的路徑長度，從中篩選出最短路徑，并且將每條路徑上的信息素濃度都進行更新，一段時間后，將揮發(fā)一部分信息素，如式（4）所示：

其中：ρ是信息素?fù)]發(fā)系數(shù)。

同時螞蟻也將在路徑上留下一些信息素，如式（5）所示：

式（6）為蟻群模型的信息素更新策略，其中：Q為信息素的強度，若螞蟻搜索到的路徑長度dij越小，依據(jù)公式，則將會有更多的信息素被加到路徑上，之后其他螞蟻選中該路徑的可能性也將更大［15］。

2 環(huán)境建模

常用的環(huán)境建模方法有柵格圖法、可視圖空間法、自由空間法、幾何信息法［16］等。本文選擇柵格圖法對移動機器人二維運動空間進行建模，假設(shè)每個柵格的邊長為1，其中：白色柵格為自由柵格，表示可通行區(qū)域；黑色柵格為障礙物區(qū)域，移動機器人不可通行。如式（7）所示：

移動機器人平行行駛在障礙物邊緣的位置關(guān)系如圖1所示。

圖1 機器人與障礙物的位置關(guān)系Fig.1 Position relationship between robot and obstacle

假設(shè)移動機器人的直徑為W，從圖1 可以看出，當(dāng)機器人的中心占據(jù)柵格距離障礙物邊緣的最小距離小于W/2 時，就會發(fā)生碰撞［17］，此時的碰撞概率為100%，即

其中：P（x，y）為柵格（x，y）的碰撞概率；N（x，y）為移動機器人中心所占據(jù)的柵格；｛O｝為障礙物所有邊緣柵格的集合；min（｛O｝，N（x，y））表示移動機器人中心占據(jù)柵格到障礙物所有邊緣柵格距離集的最小值。

為確保移動機器人在運動中不與障礙物邊緣發(fā)生碰撞，且保證每次轉(zhuǎn)彎的順利進行，本文將障礙物尺寸進行適當(dāng)膨化后再預(yù)留出一定的安全距離，其中安全距離為移動機器人的半徑，進而可將機器人簡化為一個質(zhì)點來處理，障礙物處理過程如圖2所示。

圖2 障礙物處理圖Fig.2 Obstacle processing diagram

網(wǎng)格模型被放置在二維坐標(biāo)系中，x為橫軸，y為縱軸，采用序列號的方法標(biāo)記每個網(wǎng)格。在N*N的網(wǎng)格圖中，起始節(jié)點以“起始”命名，目標(biāo)節(jié)點以“目標(biāo)”命名，其余柵格分別用編號i表示，每個柵格的中心點坐標(biāo)為（xi，y）i，柵格編號與其坐標(biāo)的對應(yīng)關(guān)系如式（9）所示：

3 改進蟻群優(yōu)化算法

基本的蟻群優(yōu)化算法有以下缺點：每個柵格的初始信息素值相同且啟發(fā)式值之間也不存在明顯差異，因此往往搜索時間較長，難以尋找到全局最優(yōu)解［18］；同時在柵格地圖中，使用基本蟻群優(yōu)化算法規(guī)劃出來的路徑可能會有更多的轉(zhuǎn)彎次數(shù)和較大的累計轉(zhuǎn)彎角度。為了解決上述問題，本文進行了以下改進。

3.1 初始信息素不均勻分布

在基本蟻群優(yōu)化算法的初始階段，每個柵格的初始信息素值相同，這就使得螞蟻在初期搜索時存在不小的盲目性，算法運行時間增加。因此本文將初始信息素的分布進行適當(dāng)調(diào)整，使其不均勻分布，并且不會增加算法的復(fù)雜性。通過參考其他眾多文獻中的路徑，本文發(fā)現(xiàn)最優(yōu)路徑大部分情況下都存在于起點與終點連線的附近［19］，因此此處取柵格地圖各邊的中點，連接相鄰邊的中點，得到與起點終點連線平行的兩條直線，直線AB與直線CD之間的區(qū)域如圖3 所示，增強該區(qū)域的初始信息素值，如式（10）所示。

圖3 初始信息素增強區(qū)域Fig.3 Initial pheromone enhancement area

其中：τ0為信息素初始值，C為大于τ0的常數(shù)。

3.2 改進啟發(fā)式信息

基本蟻群優(yōu)化算法的啟發(fā)函數(shù)中，相鄰網(wǎng)格之間啟發(fā)式值的大小相差無幾，所以往往需要較長的搜尋時間且不易搜索到全局最優(yōu)路徑。為此，本文將A*算法加入到蟻群優(yōu)化算法的啟發(fā)式信息中，以提高算法的收斂速度并獲得更優(yōu)的全局路徑［20］。

A*算法有較快的尋路速度，其啟發(fā)式成本由估價函數(shù)（fn）表示，通過（fn）來指導(dǎo)節(jié)點的擴展與搜索，每一次都是搜索從起始點到目標(biāo)點之間使得（fn）最小的路徑，估價函數(shù)方程為：

其中：g（n）為從起始節(jié)點到當(dāng)前節(jié)點的最小路徑成本值；h（n）為從當(dāng)前節(jié)點到目標(biāo)節(jié)點的最小路徑成本估計值；nx和ny是當(dāng)前節(jié)點n的坐標(biāo)；gx和gy是目標(biāo)節(jié)點g的坐標(biāo)；sx和sy是初始節(jié)點s的坐標(biāo)。

機器人在經(jīng)過障礙物群時，若只是把路徑最短作為主要因素，則會造成機器人轉(zhuǎn)彎次數(shù)過多，時間和能耗大大增加，也會導(dǎo)致機器人壽命的減少。因此，本文將轉(zhuǎn)彎角度因子也加入到蟻群優(yōu)化算法的啟發(fā)信息中，使移動機器人盡可能選擇一條轉(zhuǎn)彎角度更小的路徑，若一條路徑中節(jié)點之間的轉(zhuǎn)彎角度過大，則啟發(fā)函數(shù)值將降低，路徑中節(jié)點之間的轉(zhuǎn)彎角度示意圖如圖4所示。

圖4 轉(zhuǎn)彎角度示意圖Fig.4 Schematic diagram of turning angle

圖4中統(tǒng)一按照順時針的方向進行角度測量，（A，B）節(jié)點之間的路徑相對于（O，A）節(jié)點之間轉(zhuǎn)彎角度是45°，而（C，D）節(jié)點之間的路徑相對于（B，C）節(jié)點之間的轉(zhuǎn)彎角度是90°，轉(zhuǎn)彎角度值的計算公式如下：

其中：R是轉(zhuǎn)彎角度因子；γ是轉(zhuǎn)彎角度（單位：rad）；c是轉(zhuǎn)彎角度權(quán)重系數(shù)。

綜上，在蟻群優(yōu)化算法中，將A*算法的估計函數(shù)用作啟發(fā)式信息，以便于搜索全局最優(yōu)路徑、提高收斂速度；同時，將轉(zhuǎn)彎角度因子也添加到蟻群優(yōu)化算法的啟發(fā)式值中，以減少轉(zhuǎn)彎次數(shù)和累計轉(zhuǎn)向角度，促使機器人按照路徑長度和轉(zhuǎn)彎角度雙重因素進行最優(yōu)選擇。改進后的啟發(fā)函數(shù)公式如下：

其中：Q1是大于1的常數(shù)。

3.3 改進信息素更新

蟻群算法模擬自然界中的蟻群覓食機制，采用分布式正反饋并行計算機制，傳統(tǒng)蟻群算法是各個螞蟻單獨行動且每只螞蟻都執(zhí)行相同的操作，螞蟻之間的協(xié)作不足，可能會導(dǎo)致滯后、算法陷入局部最優(yōu)、收斂速度慢等問題。在搜索路徑時，存在一部分螞蟻找到的路徑是最差路徑，它們所釋放的信息素將對之后的螞蟻尋路造成負(fù)面影響，從而容易使搜索陷入局部最優(yōu)，還可能出現(xiàn)死鎖情況導(dǎo)致有效螞蟻數(shù)量損失；而另一些螞蟻尋得最優(yōu)路徑，它們所釋放的信息素將對其余螞蟻尋找最優(yōu)路徑起到促進作用。為了提升收斂速度、獲得最優(yōu)路徑，此處融合狼群算法，在蟻群算法的信息素更新公式中加入獵物分配原則［21］。

狼群算法是一種智能優(yōu)化算法，模擬狼群的社會分工和捕食行為，其分配規(guī)則為“強者生存”的狼群更新機制，狼群中存在貢獻能力弱的狼，即身體瘦弱的狼，它們獵得食物的數(shù)量和可能性都遠(yuǎn)小于身體強壯的狼，就如蟻群中存在尋得路徑差的螞蟻，這些螞蟻尋得的路徑要差于尋路能力強的螞蟻。

因此，狼群算法中按照狼“由強到弱”的順序進行獵物分配，身體強壯且善于捕獵的狼會優(yōu)先獲得食物，反之身體瘦弱的狼則只能分得很少的食物。隨著每次分配的進行，部分身體弱小的狼將越來越難以生存下去，直至餓死；而先前本就強壯的狼將越發(fā)強壯，在下一次捕獵時獵得食物的可能性將進一步增大，經(jīng)過迭代，狼群的生存能力被逐漸提高。

在蟻群算法中融合狼群算法中獵物分配原則的動機是借鑒該分配原則來解決傳統(tǒng)蟻群算法在信息素更新時存在的問題，即尋得最差路徑的螞蟻釋放的信息素將會對隨后的螞蟻尋路造成一定的誤導(dǎo)作用，容易使路徑陷入局部最優(yōu)，并且尋得最優(yōu)路徑的螞蟻釋放的信息素不能很好地傳遞給之后的螞蟻。這一融合過程可以理解為，加強蟻群算法中優(yōu)質(zhì)路徑上的信息素濃度，較弱個體的經(jīng)驗由于參考價值少，不應(yīng)被著重考慮，便于更多的螞蟻吸收優(yōu)質(zhì)個體的經(jīng)驗，提高收斂速度。

采用狼群算法中“強者生存”的更新機制有效傳承了整個螞蟻種群在搜索路徑時形成的“智慧”、提高全局搜索能力、避免陷入局部最優(yōu)解，符合自然界種群繁衍進化的特點，不斷更新的信息素代表著蟻群在整個路徑搜索過程中形成的尋路智慧，有利于該智能優(yōu)化算法對解空間進行更好的學(xué)習(xí)。

借鑒這種思想，本文算法在每次迭代中，計算各個螞蟻的運動軌跡長度，將到達目標(biāo)點路徑最短的螞蟻所留下的信息素增強，路徑最長的螞蟻所留下的信息素減弱，突出不同路徑之間信息素的差別化。對信息素更新公式作如下改進：

其中：Δ*τij和Δ**τij分別代表每次迭代中最優(yōu)和最差路徑經(jīng)過節(jié)點i、j的信息素大小；L*和L**分別代表每次蟻群到達目標(biāo)點的最短運動軌跡和最長運動軌跡；δ和ω分別表示每次搜索時找到最短路徑和最長路徑的螞蟻數(shù)量；Q2為增強因子，此處將其設(shè)為1；R1為減弱因子，將其值設(shè)為0.5。

經(jīng)過多次迭代后，某條路徑上的信息素值可能遠(yuǎn)大于或遠(yuǎn)小于其他路徑，使得搜索不能繼續(xù)進行下去、過早收斂，為防止這種極端情況產(chǎn)生，借鑒MMAS算法［22］，將信息素的取值范圍限定在τmin到τmax，如式（19）所示：

4 改進算法的步驟

綜上所述，本文對基本蟻群算法改進后，移動機器人路徑規(guī)劃的步驟如下：

步驟1 通過柵格法對工作環(huán)境進行建模，為移動機器人設(shè)定好運動的起始點和目標(biāo)點。

步驟2 初始化參數(shù)：螞蟻數(shù)量m，信息素重要程度因子α，啟發(fā)函數(shù)重要程度因子β，信息素?fù)]發(fā)系數(shù)ρ，信息素強度系數(shù)Q、迭代次數(shù)N等，其中初始信息素濃度按式（10）設(shè)置。

步驟3 更新禁忌表。將螞蟻k（k=1，2，…，n）放在當(dāng)前節(jié)點上，將當(dāng)前節(jié)點添加到禁忌表中。

步驟4 選擇下一步的網(wǎng)格。根據(jù)式（15）計算加入A*估價函數(shù)和轉(zhuǎn)角約束的啟發(fā)式函數(shù)值，然后依據(jù)式（1）～（3）求出狀態(tài)轉(zhuǎn)移概率值。再借鑒輪盤賭法選出下一步將要到達的柵格，若螞蟻抵達目標(biāo)位置，則轉(zhuǎn)到步驟5；反之轉(zhuǎn)到步驟3。

步驟5 如果螞蟻到達目標(biāo)位置，重復(fù)步驟3，直到每個螞蟻在其迭代過程中完成整個搜索過程，之后轉(zhuǎn)到步驟6。

步驟6 更新信息素。每次迭代完成，如果此時迭代次數(shù)小于最大迭代次數(shù)，將按照狼群算法的獵物分配原則即式（16）～（18）計算路徑上的信息素濃度，同時要保證其滿足式（19），若滿足收斂條件，則退出；若不滿足，轉(zhuǎn)到步驟3。反之迭代次數(shù)大于最大迭代次數(shù)時，則停止計數(shù)，輸出最終結(jié)果。

本文算法整體流程如圖5所示。

圖5 本文算法流程Fig.5 Flowchart of proposed algorithm

5 仿真分析

為了驗證本文改進蟻群算法的可靠性，使用Matlab 軟件進行仿真。分別使用4 種不同規(guī)模的柵格地圖，每次在同樣大小的柵格地圖中，采用相同的實驗條件對8 種不同的算法進行對比分析。

5.1 參數(shù)取值

關(guān)于蟻群算法主要參數(shù)值的確定，目前沒有特別詳盡的理論方法，因此本文根據(jù)經(jīng)驗反復(fù)實驗而定，設(shè)置不同的參數(shù)組合進行仿真，分析實驗結(jié)果，選擇最佳參數(shù)組合。

對每一個參數(shù)設(shè)置一組值，以圖3 的柵格地圖為本次實驗環(huán)境，起始點和目標(biāo)點分別用點S和點T在圖中表示，在每次測試中僅改變一個參數(shù)的取值，其他參數(shù)為常量，分別計算最佳路徑長度和迭代次數(shù)。由于對規(guī)劃結(jié)果影響較大的參數(shù)是螞蟻數(shù)量m、信息素啟發(fā)因子α和期望啟發(fā)式因子β，因此本文僅介紹這三個參數(shù)的取值過程。其余參數(shù)根據(jù)經(jīng)驗及實驗仿真對比，初始化參數(shù)值如表1所示。

表1 初始化參數(shù)值Tab.1 Initialized parameter values

5.1.1 螞蟻數(shù)量m

在蟻群算法中，當(dāng)螞蟻數(shù)目過多時，信息素的作用將被削弱，導(dǎo)致蟻群算法的收斂速度變慢；當(dāng)螞蟻數(shù)目過少時，可能存在路徑未被選擇的情況，無法有效搜索到全局最優(yōu)解。因此，選擇合適的螞蟻數(shù)量至關(guān)重要，本文對除螞蟻數(shù)目m之外的其他參數(shù)取值分別為：α=1，β=7，ρ=0.3，取螞蟻數(shù)量m=10，20，30，40，50，60，70，80，90，100。為防止偶然因素，對每組數(shù)據(jù)運行10次，得到螞蟻數(shù)量m對計算結(jié)果的影響如圖6所示。

圖6 螞蟻數(shù)量m對ACO算法的影響Fig.6 Influence of the number of ants m on ACO algorithm

由圖6 可知，隨著螞蟻數(shù)量從10 變化到40，最短路徑的長度急劇下降，之后變化幅度減小至不再變化；迭代次數(shù)呈現(xiàn)升降升的趨勢，在螞蟻數(shù)量為50 時，迭代次數(shù)達到最小。總結(jié)發(fā)現(xiàn)，當(dāng)螞蟻數(shù)量約為自由柵格數(shù)的1/6 時，算法的收斂速度和路徑長度達到最優(yōu)。

5.1.2 信息素啟發(fā)因子α和期望啟發(fā)式因子β

α表示當(dāng)前螞蟻受前代蟻群搜索結(jié)果的啟發(fā)程度，β反映的是當(dāng)前環(huán)境相關(guān)信息對螞蟻的影響程度。α越大，β越小，則螞蟻越依賴信息素的指導(dǎo)，傾向于選擇之前走過的路徑；反之，α越小，β越大，則螞蟻更傾向依據(jù)當(dāng)下的環(huán)境選擇較短的路徑抵達目標(biāo)點。兩者是相互關(guān)聯(lián)的，因此此處選擇將β/α設(shè)為自變量，路徑長度和迭代次數(shù)作為因變量。設(shè)α=1，β/α取1～10，m=50，ρ=0.3，其余參數(shù)取值如表1。對計算結(jié)果的影響如圖7所示。

圖7 β/α對ACO算法的影響Fig.7 Influence of β/α on ACO algorithm

由圖7 可知，隨著β/α值的遞增，最短路徑長度逐漸減小直至穩(wěn)定，迭代次數(shù)先減小后增加，在β/α=7 時取最小值。因此，當(dāng)α=1，β=7時，蟻群算法各方面具有較優(yōu)的性能。

5.2 小規(guī)模柵格環(huán)境

首先將基本蟻群算法、文獻［12］、文獻［23］、文獻［24］改進的蟻群算法及本文算法在20×20、30×30規(guī)模的柵格地圖上進行對比實驗。此處實驗各相關(guān)參數(shù)取值為：m=50，α=1，β=7，其余按表1取值。

5.2.1 20×20柵格環(huán)境

在20×20 規(guī)模的柵格環(huán)境中，5 種算法仿真結(jié)果如圖8 所示。由圖8可知，基本蟻群算法規(guī)劃出的路徑長度為31.4，文獻［23］算法的路徑長度為31.4，文獻［24］算法的路徑規(guī)劃長度為29.8，文獻［12］規(guī)劃出的路徑長度為28.82，本文算法的最優(yōu)路徑長度為28.63。

圖8 在20×20地圖上5種算法規(guī)劃的路徑Fig.8 Paths planned by five algorithms on 20×20 map

五種算法的路徑長度和迭代次數(shù)如圖9 所示。由圖9 可知，本文算法和文獻［23］算法的迭代穩(wěn)定次數(shù)相差不大，比基本蟻群算法和文獻［12］算法減少50%的迭代穩(wěn)定次數(shù)，比文獻［24］的迭代穩(wěn)定次數(shù)也更優(yōu)，具體指標(biāo)比較如表2 所示。由表2 可知，在路徑長度上，本文改進之后的算法運行出的最優(yōu)路徑長度為28.63，較基本蟻群算法和文獻［23］算法縮短8.8%，較文獻［24］算法也縮短了3.9%；在轉(zhuǎn)彎次數(shù)上，本文算法轉(zhuǎn)彎次數(shù)為4，分別較基本蟻群算法和文獻［23］算法減少了75%和50%，大幅減少了轉(zhuǎn)彎次數(shù)；在累計轉(zhuǎn)彎角度上，較基本蟻群算法、文獻［23］和文獻［24］算法分別減少了720°、270°和180°，規(guī)劃出的路徑更加平滑，避免了移動機器人過多的能耗損失，延長了壽命，縮短了轉(zhuǎn)彎時間。

圖9 在20×20地圖上的路徑長度迭代圖Fig.9 Path length iteration graph on 20×20 map

文獻［12］算法的主要思想是將蟻群算法生成的全局最優(yōu)路徑再進行平滑處理，將路徑中兩個不在同一直線上的節(jié)點連線，若連線中間不穿過障礙物則此連線就是新的路徑，以此法來進行路徑平滑處理。由表2 中可以看出，文獻［12］算法能夠有效縮短路徑長度和累計轉(zhuǎn)彎角度，但是該算法仍存在明顯不足：在迭代次數(shù)上，該算法需要26 次迭代才能達到穩(wěn)定，而本文算法僅需4 次即可；在程序運行時間上，文獻［12］算法需要10.632 s，本文算法在6.921 s 內(nèi)即可完成。綜合多種指標(biāo)來看，在此處柵格環(huán)境下本文算法都要優(yōu)于文獻［12］算法。

表2 在20×20地圖上的仿真結(jié)果Tab.2 Simulation results on 20×20 map

綜上，本文算法生成的路徑綜合指標(biāo)最優(yōu)，改進之后的算法優(yōu)勢明顯。

5.2.2 30×30柵格環(huán)境

為了進一步驗證本文算法的可靠性，將柵格地圖擴大為30×30，障礙物增多，再次進行仿真。基本蟻群算法、文獻［12］算法、文獻［23］算法、文獻［24］算法以及本文算法的路徑規(guī)劃如圖10所示。

圖10 在30×30地圖上五種算法規(guī)劃的路徑Fig.10 Paths planned by five algorithms on 30×30 map

由圖10 可以看出，當(dāng)柵格地圖規(guī)模擴大并且障礙物增多時，基本蟻群算法、文獻［12］算法、文獻［23］算法、文獻［24］算法無法很好地適應(yīng)該類較為復(fù)雜環(huán)境的全局路徑規(guī)劃，其規(guī)劃出的最優(yōu)路徑長度分別為50.2、45.8、47.2和47.5，而本文算法仍然可以很好地執(zhí)行，尋得的最優(yōu)路徑長度為43.3，較其他算法有效縮短了路徑長度，路徑長度與迭代次數(shù)的關(guān)系如圖11所示。

圖11 在30×30地圖上的路徑長度迭代圖Fig.11 Path length iteration graph on 30×30 map

圖11為五種算法在30×30柵格規(guī)模下的收斂曲線變化趨勢，可以看出當(dāng)環(huán)境復(fù)雜化后，本文算法及文獻［23］算法在迭代穩(wěn)定次數(shù)上比其余三種算法更優(yōu)，文獻［23］算法的收斂速度比文本算法稍快一些，具體指標(biāo)比較如表3所示。

表3 在30×30地圖上的仿真結(jié)果Tab.3 Simulation results on 30×30 map

由表3 可知，本文的改進蟻群算法在路徑長度、轉(zhuǎn)彎次數(shù)以及累計轉(zhuǎn)彎角度等指標(biāo)上都明顯優(yōu)于基本蟻群算法、文獻［23］及文獻［24］的算法，這三種算法在障礙物增多的環(huán)境中都無法很好地適應(yīng)，其中本文算法在路徑長度上較基本蟻群算法縮短了13.7%、較文獻［23］算法和文獻［24］算法縮短了8.3%和8.8%；轉(zhuǎn)彎次數(shù)也是其中最少的，尤其是較基本蟻群算法減少了64.3%；在累計轉(zhuǎn)彎角度指標(biāo)上，本文算法占明顯優(yōu)勢，較迭代穩(wěn)定次數(shù)表現(xiàn)較優(yōu)的文獻［23］算法減少了41.2%。另外，可以看出文獻［12］算法、文獻［23］算法和文獻［24］算法在復(fù)雜環(huán)境下出現(xiàn)多次直角轉(zhuǎn)彎，而移動機器人面臨直角轉(zhuǎn)彎時比45°轉(zhuǎn)彎會消耗更多的能量，本文算法規(guī)劃的路徑中不存在直角轉(zhuǎn)彎的情況。同時在實際運動中，直角轉(zhuǎn)彎所需要的時間也更多，將大大增加機器人從起始點到目標(biāo)點的運行時間，而本文算法不僅累計轉(zhuǎn)彎角度最小，也有效避免了直角轉(zhuǎn)彎的出現(xiàn)。

目前針對移動機器人轉(zhuǎn)角減小的研究中，文獻［12］中的平滑方法較為普遍，但該方法存在一定的局限性。由表3 可以看出，在路徑長度上，文獻［12］算法較其他三種算法更優(yōu)，但本文算法規(guī)劃出的路徑長度是43.3，比其更短；在轉(zhuǎn)彎次數(shù)上，兩者相同；但在累計轉(zhuǎn)彎角度上，本文算法比文獻［12］算法減少了20.4%；除此之外，本文算法在迭代穩(wěn)定次數(shù)和程序運行時間上分別比文獻［12］算法減少了50.0%和21.1%。綜合來看，本文算法在30×30 的柵格地圖中具有更好的計算結(jié)果，各方面性能更優(yōu)，克服了傳統(tǒng)路徑平滑方法的不足。

由兩次不同規(guī)模的柵格實驗可以看出，環(huán)境變復(fù)雜時，本文算法仍有良好的適應(yīng)性并且優(yōu)勢更加明顯，可以尋得一條綜合性能更優(yōu)的路徑。

5.3 大規(guī)模柵格環(huán)境

5.3.1 100×100柵格環(huán)境

為了進一步驗證本文改進算法在規(guī)模較大的柵格地圖中的適應(yīng)性，首先建立100×100 規(guī)模的柵格地圖，將文獻［25］的改進A*算法、文獻［26］的改進RRT（Rapidly-exploring Random Tree）算法以及本文算法在該規(guī)模的地圖中進行仿真，此處實驗各相關(guān)參數(shù)取值為：m=100，α=1，β=7，其余按表1 取值。三種算法的路徑規(guī)劃如圖12所示。

圖12 在100×100地圖上三種算法規(guī)劃的路徑Fig.12 Paths planned by three algorithms on 100×100 map

由圖12可以直觀地看出，相較于改進的A*算法以及RRT算法，本文算法生成的路徑擁有更少的轉(zhuǎn)彎次數(shù)，三種算法的具體仿真結(jié)果如表4所示

表4 在100×100地圖上的仿真結(jié)果Tab.4 Simulation results on 100×100 map

由表4 可以看出，改進A*算法和改進RRT 算法在路徑長度上相差很小，本文算法規(guī)劃的路徑長度上更優(yōu)；同時，在轉(zhuǎn)彎次數(shù)上，本文算法表現(xiàn)更好，規(guī)劃出的路徑最為平滑；本文規(guī)劃路徑的累計轉(zhuǎn)彎角度較前兩種算法分別減少了19.9%和37.6%；但在程序運行時間上，表現(xiàn)得不如改進A*算法優(yōu)異。綜合來看，本文算法在100×100 規(guī)模的柵格地圖中仍具有良好的適應(yīng)性，規(guī)劃路徑的長度和轉(zhuǎn)角次數(shù)是最優(yōu)的。

5.3.2 200×200柵格環(huán)境

將柵格規(guī)模再次擴大為200×200，此處將文獻［27］的改進蟻群算法作為本文算法的對比算法。將兩者在柵格地圖中進行仿真分析，兩種算法的路徑規(guī)劃如圖13所示。

圖13 在200×200地圖上兩種算法規(guī)劃的路徑Fig.13 Paths planned by two algorithms on 200×200 map

由圖13 可知，兩種算法在大規(guī)模的復(fù)雜環(huán)境中均能從起點順利抵達終點，與文獻［27］算法相比，本文算法規(guī)劃出的路徑更加平滑，轉(zhuǎn)彎次數(shù)更少，具體實驗結(jié)果如表5所示。

表5 在200×200地圖上的仿真結(jié)果Tab.5 Simulation results on 200×200 map

由表5 可知，本文算法在運行時間上稍遜于文獻［27］算法，但在路徑長度、轉(zhuǎn)彎次數(shù)以及累計轉(zhuǎn)彎角度上都更占優(yōu)勢，分別較文獻［27］算法降低了6.7%、55.6%和65.8%。

由以上實驗結(jié)果，驗證了本文改進蟻群算法在復(fù)雜地形環(huán)境中進行路徑規(guī)劃的可行性和有效性。

6 結(jié)語

本文針對基本蟻群算法在移動機器人路徑規(guī)劃應(yīng)用上存在的缺陷，提出了基于轉(zhuǎn)彎角度約束的改進蟻群算法。規(guī)劃不同柵格的初始信息素值，在啟發(fā)函數(shù)中有效融合了A*算法的尋路能力，以路徑長度和轉(zhuǎn)彎角度兩因素為下一步柵格的選擇指標(biāo)，使路徑更加平滑，并且在信息素更新中引入了狼群算法的分配原則，同時限制最大最小信息素的值。本文改進之后的算法使螞蟻能在更短的時間內(nèi)尋得一條綜合路徑長度和轉(zhuǎn)角次數(shù)的最優(yōu)路徑，降低了移動機器人的能耗損失，延長壽命，使其能高效、安全地移動到目標(biāo)點，驗證了本文算法在復(fù)雜環(huán)境中的有效性和適應(yīng)性。

在今后的研究中，將進一步研究蟻群算法參數(shù)的取值問題，利用神經(jīng)網(wǎng)絡(luò)計算出使路徑更優(yōu)的參數(shù)取值，將大大節(jié)約調(diào)試時間，使算法更加智能化。