陳勁峰 黃衛(wèi)華 王 肖 章 政

(武漢科技大學信息科學與工程學院 武漢 430081) (智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室 武漢 430081)

0 引 言

移動機器人路徑規(guī)劃是機器人研究領(lǐng)域中的一個重要分支和研究熱點，它指的是按照一定參考指標，機器人在具有障礙物的環(huán)境中尋找一條從起點到目標點最優(yōu)或次優(yōu)的無碰撞路徑[1]。傳統(tǒng)的路徑規(guī)劃方法有柵格法[2]、人工勢場法[3]、可視圖法[4]、快速探索隨機樹法[5]等。然而對于一些復雜環(huán)境，如震后救援、野外運輸?shù)?，搜索區(qū)域空間大，且障礙物的分布不規(guī)則，傳統(tǒng)路徑規(guī)劃算法存在尋優(yōu)效率低等問題。近年來，一些具有啟發(fā)性智能算法應(yīng)用于移動機器人路徑規(guī)劃中，其中蟻群算法[6]已得到較為廣泛的應(yīng)用。

蟻群算法是一種自組織算法，具有較強的魯棒性，優(yōu)良的并行分布式計算能力、易于與其他算法結(jié)合等優(yōu)點。然而，蟻群算法存在初期信息素匱乏、收斂速度慢、易陷入局部最優(yōu)解等問題[7]，眾多學者展開了一系列的改進工作。文獻[8]提出了將信息素與啟發(fā)信息兩者的權(quán)重參數(shù)互鎖，改進啟發(fā)信息，提高了搜索速度，避免算法陷入局部最優(yōu)。文獻[9]和文獻[10]主要提出了螞蟻雙向搜索策略，并輔之信息素更新等方法，提高了避障能力且加快了算法收斂速度。文獻[11]將貪婪交叉算子應(yīng)用于每次迭代結(jié)束時的輪盤賭中，以實現(xiàn)交叉操作，加快了求解最優(yōu)解的速度。文獻[12]使用刺激概率與無限步長的啟發(fā)信息，改進信息素揮發(fā)率，加快了算法的收斂速度。文獻[13]通過設(shè)置初始信息素，以及信息素揮發(fā)機制，調(diào)整自適應(yīng)路徑長度等策略提高了算法找最優(yōu)解的收斂速度。文獻[14]改進信息素更新機制和信息素平滑機制，豐富了解的多樣性且提高了收斂速度。

上述算法，通過改進信息權(quán)重參數(shù)，信息素揮發(fā)與更新機制以及搜索模式有效地提高了全局搜索的收斂速度，但存在一些問題有待于進一步研究，如：(1)當?shù)貓D中存在多達7個方向的鄰節(jié)點時，路徑判斷過程復雜會導致降低算法運算速度，同時引起步數(shù)冗余；(2)啟發(fā)信息缺乏緊密地對螞蟻的引導性與對環(huán)境的適應(yīng)性；(3)給予初始信息素總量恒定容易導致路徑信息素過度積累，使機器人尋優(yōu)陷入局部最優(yōu)。

鑒于此，本文設(shè)計了一種改進的蟻群算法，并用于解決復雜環(huán)境下的移動機器人路徑規(guī)劃問題。首先，通過精簡可選孫節(jié)點策略，縮小傳統(tǒng)蟻群算搜索節(jié)點的范圍，同時實現(xiàn)減小算法復雜度；其次，將環(huán)境規(guī)模尺寸與目標點引入到啟發(fā)函數(shù)，使得螞蟻搜索具有明確的方向性，并且適應(yīng)不同環(huán)境規(guī)模；然后，設(shè)置每代信息素總量按高斯函數(shù)下降趨勢自適應(yīng)給予機制。最后，建立了移動機器人路徑規(guī)劃的復雜環(huán)境模型，將本文設(shè)計的改進蟻群算法應(yīng)用于路徑規(guī)劃中，仿真結(jié)果證明了本文算法的有效性。

