基于模糊控制蟻群算法的移動機器人路徑規(guī)劃*

劉建娟，劉忠璞，張會娟，袁 航，姬淼鑫

(河南工業(yè)大學a.電氣工程學院；b.機電設備及測控技術研究所，鄭州 450000)

0 引言

在科技進步和工業(yè)發(fā)展的推動下，以AGV為代表的移動機器人已經(jīng)廣泛運用到各類行業(yè)的技術革新和發(fā)展之中。如醫(yī)療行業(yè)的特殊服務機器人、智慧城市建設中AGV的設計和使用[1]。

路徑規(guī)劃是AGV技術中的重點和難點，保證AGV獲得一條安全、節(jié)能、無碰撞的最優(yōu)路徑，完成相應的作業(yè)任務。在國內(nèi)外的研究中，AGV路徑規(guī)劃算法種類眾多[2]，包括Dijkstra算法、A*算法、人工勢場法、遺傳(GA)算法、粒子群(PSO)算法[3]、快速探索隨機樹(RRT)算法[4]以及蟻群(ACO)算法等。不同種類的算法優(yōu)劣各不相同，如A*算法搜索速度快但尋優(yōu)路徑并不是全局最優(yōu)[5]；遺傳算法(GA)具有較強的魯棒性，但是算法復雜，規(guī)劃效率不高，并且存在尋優(yōu)早熟現(xiàn)象[6]。其中，蟻群算法簡單并且具備良好的全局搜索能力，在目前的路徑規(guī)劃研究和工程應用中是常用算法。

蟻群算法(ant colony algorithm)是一種具有正反饋和啟發(fā)式搜索特性的生物啟發(fā)式算法[7]。傳統(tǒng)的蟻群搜索算法存在收斂速度慢、效率低等問題。國內(nèi)外學者對此進行相應改進，LIANG等[8]提出一種結合遺傳算法和蟻群算法的融合算法，解決蟻群算法容易出現(xiàn)早熟的現(xiàn)象，提高了蟻群算法的有效性和魯棒性，但算法存在迭代速度緩慢，存在冗余節(jié)點的問題；AJEIL等[9]提出了一種螞蟻種群迭代優(yōu)化機制。該機制提出老齡化螞蟻群的概念，并根據(jù)老齡化螞蟻的數(shù)量和迭代結果計算和更新路徑權重，以提高ACO算法的全局收斂性和穩(wěn)定性。但該機制容易造成蟻群搜索多樣性大幅降低，增加算法陷入局部最優(yōu)的可能性。姚曉通等[10]引入帶權重的節(jié)點概率搜索公式，并通過自定義信息素揮發(fā)因子更新機制進一步增加蟻群算法有向性引導和搜索能力，但在該機制的作用下，蟻群定向搜索能力加強，破壞全局多樣性搜索和比較的平衡能力，在復雜環(huán)境中缺陷性較大。ZHENG等[11]提出一種“獎懲”策略，用于改進信息素更新效果，在一定程度上促進蟻群搜索收斂速度，但對于復雜障礙環(huán)境，蟻群搜索存在高度冗余性，“獎懲”策略的使用存在一定的局限，不利于全類型場景使用。杜力等[12]提出一種融合螢火蟲算法的復合蟻群算法，通過螢火蟲算法進行蟻群算法參數(shù)優(yōu)化，通過精英策略促進全局極值搜索和收斂，但該方法減弱了蟻群算法的全局隨機程度，存在收斂陷入局部極值的問題。

常規(guī)的蟻群算法在路徑規(guī)劃中存在路徑最優(yōu)性低、算法收斂速度緩慢等問題。為解決上述問題，本文在保證蟻群算法多樣性搜索的基礎上提出一種改進的智能自適應蟻群算法。本文改進蟻群算法，融合模糊控制技術，引入新的信息素更新策略，優(yōu)化信息素更新效果。同時，改進節(jié)點搜索概率公式，動態(tài)調(diào)整蟻群算法節(jié)點概率搜索公式的計算因子，加快算法的收斂速度。此外，本文提出基于幾何優(yōu)化的路徑節(jié)點優(yōu)化算法，優(yōu)化最短路徑，減少冗余節(jié)點，動態(tài)更新最優(yōu)路徑。本文提出的改進蟻群算法，能夠進一步減短最優(yōu)路徑長度，加快算法迭代收斂次數(shù)，避免算法陷入在局部最優(yōu)，保證多樣性。

1 環(huán)境建模與蟻群算法

1.1 環(huán)境建模

