柵格環(huán)境下基于開闊視野蟻群的機器人路徑規(guī)劃

劉智飛，劉冬冬

(中國石油大學(華東) 石油工業(yè)訓練中心， 山東 青島 266580)

近年來機器人在生產制造業(yè)、物流、醫(yī)療、服務業(yè)等多個行業(yè)得到了廣泛應用，不僅提高了生產效率，降低了生產成本，而且機器人可以代替人類從事勞力密集度高、危險、甚至人類無法完成的工作。路徑規(guī)劃技術是機器人的關鍵技術之一，是自主完成任務、實現智能化的前提，也極大地決定了機器人的工作效率[1]。因此，研究機器人路徑規(guī)劃問題對提高機器人工作效率、推動機器人廣泛應用具有重要意義。

路徑規(guī)劃的主要任務是在滿足設定約束的前提下，為機器人規(guī)劃一條安全的最優(yōu)路徑，所謂最優(yōu)路徑是設定優(yōu)化目標意義下的最優(yōu)路徑。根據環(huán)境信息的不同，路徑規(guī)劃可以劃分為全局路徑規(guī)劃和局部路徑規(guī)劃[2]。全局路徑規(guī)劃適用于靜態(tài)、已知的環(huán)境，這種情況下機器人可以獲得先驗地圖。局部路徑規(guī)劃適用于動態(tài)的、未知的環(huán)境，機器人只能依靠自身傳感器對周圍環(huán)境進行探測，并實時進行路徑規(guī)劃。路徑規(guī)劃的核心問題是規(guī)劃算法，路徑規(guī)劃方法可以分為傳統(tǒng)路徑規(guī)劃算法和仿生路徑規(guī)劃算法，傳統(tǒng)路徑規(guī)劃算法有人工勢場法[3]、A*算法[4]、柵格法[5]等，仿生的的路徑規(guī)劃算法包括遺傳算法、蟻群算法[6]、神經網絡算法等。裴躍翔等[7]提出了嵌入篩選操作的遺傳算法，一方面使用改進遺傳算法在優(yōu)化空間中細致搜索，另一方面使用標準遺傳算法進行大范圍開拓，將此算法應用于車身焊接路徑規(guī)劃中，得到了較好路徑。胡平志等[8]為了解決復雜山地中機器人遇到的坡度問題，將坡度約束作為啟發(fā)因素引入到蟻群算法中，得到了滿足機器人坡度約束的山地路徑。DAS等[9]提出了改進粒子群算法，同時將差分攝動速度算法融入到改進粒子群算法中，得到了適用于復雜環(huán)境的路徑規(guī)劃方法。由以上分析可知，在不同環(huán)境和應用背景下，具有不同的路徑規(guī)劃方法。在眾多規(guī)劃方法中，存在的共性問題是算法的規(guī)劃能力，通過對算法不斷改進而得到更加優(yōu)化的路徑是當前的研究熱點。

本文針對柵格環(huán)境下的路徑規(guī)劃問題，提出了具有開闊視野的蟻群算法規(guī)劃方法，對螞蟻視野、鄰域柵格、鄰域中的可選柵格進行了重新定義，將開闊視野蟻群算法應用于柵格環(huán)境下的機器人路徑規(guī)劃，有效減小了路徑長度并提高了路徑平滑性。

1 環(huán)境模型與算法分析

1.1 柵格環(huán)境模型

柵格環(huán)境是指使用固定尺寸的柵格將機器人工作環(huán)境進行劃分，機器人在行駛過程中以柵格為軌跡的基本單元。使用柵格分割完畢后，對柵格內的障礙物進行膨化處理，即當某柵格存在障礙物時，則障礙物膨脹而占滿整個柵格[10]。如圖1(a)為實際障礙物分布，膨化處理后如圖1(b)所示。

圖1 障礙物膨化示意圖

為了使機器人能夠識別障礙物柵格和可自由行駛柵格，本文對不同類型的柵格賦予不同的屬性值，將障礙物柵格的屬性賦值為1，將自由柵格的屬性賦值為0，從而得到機器人可以識別的0-1矩陣。以圖1所示柵格環(huán)境為例，其對應的0-1矩陣為：

使用蟻群算法在柵格環(huán)境下進行路徑規(guī)劃時，將螞蟻放置于起始柵格，螞蟻通過在鄰域自由柵格中不斷選擇，最終到達目標點。

1.2 標準蟻群算法

在標準蟻群算法中，螞蟻依據啟發(fā)信息和信息素濃度對鄰域內自由柵格進行選擇，螞蟻對自由柵格的選擇概率為[11]：

(1)

