改進蟻群算法在移動機器人路徑規劃中的應用

楊樹廣,董西松

(1 山東交通學院軌道交通學院 山東 濟南 250000) (2 中國科學院自動化研究所多模態人工智能系統全國重點實驗室 北京 100190)

0 引言

伴隨著工業的快速發展,工業設備廣泛應用于制造業、建筑業、物流、礦山開采等領域,在各種應用場景中朝著自動化、智能化等方面發展。智能工業設備可以看作一種能自動控制、可重復編程、多功能、高度靈活的多功能機器人,它具備一些與人大腦相似的思考行為,例如:依靠傳感設備的感知能力、復雜環境下的路徑規劃能力、不同動作的協調能力和其他設備的協同能力等。移動機器人的路徑規劃是指機器人在其工作空間自行規劃出最優或者較優的安全路徑[1]。目前常被人們使用的路徑規劃方法有很多種,例如遺傳算法、人工勢場法、粒子群算法、Dijkstra算法、蟻群算法等,每種算法都有自己的優缺點。在研究經典算法的過程中,發現蟻群算法的魯棒性強、每次搜索相對獨立、有正反饋等特點,但是在復雜環境下也存在尋找最優路徑能力較差和容易陷入局部最優等問題。

針對蟻群算法的缺點和問題,很多學者進行了大量的研究。LUO Q等[2]構造了不平等分配初始信息素,采用偽隨機狀態轉移規則進行路徑選擇,自適應調整確定選擇和隨機選擇的比例,提高了算法的全局最優搜索能力和收斂速度;陳丹鳳等[3]提出一種基于強化學習和人工勢場改進的蟻群算法,利用強化學習對蟻群算法的參數進行配置,引入人工勢場算法的局部優化機制,提升算法避障能力,實現更快更平穩的路徑規劃效果;劉海鵬等[4]采用一種獎懲機制對路徑上的信息素進行更新,還利用拐點優化算法與分段B樣條曲線相結合的方法來進行路徑優化,有效地改善了路徑的平滑性;周敬東等[5]通過改變初始化信息素濃度分配、改變啟發式函數、采取螞蟻回退策略、引入螞蟻優化排序等方法對蟻群算法進行優化,提高了算法的魯棒性和尋優能力;錢平等[6]提出了蟻群算法本身參數及融合遺傳算法以及加入平滑機制,提高了路徑水下機器人路徑規劃的整體性能。

受到上述研究的啟發,針對經典蟻群算法一般容易陷入局部最優和容易出現停滯現象等不足,本文采用以下改進策略。

(1)將當前步長和終點歐氏距離結合起來的方法改進啟發函數,并且引用了前位置因子ε和終點位置因子μ,搜索路徑的方向性得到了加強。

(2)將信息素揮發程度改為一個動態的更新方式,使算法擁有了較好的收斂性。在與經典蟻群算法比較中得出,改進蟻群算法增大了螞蟻選擇最優路徑的可能性,避免出現局部最優解,提高了算法收斂速度的同時,具有較好的全局搜索能力,使原有算法的各項指標都得到提升。

1 移動機器人的環境模型

構建環境地圖的目的在于幫助移動機器人在建立好的含有障礙的環境模型中規劃出一條從起點到目標點的最優路徑。建立適用于移動設備路徑規劃的環境模型已經有了許多成熟的方法,現有的基本的環境模型主要包括柵格分解圖、四叉分解圖、可視圖、Voronoi圖。其中柵格分解圖的代表性強,構建方法較為簡單和后期維護成本低。柵格分解圖就是假設移動機器人的工作環境是在一個二維空間,將空間按照單位大小的正方形劃分為大小相同的單元。一般情況下,在柵格分解圖建模中,0表示可以自由移動的區域,1表示的是存在障礙物的區域,0和1分別對應了白色和黑色區域。本文不考慮障礙物的形狀,如果障礙物所占面積不足一個柵格面積時,也按照一個柵格的面積進行計算。

移動機器人的環境地圖建模如圖1所示,柵格分解圖中的x、y坐標軸和一般的坐標軸遞增順序是一樣的。柵格分解圖共有i行m列,單個柵格邊長為1,則每個柵格中心坐標可以表示為式(1)所示:

圖1 移動機器人環境模型

(1)

式(1)中xi、yi表示此點中心位置的橫坐標、縱坐標;mod(*)表示除后的余數;ceil(*)表示每個元素四舍五入到大于或等于此元素的最接近的數。

2 經典蟻群算法

2.1 算法基本原理

我們所熟知的螞蟻在大自然中尋找食物時,會留下類似于信息素之類的物質,其他螞蟻可能感知到先前螞蟻留下的這種物質。我們用信息素濃度的表征此路徑的長短,所以在較短的路徑上的信息素濃度較高。信息素的濃度也會影響螞蟻選擇路徑的概率,再加上蟻群在路程中也會留下信息素,最終會形成一個正反饋,不斷引導著蟻群尋找出最短的路徑。

2.2 算法公式

(2)

ηij=1/dij

(3)

