[發明專利]基于等步采樣A*算法的無人駕駛局部路徑規劃方法

有效

• 申請號: 201810112446.1
• 申請日: 2018-02-05
• 公開（公告）號: CN108444488B
• 公開（公告）日: 2021-09-28
• 發明（設計）人: 王一晶;劉正璇;左志強
• 申請（專利權）人: 天津大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 劉國威

本發明屬于無人駕駛路徑規劃領域，為滿足汽車的運動學約束與實際交通限制，本發明，基于等步采樣A*算法的無人駕駛局部路徑規劃方法，具體步驟如下：步驟1：定義搜索步長和搜索安全域；步驟2：確定局部柵格圖中路徑搜索的起始點與目標點；步驟3：建立Open列表和Closed列表；步驟4：求解Open列表中柵格點的代價函數；步驟5：從Open列表中選擇代價函數值最小的柵格點；步驟6：分別考察當前節點的所有安全相鄰節點；步驟7：搜索過程中當前節點無子節點的處理；步驟8：重復步驟5?7的過程，直到滿足條件，返回可行路徑，或返回搜索失敗。本發明主要應用于無人駕駛路場合。

技術領域

本發明屬于無人駕駛路徑規劃領域，具體講，涉及一種利用等步采樣和A*算法原理的路徑搜索算法進行無人駕駛車輛的局部路徑規劃。

背景技術

隨著社會的發展，人們對生活品質的要求越來越高，汽車成為人類生活不可或缺的交通工具，然而汽車數量的增加以及駕駛員自身安全意識薄弱導致全球交通事故發生率急劇增長。面對日益嚴峻的交通安全與交通擁堵問題，構建智能交通系統的任務變得更加急切。無人駕駛車輛作為構建智能交通系統的關鍵部分，近年來受到各方的關注。無人駕駛車輛融合了環境感知與定位、決策規劃與運動控制等多項功能，從而代替駕駛員的眼、腦和手，具有反應迅速、行駛安全可靠等優點。目前美國、英國和德國等一些國家的無人駕駛技術已發展較為成熟，我國的無人駕駛技術起步較晚，在一些關鍵技術的發展距離世界先進水平還有一定的差距。

無人駕駛車輛的路徑規劃算法主要繼承了機器人領域的算法，例如A*算法、RRT算法、人工勢場法等。A*(A-Star)算法是一種靜態路網中求解最短路徑最有效的直接搜索方法，其魯棒性好，對環境信息反應速度快，被廣泛應用于各類機器人中。A*算法是Dijkstra算法的改進，比起原始的Dijkstra算法具有收斂速度快、指向性明顯、搜索空間小的優點。但是傳統的基礎A*算法由于依賴于方形柵格中點進行搜索，且其代價函數僅是路徑長度的函數(代價只與路徑長短有關)，所以存在路徑方向固定、路徑平滑度不足、轉折角度大等不足，而且在考慮車道線限制的實際道路仿真和大彎道道路仿真中，效果不理想。早在2007年美國DARPA(美國高級研究計劃局)舉辦的城市挑戰賽中，斯坦福大學研制的Junior無人車即利用一種改進的A*算法取得了比賽的亞軍。我國一些科研單位也將A*算法用于無人駕駛車輛的路徑規劃中，例如中國科學技術大學即提出一種基于可搜索連續鄰域A*算法的無人駕駛車輛路徑規劃方法。另外，RRT算法是一種隨機采樣的規劃方法。自1998年提出，RRT算法由于其增量式生長特性被廣泛應用于動態環境、高維狀態環境以及存在運動動力學約束的環境中。人工勢場法是由Khatib提出的一種虛擬力法，將機器人的運動設計成一種在人造引力場中的運動，規劃出安全且較平滑的路徑。由于以上兩種方法在本發明中沒有應用，后面不再進行說明。

雖然前人已提出多種無人駕駛路徑規劃算法，可是大多算法不滿足車輛運動學約束，不能直接用于車輛控制，需要進行大量的處理工作。

發明內容

為了滿足汽車的運動學約束與實際交通限制，針對無人駕駛車輛的局部路徑規劃做出以下幾方面研究：

(1)加入車道線約束下的代價函數的選擇；

(2)帶有避障要求的代價函數的選擇；

(3)考慮車輛實際運動學模型，帶有轉向約束的A*算法；

(4)基于柵格內任意點(非中心點)的A*路徑搜索及安全域選擇；

(5)十字路口車輛轉彎的路徑規劃。

本發明將等步采樣的思想引入到局部路徑規劃策略中，基于等步采樣A*算法的無人駕駛局部路徑規劃方法，具體步驟如下：

步驟1：定義搜索步長和搜索安全域；

搜索步長計算公式為：