1 問題描述及環(huán)境建模

本文中機器人工作環(huán)境為復雜的靜態(tài)2維空間，在全局路徑規(guī)劃中，設(shè)工作環(huán)境為n×n的柵格環(huán)境，黑色柵格用1表示障礙物，白色柵格用0表示自由可行區(qū)，不滿一個柵格的障礙物仍按照一個柵格處理。柵格序號按自上向下、從左到右的順序編為1，2，3，…，N。以柵格圖左下角為坐標原點，橫軸以從左至右為x軸正方向，縱軸以自下向上為y軸正方向，每個柵格長度取為單位長度，每一個柵格記為一個節(jié)點，建立的環(huán)境模型如圖1所示。

圖1 柵格環(huán)境模型

設(shè)柵格序號為Dx，n為每行每列的柵格數(shù)，則柵格序號與直角坐標的轉(zhuǎn)換關(guān)系為

(1)

式(1)中，MOD(Dx,n)表示Dx/n的取余函數(shù)；CEIL(Dx/n)表示求取大于或者等于Dx/n的最小整數(shù)函數(shù)。提取柵格環(huán)境二值信息(0或1)得到對應(yīng)矩陣G(n,n)，設(shè)mr表示矩陣的行，mc表示矩陣的列，則柵格序號與矩陣坐標轉(zhuǎn)換關(guān)系為

(2)

2 基于改進蟻群算法的路徑規(guī)劃

本文改進的蟻群算法主要分為3個部分：(1)根據(jù)螞蟻已走的兩步節(jié)點，確定性分析出將運動下一節(jié)點最小的選擇區(qū)域；(2)采用既符合環(huán)境規(guī)模大小又具有目標點的指引性的啟發(fā)函數(shù)對螞蟻進行引導；(3)將初始給定信息素總量Q隨迭代次數(shù)的增加，按照高斯函數(shù)下降部分依次遞減分配。

2.1 路徑精簡策略的選擇

一般而言，在傳統(tǒng)蟻群算法的鄰節(jié)點選擇中，當前節(jié)點在鄰節(jié)點不含有障礙物前提下，除去已走過的上一節(jié)點外，對于將選擇的下一節(jié)點有7個方向需要判斷，很大程度上降低了螞蟻搜索效率，導致步數(shù)冗余，造成搜索路徑加長。鑒于此，提出一種精簡螞蟻下一步可行區(qū)域的策略。以圖2所示的孫節(jié)點選擇方向為例說明路徑精簡策略，策略如下。

針對一條路徑中順序相連的節(jié)點D、F和節(jié)點G，按照螞蟻經(jīng)過節(jié)點D、F和G的順序，若先經(jīng)過節(jié)點D，其次經(jīng)過節(jié)點F，再經(jīng)過節(jié)點G，則將D記為父節(jié)點，F(xiàn)記為子節(jié)點，G記為孫節(jié)點，同時規(guī)定節(jié)點G不屬于節(jié)點D的鄰接點。其示意如圖2所示。

針對柵格模型中，螞蟻單步運動行走方式：直線和斜線，分別由圖2(a)與圖2(b)的路徑“父→子”所示。針對圖2(a)所示可選的3個孫節(jié)點，由移動機器人路徑規(guī)劃定義有，假定每一只螞蟻由父節(jié)點到子節(jié)點這一搜索路徑是并且就是所尋找的最優(yōu)路徑，也即當前子節(jié)點為父節(jié)點到達目標點的必經(jīng)節(jié)點，即子節(jié)點已定，那么由父節(jié)點到當前子節(jié)點，有5條可選路徑，如圖3(a)所示，分別為：①父→a→子；②父→b→子；③父→子；④父→c→子；⑤父→d→子。

圖2 孫節(jié)點選擇方向

圖3 父子節(jié)點走向圖