實際環(huán)境地圖是AGV路徑規(guī)劃的主要應用場景。為了與路徑規(guī)劃算法相結合，環(huán)境地圖常常使用柵格地圖[13]建模的方式展現(xiàn)，如圖1所示。其中黑色陰影區(qū)域為柵格地圖中的障礙物標識區(qū)域，空白區(qū)域為AGV允許運行區(qū)域。

圖1 二維柵格地圖建模

假設實際環(huán)境地圖為正方形地圖，柵格化建模后，以柵格地圖的左下角為坐標系原點建立OXY坐標系，每個柵格的長度為一個單位a，柵格地圖每一行共有M個柵格，那么柵格地圖的柵格數(shù)總量為M*M個。設當前AGV所在柵格為第G個柵格，那么此時AGV所在位置的二維坐標(x,y)可由式(1)和式(2)計算。

(1)

(2)

式中，mod為取余符號；ceil為向上舍入的取整符號。

此外，實際環(huán)境地圖存在不全為正方形的特殊情況。對于此，柵格化建模通常采用“地圖規(guī)則化”處理，即擴大柵格化地圖范圍，其中擴大的柵格范圍設定為AGV不可行區(qū)域的處理方式，如圖2所示。其中，圖2a為實際地圖俯視圖，陰影區(qū)域為障礙物，圖2b為柵格化建模地圖，條狀陰影區(qū)域為擴大范圍的地圖障礙物區(qū)域。

(a) 實際地圖俯視圖 (b) 柵格化建模地圖圖2 特殊環(huán)境建模

實際環(huán)境地圖根據(jù)上述建模規(guī)則進行二維柵格化處理，使用柵格坐標標記AGV位置等參數(shù)，并支撐路徑規(guī)劃算法的運行和實現(xiàn)。

1.2 路徑規(guī)劃基本蟻群算法

蟻群算法是以自然界螞蟻尋找食物的自然現(xiàn)象為主要思想進行設計算法[15]，能夠良好地解決優(yōu)化控制領域、路由分配及路徑規(guī)劃等問題。

路徑規(guī)劃技術中的蟻群算法實現(xiàn)主要包括算法初始化、轉輪賭法尋找下一合適節(jié)點和信息素更新3部分。其中，蟻群算法初始化主要進行蟻群參數(shù)設定，包括：蟻群算法起始點和目的點、螞蟻種群數(shù)量、信息素初始分布、迭代次數(shù)的設置以及信息素蒸發(fā)率的設定等，其中，蟻群尋路起始點和目的點即為機器人路徑規(guī)劃的起始點和目的點。在尋路迭代次數(shù)為t時，螞蟻z從節(jié)點i轉移到節(jié)點j的概率如式(3)所示。

(3)

(4)

圖3 蟻群搜索八向示意圖

每只螞蟻重復上述尋路過程，直至通過概率公式計算確定下一節(jié)點為路徑規(guī)劃目的點或迭代次數(shù)達到預設值時，完成一次尋路過程。當所有的螞蟻完成一次尋路之后，每條路徑節(jié)點上的信息素濃度開始進行更新，更新計算如式(5)所示。

(5)

(6)

式中，Q為正常數(shù)，一般設定為1；Lz為本次尋路得到的最優(yōu)路徑的長度數(shù)值。

蟻群通過概率選擇、信息素更新等步驟不斷迭代循環(huán)，利用正反饋特性不斷促進算法收斂，實現(xiàn)路徑規(guī)劃。

2 融合模糊控制的改進蟻群算法

本文提出一種路徑規(guī)劃中融合模糊控制的改進蟻群算法FOACO，解決蟻群算法在路徑規(guī)劃過程中存在的收斂速度緩慢、精確度有待提高等問題。改進蟻群算法提出3個策略優(yōu)化方法：信息素更新策略改進、權重因子自適應調(diào)整和規(guī)劃路徑幾何優(yōu)化。

2.1 初始化信息素濃度分布規(guī)則

普通蟻群算法路徑規(guī)劃信息素初始分布為均一分布，全局信息素無差排列，蟻群尋路過程出現(xiàn)盲目性和不確定性，影響全局性能。為了增大初始化信息素的啟發(fā)作用，本文引入一個初始化信息素濃度分布規(guī)則，如圖4所示。

圖4 初始化信息素分布

根據(jù)規(guī)劃起點和終點建立信息素濃度特殊初始化區(qū)域，其余區(qū)域為信息素普通初始化區(qū)域。信息素初始化分布如式(7)所示。

(7)

式中，χ為普通信息素初始化濃度分布數(shù)值；f為特殊分布系統(tǒng)，取值范圍為[0,0.5]。通過增加信息素初始分布，構建蟻群有向性移動最優(yōu)路徑區(qū)域，降低螞蟻尋路的盲目性和不確定性，加快蟻群算法路徑規(guī)劃速度。

