[發明專利]一種基于Dsl_GA算法的移動機器人路徑規劃方法

在審

• 申請號: 202011230415.X
• 申請日: 2020-11-06
• 公開（公告）號: CN112504274A
• 公開（公告）日: 2021-03-16
• 發明（設計）人: 路瑞;張兆軍;趙明龍
• 申請（專利權）人: 江蘇師范大學
• 主分類號: G01C21/20
• 分類號: G01C21/20;G06N3/00;G06N3/12
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 馬進

一種基于Dsl_GA算法的移動機器人路徑規劃方法，包括采用柵格法對移動機器人的工作環境進行建模；使用實數編碼和二維坐標法對自由柵格進行編碼；隨機選取自由柵格作為路徑的中間節點，再利用Dstar_lite算法補齊起始節點、中間節點、終止節點之間的路徑，從而形成一條從起始節點到終止節點不經過任何障礙物的可行連續路徑；設置歐式距離為適應度函數；采用錦標賽選擇法和最優保護策略作為選擇操作、算術交叉、隨機變異的方式對初始化種群進行遺傳操作；最后通過仿真實驗表明本文提出算法的有效性和可行性。本發明增加了生成路徑的可行性，為解決路徑規劃問題提供了新的思路。

技術領域

本發明屬于機器人領域，涉及一種基于Dsl_GA算法的移動機器人路徑規劃方法。

背景技術

隨著科學技術的快速發展，優化方法已經成功地應用于自動控制、圖像處理、組合優化、數據挖掘、國防軍事、人工智能、交通運輸、電子科學等領域。國內外許多專家學 者從自然界和仿生學中得到啟發，提出了一系列群體智能優化算法，其中包括：蟻群算法、 粒子群算法、遺傳算法、布谷鳥算法以及狼群算法等。其中，蟻群算法在求解性能上，具 有很強的魯棒性，但存在計算量過大、搜索時間過長等缺陷；粒子群算法長用來求解連續 問題，但容易陷入局部最優，局部尋優能力較差。

從上個世紀60年代起，許多學者就開始了對機器人的研究。截止至今，機器人已經成功地應用于交通運輸、工業生產、醫療、人工智能等各個領域。機器人路徑規劃是機器 人的一個重要環節，其目標是找到一條從起始節點到終止節點不經過任何障礙物的可行路徑。而對機器人路徑規劃的研究一直是國內外機器人領域的重要內容。從當前的研究成果來看，以遺傳算法、蟻群算法、粒子群算法為代表的群體智能優化算法應用于機器人路徑規劃領域取得了不錯的進展。

遺傳算法作為群體智能優化算法的主要算法之一。相比其他算法而言，遺傳算法憑 借這能夠從多個初始解開始搜索，容易跳出局部最優、具有較好的全局尋找最優解的能力、 天生的并行性并廣泛地應用于機器人路徑規劃問題。

發明內容

本發明的目的是提供一種基于Dsl_GA算法的移動機器人路徑規劃方法。該算法通過隨機選取自由柵格和Dstar_lite算法相結合的方式，隨機生成適應度不同的初始種群，然 后，通過錦標賽選擇法和最優保護策略、算術交叉、隨機變異優化初始種群，得到一條從起點到終點不經過任何障礙物的最優路徑，增加了生成路徑的可行性，為解決移動機器人路徑規劃問題，提供新的解決思路。

本發明采用的技術方案是：一種基于Dsl_GA算法的移動機器人路徑規劃方法，包括如下步驟：

S1：本發明采用柵格法對移動機器人的工作環境進行建模；

S2：本發明按照從下到上、從左到右的順序使用實數編碼和二維坐標法對自由柵格 進行編號；

S3：設置初始化參數。設置移動機器人的起點、終點、種群數量、迭代次數、代溝、交叉率、變異率和中間節點的個數；

S4：隨機生成初始化種群，生成初始路徑；

S5：計算適應度值；

S6：執行選擇操作，對初始化種群生成的中間節點進行更新；

S7：執行交叉操作，對選擇操作生成的中間節點進行更新；

S8：執行變異操作，對交叉操作生成的中間節點進行更新；

S9：判斷是否達到最大迭代次數，若是則停止搜索，輸出全局最優路徑，否則跳轉至S5進行下一次迭代。

根據權利要求1所述的一種基于Dsl_GA算法的移動機器人路徑規劃方法，其特征在于，所述步驟S1的柵格法建模具體為：

將機器人的工作環境劃分為一系列大小相等的柵格，其中，黑色柵格表示障礙物，機器人不可以通行；白色柵格表示自由柵格，機器人可以通行。