當蟻群算法完成一次迭代，則所有路徑進行一次信息素濃度的更新，信息素濃度更新包括信息素揮發(fā)和信息素殘留2個方面，即：

(2)

1.3 基于蟻群算法的路徑規(guī)劃分析

基于柵格地圖的路徑規(guī)劃方法中，由于柵格地圖的特點限制，主要存在4方向搜索和8方向搜索2種方法。其中4方向搜索主要指正上、正下、正左、正右4個方向的柵格，如圖2(a)所示。8方向搜索主要指正上、正下、正左、正右、左上、左下、右上、右下8個方向的柵格，如圖2(b)所示，圖中圓圈所在柵格為當前柵格。

圖2 不同的鄰域搜索方法

在圖2(a)所示的4方向搜索方法中，螞蟻的可選柵格為鄰域內的4個柵格，此時螞蟻的角度分辨率為90°；在圖2(b)所示的8方向搜索方法中，螞蟻的可選柵格為鄰域內的8個柵格，此時螞蟻的角度分辨率為45°。由以上分析可知，當前基于柵格環(huán)境的蟻群算法中，螞蟻的活動能力(即轉角分辨率)被限制在90°或者45°，這意味著螞蟻的活動能力受到了極大限制。

2 開闊視野蟻群算法

2.1 開闊視野設置方法及優(yōu)勢分析

為了提高螞蟻活動的機動能力，提出了柵格環(huán)境下具有開闊視野的蟻群算法。其核心思想為：將螞蟻的視野范圍擴大1倍，在這種設置方式下，螞蟻的鄰域柵格由之前的8柵格變?yōu)?4柵格，如圖3所示。圖中圓形所在柵格為當前柵格，實心圓點所在柵格為鄰域柵格。

圖3 不同視野螞蟻的鄰域柵格

螞蟻的視野范圍經過擴展以后，鄰域柵格數量上的增加可以帶來螞蟻機動能力的提高。如前文所述，在8方向搜索方式中，螞蟻運動的角度分辨率為45°；結合圖3(b)可知，具有開闊視野的螞蟻運動的角度分辨為22.5°，這意味著螞蟻運動的靈活性得到了明顯提高。

將開闊視野蟻群算法與傳統(tǒng)的4方向搜索、8方向搜索進行對比，更加能夠體現開闊視野蟻群算法的優(yōu)勢，以圖4所示的情況為例進行說明。圖4中S柵格為起點柵格，G柵格為目標柵格。

圖4 不同蟻群的運動路徑

對比圖4中各種蟻群算法的規(guī)劃路徑，從轉彎次數、路徑長度、規(guī)劃次數3個角度進行對比，結果如表1所示。設定柵格的邊框長度為1。

表1 不同算法規(guī)劃結果

結合表1和圖4可以明確看出開闊視野蟻群算法的幾點優(yōu)勢：① 路徑轉彎次數少，這意味著路徑更加平滑；② 規(guī)劃次數最少，這意味算法的規(guī)劃效率最高；③ 所規(guī)劃路徑長度最短，可以有效減少機器人的行駛能耗。

2.2 鄰域可選柵格的重新定義

按照開闊視野蟻群算法的鄰域設置，傳統(tǒng)關于可選柵格的定義不再適用，在此對鄰域內的可選柵格進行重新定義。分析圖5(a)中開闊視野蟻群的鄰域柵格可知，可以將24個鄰域柵格分為2類，一類是一步可到達的鄰域柵格，如圖5(a)中紅色三角標出的柵格，此類柵格的可選柵格定義與傳統(tǒng)一致，也即柵格中不存在障礙物時為可選柵格。另一類是兩步可到達柵格，如圖5(a)中黑色實心圓標出的柵格，當此類柵格自身為自由柵格且與螞蟻間不存在障礙物遮擋時為可選柵格。

以圖5(b)為例對第2類柵格的可選柵格進行解釋，圖5(b)中紅色實心圓所在柵格為當前柵格，柵格1～5為其兩步可達的鄰域柵格，雖然柵格1～5均為自由柵格，但是由于柵格2、3、4與當前柵格的連線經過了障礙物，因此柵格2、3、4為不可選柵格，而柵格1、5與當前柵格的連線不經過障礙物，因此柵格1、5為可選柵格。

圖5 開闊視野蟻群的可選柵格定義

2.3 柵格選擇概率

按照2.2節(jié)可以確定當前柵格的可選柵格，而每個可選柵格的選擇概率可以依據式(1)計算得到。在此需要明確的是，式(1)中的啟發(fā)信息ηij(t)為：

(3)

式中：sjG為柵格j與目標柵格G之間的直線距離。

結合式(1)和式(3)計算各可選柵格的選擇概率，選擇概率最大的柵格為運動的下一柵格。

