[發明專利]一種非均勻采樣FMT*的移動機器人路徑規劃方法

有效

• 申請號: 202011251462.2
• 申請日: 2020-11-11
• 公開（公告）號: CN112286202B
• 公開（公告）日: 2021-07-27
• 發明（設計）人: 陳彥杰;吳錚;林依凡;黃益斌;何炳蔚;林立雄
• 申請（專利權）人: 福州大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 郭東亮;蔡學俊

本發明提出一種非均勻采樣FMT*的移動機器人路徑規劃方法，包括如下步驟：步驟S1、地圖初始化；步驟S2、建立廣義Voronoi圖，即GVG；步驟S3、尋找初始化路徑并實現最優路徑與初始路徑同倫；步驟S4、安全隧道建立；步驟S5、非均勻采樣；步驟S6、構造采樣集合、探索集合、已探索集合；步驟S7、搜索采樣集合的節點，組成集合；步驟S8、探索中點組成集合；步驟S9、計算所有點到點的代價，實現算法的漸進最優；步驟S10、判斷與是否有障礙物并針對結果進行處理；步驟S11、將所需的Z從放入；步驟S12、若Z是是目標點則返回路徑解，若否則返回步驟S7繼續；步驟S13、機器人對可行路徑解進行處理；本發明算法收斂速度快于FMT*，能快速得到最優解，在單查詢規劃中具有優勢。

技術領域

本發明涉及移動機器人路徑規劃技術領域，尤其是一種非均勻采樣FMT*的移動機器人路徑規劃方法。

背景技術

現如今智能機器人為人類提供的服務都將自動導航作為機器人的重要功能之一，如自動駕駛、空中無人機和服務機器人等領域。而路徑規劃作為其導航的主要部分之一，旨在讓對象在規定的運行空間范圍內找到一條從起始目標到終止目標的無碰撞安全路徑，即為機器人在復雜環境中運動尋找無碰撞路徑，同時要優化機器人的運動路徑，使其盡可能達到更短、更平滑的要求。因此，智能機器人和無人操作技術的發展在很大程度上取決于能否更快地為運動規劃問題提供切實有效的方案。

路徑規劃發展迅速，已產生許多規劃算法。基于采樣的算法，如快速探索隨機樹(RRT)，概率路線圖(PRM)，以及它們的變體，因其能夠有效地解決約束動力學和高維空間規劃問題而越來越受歡迎。在許多應用領域，除了生成可行的解決方案路徑之外，還需要獲得高質量的求解路徑，因此具有漸近最優性的方法，如RRT*和PRM*被提出，使得采樣算法成為應用最廣泛的算法之一，然而，采樣算法的一個局限性是它們收斂到最優解的速度緩慢，需要大量的迭代過程或樣本，漸近地找到規劃問題的最優解。在實際應用中，如無人機或移動機器人，為了節省時間或電源，需要快速計算一條較短的路徑來確保工程的實施。

樣本偏置是一種常見的方法，方法試圖通過偏置手段將采樣點分布在有利的區域來進行探索。例如，Rodriguez,S.等人提出的Obstacle-Based RRT或者K.Cao等人提出的基于混合偏置的PRM是利用障礙物的信息，或在障礙物附近增加采樣概率來指導采樣過程，主要應用于環境存在狹窄通道的問題，但這只提高了計算效率，確保算法的成功率。X.Zhao等人提出的混合高斯模型進行偏差采樣，可以有效地利用局部空間，同時保持全局路徑規劃的效率。結合啟發式的樣本偏置控制采樣區域，對樣本進行啟發式估計進行篩選；例如A.Yershova andL.Jaillet等人的Dynamic-Domain RRTs及其自適應版本通過在障礙物近處形成小區域來進行局部采樣，指導算法擺脫陷阱問題，然而，RRT的使用意味著該解決方案幾乎肯定是次優。

基于局部采樣對配置空間中的有效軌跡進行采樣也是常見方法，InformedAnytime Fast Marching Tree(IAFMT*)根據尋找到的初始路徑來構造橢圓啟發式區域，一旦找到初始解決方案，算法將在區域內繼續迭代或采樣，這增加了改進當前路徑的概率，并收縮區域范圍，從而收斂路徑到最優，能夠有效的提高FMT*算法的收斂速度，但當路徑彎曲復雜時，形成的橢圓區域大于地圖，那么區域無法收縮導致無法起到提速的作用。基于Motion Planning using Lower Bounds(MPLB)[26]的FMT*上，通過求解一系列獨立的問題來實現，并且只有在子問題解決后才能返回更好的解，同時減少最近鄰查詢來減少時間的損耗，提高算法收斂速度。Safety certificates利用每個采樣點與障礙物形成的自由區域，來減少區域中樣本的碰撞檢測次數，隨著樣本覆蓋整個空間，碰撞檢測次數將為零，從而提高算法的計算效率。