基于改進(jìn)蟻群算法的移動機器人路徑規(guī)劃

劉兆麗 朱運海 劉成業(yè) 李向東

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

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

引言

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

1 蟻群算法核心思想

1.1柵格地圖建模

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

2 改進(jìn)蟻群算法

2.1 狀態(tài)轉(zhuǎn)移概率公式的改進(jìn)

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

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

2.2信息素更新策略

2.3通過多步長策略進(jìn)行二次路徑規(guī)劃

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

3 算法仿真對比

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

4 結(jié)論

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

參考文獻(xiàn)：

[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]游曉明，劉升，呂金秋.一種動態(tài)搜索策略的蟻群算法及其在機器人路徑規(guī)劃中的應(yīng)用[J].控制與決策，2017，32（03）：552-556.

[3]姚艷.一種最大最小螞蟻系統(tǒng)的改進(jìn)算法[J].數(shù)學(xué)的實踐與認(rèn)識，2014，44（15）：242-247.

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

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

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

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

[8]夏小云，周育人.蟻群優(yōu)化算法的理論研究進(jìn)展[J].智能系統(tǒng)學(xué)報，2016，11（01）：27-36.

基金項目：山東省科學(xué)院院地產(chǎn)學(xué)研協(xié)同創(chuàng)新基金（2018XXY-19、2019-CXY12）

作者簡介：劉兆麗（1992），研究生：研究方向：物聯(lián)網(wǎng)工程

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

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

（齊魯工業(yè)大學(xué)（山東省科學(xué)院）自動化研究所 ?濟南 ?250353）