2.4 基于開闊視野蟻群算法的路徑規(guī)劃步驟

按照開闊視野蟻群算法原理，結合工作環(huán)境的柵格模型特點，制定基于開闊視野蟻群算法的路徑規(guī)劃步驟為：

步驟1設置開闊視野蟻群算法參數，包括螞蟻規(guī)模、信息素因子、啟發(fā)因子、信息素揮發(fā)系數、算法最大搜索次數等。

步驟2將所有螞蟻放置在起點柵格。

步驟3螞蟻按照2.1節(jié)方法確定鄰域中的可選柵格，根據式(1)(2)(3)計算各可選柵格的選擇概率，并選擇概率最大的柵格作為下一柵格，每只螞蟻重復執(zhí)行步驟3直至到達目標柵格。

步驟4當所有螞蟻到達目標柵格時，意味著算法完成一次迭代，此時迭代次數+1。

步驟5判斷是否達到最大迭代次數，若否，則轉至步驟2；若是，則輸出最優(yōu)路徑，算法結束。

3 仿真驗證

為了驗證本文提出的開闊視野蟻群算法的規(guī)劃效果，設置15×15和30×30 2種規(guī)模的柵格環(huán)境，同時使用開闊視野蟻群算法、傳統(tǒng)的4向蟻群算法、8向蟻群算法進行路徑規(guī)劃。算法的參數設置為：螞蟻數量為50，最大迭代次數為100，信息素因子為1.5，啟發(fā)因子為6.0，揮發(fā)系數為0.4。計算環(huán)境為Windows 10、i5CPU、內存8 GB，仿真軟件為Matlab2017。

為了減小隨機因素的影響，同時使用3種算法在2個規(guī)模的柵格環(huán)境下進行10次路徑規(guī)劃，2種柵格環(huán)境下10次規(guī)劃結果如圖6所示。

圖6 不同算法的10次路徑規(guī)劃結果曲線

由10次規(guī)劃路徑的長度可以看出，4方向蟻群算法的路徑長度最大，其次為8方向蟻群算法，開闊視野蟻群算法的路徑長度最小，這是因為開闊視野蟻群算法中螞蟻具有較大視野，螞蟻運動的機動能力較強，路徑轉彎的角度最小分辨率僅為22.5°，轉角分辨率遠遠高于4方向蟻群算法和8方向蟻群算法。另外，由于本文蟻群算法具有較大的視野，當螞蟻選擇兩步可達柵格時，則算法規(guī)劃1次相當于另外2種算法規(guī)劃2次。因此在10次規(guī)劃結果中，開闊視野蟻群算法規(guī)劃的路徑長度遠小于另外2種方法。以30×30規(guī)模柵格環(huán)境為例，給出3種蟻群算法的最短路徑，結果如圖7所示。

圖7 不同算法規(guī)劃的最短路徑

從圖7中可以明顯看出，開闊視野蟻群算法規(guī)劃的路徑最為光滑，不存在路徑折返現象。8方向蟻群算法規(guī)劃的最短路徑光滑性次之，4方向蟻群算法規(guī)劃的最短路徑光滑性最差，且存在一定的折返現象。為了進一步進行比較，統(tǒng)計3種蟻群算法規(guī)劃路徑的長度、迭代次數，結果如表2所示。

表2 不同算法的規(guī)劃參數

由表2中數據可知，在30×30規(guī)模的柵格環(huán)境中，開闊視野蟻群算法規(guī)劃的最短路徑長度為45.236，比8方向蟻群算法減少了14.37%；比4方向蟻群算法減少了33.88%。這是因為開闊視野蟻群算法中螞蟻活動的機動能力強、路徑平滑性好。從迭代次數的角度看，開闊視野蟻群算法迭代19次搜索到最短路徑，8方向蟻群算法迭代了32次，4方向蟻群算法迭代了63次，這是因為開闊視野蟻群算法的螞蟻視野范圍廣、機動能力強，當螞蟻選擇2步可達柵格時相當于另外2種算法迭代2次，因此開闊視野蟻群算法的迭代次數較少。綜合以上分析可知，本文提出的柵格環(huán)境下開闊視野蟻群算法的路徑規(guī)劃方法可以有效減少路徑長度、提高路徑平滑性。

4 結論

1) 開闊視野蟻群算法規(guī)劃的路徑長度小于4方向蟻群算法、8方向蟻群算法；

2) 開闊視野蟻群算法的螞蟻轉角分辨率較高，因此路徑平滑性優(yōu)于另外2種算法；

3) 開闊視野蟻群算法的收斂速度更快，收斂次數少于另外2種算法。