分析如下，經(jīng)比較，從起點到目標點，③父→子這一路徑長度最短，且無拐角，故路徑中如果出現(xiàn)了路徑③，那么路徑①②④⑤則不會出現(xiàn)在該次搜索路徑中，否則搜索路徑將會冗余曲折，不符合最短路徑要求?；谏鲜龇治?，路徑精簡策略是除了將父節(jié)點加入禁忌表中，同時如圖3(a)將父節(jié)點的相鄰節(jié)點a、b、c和d不納入孫節(jié)點可選范圍，進行屏蔽處理。因此根據(jù)父節(jié)點到子節(jié)點這一既定直線運動趨勢，可選孫節(jié)點有3個，如圖2(a)所示孫1、孫2和孫3。同理針對螞蟻走斜線的情形，可得到有效孫節(jié)點范圍如圖2(b)所示，孫1、孫2、孫3、孫4和孫5共5個節(jié)點。

由上述分析可知，通過使用對下一可選節(jié)點的精簡策略相對原始搜索需要判斷鄰近多達7個節(jié)點的模式，變?yōu)楫敻概c子節(jié)點路徑呈直線時，孫節(jié)點的可走路徑如圖2(a)有①子→孫1、②子→孫2、③子→孫3，只需判斷處理3個節(jié)點；呈斜線時孫節(jié)點的可走路徑如圖2(b)有①子→孫1、②子→孫2、③子→孫3、④子→孫4、⑤子→孫5，只需判斷處理5個節(jié)點。走直線和斜線處理的共同點是當父節(jié)點和子節(jié)點已定，孫節(jié)點的選擇區(qū)域是在子節(jié)點的鄰節(jié)點中，除去父節(jié)點與子節(jié)點共有鄰節(jié)點而余下的節(jié)點。2種運動方式中的節(jié)點處理數(shù)均小于7個，有利于提高搜索效率，降低搜索盲目性，同時降低計算代價。

邊界特殊孫節(jié)點的處理。針對上述精簡下一節(jié)點的策略，為避免螞蟻因根據(jù)圖2(a)中尋找孫節(jié)點的搜索模式運動到環(huán)境邊界節(jié)點，出現(xiàn)如圖4(a)中所示的困境，也即當父→子節(jié)點已定，子節(jié)點的上下鄰節(jié)點被屏蔽而其右邊無孫節(jié)點可選，導致出現(xiàn)此螞蟻由于路徑精簡策略的局限性而鎖死，提出取消搜索局部屏蔽機制，提高螞蟻的存活率，處理方式為開放其偽孫節(jié)點，如圖4(b)所示，取消算法對子節(jié)點的上下鄰節(jié)點的屏蔽；同理，針對當螞蟻若走斜線到達環(huán)境角落如圖4(c)無孫節(jié)點可選的情形時，同樣對其開放偽孫節(jié)點，如圖4(d)所示。

圖4 邊界孫節(jié)點

2.2 啟發(fā)函數(shù)與概率函數(shù)選擇

基本蟻群算法在搜索過程中具有搜索時間長，存在搜索指向不明確的缺陷。蟻群算法作為啟發(fā)型算法中的一種，啟發(fā)函數(shù)質(zhì)量的優(yōu)劣，對算法的應(yīng)用效果具有較大影響，但是傳統(tǒng)蟻群算法的啟發(fā)函數(shù)1/dij，其中dij表示相鄰節(jié)點之間的距離，對環(huán)境的能見度較低，且不具有目標點的引導作用，導致搜索盲目性。針對此問題，提出一種不受環(huán)境規(guī)模大小影響的具有引導機制性啟發(fā)函數(shù)，如式(3)所示：

(3)

式(3)中，Jk表示螞蟻k在一條路徑上鄰近可選下一節(jié)點的集合，n為環(huán)境柵格的行列數(shù)；DijE表示節(jié)點i、j以及目標點依次連接的距離之和。當子節(jié)點到孫節(jié)點以及目標點的距離越短，其引導性越強。

