[發明專利]一種基于RRT算法改進的車輛規劃算法

有效

• 申請號: 202010104879.X
• 申請日: 2020-02-20
• 公開（公告）號: CN111207767B
• 公開（公告）日: 2023-06-16
• 發明（設計）人: 吳迪;鄭亞楠;王欣;胡順奇
• 申請（專利權）人: 大連理工大學
• 主分類號: G01C21/34
• 分類號: G01C21/34;G01C21/30;G06F16/29
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 李曉亮;潘迅

一種基于RRT算法改進的車輛規劃算法，屬于路徑規劃領域，包括兩個階段，第一階段找到一定數量的引導根節點。首先，已知在地圖上的障礙物的數量、分布情況，起始節點與目標節點，通過計算和碰撞檢測得到引導根節點的集合，該引導根節點分布在起始節點指向目標節點的路徑上，具有導向性且不與周圍的障礙物發生碰撞。第二階段，將起始節點、目標節點和引導根節點放入一個根節點的集合中，逐個開始擴展節點，引導樹的生長，當兩棵樹的葉子節點的最近距離小于等于步長，就將兩棵樹合并為一棵樹。當所有的樹合并成為一棵樹，即同時含有起始節點與目標節點，則尋路成功。本發明在原有的RRT路徑規劃算法上進行改進，使得在復雜路況也可以快速尋徑，快速收斂。

技術領域

本發明屬于路徑規劃領域，涉及一種快速擴展隨機樹算法(Rapidly-exploringRandom?Tree，RRT)的改進，尤其涉及一種基于RRT算法改進的車輛規劃算法MT-RRT。

背景技術

近幾年無人駕駛技術發展的非常迅速，路徑規劃作為其中的重點技術，也得到了廣泛的關注與發展。車輛的路徑規劃是為了在復雜的環境中為車輛從起始位置到目標位置規劃出一條可以通過的與障礙物沒有碰撞的路徑。目前的路徑規劃算法的種類有很多種，常用的主要包括蟻群算法，A*算法，人工勢場法，遺傳算法以及RRT算法等等。

關于RRT算法的改進目前也有非常多種，Urmson等人提出具有節點偏置概率的hRRT算法，使擴展更具有目的性增強節點的利用率。Frazzoil提出了具有漸進最優性的RRT*算法，基于均勻的采樣，在RRT節點擴展基礎上添加隨機幾何圖形與剪枝算法優化理論，確保隨機樹的節點可以收斂到當前最優值，但是節點的計算量很大。除此之外還有SRRT算法，RRT-Connect算法等。以上對RRT算法的改進分別從對隨機點的采樣是否均勻，步長是否動態變化，擴展的方向做出了不同程度的改進，來提高算法的性能。還有一種針對RRT算法的改進主要是通過與其他路徑規劃算法的融合，比如與A*算法，與人工勢場算法的融合。文章提出的MT-RRT算法計算一定數目的根節點來生成局部生成樹，提高算法的導向性，增強節點的利用率，加快算法的收斂速度。

發明內容

針對RRT算法節點利用率低，區域搜索重復度高，缺少目的性以及收斂速度慢的問題，本文提出了一種基于RRT算法進行改進的MT-RRT算法，該方法的全稱為基于多向的快速擴展隨機樹(Multi-Targeting?Rapidly-exploring?Random?Tree，MT-RRT)。即通過計算在目標路徑上的一定數量的無碰撞引導根節點，生成多棵局部生成樹最終合并為一棵樹找到一條可通過的路徑。

為了達到上述目的，本發明采用的技術方案為：

一種基于RRT算法改進的車輛規劃算法MT-RRT，用于解決車輛的路徑規劃問題，即從起始位置向目標位置規劃出一條無碰撞的路徑，步驟如下：

步驟一：已知障礙物的數量、分布情況、起始節點與目標節點，判斷起始節點到目標節點的距離是否小于步長和是否與障礙物發生碰撞：如果距離小于步長并且沒有與周圍障礙物發生碰撞，直接連接起始節點與目標節點，此時直接連接起始節點，與目標節點，尋路完成。否則調用計算引導根節點的方法(collisionZ(x_init,x_goal,Map)方法)得到一定數目的引導根節點，放入集合中。該方法具體步驟如下：

(1.1)調用collisionZ(x_init,x_goal,Map)方法，輸入起始節點目標節點，地圖上障礙物的數量，分布情況。連接起始節點x_init與目標節點x_goal得到直線l，計算直線的斜率與截距。