[發明專利]一種改進拓展式RRT路徑規劃方法、系統及裝置

在審

• 申請號: 202010480397.4
• 申請日: 2020-05-30
• 公開（公告）號: CN111707264A
• 公開（公告）日: 2020-09-25
• 發明（設計）人: 劉成菊;姚陳鵬;陳啟軍
• 申請（專利權）人: 同濟大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 上海科盛知識產權代理有限公司 31225
• 代理人: 丁云

本發明涉及一種改進拓展式RRT路徑規劃方法、系統及裝置。所述的改進拓展式RRT路徑規劃方法包括如下步驟：步驟S1、將起點x_start加入隨機樹；步驟S2、生成隨機點x_rand并判斷其是否有效，有效則將隨機點x_rand加入隨機樹，否則舍棄該隨機點x_rand并重復步驟S2直至獲取有效的隨機點x_rand；步驟S3、以步驟S2獲得的有效的隨機點x_rand為中心向周側進行隨機點拓展，并將拓展的有效隨機點加入隨機樹中，判斷目標點x_goal是否在隨機樹中，若是，則執行步驟S4，否則，返回步驟S2；步驟S4、從目標點x_goal開始向起點x_start追溯父節點作為最終路徑。與現有技術相比，本發明具有效率高、搜索速度快、在狹窄通道情況下的成功率高等優點。

技術領域

本發明涉及機器人控制技術領域，尤其是涉及一種改進拓展式RRT路徑規劃方法、系統及裝置。

背景技術

規劃算法被廣泛應用于機器人導航，電腦游戲等多種領域之中，快速拓展隨機樹算法(Rapidly-exploring Random Tree，RRT)作為最常見的規劃算法之一，具有覆蓋率高，搜索范圍廣等有優點，但由于RRT是一種基于采樣的算法，其僅僅具有概率完備性，尤其對于類似狹窄通道的環境，難以得到可行解。

針對此問題，諸多學者做出了相應的改進。雙向RRT(RRT-connect)同時從起點和終點開始以對方為終點拓展隨機樹，并在兩棵隨機樹相連時完成搜索，該方法在加速了搜索的同時，對狹窄通道情況有一定作用，但效果甚微。DD-RRT(Dynamic-Domain RRT)在多次連接采樣點失敗后，認為搜索陷入困境，隨機樹拓展至狹窄通道附近，通過動態調整下一次采樣的范圍來增加其進入狹窄通道的可能性，但該算法對于搜索范圍的半徑選擇較為敏感，不當的半徑選擇可能反而導致算法陷入困境，無可行解。DD-RRT僅僅通過采樣失敗次數來判定隨機樹拓展的情況，該判定方法較為粗糙，相對的，RRV(Rapidly-exploring RandomVines)在連接采樣點失敗后，并不直接舍棄，而是在以該點為中心，設定值為半徑的圓內進行采樣，通過對采樣點進行主成分分析進一步區分采樣點位于障礙物前，位于狹窄通道前，還是位于通道內，并針對不同的情況進行特定的處理，以保證隨機樹順利的向狹窄通道內進行延展。然而，RRV雖然在狹窄通道情況下有較好的效果，但在普通情況下的效果反而不如RRT，且計算繁瑣，可能出現誤判。

現有改進RRT算法雖然在一定程度上改善了原有算法在狹窄通道情況下的窘境，但受到參數選擇以及環境限制等因素的影響，效果有限。

發明內容

本發明的目的就是為了克服上述現有技術存在的缺陷而提供一種效率高、搜索時間短的改進拓展式RRT路徑規劃方法、系統及裝置。

本發明的目的可以通過以下技術方案來實現：

一種改進拓展式RRT路徑規劃方法，該方法包括如下步驟：

步驟S1、將起點x_start加入隨機樹；

步驟S2、生成隨機點x_rand并判斷其是否有效，有效則將隨機點x_rand加入隨機樹，否則舍棄該隨機點x_rand并重復步驟S2直至獲取有效的隨機點x_rand；

步驟S3、以步驟S2獲得的有效的隨機點x_rand為中心向周側進行隨機點拓展，并將拓展的有效隨機點加入隨機樹中，判斷目標點x_goal是否在隨機樹中，若是，則執行步驟S4，否則，返回步驟S2；

步驟S4、從目標點x_goal開始向起點x_start追溯父節點作為最終路徑。