以螞蟻第一步出發(fā)并無既定的父子節(jié)點位置關(guān)系作為指引，本文設(shè)計了聯(lián)合概率函數(shù)，如式(4)和式(5)所示：

(4)

式(4)中，τij(t)為t時刻在邊ij上的信息素積累，?為信息素權(quán)重參數(shù)，?越大表明螞蟻越傾向選擇過往螞蟻走過的路徑；ηij(t)表示t時刻從節(jié)點i轉(zhuǎn)移到節(jié)點j的啟發(fā)信息，β為啟發(fā)信息權(quán)重參數(shù)，其值越大，表明螞蟻越傾向走距離目標點更近的節(jié)點。

(5)

式(5)中，Ns表示起始點的相鄰有效節(jié)點個數(shù)，step表示螞蟻k在一條路徑上累計搜索的節(jié)點個數(shù)；當step=1時，使用等概率搜索，一方面有利于從起點擴大全局搜索范圍，同時可解決螞蟻第一步出發(fā)無既定的父子節(jié)點位置關(guān)系作為指引的限制。

2.3 自適應(yīng)信息素總量給予機制

在基本蟻群算法中，信息素總量是一個定值，極大可能性存在隨著迭代次數(shù)的增加，后期路徑上的信息素濃度易積累過高導致螞蟻一定程度上失去搜索優(yōu)質(zhì)解能力而陷入局部最優(yōu)解，針對此問題，提出將信息素的總量根據(jù)迭代次數(shù)遞增而按照高斯函數(shù)模型下降部分逐步降低的給予機制。

在一次迭代完成后，針對到達目標點的螞蟻，將路徑上的信息素進行更新，可得：

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1)

(6)

式(6)中，ρ為信息素揮發(fā)系數(shù)，其中0<ρ<1，Δτij(t,t+1)表示t+1時刻所有經(jīng)過邊ij之間的螞蟻殘留信息素增量，可得：

(7)

Δτij表示第k只螞蟻經(jīng)過邊ij殘留的信息素，可得：

(8)

式(8)中，Q為信息素常量，Lk為螞蟻k在本次搜索中的路徑長度。其中信息素總量Q的給予機制設(shè)計為

(9)

式(9)中，G為算法的迭代次數(shù)，設(shè)定μ=0對應(yīng)信息素總量Q的峰值，保證從第一代直至最后一代Q(G)呈下降趨勢；取σ=35，使得信息素總量符合正態(tài)分布的3σ法則，也即保證最后一代給予的總信息素量近乎為最低值。

3 改進蟻群算法流程

將所設(shè)計的改進蟻群算法用于路徑規(guī)劃中，算法流程如下。

步驟1參數(shù)初始化。將具有多個障礙物的地圖柵格化，并計算任意兩節(jié)點之間距離，取障礙柵格到其他柵格距離為無窮大，表示不可達；設(shè)定節(jié)點之間初始信息素，迭代次數(shù)K，螞蟻種群個數(shù)M，起始點S，目標點E，信息素權(quán)重系數(shù)α，啟發(fā)信息權(quán)重系數(shù)β和揮發(fā)系數(shù)ρ，以及信息素總量Q。

步驟2路徑選擇。利用式(5)計算螞蟻下一節(jié)點的選擇概率，然后采用輪盤賭選出下一節(jié)點，判斷是否滿足到達目標點或可選孫節(jié)點數(shù)小于1的條件，不滿足則轉(zhuǎn)至步驟3，滿足轉(zhuǎn)至步驟4。

步驟3狀態(tài)更新。將步驟2選出的子節(jié)點同時加入路徑列表和禁忌表，計算當前路徑總距離，并根據(jù)父節(jié)點和子節(jié)點的位置關(guān)系，推導出可選孫節(jié)點范圍，返回步驟2。

