基于混合參數蟻群算法的移動機器人路徑規劃

荊學東，杜黎童，郭泰，蔡震寰

(上海應用技術大學機械工程學院，上海 201418)

0 前言

全局路徑規劃是研究室內移動機器人運動控制的重點技術之一。移動機器人根據自身所處的全局地圖環境和目標點的信息，它可以迅速地通過自主計算找到一條從當前位置到達指定目標點的適宜路徑。路徑規劃的算法許多，主要有A算法、柵格解耦法和人工勢場法、神經網絡算法、遺傳算法和粒子群算法等。

蟻群算法(Ant Colony Optimization,ACO)是由意大利學者DORIGO等提出的一種群集智能算法。算法早期主要是用來解決商旅問題，隨著算法的應用發展，且ACO算法本身具備的分布式計算、正反饋性和強魯棒行等特點，它也廣泛應用到路徑規劃領域，并且取得了許多優秀成果。雖然ACO算法優點很多，但也存在許多缺點。對它的缺點，STüTZLE、HOOS提出了最大最小蟻群系統；文獻[14]提出了把ACO算法和遺傳算法(Genetic Algorithm,GA)結合使用的混合算法(Genetic Algorithm-Ant Algorithm,GAAA)；文獻[15-18]則把GAAA算法成功運用到旅行商、車間調度等生產生活的問題中去。本文作者設計了一種混合參數的蟻群進化算法(Hybrid Parameter Ant Colony Evolutionary Algorithm,HPACEA)，此算法在GA算法和ACO算法融合節點和銜接處進行優化改進，并通過實驗驗證了該算法的可行性和有效性。

1 基于柵格地圖的環境建模

文中的室內移動機器人搭載單線激光雷達，它無法獲取周圍物體的高度信息，僅能獲取平面數據，掃描數據為二維數據。為簡化室內環境，采用柵格地圖法對移動機器人獲得的室內環境數據進行建圖，柵格尺寸大小與移動機器人的外形大小有關，用黑白2色柵格表示不可行路徑節點和可行路徑節點。為保證機器人和障礙物有安全的間隔距離，根據機器人實際尺寸取邊長的二分之一長度對障礙物進行“膨化”處理，用黃色柵格表示膨化處理的安全距離空間。當雷達數據映射到地圖中時，如果障礙物面積不足一個柵格，則當作占據一個完整柵格。文中柵格地圖中每個柵格的序號從左上角開始，依次編號為1、2、…、。對環境進行柵格建圖，如圖1所示。

圖1 柵格法的環境地圖

2 混合參數蟻群進化算法的原理與改進

本文作者提出的混合參數蟻群進化算法(HPACEA)的總體框架如圖2所示。

圖2 HPACEA算法框架

2.1 HPACEA中遺傳算法的設定

2.1.1 交叉概率和變異概率的改進

為增加算法初期蟻群信息素分布的多樣性，對遺傳算法的交叉概率和變異概率引入高斯變異算子。首先在種群每次迭代中隨機在區間[0.2，0.9]中選擇交叉概率，然后對該交叉概率隨機選擇一定數量的維度進行高斯變異操作，生成的滿足+=1。其操作方式為

=roundn(0.2+0.7×rand(),-1)

(1)

(2)

(3)

式中:～(1,1),(1,1)表示均值為1、方差為1的高斯分布；roundn為四舍五入函數；rand產生[0,1)均勻分布隨機數。

在高斯變異過程中，產生的可能會超出區間范圍。當它在維度上超出邊界，通過式(4)的映射規則映射到可行區間的新位置。

(4)

式中:、分別為交叉概率區間的上邊界和下邊界。

2.1.2 適應度函數改進

GA算法的適應度函數是基于路徑長度和路徑拐角獎懲機制進行評價的。路徑長度計算公式如下：

(5)

=1

(6)

式中:為連續路徑的總長度。

為減少路徑的拐彎個數，讓路徑盡量平滑，引入拐點獎懲機制，公式如式(7)所示：

(7)

=1

(8)

式中:為連續路徑的獎懲點數。

適應度函數總的計算公式如下：

=+

(9)