2.2 融合模糊控制的信息素更新策略改進

普通蟻群算法信息素更新啟發(fā)性較弱，全局規(guī)劃精度和速度不足。本文引入二維模糊控制器進行蟻群經(jīng)過路徑節(jié)點信息素更新增量的計算與控制。模糊控制器輸入變量為螞蟻所在節(jié)點信息素濃度值Tau和當前時刻傳統(tǒng)信息素更新策略的信息素更新值ΔTau_tra，模糊控制器輸出量ΔTau_Fuzzy作為信息素更新的變化量之一。模糊控制器結構如圖5所示。

圖5 模糊控制器設計

模糊控制器的變量隸屬度函數(shù)根據(jù)專家經(jīng)驗知識選定。其中，三角型隸屬度函數(shù)和廣義鐘型隸屬度函數(shù)對于離散系統(tǒng)具備良好的計算能力和平滑處理能力，因此，本文模糊控制器的隸屬度函數(shù)設計如表1所示。

表1 模糊控制器的變量模糊化

同時，模糊控制器輸出量的論域選定為[0.001,0.1]，為避免模糊控制器輸入溢出影響算法速度，本文選用的輸入和輸出變量隸屬度函數(shù)如圖6所示。

(a) Tau (b) ΔTau_tra (c) ΔTau_Fuzzy圖6 隸屬度函數(shù)

蟻群算法規(guī)劃路徑長度隨著迭代次數(shù)的增加逐漸趨近于收斂狀態(tài)。在路徑規(guī)劃趨近收斂狀態(tài)中，普通信息素增加值的啟發(fā)作用不明顯，因此，蟻群算法路徑規(guī)劃速度受到極大的限制。為解決這個問題，本文引進收斂狀態(tài)信息素增量ΔTau_ste計算方式為：

(8)

式中，lengthk為第k次迭代的路徑長度；itermax為最大迭代次數(shù)；R為常數(shù)。綜上所述，改進蟻群算法信息素更新策略為：

(9)

式中，ΔTau_Fuzzy(j)為模糊控制器輸出量的值，即模糊控制器輸出的節(jié)點j的數(shù)值增量。

2.3 蟻群參數(shù)自適應調(diào)整規(guī)則

普通蟻群算法參數(shù)數(shù)值固定，容易引起算法收斂速度降低，甚至不利于算法收斂。為了提高蟻群算法穩(wěn)定性和快速性，本文采用信息素權重因子和蒸發(fā)率自適應調(diào)整規(guī)則，進行算法優(yōu)化。信息素權重因子自適應調(diào)整為：

(10)

式中，lengthop為第k次迭代最優(yōu)路徑長度；R為常數(shù)。根據(jù)規(guī)劃路徑長度進行信息素啟發(fā)因子數(shù)值調(diào)整，增大信息素在后續(xù)迭代規(guī)劃中的啟發(fā)性，促進算法快速收斂。同時，信息素蒸發(fā)率固定，隨著迭代次數(shù)增加，路徑節(jié)點信息素累積速度超過蒸發(fā)速度，容易出現(xiàn)冗余節(jié)點和冗余路徑?，F(xiàn)引入信息素蒸發(fā)速率自適應調(diào)整規(guī)則，提高路徑節(jié)點蒸發(fā)速度。若第k次迭代路徑長度大于第k-1次，為減小較差路徑信息素濃度的啟發(fā)作用，促使蟻群向更優(yōu)路徑移動，現(xiàn)對信息素蒸發(fā)率進一步增加，如式(11)所示：

(11)

通過信息素權重因子和蒸發(fā)率自適應調(diào)整，對全局迭代路徑信息素濃度有向性處理，加快全局最優(yōu)路徑的規(guī)劃速度。

2.4 規(guī)劃路徑幾何優(yōu)化算法(FOACO)

為了進一步優(yōu)化改進算法FACO的性能和效果，采用幾何原理進行路徑優(yōu)化，即利用三角形兩邊的長度之和大于第三邊的特性去除路徑中的冗余點。如圖7所示，路徑節(jié)點為1→2→3→4→5，以三個節(jié)點為一組判斷冗余節(jié)點，D為極限距離，如式(12)所示，其中a為柵格邊長。假定節(jié)點組為3，4，5，以首尾節(jié)點為固定兩點建立直線y=K*x+B，計算中間節(jié)點距離該直線的距離d，并以此為節(jié)點冗余判斷參數(shù)。假設數(shù)值d大于極限距離D，則直線y經(jīng)過障礙物，節(jié)點4不可刪除。反之，節(jié)點4為冗余節(jié)點，刪除優(yōu)化后，路徑為1→2→3→5。

