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

劉兆麗 朱運海 劉成業 李向東

摘 要：本文在傳統蟻群算法的基礎上進行了相應的改善。通過改進轉移概率、信息素更新策略以及利用多步長策略進行二次路徑規劃。在轉移概率中增加權重系數，降低螞蟻陷入盲目搜索的可能，減少了螞蟻死鎖的數量;信息素更新原則，自適應調整提高搜索能力，降低局部收斂性，提高全局收斂性和機器人尋找目標點的工作效率;通過利用多步長策略進行二次路徑規劃，求解路徑長度的最優解不僅降低了機器人的能耗，也降低了機器人的勞損，節約成本。實驗結果顯示，本文提出的算法全局搜索能力較高，收斂速度較快，能夠快速的找到最優路徑，可以有效提高機器人工作的效率，驗證了本文算法的適用性和有效性。

關鍵詞：蟻群算法;全局收斂;移動機器人;信息素

引言

蟻群算法是由Dorigo.M等人提出的一種新型進化的算法，在路徑規劃的問題上具有解決問題的明顯優勢[1]。但是蟻群算法也存在易陷入局部最優解和死鎖等問題，為此很多學者做出了大量改進工作，比如動態化搜索算子[2]，有效提高解的質量和收斂速度;設定信息素閾值[3]，防止信息素過多或者過少而使算法收斂速度慢或者過早收斂;最大最小螞蟻系統[3]，只在每次迭代的最優路徑上強化信息素濃度，減少其他路徑對螞蟻尋找路徑的影響。蟻群算法還可以與其他算法相嵌合，比如：文獻[5]將人工勢場產生的力與蟻群的信息素相結合，使信息素擴大到遠離障礙區域的地方，提高了機器人搜索范圍和速度;文獻[6]將遺傳算法和蟻群算法相結合，把每一次迭代完成后所產生的路徑作為基礎，通過不斷選擇的交叉不同來獲得本次迭代的最佳路徑。本文做出的改進具體有：1）改進狀態轉移概率公式，減少螞蟻死鎖的數量，進一步提高收斂速度;2）改進信息素更新策略，自適應調節信息素的揮發因子，克服螞蟻在尋優過程中陷入局部收斂等問題;3）進行二次路徑規劃，優化路徑長度和轉彎次數降低能耗，提高移動機器人適應性和運轉效率。

1 蟻群算法核心思想

1.1柵格地圖建模

柵格法是路徑規劃常用的模型，其中利用每個柵格的取值來表示障礙物和可移動區域，空白部分用0表示，為自由柵格，即移動機器人可以移動的區域，陰影部分用1表示，為障礙物柵格，即移動機器人不可移動的區域[7]。本文選用柵格地圖建模，將柵格地圖的左下角視為坐標原點，將柵格最下端的水平方向視為X軸，將柵格最左端的垂直方向視為Y軸，構建出直角坐標系，在本文中小于柵格面積1/2的視為自由柵格，大于柵格面積1/2的視為障礙物柵格。另外，本文假設每個柵格為邊長為1cm的正方形。如圖1所示。

2 改進蟻群算法

2.1 狀態轉移概率公式的改進

蟻群在路徑搜索初期無法避免的會產生大量交叉路徑，另外由于算法禁忌表的限制，螞蟻很容易陷入死鎖狀態，最終導致“迷失”，大量螞蟻停滯不前[8]。如圖2所示。

螞蟻k 從當前位置i 移動到下一個位置j 受到兩個指標的影響：概率選擇和信息素的更新。本文在狀態轉移概率公式中引入加權因子T（T∈（0，1）） ，提高算法的收斂速度。改進后的公式如下：

2.2信息素更新策略

2.3通過多步長策略進行二次路徑規劃

目前國內外學者針對移動機器人步長選擇主要為單步長策略，這種單步長搜索方式會使移動機器人搜索到的路徑過長，時間成本增加，本文算法選擇多步長策略，當移動機器人采用多步長二次路徑規劃策略時，先通過本文的改進蟻群算法搜索出移動機器人最優單步長路徑，如圖3中的虛線所示，其中將虛線路徑作為二次路徑規劃的參考，依次把當前節點與下一個節點相連，同時判斷移動機器人是否與障礙物相撞，如果沒有碰撞，則繼續往下一個節點轉移，直至撞到障礙物，那么當前節點與此節點的上一個節點連心為最佳路徑，如圖3中實線所示，兩條路徑的對比結果很明顯，多步長選擇策略具有明顯的優勢，縮短了移動機器人的路徑長度、轉彎次數以及降低了時間成本。