根據路徑長度和拐角獎懲點數選擇合適的權重參數。

2.1.3 交叉方法

遺傳算法的交叉操作流程如圖3所示。

圖3 交叉方法流程

2.1.4 變異方法

遺傳算法的變異操作流程如圖4所示。

圖4 變異方法流程

2.2 HPACEA中蟻群算法的改進與鏈接

2.2.1 蟻群算法銜接設置

為了充分發揮GA算法的進化效果，減少算法的無用迭代,在GA算法和ACO算法融合處采用最小進化率參數評估是否由GA算法進入ACO算法。對GA算法設置一個最小迭代數和最大迭代數,當GA算法的進化率連續代小于給定的最小進化率時開始進入ACO算法。進化率計算方法如下：

=(--1)-1=2,3,…,

(10)

(11)

式中：為適應度評價值；為個體的進化率；為進化代數；為種群規模；RE為每一代的進化率。

當確定由GA算法進入ACO算法時，將GA算法最后一代得到的路徑中排名前15%路徑信息轉化為HPACEA算法中的初始信息素分布。

=+

(12)

式中：為信息素常數；為由遺傳算法得到的初始路徑經過計算得到的信息素值。

2.2.2 蟻群算法信息因子和期望因子改進

HPACEA算法螞蟻尋路時采用混合參數來提高蟻群尋路的多樣性，即每次迭代都引入高斯變異產生新的和?！?0,3),∈(0,7),其選擇公式如下:

=roundn(((3-rand())·min(3,2+7)),-2)

(13)

(14)

=roundn(7×rand()06,-2)

(15)

(16)

(17)

(18)

式中:、、、分別為、的上邊界和下邊界。

2.2.3 信息素更新方法

在每代蟻群尋路結束后，進行信息素更新時采用精化策略，其更新方式為

(19)

(20)

對信息素揮發因子采用一種自適應調整方式：

(21)

式中:為的最小值；為的最大值；為適應度最大值；為適應度最小值。

在ACO算法的最后再次引入遺傳操作，當ACO算法每次迭代路徑的進化率大于給定的時，根據輪盤賭的概率決定是否對當代產生的路徑進行交叉操作或變異操作，這樣HPACEA算法總體形成了一個類似閉環的算法機制。

2.3 HPACEA算法路徑光滑處理

在HPACEA算法的最后階段引入三次B樣條曲線，實現機器人路徑的相對光滑。為判斷去除多余節點后新生成的路徑是否經過障礙物區域，引入評價變量。的表達式為

(22)

式中:為障礙物節點中心到新生成路徑的距離。

平滑機制實施步驟：

(1)針對所有路徑的節點，兩兩相連計算它們的斜率，若2個斜率不相同，則取它們共有的節點，放入節點集合中。

(2)把最優路徑的起始節點和終止節點放入集合中，設={|=1,2，…，}，為起始點，為目標點。首先連接、，判斷、連線是否經過障礙物，若=1;繼續連接與下一節點，直到、連線穿過障礙物區域停止，則把、-1連接起來，刪除它們中間的多余節點、…、-2，得到新的路徑;從節點-1開始連接+1，依次判斷每次連線是否經過障礙物。當集合中的節點都被連線過且新生路徑中沒有多余節點為止。

(3)對去除多余節點的新路徑,采用準均勻B樣條曲線對其進行優化處理。

圖5展示了路線光滑過程中的3個路徑階段。

圖5 光滑機制處理前后的路徑

3 仿真實驗驗證

為證明HPACEA算法是有效可行的，采用MATLAB軟件對柵格環境下的室內機器人進行路徑規劃仿真驗證，和不同的算法進行驗證比較。

3.1 20×20簡單環境實驗仿真

將HPACEA算法與傳統的GA算法、ACO算法和文獻[14]中GAAA算法在20×20的柵格地圖進行仿真對比試驗。HPACEA算法的初始條件為：遺傳算法的迭代次數=50和=10，=3%，=50，=100，=100，∈[0,3]，∈[0,7]，(0)=07，=0.2,=1.8，設置起始點柵格序號為1，終止點為400。GA算法、ACO算法和GAAA算法，共有的參數設置和HPACEA相同，不相同參數按照經驗自行設定。對比算法的具體參數設為：GA算法和ACO算法最大迭代次數為120,=0.8，=0.2，=1，=7。結果如圖6、圖7所示。

