[發明專利]基于改進蟻群算法的移動機器人全局路徑規劃方法

在審

• 申請號: 201910456135.1
• 申請日: 2019-05-29
• 公開（公告）號: CN110196061A
• 公開（公告）日: 2019-09-03
• 發明（設計）人: 任紅格;史濤;胡鴻長;陳俊吉;劉尚瑜;洪濤;梁晨;吳啟隆
• 申請（專利權）人: 華北理工大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 唐山永和專利商標事務所 13103
• 代理人: 張皓清

本發明公開了一種基于改進的蟻群算法的路徑規劃方法,相對于傳統蟻群算法,修改螞蟻路徑搜索策略以跳出部分特殊形狀障礙物；修改傳統蟻群算法概率選擇公式中的啟發函數，將目標節點信息加入啟發函數中，加速算法收斂；修改傳統蟻群算法概率選擇公式中的揮發系數，將時間和空間信息加入揮發系數中，提高了算法的自適應性。通過以上改進之處,本發明能夠有效減少蟻群算法收斂時間,提高運行效率。

技術領域：

本發明涉及人工智能領域，具體設計一種基于改進蟻群算法的移動機器人全局路徑規劃方法。

技術背景：

移動機器人路徑規劃是機器人學研究領域中的一個重要組成部分，其任務是在具有障礙物的環境內，按照一定的評價標準(工作代價最小、行進路線最短等)尋找一條從起始狀態(包括位置和姿態)到目標狀態(包括位置和姿態)、與障礙物無碰的最短路徑。根據環境信息的已知程度不同，移動機器人路徑規劃又可分為環境已知的全局路徑規劃及環境未知的局部路徑規劃，全局路徑規劃主要分為兩個問題，環境構建與搜索算法，目前，可視圖法、柵格法等在環境構建中應用較多，對于搜尋路徑最優的算法，比較流行的是A^*算法、遺傳算法、蟻群算法等。

蟻群算法最早成功應用于解決著名的TSP(Travelling salesman problem)，該算法采用了分布式并行計算機制，易于和其他方法結合，而且具有較強的魯棒性,因此，也常常將蟻群算法應用到移動機器人路徑規劃上，但是傳統蟻群算法存在著前期搜索盲目性，收斂速度慢，易陷入局部最優點等問題，針對傳統蟻群算法應用于機器人路徑規劃存在的局限性，許多專利也對算法做出過相應改進，如公開號CN107272679A的專利通過對路徑拐點進行操作，減少冗余節點等的方式來改進蟻群算法；公開號CN108413963A的專利通過將機器學習思想融入蟻群算法中來改進蟻群算法；公開號CN108241375A的專利通過構建點對點自適應路徑選擇策略，以分段組合的狀態轉移優化方式來擇優選擇路徑點的方式來改進蟻群算法，但是，以上專利并沒有涉及對路徑搜索策略的改進，目前，尚未見到與本發明相似的專利記錄。

發明內容：

針對傳統蟻群算法應用于機器人路徑規劃的局限性，本專利提出一種改進蟻群算法，修改算法路徑搜索策略、啟發函數以及信息素揮發系數，增強了算法的搜索效率，加速了算法的收斂，提高了算法的自適應性，一種基于改進蟻群算法的移動機器人全局路徑規劃方法，包括以下步驟：

(1)利用柵格法對地圖環境進行建模，設置起點，終點以及障礙柵格；

(2)算法流程及各參數初始化；

(3)循環次數Nc＝Nc+1，k＝1；

(4)螞蟻數目k＝k+1；

(5)螞蟻個體根據狀態轉移概率公式計算的概率，使用輪盤賭法，選擇下一步可行點并前進；

(6)修改禁忌表指針，既選擇好可行點之后將螞蟻移動到新的柵格，并把該點加入到此螞蟻個體的禁忌表中；

(7)按改進的螞蟻搜索策略進行路徑搜索。按改進的螞蟻搜索策略進行路徑搜索，如果螞蟻搜索到終點或陷入特殊類型障礙物中，返回步驟(4)；如果搜索既為搜索到終點，又沒有陷入特殊類型障礙物，則返回步驟(5)；

(8)如果k>m，m為螞蟻數目，既一次迭代過程中搜索的次數，按信息素更新策略更新路徑信息素并返回步驟(3)；

(9)如果Nc>Nc_max，輸出算法計算結果，算法結束。

采用上述技術方案的本發明，與現有技術相比，其突出的特點是：