基于改進蟻群算法的移動機器人路徑規劃

周敬東， 高偉周， 楊文廣， 戚得眾， 周天

(1.湖北工業大學機械工程學院， 武漢 430068； 2.湖北工業大學農機工程研究設計院， 武漢 430068； 3.武漢沐沃霖科技發展有限公司， 武漢 430068)

隨著機器人技術的迅速發展，移動機器人受到各領域廣泛的應用。路徑規劃作為機器人行走的重要部分[1-2]。迄今為止，中外研究人員對移動機器人的路徑規劃算法開展了大量的研究[3]，如遺傳算法[4]、神經網絡算法[5]、粒子群算法[6]、蟻群算法[7]、A*算法[8]以及Dijkstrta算法[9]等各類算法。由于蟻群算法的魯棒性強和自組織性好，并且是一種并行算法，被廣泛應用在機器人路徑規劃問題[10]。

針對蟻群算法出現的收斂速度慢、易發生死鎖等不足，許多研究人員提出了大量的解決對策。袁福龍等[10]通過構造數學模型、引入區域安全信息函數和轉角啟發信息函數等策略，采用“狼群分配策略”方法避免陷入局部最優和加快最優路徑的收斂，能夠有效避開靜態和動態環境中的障礙物而迅速找到一條較平滑的最優路徑。曹新亮等[11]通過在柵格地圖中劃出優選區域對初始信息素濃度差異化設置，盡管建立新的數學模型能有效地加快算法前期搜索的速度和減少了最優迭代次數，但是算法建立復雜的數學模型以及選取比值節點會很大地增加了算法的運算量和運行時間。史恩秀等[12]針對蟻群算法中的啟發因子α等主要參數對路徑規劃效率的影響進行了仿真實驗分析，綜合考慮找到了改進蟻群算法最佳匹配參數。牛龍輝等[13]通過引入自適應信息素揮發系數方法解決中尋優能力不足和算法多樣性低等問題，以加強全局尋優能力，提高了算法多樣性。以上學者在蟻群算法理論方面做了研究改進，對算法做了優化，具有一定的適用性，但對機器人實際運行效果研究較少，依然需要進行優化算法，提高改進蟻群算法的實用性。

為了優化路徑規劃，在已有的研究基礎上，提出一種新的蟻群算法，改變原有的初始信息素分配方式為階梯分配，融合A*算法作為路徑搜索的啟發式信息改進啟發函數，加強最優解對螞蟻的吸引力,設置蟻群回退策略，避免蟻群陷入“陷阱”后無法退回，引入螞蟻優化排序，使算法路徑規劃更短、迭代次數更少的理想效果。通過MATLAB 軟件仿真和使用樹莓派六足機器人實驗，期望改進后的蟻群算法在路徑長度、迭代次數和轉折點數等方面性能優越于傳統蟻群算法。

1 蟻群算法

1.1 基本蟻群算法

蟻群算法是由一種基于種群的啟發式隨機搜索算法[14]。蟻群在覓食的過程中，起點從蟻巢位置，食物位置為終點，通過多次搜索行走路徑，在已走的路徑上留下信息素[15]，避開障礙物選擇最佳路徑行走。蟻群覓食過程如圖1所示。

圖1 蟻群覓食過程Fig.1 Ant colony foraging process

1.2 改進的蟻群算法

1.2.1 初始化信息素濃度的改變

傳統蟻群算法初始化信息素濃度是采取均勻分配在各個柵格的方式，這樣會降低螞蟻的搜索效率。蟻群在行走路徑的過程中，每只螞蟻是從起點出發搜索選擇最短路徑到達終點。為了避免蟻群在尋優路徑中出現“原地不動”現象，通過設置信息素軌跡量在[τmin,τmax]這個區間，合理安排路徑上的軌跡量，有利于避免初期盲目搜索的行為。故在設定信息素濃度矩陣Tau時，在起點與終點的最短路徑以及周圍路勁信息素值按照逐漸遞減方式設定。這樣可以有利于蟻群在初期對最優路徑方向搜索，有效地提高了收斂速度。

1.2.2 啟發函數的改進

傳統蟻群算法中啟發函數ηij(t)=1/dij(其中dij為柵格節點i,j之間的距離)表明螞蟻從節點i行走至柵格j的期望程度與節點之間的距離相關聯，在運行過程中，出現迭代次數過少且無法找到最優路徑，算法耗時比較長，導致收斂速度較慢[16]。針對此缺陷對啟發函數進行改進，融合A*算法作為路徑搜索的啟發式信息，從而獲得較好的路徑。已知A*算法的評價函數表達式為

f(n)=g(n)+h(n)

(1)

式(1)中：f(n)為由起始點到達結束點的總代價值；g(n)為f(n)的前一部分代價，即起始點到當前點的代價；h(n)為f(n)的后一部分代價，即當前點到結束點的代價。

