[發明專利]一種基于自由空間與快速搜索隨機樹算法的無人車動態路徑規劃方法

在審

• 申請號: 202110006607.0
• 申請日: 2021-01-05
• 公開（公告）號: CN112833904A
• 公開（公告）日: 2021-05-25
• 發明（設計）人: 李昭瑩;石若凌
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 暫無信息
• 代理人: 暫無信息

本文發明公開了一種基于自由空間與快速搜索隨機樹算法的無人車動態路徑規劃方法。本文利用凹多邊形凸分解的圖形學方法，設計了一種在含有障礙地圖上構建自由空間的方法，并應用人工蜂群算法對進行路徑優化找出全局最優路徑。本文通過調整隨機樹節點采樣概率，實現了基于改進快速搜索隨機樹算法的快速路徑規劃方法。最后，本發明分別利用自由空間法和快速搜索隨機樹算法實現動態地圖的全局路徑規劃和無人車行進過程中的局部快速路徑規劃，兼顧了動態環境下路徑規劃的質量和速度。

1.技術領域

本發明涉及路徑規劃領域，尤其涉及動態環境下無人車行進過程中地圖發生變化的路徑規劃。

2.背景技術

自動駕駛技術是人工智能領域中的熱點方向，在未來社會中，大部分車輛將會配置自動駕駛技術，使得地面交通更加通暢、交通事故率更低。作為其中關鍵一環的動態環境路徑規劃方法，須要達到以下目的和要求：1)行駛路徑不與障礙物發生碰撞；2)路徑須連接起點與終點區域；3)路徑質量較高；4)動態規劃時間短。

現有的路徑規劃算法很難同時滿足上述要求，例如，RRT算法與A*算法容易陷入陷阱區域，且在復雜環境下規劃速度較慢；人工勢場法和粒子群算法易陷入局部最優解；柵格法易受柵格劃分精度的影響；V圖算法和切線法不適用于復雜地圖；自由空間法適用于復雜地圖，但由于自由空間原始構建邏輯略顯復雜且計算量較大，不適用于動態環境下的局部快速規劃。

3.發明內容

由于不同的路徑規劃算法特點各不相同，使用單一算法難以在動態環境下實現快速、高質量的響應。本發明結合自由空間法和快速搜索隨機樹算法，提供了一種既可以滿足路徑規劃質量，又可以在動態變化的環境中保證路徑規劃實時性的算法。在無人車啟動前，根據已知環境規劃出一條由起點至終點且不與障礙物發生碰撞的最優路徑，在無人車行進過程中，根據環境變換情況，利用局部快速規劃算法實時調整路徑。這樣既可以保證路徑質量接近最優，又可以利用局部快速路徑規劃算法完成快速響應。

本發明首先提出了一種基于自由空間法的全局最優路徑規劃算法，結合人工蜂群算法進行改進，自由空間法是一種基于圖形學的路徑規劃算法，這種算法可以在配合優化算法的基礎上得到全局最優路徑。然后還提出了一種基于快速搜索隨機樹算法的局部路徑規劃方法，通過調整隨機節點的采樣概率，得到一種可以在局部簡單地形的環境下進行快速路徑規劃的算法。最后，本發明結合以上兩種算法，實現了動態環境下的無人車路徑規劃。

4.附圖說明

圖1為：構造單連通多邊形示意圖

圖2為：凹凸頂點及多邊形正負判斷示意圖

圖3為：可見點判斷及最優可見點選擇示意圖

圖4為：全局搜索初始路徑示意圖

圖5為：路徑鄰域搜索示意圖

圖6為：快速搜索隨機樹生成過程示意圖

圖7為：改進自由空間法生成全局最優路徑示意圖

圖8為：環境動態變化示意圖

圖9為：改進RRT*算法生成局部路徑示意圖

圖10為：路徑調整示意圖

5.具體實施方式

5.1將地圖構建為單連通多邊形

自由空間法的基本思想為將地圖劃分為若干個由凸多邊形組成的自由空間，本文使用了凹多邊形凸分解算法，因此首先應將帶障礙物的地圖轉換為一個多邊形，其基本思想及步驟如下。