從圖6可以看出:HPACEA算法獲得的路徑最短且相對光滑，ACO算法和GAAA算法次之，GA算法的運動軌跡最長且拐角最多。圖7為4種算法的收斂曲線：GA算法的收斂速度最快，在迭代18次找到穩定解，但找到的路徑經常屬于次優解；HPACEA算法的收斂速度較快，在迭代20次即可找到最優解；GAAA算法和ACO算法都是50次迭代以后找到穩定解，并且找到的解經常不是最短路徑。

圖6 20×20環境中4種算法運動軌跡

圖7 20×20環境中4種算法的收斂曲線

表1是在20×20的柵格地圖對4種算法進行10次路徑規劃的仿真實驗數據，表中引入最佳尋優性能指標、時間性能指標和魯棒性能指標作為路徑規劃算法的評價指標。可以看出：HPACEA算法找到的最優路徑為29.49 m,相比其他算法找到的路徑長度減少4.7%～9.8%，轉彎節點減少45%～57%。從性能評價指標可以看出:GAAA算法和HPACEA算法的最佳尋優性能指標和魯棒性能指標明顯優于GA和ACO算法，其中HPACEA算法最好，GAAA算法次之；從時間性能指標上對比，GA算法收斂速度最快，HPACEA算法次之；從綜合性能指標看出，HPACEA算法最優，綜合性能明顯比其他3種算法優秀。

表1 20×20環境中4種算法的仿真結果

3.2 30×30復雜環境實驗仿真

采用30×30的復雜環境驗證HPACEA算法的有效性，并與其他3種算法進行驗證對比。實驗結果如圖8、圖9所示。

圖8 30×30環境中4種算法運動軌跡

由圖8知:傳統GA、傳統ACO和文獻[14]的GAAA算法在面臨復雜環境時，規劃的路線存在許多轉折點;而HPACEA算法加入光滑機制后，拐點數減少31%～40%，并且規劃的路徑更光滑。由表2知：最短路徑長度是HPACEA算法找到的43.12 m,相比其他算法找到的路徑長度減少6.8%～8%；文獻[14]的GAAA和改進的HPACEA算法在魯棒性能和最佳尋優性能指標上比較優秀，且HPACEA算法表現得最好。結合圖9知:在復雜的環境里，傳統GA算法和HPACEA算法達到穩定解的迭代速度是最快的，但HPACEA算法能找到更短的路徑，且它的魯棒性最好。HPACEA綜合性能比其他3種算法更優秀，即使面對復雜的環境也能保持穩定性和快速尋找最優解的能力。

圖9 30×30環境中4種算法的收斂曲線

表2 30×30環境中4種算法的仿真結果

通過設計2種不同室內環境，對傳統GA算法、傳統ACO算法、文獻[14]的GAAA算法和改進HPACEA算法進行仿真實驗，從算法的尋優能力、收斂速度和算法魯棒性進行評估對比，驗證了改進HPACEA算法在進行路徑規劃時具有較強的尋優能力、較快的搜索速度和求解穩定的特點，對復雜的環境也具有較強的適用性。

4 結論

(1)針對蟻群算法收斂速度慢和易陷入局部最優等缺陷，提出了混合參數的蟻群進化算法。該算法首先進行選擇、交叉、變異操作，為下一步蟻群算法提供不同信息素信息;然后對蟻群算法的、、因子進行優化改進;最后對輸出路徑進行光滑加工處理。通過仿真實驗證實了算法的可行性。

(2)在MATLAB中采用柵格法建立兩種室內環境模型，將文中算法與其他3種算法進行仿真對比實驗。結果表明：改進的算法在不同的環境下，找到的路徑長度比其他3種算法減少了4.7%～8%，路徑拐點減少了30%以上，且改進的算法可以較快找到一條相對光滑的路徑，達到穩定解的迭代次數比ACO和GAAA算法減少了50%。