改進后啟發算子ηij(t)為

(2)

改進后的啟發函數提高了算法的有效性，提高了算法的尋優能力，大大減少了算法收斂時間，使蟻群朝著最優路徑方向快速搜索前進。

1.2.3 蟻群回退策略的設置

為了避免蟻群在行走的過程中陷入H形、U形等障礙后沒有選擇的地步，采用螞蟻回退策略來應對。通過加進螞蟻回退策略，使螞蟻進入“陷阱”后，有能力擺脫困境，發揮螞蟻的搜索作用，完成搜索任務。圖2為U形障礙物的柵格地圖，當一只螞蟻到達N10位置時,這只螞蟻無法前進，此時被迫需要退回N7位置，同時要更新禁忌表記錄的螞蟻k當前已走過的位tabuk中的數據，刪除N10位置信息，然后在選取合適路徑行走，假如這只螞蟻仍然無法前進，則選擇繼續回退，這只螞蟻仍需從tabuk中刪除N7位置信息，螞蟻回退到N3位置，重新選擇前進路徑。

蟻群回退策略的設置，使螞蟻在前進搜索過程中擺脫“陷阱”困境，充分發揮每只螞蟻的搜索作用，大大增強了算法的健壯性以及蟻群對環境的適應能力。

黑色陰影柵格為障礙物；帶數字柵格為螞蟻可通行區域(無障礙)， 其中數字表示位置順序，如“1”表示N1圖2 U形障礙物的柵Fig.2 Grid map of U-shaped obstacle

1.2.4 優化排序的引入

為了加快蟻群找到最優解速度，在每次蟻群完成行走路徑后，標記信息素最優解[17]。每只螞蟻完成路徑搜索后，螞蟻行走的路徑長度不同。在修改信息素路徑前，按照螞蟻的長度由短到長進行排序L1≤L2≤…≤Lm，每只螞蟻釋放的信息素量和排名相乘。已知在每次循環中，只有排名前h-1位的螞蟻和精英螞蟻才允許在行走路徑上釋放信息素[18]。已知的最優路徑給以最強的反饋，和系數h相乘，排名第k位的螞蟻則乘系數h-k。則信息素表達式為

(3)

(4)

(5)

式(5)中：Lbs為已知最優路徑Tbs的長度。

2 算法運行流程

2.1 環境建模

環境建模有柵格地圖法和數字序列法等方法，使用柵格法建立移動機器人的環境模型[19]。柵格法采用“0”“1”表示柵格地圖中有無障礙，0表示此處無障礙物，機器人可以自由通過，1表示此處有障礙，機器人無法通過。設置移動機器人的移動范圍為20×20大小的柵格方形，單位長度為1，如圖3所示。

S為起始點；E為目標點圖3 20×20柵格地圖Fig.3 20×20 grid map

機器人前進必須占用柵格，考慮到移動機器人在真實環境下會有很多方向可供選擇，為了簡化移動方向，規定機器人停在每個活動區域的中心點為準，每一步移動可供參考的方向只有8種，分別為左前、左后、右前、右后4個斜方向和前后左右4個直行方向。機器人的移動方向，如圖4所示。

圖4 機器人移動方向Fig.4 Direction of robot movement

2.2 算法執行步驟

蟻群算法應用于機器人路徑規劃時主要由初始化、解構建和信息素更新三部分組成[15,20-21]。參數初始化主要對時間、循環次數、信息素、迭代次數等參數設置初始值。螞蟻根據狀態轉移概率公式計算出的概率選擇元素j并前進，最終完成搜索路徑到達目標點[21]。通過不斷修改禁忌表指針和更新每條路徑上的信息量方法，找到一條最優行走路徑。蟻群算法的執行步驟流程圖，如圖5所示。

圖5 蟻群算法的執行步驟流程圖Fig.5 Flow chart of the execution steps of ant colony algorithm

(6)

式(6)中：Jk={1,2,…,n}-tabuk為螞蟻k在下一步可以選擇的位置集合，其中tabuk為禁忌表記錄的螞蟻k當前已走過的位置；ηij為一個啟發因子，表示螞蟻從位置i轉移到位置j的期望程度；α為信息素的相對重要程度；β為期望啟發因子的相對重要程度；τij為柵格節點i,j之間的信息素濃度；τis為位置點i到初始點的信息素濃度；ηis為位置點i到初始點的啟發函數。

在所有螞蟻完成一次從起點到終點后，各路徑信息素開始更新，信息素更新公式為[18]

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

(7)

式(7)中：ρ為路徑上信息素的蒸發系數，0<ρ<1；1-ρ為信息素的持久性系數；Δτij為本次迭代中邊ij上信息素的增量。

Δτij可表示為[18]

