[發明專利]一種結合運動控制的改進A*的AGV路徑規劃方法

有效

• 申請號: 202110605550.6
• 申請日: 2021-05-31
• 公開（公告）號: CN113359721B
• 公開（公告）日: 2022-10-25
• 發明（設計）人: 危淵;武彤暉;劉瑾瑜;鐘夢溪
• 申請（專利權）人: 西安交通大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 閔岳峰

本發明一種結合運動控制的改進A＊的AGV路徑規劃方法，包括：步驟1，根據任務需求以及AGV性能，計算出AGV平滑左轉和平滑右轉的運動控制，滿足AGV轉彎前后速度不變；步驟2，根據步驟1的運動控制，得出AGV的最小轉彎半徑，對任務區域柵格化處理，并對A*算法中相鄰節點的定義進行修改；步驟3，基于步驟1的運動控制以及步驟2的柵格處理，利用改進A*算法對任務區域進行路徑規劃，計算出一條平滑路徑；步驟4，對步驟3規劃出的路徑刪除冗余路徑點；步驟5，基于步驟4的路徑點，AGV根據路徑點的速度標志量進行運動控制，完成作業。本發明通過運動控制與路徑規劃結合的方式對傳統A*算法進行改進，在滿足任務需求和計算性能的約束條件下，完成規劃任務。

技術領域

本發明屬于移動機器人領域，具體涉及一種結合運動控制的改進A * 的 AGV路徑規劃方法。

背景技術

路徑規劃與運動控制均是移動機器人領域的關鍵技術。路徑規劃技術指的是在某一指標下(指標常為路徑總長度、機器人能耗或移動時間等)，在任務區域內生成一條從起點到終點的最優或次優路徑，該路徑能滿足最基本的避障要求；運動控制則指的是控制移動機器人按照路徑規劃算法規劃出的避障路徑行駛的運動方法。

隨著計算機技術、人工智能算法和傳感器技術的不斷發展，適用于AGV路徑規劃的理論研究也不斷深入。目前常用的路徑規劃算法有遺傳算法、快速隨機搜索樹、人工勢場法和A*算法等。遺傳算法受達爾文進化論的啟發，利用遺傳時的交叉變異和遺傳特性，得出每一代的候選解，最終從其中求出最優解。該算法運行效率低，收斂速度慢，并且易于陷入局部最優解；快速隨機搜索樹基于隨機采樣的思想，同樣容易陷入局部最小值問題，并且其搜索時盲目性太大導致在某些環境中耗時較長；人工勢場法創造性地將環境視為一個勢場，AGV的運動由終點產生的引力與障礙物產生的斥力共同操控，結構簡單的同時給其帶來了不少缺陷，比如容易發生“震蕩”現象，求出的路徑也往往不是最優路徑，甚至停滯在局部最優解；A*算法是一種啟發式算法，需要對環境進行柵格化處理，隨著柵格地圖尺度的增長，其計算效率明顯下降，并且生成的路徑存在“僵硬”的折線，不便于AGV的運動控制。其中，A*算法鑒于其在靜態環境下的最優性，一經提出便被大量地應用在實際的路徑規劃研究中。

此處需要對A*算法流程進行簡單描述。傳統的A*算法繼承保留了Dijkstra算法的流程，在保證求得最優路徑的基礎上，采用了啟發式搜索，其主要流程如圖1所示。該算法共需維護OPEN和CLOSED兩個列表。初始時，將起點作為第一個節點加入OPEN列表中，其代價值由公式f(n)＝g(n)+h(n)計算而來，g(n) 為起點至當前節點的距離，h(n)為當前節點至終點的啟發函數，常選用歐式距離或曼哈頓距離，顯然，起點的g(n)為0，其父節點設為空，之后便進入循環：取出當前OPEN列表中代價值最小的節點，設為當前節點n，放入CLOSED列表中。根據不同的代價函數計算方式，計算并更新當前節點n的所有相鄰可行節點(可行節點是指該相鄰節點可供AGV通過，如非過界部分和非障礙物部分等) 的代價值及其父節點，更新方法為，選取使該節點代價值更小的節點作為該節點的父節點。更新完所有相鄰節點后，將這些節點包含其父節點信息和代價值均加入到OPEN列表中，再進入循環迭代。若某次循環后，當前節點n為終點，則直接將其加入CLOSED列表中，并通過逆向搜索父節點的方式，獲得完整路徑；若在未達到終點時，OPEN列表已經為空，則表明當前環境不存在一條從起點到終點的路徑，算法結束。