[發明專利]一種基于概率模型的路徑規劃方法、系統及介質

在審

• 申請號: 202111157218.4
• 申請日: 2021-09-30
• 公開（公告）號: CN113741484A
• 公開（公告）日: 2021-12-03
• 發明（設計）人: 龔文勇;吳小天
• 申請（專利權）人: 暨南大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李斌

1.一種基于概率模型的路徑規劃方法，其特征在于，包括下述步驟：

給定地圖或點云上的起點和終點位置；

多次執行改進的RRT算法；

根據改進的RRT算法的隨機性質構造概率轉移矩陣；

基于概率轉移矩陣以及概率模型進行路徑規劃；

在所得路徑規劃結果中，基于push動態規劃算法進行最優路徑計算，得到最優路徑。

2.根據權利要求1所述一種基于概率模型的路徑規劃方法，其特征在于，所述改進的RRT算法具體為：

設起始位置為S₀，目標位置為S_t，最大步長為M，迭代以下步驟K次，得到RRT樹T：

隨機初始化一棵樹T＝S₀；

生成隨機狀態x_r；

找到T中最近的節點x_n；

在區間[1，M]中生成隨機數r_n；

用r_n生成新的可行狀態x_p；

將x_p插入到T中。

3.根據權利要求1所述一種基于概率模型的路徑規劃方法，其特征在于，所述構造概率轉移矩陣具體為：

設S_i為地圖上給定的一個點，由改進的RRT算法計算得其可供轉移的位置個數最多為z_i＝M²-1個，記此z_i個可供轉移的位置為

執行改進的RRT算法足夠多的次數，統計得從S_i轉移到S_i，j的次數t_i，j；

令則從S_i轉移到S_i，j的概率為p_i，j＝t_i，j/t_i；

概率轉移矩陣P定義為矩陣(p_i，j)，即矩陣P的位置(i，j)處的值為p_i，j，若p_i，j不存在，則對應位置為0。

4.根據權利要求1所述一種基于概率模型的路徑規劃方法，其特征在于，所述基于概率轉移矩陣以及概率模型進行路徑規劃具體為：

設給定的起始位置S₀和目標位置S_t之間存在N_p-1個點連成的無碰撞路徑曲線，則從S₀和目標位置的路徑曲線表示為度量路徑S的發生概率為：

為尋找最優的路徑S^*，使得M(S^*)最大，由上式取對數并取反得：

對E(S)求極小值即得基于RRT算法的確定性路徑規劃結果。

5.根據權利要求1所述一種基于概率模型的路徑規劃方法，其特征在于，所述進行最優路徑計算具體為：

若S_k為最優路徑S^*上的點，則：

D^*(S₀，S_j)＝D^*(S₀，S_j-1)+d(S_j-1，S_j)；

函數表示點S₀到點的最優路徑，式D^*(S₀，S_j)＝D^*(S₀，S_j-1)+d(S_j-1，S_j)為動態規劃的泛函方程，其中d(S_j-1，S_j)為邊(S_j-1，S_j)的邊長或權重。