[發明專利]一種基于交流策略蟻群算法的移動機器人路徑規劃方法

有效

• 申請號: 202010893573.7
• 申請日: 2020-08-31
• 公開（公告）號: CN112000105B
• 公開（公告）日: 2021-07-06
• 發明（設計）人: 侯文彬;熊志華;王長生
• 申請（專利權）人: 大連理工大學;大連理工大學寧波研究院
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 李曉亮

本發明提供了一種基于交流策略蟻群算法的移動機器人路徑規劃方法，屬于機器人路徑規劃領域。該方法通過賦予螞蟻交流的能力，充分利用已經探索的路徑，不僅避免了基本蟻群算法的上述缺點，更能有效快速地進行最優路徑的探索，極大地提高了算法的尋優性能和穩定性；本發明提出了自適應死鎖螞蟻懲罰策略、啟發式信息可調節衰減策略、信息素雙重獎勵策略和基于放大乘子的改進輪盤賭法路徑選擇策略，既減少了螞蟻死鎖現象，提升了算法多樣性，又加速了最優路徑信息素濃度積累，賦予算法更快的收斂速度和更穩定的全局尋優能力，極大地提高了蟻群算法的整體性能。

技術領域

本發明屬于機器人路徑規劃領域，涉及一種基于交流策略蟻群算法的移動機器人路徑規劃方法。

背景技術

路徑規劃是移動機器人導航領域中最重要的部分。其主要目的是在給定環境中找到起點和目標之間的最佳無碰撞路徑。機器人路徑規劃技術可分為經典方法和啟發式方法兩大類。經典方法主要包括細胞分解方法(CD)、勢場方法(PFM)、子目標方法(SG)和基于采樣的方法等。啟發式算法主要包括神經網絡(NN)、模糊邏輯(FL)和自然啟發方法(NIM)以及混合算法等。經典方法由于難以在路徑搜索效率和路徑優化方面進一步提高，使用率逐漸降低。而啟發式方法得益于良好的全局優化能力和并行性等特點，在路徑規劃領域越來越流行。

蟻群算法是M.Dorigo等學者提出的一種分布式自然啟發方法。該算法模擬了螞蟻協作覓食行為的性質，具有正反饋、高魯棒性和并行性的優點。蟻群算法在其他群體智能系統中處于領先地位，已成功用于解決許多組合優化問題，并逐漸應用于移動機器人導航領域。

盡管蟻群算法在路徑規劃任務中表現出若干良好的性能，但仍然存在搜索效率低、收斂速度慢、容易停滯和局部最優解等缺點。為了提高算法的性能，許多研究人員在信息素設置、搜索策略、路徑選擇方法、啟發式信息等方面進行了改進。Zhao Jiang等引入了不均分分布的初始信息素和帶方向的啟發式信息，有效減少了搜索的盲目性。Wu Xiao Xu等應用了回滾策略使得更多螞蟻可以到達目標，應用死亡策略減少了無效信息素對蟻群進化的影響。Wang Hong Jian等采用改進的偽隨機比例規則選擇螞蟻狀態轉移，極大地提高了蟻群算法的收斂速度。Yue Long Wang等通過懲罰策略對較差路徑進行信息素揮發，提高了螞蟻探索的利用率。Chen Guo Liang等基于無限步長原理提高啟發式信息可見性，并利用動態調整的信息素更新規則和蒸發速率加快了收斂速度。Dai Xiao Lin等利用A*算法的評估函數和彎曲抑制算子改進啟發式信息，加快了收斂速度并提高了全局路徑的平滑度。Luo Qian等對蟻群算法做了多方面的改進，將衰減因子引入啟發式信息，并采用自適應函數調整狀態選擇的偽隨機比例，顯著提高了全局最優解搜索能力和丟失螞蟻數量等性能指標。

當前蟻群算法的最佳路線主要是通過評估螞蟻在路徑上沉積的信息素數量而獲得的，并未考慮螞蟻個體之間的直接互動交流。這導致在實際操作中，經常出現歷代螞蟻路線中隱藏更優路線未被探索的現象。從行為的本質上講，螞蟻之間的直接互動交流使它們有更大的可能找到巢穴和食物來源之間的最短路徑。本發明通過建立螞蟻交流機制和交流策略，提出一種基于交流策略的增強型蟻群算法；解決了遺漏更優路線問題，提高了算法性能。本發明所述的算法還可應用于無人機導航、無人駕駛等涉及路徑規劃的領域。

發明內容

本發明旨在解決上述現有的技術問題，公開了一種基于交流策略的蟻群算法用于移動機器人路徑規劃。本發明的技術方案如下：

一種基于交流策略蟻群算法的移動機器人路徑規劃方法，該方法包括以下步驟：

S1，設置地圖任務

根據機器人的工作環境建立地圖坐標系，以橫向為x軸，豎向為y軸，并把地圖劃分為均勻的網格節點，依次按x軸正向和y軸負向進行編號并獲取對應的坐標值；對可行點和障礙物進行二進制處理，可行點的值為0，障礙物的值為1；然后根據任務在地圖上設置起始點S和目標點E；

S2，初始化基本參數