圖7 幾何優(yōu)化示意圖

(12)

結合路徑規(guī)劃結果中存在銳角路徑轉折的特殊情況，如圖7中路徑節(jié)點組1→2→3，采用上述冗余路徑判斷方法可能出現(xiàn)“幾何優(yōu)化”無效的問題。本文采用“檢測銳角—增加節(jié)點優(yōu)化”的處理方法，即增加節(jié)點6，更新路徑節(jié)點組為1→2→6，重復進行冗余路徑判斷過程，如圖7所示。幾何優(yōu)化后路徑為1→6→3→5，與原路徑相比，路徑長度進一步縮短，優(yōu)化路徑規(guī)劃整體效果。

2.5 FOACO算法總體流程

結合上述改進策略：信息素更新策略改進、權重因子自適應調(diào)整和規(guī)劃路徑幾何優(yōu)化，改進算法工作流程如圖8所示，通過改進措施，動態(tài)更新蟻群算法參數(shù)數(shù)值，優(yōu)化算法整體結構，額外增加幾何優(yōu)化步驟提高改進算法的完整度。

圖8 改進蟻群算法(FOACO)流程圖

3 仿真實驗與驗證

為了驗證本文算法的可靠性，在MATLAB 2017a開發(fā)平臺下編寫算法，實驗硬件設備為：Intel(R)Core(TM)i5-6200U CPU@2.40 GHz和8 GB運行內(nèi)存。本文根據(jù)不同實驗環(huán)境分別設置三組對照實驗，采用普通蟻群算法ACO、遺傳算法改進蟻群算法GACO和本文算法FACO進行算法效果對比，實驗地圖大小為20×20。此外，三組蟻群算法基礎參數(shù)設置如表2所示。

表2 基礎蟻群算法參數(shù)設置

本文設置兩種仿真地圖，分別為一般地圖MAP1和文獻[15]地圖MAP2，對照實驗結果如圖9所示。

(a) MAP1 (b) 迭代曲線

(c) MAP2 (d) 迭代曲線圖9 對照實驗

如圖9所示，通過本文改進方法實現(xiàn)，F(xiàn)ACO算法規(guī)劃路徑收斂速度優(yōu)于普通蟻群算法ACO和融合遺傳算法的蟻群算法GACO，規(guī)劃路徑長度也有不同程度的降低改善。與文獻[15]的改進蟻群算法相比，本文算法收斂性能和路徑最優(yōu)程度均進一步得到提升，規(guī)劃路徑轉折次數(shù)降低，路徑更加平滑。加入幾何優(yōu)化策略后改進蟻群算法FOACO路徑規(guī)劃結果如圖10所示。

圖10 FOACO幾何優(yōu)化實驗

結合圖10和表3，本文改進FOACO算法與對照組算法相比具有更強的最優(yōu)路徑規(guī)劃能力。對于MAP1，本文算法與ACO和GACO相比，路徑長度減小8.51%和6.17%，迭代次數(shù)減小27.9%和36.73%；對于MAP2，本文算法與文獻[15]相比，路徑長度減小0.371%，迭代次數(shù)減小6.25%。因此，本文改進蟻群算法具備一定的優(yōu)越性。

表3 仿真對比實驗數(shù)據(jù)表

4 結論

本文提出一種融合模糊控制和自適應權重信息調(diào)整的改進蟻群算法來優(yōu)化移動機器人路徑規(guī)劃技術的性能。首先使用信息素初始化規(guī)則提高初始信息素啟發(fā)能力。同時，引入模糊控制和收斂狀態(tài)信息素增量改進普通蟻群算法的信息素更新策略，進一步提高信息素更新效果，促進算法全局最優(yōu)收斂；采用自適應權重因子調(diào)整的方式，促進蟻群算法快速迭代和收斂；最后，采用幾何優(yōu)化算法進一步優(yōu)化規(guī)劃路徑，進一步縮減路徑長度，深化全局收斂路徑結果的最優(yōu)性。實驗表明，本文算法能夠有效地提高移動機器人路徑規(guī)劃性能，縮減路徑長度效果明顯，有效減低最短路徑迭代次數(shù)，整體效果優(yōu)于其余同類型算法。結合移動機器人實際使用場景，下一步可著重于動態(tài)障礙物蟻群算法路徑規(guī)劃性能改進與提升的研究工作，盡可能拓寬本文算法應用場景和技術深度。