[發明專利]一種基于柵格地圖模型的改進AGV路徑規劃算法

在審

• 申請號: 202110375481.4
• 申請日: 2021-04-07
• 公開（公告）號: CN113093758A
• 公開（公告）日: 2021-07-09
• 發明（設計）人: 馮子驍;陳澤宇
• 申請（專利權）人: 河海大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 北京盛凡智榮知識產權代理有限公司 11616
• 代理人: 孫鑫

在傳統自動引導小車路徑規劃研究方法中，針對環境模型多為正方形柵格導致模擬效果差的問題，提出了一種基于蜂巢柵格形狀的地圖模型，并針對傳統蟻群算法求解路徑規劃問題時效率低下且結果不穩定的缺點，提出了一種基于改進型蟻群算法的AGV路徑規劃方法。首先，利用蜂巢柵格對環境進行模型建立，再使用改進型蟻群算法，根據每只螞蟻和每次迭代的評估，使用不同的信息素更新規則來得到最終路徑。實驗結果表明改進型蟻群算法解決了傳統蟻群算法不能較好收斂的問題，并能獲得更短的規劃路徑。再和相關文獻算法的結果進行對比，發現在使用此改進型蟻群算法能在算法前期獲得更好的路徑采集效果，在算法后期能獲得更好的收斂效果。

技術領域

本發明涉及計算機算法領域，尤其涉及一種基于柵格地圖模型的改進AGV路徑規劃算法。

背景技術

自動引導小車(Automated Guided Vehicle，AGV)最早出現于上世紀五十年代，是一種智能化物料自動搬運設備，其特點在于自動化程度高、易于控制、節省勞動力、提高運輸效率、占地空間小等，因此，AGV在眾多生產制造物流行業中得到了廣泛應用。在汽車制造行業中，物流領域自動化設備應用的是大勢所趨，使用AGV替代人力能夠降低汽車制造企業的運輸成本，提升服務質量。對煙草、醫藥、食品和化工等行業而言，業內對搬運任務有清潔、無排放污染、安全等要求，AGV能夠較好的勝任。在倉儲業中，AGV使用程度更為廣泛，因為AGV有較強自動化水平和較高柔性，在倉儲物流行業中能夠降低人力成本，提高運輸效率。在AGV的使用中，進行合理的路徑規劃對于降低企業運營成本，提高利潤率有重大作用，因此AGV的路徑規劃問題十分值得研究。

為了計算得到全局最優路徑，目前采用的方法主要有遺傳算法、粒子群算法、快速擴展隨機樹尋路算法和蟻群算法。之后的研究主要針對這幾種算法進行改進，改進遺傳算法減少了最短路徑的路程，提高算法的收斂速度和效率。改進粒子群算法提高了在AGV在規避障礙時搜得解的精度。快速擴展隨機樹尋路算法使得在復雜環境下機器人的運行更加平穩，且在一定程度上縮短了路徑長度。融合粒子群與蟻群算法提升了蟻群算法的整體性能。對于傳統蟻群算法收斂性差，容易陷入局部最優，結果不穩定的缺點，則考慮在對螞蟻和迭代質量的評估之后，對每一次尋路的信息素進行區別更新，有利于擴大算法前期的搜索范圍，加強算法后期的收斂性，提高算法的穩定性。

綜上所述，以上所用方法是目前解決AGV路徑規劃問題中普遍認可的，較優的算法，但是傳統算法存在容易進入局部最優解，收斂性較差和搜尋結果穩定性差的問題。基于此提出了改進型蟻群算法，使用兩次評估來合理區分蟻群，根據區分結果使用不同的信息素更新方式，以此實現提高算法解的多樣性，收斂性和穩定性的目標。此外使用蜂巢柵格建立地圖模型，使得模型更加實際可靠，能提高AGV小車行駛時的平穩性，并降低避險路徑的長度。

發明內容

本發明的目的是解決現有AGV路徑規劃中存在的容易陷入局部最優解的缺陷，而提出一種基于柵格地圖模型的改進AGV路徑規劃算法。

為了實現上述目的，本發明技術方案如下：

本系統的設計主要分為如下幾個部分：首先，對環境模型進行建立并進行預處理；接著，對蟻群進行評估分類，減小算法前期多樣性和后期收斂性的影響；再結合信息素更新規則對不同蟻群采取不同的信息素更新規則；最終將數據放入Matlab軟件中模擬仿真，得出結果。

環境模型進行建立并進行預處理大致流程為：在常用的空間移動環境模型中，選擇出具有簡單、容易表達和靈活等優點的柵格法，并在傳統的柵格基礎上，模擬蜂巢建立起正六邊形的柵格。

接下來，對蟻群進行評估分類。在對蟻群評估分類的過程中，傳統的蟻群算法信息素的更新完全根據路徑長度，也有學者研究了改良的信息素更新規則來優化蟻群算法，但是在算法前期多樣性和后期的收斂性方面還有待提高，針對這個問題，在考慮螞蟻的動態分級之上，考慮每一次迭代的質量，將每一次的迭代性質分為尋優和偵察，不同性質的迭代采用不同的信息素更新規則，來提高前期解的多樣性和后期解的收斂性。