步驟4螞蟻序號更新。針對沒到達目標點且可選孫節(jié)點個數(shù)小于1的螞蟻路徑長度記為無窮大；m=m+1，計算下一只螞蟻的搜索路徑，返回步驟2；當前螞蟻序號m等于種群總數(shù)M時，轉(zhuǎn)至步驟5。

步驟5信息素更新。將完成一次迭代的所有螞蟻按式(6)的信息素更新函數(shù)進行路徑上的信息素更新。

步驟6螞蟻迭代次數(shù)更新。迭代次數(shù)k=k+1，返回步驟2；當?shù)螖?shù)滿足設(shè)定迭代次數(shù)時，結(jié)束算法。記錄歷史最優(yōu)路徑，繪制出每代平均距離曲線與算法收斂曲線。

4 仿真實驗與分析

在不同規(guī)模的復雜環(huán)境下，驗證本文設(shè)計的改進蟻群算法并用于移動機器人的路徑規(guī)劃，基于柵格法建立如圖5(a)和圖6(a)所示的環(huán)境地圖，環(huán)境1和環(huán)境2分別為20×20與30×30的柵格地圖。地圖中，一部分障礙物呈現(xiàn)凹陷狀，另一部分障礙物設(shè)置成無次序且無規(guī)則的近似隨機分布狀態(tài)，設(shè)置機器人起始點為柵格模型的左上角，目標點為右下角。

4.1 環(huán)境1實驗結(jié)果分析

在20×20的柵格環(huán)境1中，傳統(tǒng)蟻群算法與本文改進蟻群算法最短路徑如圖5(a)所示，每代最小路徑與平均路徑距離分別如圖5(b)和圖5(c)所示。對比搜索路徑，傳統(tǒng)蟻群算法在搜索時缺乏目標點的引導作用，導致搜索盲目，同時算法后期路徑上信息素積累過高，螞蟻更多地選擇已走路徑，從而出現(xiàn)圖5(a)虛線所示路徑上的第4個不必要的拐點；而本文算法在使用精簡下一節(jié)點的可選范圍策略上，首先就避免了路徑直角折點的出現(xiàn)，在實際情形下實現(xiàn)降低移動機器人消耗的能量，其次引入具有啟發(fā)性的啟發(fā)函數(shù)，自適應(yīng)遞減信息素總量，因此路徑無多余曲折的拐點。

對比收斂曲線，如圖5(b)所示，在傳統(tǒng)蟻群算法中由于沒有目標點的引導作用，在前60代搜索中只有4代搜索到了最短路徑，直至接近第90代平均路徑與最短路徑才最終匯合，歸結(jié)于傳統(tǒng)蟻群算法的初期信息素匱乏，導致收斂速度慢；而本文算法中螞蟻搜索存在目標點的引導作用，以高斯函數(shù)下降部分按迭代次數(shù)遞減信息素總量避免信息素積累的基礎(chǔ)上，不僅在第13代就能找到最短路徑，而且在圖5(c)可以看出平均路徑距離開始逐步降低且趨于穩(wěn)定，由于信息素的自適應(yīng)給予機制使得全體螞蟻搜索路徑收斂很快。

(a) 傳統(tǒng)蟻群算法與本文算法最優(yōu)路徑圖

(b) 傳統(tǒng)蟻群算法與本文算法路徑最小曲線

(c) 傳統(tǒng)蟻群算法與本文算法路徑平均距離曲線圖5 環(huán)境1中實驗結(jié)果比較

4.2 環(huán)境2實驗結(jié)果分析

在環(huán)境2中，傳統(tǒng)蟻群算法與本文算法最短路徑實驗結(jié)果如圖6(a)所示，最小路徑距離和平均距離曲線圖分別如圖6(b)和圖6(c)所示。柵格環(huán)境中設(shè)置了更多凹陷區(qū)，對于基本蟻群算法結(jié)果而言，其路徑由于沒有目標點的引導作用，同時由于路徑信息素的積累作用，導致后期信息素過高，后期螞蟻選擇前期螞蟻走過的路徑，出現(xiàn)了3個多余的拐點，如圖6(a)曲線直角所示，在實際搜索中增加了能量損耗，而本文算法由于設(shè)置了自適應(yīng)信息素總量給予機制，避免了路徑上的信息素過度積累，在以找到最短路徑為目標時，只出現(xiàn)了不可避免最少的拐點數(shù)。

