[發明專利]一種基于改進蟻群算法的路徑規劃方法

在審

• 申請號: 202010891876.5
• 申請日: 2020-08-31
• 公開（公告）號: CN111982125A
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 侯阿臨;楊騏豪;姜偉楠;吳浪;孫弘建;季鴻坤;楊理柱;劉麗偉;李秀華;梁超;楊冬
• 申請（專利權）人: 長春工業大學
• 主分類號: G01C21/20
• 分類號: G01C21/20;G05D1/02
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及一種基于改進蟻群算法的路徑規劃方法。該算法將改進的人工勢場(APF)算法和蟻群算法相結合，采用改進APF算法進行初始地圖規劃，降低了蟻群算法初始規劃的盲目性。該算法利用A*算法的評估函數以及路徑轉折角度來改進啟發函數，引入啟發信息遞增函數，免于局部最優的同時保證收斂速度。改進狀態轉移規則并自適應地調整狀態轉移函數的閾值，可以提高算法的運行效率，同時可以增加解的多樣性。改進算法的信息素更新機制和路徑評價函數，提高了算法的全局最優性，使得到的路徑更符合實際需求。

技術領域

本發明涉及一種基于改進蟻群算法的路徑規劃方法，屬于智能機器人路徑規劃領域。

背景技術

機器人的路徑規劃是機器人導航技術里最重要的一個環節，它指的是將移動機器人放在一個有障礙物的工作環境中，通過設置機器人在這個工作空間中的初始點和目標點，使機器人找到一條從初始點到目標點的路徑的過程。在這個過程中，通過使用一定的路徑規劃方法，使機器人找到一條令人滿意的路徑。目前，國內外研究人員對路徑規劃提出了很多算法，包括A*算法、人工勢場等傳統算法。以及一系列智能優化算法，如蟻群算法、遺傳算法、粒子群算法等。每種算法均根據不同的性能指標有不同的優缺點。

人工勢場法是一種重要的局部路徑規劃方法，其由于計算量小、規劃結果安全可靠而被廣泛關注。但該算法對周圍環境的感知信息具有局限性，易出現局部最優問題。蟻群算法是一種基于智能仿生計算的優化算法，通過模擬螞蟻的覓食行為，在空間中進行路徑規劃，在機器人路徑規劃和無人駕駛中都具有良好的應用前景。蟻群算法具有良好的魯棒性，容易應用到實際問題中并且易于其他算法相結合。另外，蟻群算法還有適應強、有較好的求解能力等優點，但與此同時，蟻群算法也存在以下缺點：① 蟻群在路徑規劃初期搜索存在盲目性，算法收斂速度慢，搜索時間長；② 傳統蟻群算法利用螞蟻的當前位置與下一位置的歐氏距離作為啟發信息函數，這使得螞蟻在搜索過程中容易出現停滯，陷入局部最優解；③ 此外，蟻群算法還存在計算量大，運算效率低等缺點。

發明內容

本發明提供一種基于改進蟻群算法的路徑規劃方法，通過該方法進行機器人的路徑規劃。本發明的技術方案是：一種基于基于改進蟻群算法的路徑規劃方法，所述方法步驟如下：

步驟一：采用柵格法對機器人的工作環境進行建模；

步驟二：設置起始點S，目標點G，最大迭代次數N_cmax，初始化全局信息素；

步驟三：使用一種改進的人工勢場法簡化初始地圖，減少蟻群算法探索的地圖范圍；

步驟四：將m只螞蟻置于起始點S，并將它們此時的位置加入禁忌表Tabu；基于傳統蟻群算法的基礎上引入A*算法的自適應啟發函數思想，考慮轉折角度，結合其計算螞蟻可能前往的下一節點j到目標點G的距離L_jG，綜合構造啟發信息函數，同時設計啟發函數遞增函數自適應調整啟發信息；在啟發信息函數和全局信息素的作用下，在輪盤賭法算法的基礎上進行改進自適應調整選擇概率，計算t時刻螞蟻k在節點i選擇下一個節點j的狀態轉移概率，選擇螞蟻下一個前往的節點j；螞蟻到達下一節點j后，更新禁忌表Tabu，將節點j加入禁忌表；

步驟五：判斷螞蟻是否到達目標點G；若是，停止搜索，一次迭代結束；否則，繼續按照步驟四的方法搜索直到找到目標點；

步驟六：在一次迭代結束，所有螞蟻到達目標點G后，綜合考慮路徑的長度、轉折數以及轉折角度來改進路徑的評價函數評價最優路徑，參考最優最差螞蟻系統原理，對全局排名前n的最優路徑，更新全局信息素，清空禁忌表Tabu；

步驟七：判斷當前迭代次數Nc是否到達最大迭代次數Ncmax，若是，輸出最優路徑，否則，轉到步驟三，直到Nc＝Ncmax，算法結束，輸出最優路徑。

所述改進人工勢場法具體如下：