(8)

(9)

式(9)中：Q為正常數；Lk為第k只螞蟻在本次迭代中所走過路徑的長度。

3 仿真與評價

為了驗證算法優化后的效果，在MATLAB 2016a上對改進蟻群算法進行多次仿真，與傳統蟻群算法作對比分析。利用已建成20x20的柵格地圖運行程序，設定機器人初始坐標為(0.5，19.5)，終點坐標為(19.5，0.5)。程序仿真參數設置如表1所示。

圖6、圖7分別為在傳統蟻群算法和改進蟻群算法仿真的路徑軌跡和迭代次數結果。

由圖6可知，傳統蟻群算法在初期無法確定搜索方向，盲目性大，迭代次數高達40次以上，最短路徑長度為32.5。

由圖7可知，改進蟻群算法的搜索效率較高，迭代次數少于40次，最短路徑長度只有29.2。分析表2數據可知：所提的改進蟻群算法在多方面評價參數優于傳統蟻群算法。

表1 參數設置

圖6 傳統蟻群算法Fig.6 Traditional ant colony algorithm

為驗證所提出的改進算法的先進性和有效性，通過創建帶有不同的障礙物柵格環境(20×20)，進行多次仿真驗證。表3為隨機選取6組在不同的障礙物柵格地圖環境對兩類蟻群算法仿真的結果。

通過對6組帶有不同的障礙物環境仿真結果分析可以得出，改進蟻群算法的迭代次數平均減少了30.24%，規劃出的路徑平均縮短了9.03%，運行時間平均減少了16.19%。仿真結果表明，改進蟻群算法的路徑規劃長度與傳統蟻群算法相比更短，迭代效率更高效，尤其在大尺寸地圖和障礙物多的情況下。

圖7 改進蟻群算法Fig.7 Improved ant colony algorithm

表2 蟻群算法改進前后仿真結果對比

表3 兩類蟻群算法仿真結果

4 實驗

為了驗證改進的蟻群算法仿真結果的正確性以及體現改進算法在實際應用中的實用性和有效性，采用樹莓派(SpiderPi)六足機器人為研究對象[20]。為了有效地對作業環境進行全局把控，本次實驗采用人工拍攝的方式提前將機器人的行走環境采集，達到全局監控的效果。樹莓派(SpiderPi)六足機器人，如圖8所示。

實驗環境如圖9所示，實驗場地為3 m×3 m的方形環境地圖。在實驗環境內，六足機器人處于起始位置，有各種障礙物分布，從起點爬行到終點。實驗環境處理后為邊長為15 cm、大小為20×20的柵格模型環境，如圖10所示。

設定六足機器人的起始位置為(0.5，19.5),終點位置為(19.5，0.5)。把改進后的蟻群算法和傳統蟻群算法分別應用在六足機器人的開發板中，讓機器人自主尋找路徑行走。在兩種蟻群算下行走的路徑軌跡如圖11、圖12所示。

圖8 SpiderPi六足機器人Fig.8 SpiderPi hexapod robot

圖9 實驗環境Fig.9 Lab environment

由表4可知，通過將兩類算法燒進六足機器人控制板中，改進蟻群算法程序在路徑長度、迭代次數和轉彎次數等方面性能優于傳統蟻群算法，證明了改進蟻群算法的優化效果，提高了算法的魯棒性和尋優能力。

圖10 處理后的環境Fig.10 Environment after treatment

圖11 改進蟻群算法應用Fig.11 Improved ant colony algorithm application

圖12 傳統蟻群算法應用Fig.12 Traditional ant colony algorithm application

表4 兩類算法的對比

5 結論

針對傳統蟻群算法在路徑規劃中表現出的收斂速度慢、初始化信息素少、全局規劃能力弱等缺點，提出了一種改進蟻群算法。得出如下結論。

(1)通過采用初始化信息素濃度的改變、啟發函數的改進、蟻群回退策略的設置、引入優化排序對傳統蟻群算法改進，有利于提高蟻群對最優路徑搜索效率，加快收斂速度。

(2)通過對改進的蟻群算法仿真與分析得出了改進的蟻群算法優化的效果優于傳統蟻群算法，尤其是在大尺寸地圖和障礙物多的情況下。

(3)通過對改進的蟻群算法應用在六足機器人中得到改進蟻群算法在路徑長度、迭代次數和轉彎點等方面性能優于傳統蟻群算法，證明了改進蟻群算法的優化效果，提高了算法的魯棒性和尋優能力。

所提的改進蟻群算法在傳統蟻群算法的基礎上針對初始化信息素濃度、蟻群回退策略等方面進行了優化，但在動態調整信息素揮發因子方面沒有深入考慮，在未來的算法優化中，可以引入更加智能化算法，使移動機器人的路徑規劃更有效。