(a) 傳統(tǒng)蟻群算法與本文算法最優(yōu)路徑圖

(b) 傳統(tǒng)蟻群算法與本文算法路徑最小曲線

(c) 傳統(tǒng)蟻群算法與本文算法路徑平均距離曲線圖6 環(huán)境2中實驗結(jié)果比較

在最小路徑圖6(b)中，與環(huán)境1類似，由于具有目標點對螞蟻的緊密引導作用，本文算法在找到最短路徑的代數(shù)遠遠早于傳統(tǒng)蟻群算法找到最短路徑的代數(shù)；鑒于采用了精簡可選節(jié)點策略，實現(xiàn)降低搜索范圍，使得螞蟻搜索路徑集中，本文算法平均路徑不僅下降速度比傳統(tǒng)蟻群算法快，而且距離更短。

本文實驗參數(shù)設(shè)置如表1所示，針對實驗參數(shù)的取值，本文在計算下一節(jié)點概率函數(shù)中取消信息素項，然后依舊以輪盤賭的方式選擇下一節(jié)點做測試。結(jié)果顯示，平均曲線與最小曲線均呈現(xiàn)雜亂無序狀況，即表明假使缺失信息素項的作用，算法將失效，表明了信息素項在所取該值的情況下，發(fā)揮了其在蟻群算法中使蟻群相互協(xié)作的作用，同時表明了所取值的合理性。

表1 本文實驗參數(shù)設(shè)置

本文算法與傳統(tǒng)蟻群算法在環(huán)境1與環(huán)境2的實驗結(jié)果分別如表2和表3所示。

表2 環(huán)境1實驗結(jié)果

表3 環(huán)境2實驗結(jié)果

由表2以及表3知，采用相同的螞蟻群體個數(shù)和迭代次數(shù)，本文算法與傳統(tǒng)蟻群算法在2種環(huán)境的路徑規(guī)劃比較中，本文算法獲得路徑距離更短，收斂代數(shù)更早，拐點數(shù)目更少，最優(yōu)路徑上總的拐角度數(shù)之和更小，即路徑更為平滑，對于實際機器人有利于降低能量與時間消耗。綜合而言，改進算法比傳統(tǒng)蟻群算法在復雜環(huán)境中更加體現(xiàn)出其優(yōu)越性，具有更快的搜索速度及路徑平滑度。

5 結(jié) 論

本文針對傳統(tǒng)蟻群算法在移動機器人路徑規(guī)劃時出現(xiàn)初期信息素缺乏、易陷入局部最優(yōu)、收斂速度慢等問題，對可選轉(zhuǎn)移節(jié)點進一步優(yōu)化，使用精簡可選節(jié)點策略，實現(xiàn)降低了盲目搜索性，降低了計算代價；在此基礎(chǔ)上，設(shè)計符合環(huán)境變化的啟發(fā)函數(shù)，將目標點引入其中，增強對螞蟻搜索的引導作用；最后，為了加強后期螞蟻受前期螞蟻在路徑上殘留信息素的影響，同時為了避免搜索后期信息素過度積累，引入符合高斯函數(shù)模型隨迭代次數(shù)而遞減的自適應(yīng)總信息素給予機制。仿真實驗表明，與傳統(tǒng)蟻群算法相比，在獲得路徑質(zhì)量更優(yōu)的前提下，本文算法所規(guī)劃的路徑更短、更平滑，具有更快的收斂速度，證實了本文算法在不同復雜環(huán)境中作為移動機器人路徑規(guī)劃算法的有效性與優(yōu)越性。