式(2)中,τij(t)表示t時刻i到j上的信息素濃度;ηij(t)為啟發函數,表示螞蟻從i到j的期望程度;allow表示屬于可以行進的地圖點;α表示信息素重要因子;β表示啟發函數重要因子。

在蟻群經過某個路徑會留下信息素的同時,原有的信息素濃度也會慢慢下降,設定參數ρ(0<ρ<1)表示信息素的揮發程度。所以,當循環一次后,已經走過的每個路徑上的信息素濃度會產生變化,其公式如式(4)所示:

(4)

3 蟻群算法的改進

3.1 改進啟發函數

蟻群算法中的啟發函數只是將下個節點與終點之間的歐氏距離考慮進去,考慮的因素太單一,容易陷入局部最優解。如果在原有公式加入當前位置到下個選擇可選擇位置的歐氏距離,路徑的搜索的方向性被增強。在計算中加入位置因子可以調整兩個距離的權重,這樣能使算法的調整變得靈活。其公式如式(5)所示:

(5)

式(5)中,dis表示從當前節點和下一個待選節點之間的歐式距離;djE從下一個待選節點到E終點的距離的歐式距離;ε表示當前位置因子;μ表示終點位置因子。

3.2 改進信息素揮發程度

蟻群算法中的螞蟻是依靠信息素來做去強化最優路徑的選擇,隨著時間額推移,以前留下的信息素會逐漸消失。信息素的揮發程度會直接影響算法收斂快慢和對全局路徑的搜索,它表示了螞蟻群中的每個螞蟻之間會相互影響路徑的選擇,是螞蟻獲取外界信息的途徑。將信息素揮發程度改為一個動態的更新方式會讓蟻群搜索更多的可行路徑,隨著迭代次數的增加ρ逐漸減小,螞蟻將朝著信息素濃度增高的路徑集中,因此會增快收斂速度。其公式如式(6)所示:

(6)

式(6)中,T代表總迭代次數;t代表當前迭代次數。

4 仿真實驗驗證及分析

為了驗證改進蟻群算法加快了收斂速度的同時具有較高的全局搜索能力等方面的優化效果,在MTALAB2022a上選用20×20規模和30×30規模的柵格分解圖對于改進后的蟻群算法進行仿真。實驗運行電腦的操作系統為Windows10,處理器為Intel i7-7700HQ CPU,內存為16 GB,起始點和終點分別設置在柵格分解圖的左上方與右下方。算法基本參數:迭代次數K=100次;螞蟻的數量M=50只;信息素重要程度因子α=1.2;起點位置因子ε=0.4;終點位置因子μ=0.6;啟發函數重要因子β=8;信息素的揮發程度ρ=0.6。

4.1 20×20柵格分解圖仿真

基于表所給的參數指標,首先使用20×20的固定障礙物的柵格分解圖分別對經典蟻群算法和改進蟻群算法進行仿真實驗,結果如圖2、圖3所示,并對結果進行對比。

圖2 20×20經典蟻群算法收斂曲線變化趨勢和運動軌跡圖

圖3 20×20改進蟻群算法收斂曲線變化趨勢和運動軌跡圖

從本次仿真結果得出改進蟻群算法的最優路徑長度和迭代次數為31.799 m和15次,比經典蟻群算法的路徑長度減少了10.58%,迭代次數減少了51.61%。仿真結果表明,改進蟻群算法的收斂速度遠高于經典蟻群算法,同時容易看出其各項指標更加優越。

4.2 30×30柵格分解圖仿真

為進一步驗證本文算法的優越性,在30×30的固定障礙物的柵格分解圖中將兩種算法再次進行對比仿真實驗,各個參數設置和4.1中保持一致。結果如圖4、圖5所示,并對結果進行分析。

圖4 30×30經典蟻群算法收斂曲線變化趨勢和運動軌跡圖

圖5 30×30改進蟻群算法收斂曲線變化趨勢和運動軌跡圖

從本次仿真結果來看經典蟻群算法前期路徑搜索方向較差,容易陷入局部最優和選擇方向錯誤,這是因為信息素的揮發程度在迭代開始時分布均勻,信息素的揮發程度的正反饋不強,啟發式信息的方向變弱。經典蟻群算法在30×30的仿真實驗中穩定性很差,直到最后也沒有能迭代收斂,甚至在搜尋路徑的過程中還出現了方向的混亂。改進蟻群算法在第28次迭代時就能夠收斂,此時的路徑長度僅為46.769 6 m,并且沒有出現方向混亂。

5 結語

綜上所述,本文通過兩組對比實驗在20×20和30×30的柵格分解圖中路徑規劃的最優路徑長度、找到最優路徑的迭代次數等數據,說明了改進蟻群算法能有效減少最優路徑的迭代次數,加快收斂速度,增加規劃軌跡的平滑度等方面均優于蟻群算法,此外經典蟻群算法在處理較為復雜的地圖時會出現各種問題,證明本次算法在路徑規劃問題求解上的實用性。移動機器人屬于大型設備,對于路徑的平滑程度、穩定性和迭代次數都有較高的要求。改進蟻群算法能滿足設備運行的同時也提高了設備的安全性,使用戶的使用變得更加高效便捷。