3 算法仿真對比

在同一柵格地圖環境下，圖4所示為本文改進算法的情況下移動機器人的路徑規劃軌跡，可以看出移動機器人的路徑長度更短，轉彎次數更少。圖5所示為文獻[4]的改進蟻群算法的移動機器人的軌跡，可以看出在同一柵格地圖模型下，出現了陷入局部收斂的情況，轉彎次數增多，從而增加了移動機器人的能源消耗。圖6是傳統蟻群算法，很容易看出雖然移動機器人可以到達終點，但是路徑長度明顯增長，轉彎次數明顯增多，這樣不僅增加了移動機器人的能耗也增加了機器人的勞損，相比較而言成本較大，不適合現實場景的應用和收益。圖7 是本文算法和文獻[4]的收斂曲線和最短路徑長度，通過本文算法的優化，移動機器人的收斂次數降到了13次就可達到穩定，而文獻[4]的算法需要22次才能達到穩定，實驗結果顯示本文的算法具有較高的適用性和穩定性。在柵格地圖中，文獻[4]的算法的結果顯示最短路徑的長度是41.796，而本文的算法的結果顯示最優路徑的長度是36.382，提高了12.9%;文獻[4]的算法的迭代次數是22，而本文算法的迭代次數是13，減少了40%。本文算法根據解的分布情況，自適應的進行信息素濃度的更新，動態強化最優路徑上的信息素強度，并且利用多步長策略進行二次規劃，因此在同一個柵格地圖環境下，相對于文獻[4]的算法，本文算法大大提高了收斂速度以及縮短了路徑長度，使本文算法收斂速度快并且達到全局性最優，驗證了本文算法的有效性和優越性，兩種算法比較如表1所示。

4 結論

針對傳統蟻群算法在復雜路徑規劃中的種種不足，本文提出一種改進的蟻群優化算法。該算法利用起始位置點的信息，增加權重因子，從而改進轉移概率公式，用小于1對解空間更全面的搜索，有效篩選死鎖的螞蟻，提高了螞蟻的搜索能力和速度;信息素的更新策略，提高了螞蟻全局性的指導搜索能力;利用多步長策略進行二次路徑規劃，明顯減少了節點的數量，節省了算法運行時間，有效的降低了移動機器人的損耗和能耗，降低成本。實驗結果表明，本文算法具有更高的穩定性和收斂性。

參考文獻：

[1]DORIGO M，GAMBARDELLA L M.Ant colony system：A cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation，1997，1（1） ： 53-66.

[2]游曉明，劉升，呂金秋.一種動態搜索策略的蟻群算法及其在機器人路徑規劃中的應用[J].控制與決策，2017，32（03）：552-556.

[3]姚艷.一種最大最小螞蟻系統的改進算法[J].數學的實踐與認識，2014，44（15）：242-247.

[4]楊萍，趙珍，鄭海霞.基于改進蟻群算法的移動機器人全局路徑規劃方法研究[J].機械制造與自動

[5]王曉燕，楊樂，張宇，等.基于改進勢場蟻群算法的機器人路徑規劃[J].控制與決策，2018，33（10）：1775-1781.

[6]汪杰君，劉江寬，黃喜軍，等.基于混合遺傳蟻群算法的數字微流控芯片測試路徑規劃[J].電子測量與儀器學報，2017，31（08）：1183-1191.

[7]曲小康，芮小平，韓瑩，等.柵格成本距離計算的改進蟻群算法[J].地球信息科學學報，2016，18（08）：1052-1059.

[8]夏小云，周育人.蟻群優化算法的理論研究進展[J].智能系統學報，2016，11（01）：27-36.

基金項目：山東省科學院院地產學研協同創新基金（2018XXY-19、2019-CXY12）

作者簡介：劉兆麗（1992），研究生：研究方向：物聯網工程

*通訊作者：朱運海（1974），研究員;研究方向：機器人控制決策;

*通訊作者：劉成業（1979），助理研究員;研究方向：移動機器人;

（齊魯工業大學（山東省科學院）自動化研究所 ?濟南 ?250353）