[發明專利]一種無人駕駛交通載具的導航尋徑方法、裝置及車輛

在審

• 申請號: 202011014370.2
• 申請日: 2020-09-24
• 公開（公告）號: CN112212876A
• 公開（公告）日: 2021-01-12
• 發明（設計）人: 蔣麗娜
• 申請（專利權）人: 南通路遠科技信息有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京馳納智財知識產權代理事務所(普通合伙) 11367
• 代理人: 蔣路帆

本發明提供了一種無人駕駛交通載具的導航尋徑方法，方法包括以下步驟：獲取當前所在的位置以及目標所在的位置；以當前所在的位置以及目標所在的位置作為參照點，生成虛擬的地圖范圍；獲取虛擬地圖范圍內的道路，包括道路編號即道路端點信息；修改虛擬地圖范圍中不包含當前所在的位置以及目標所在的位置，且與虛擬地圖范圍相交的道路的連通性；從連通的道路中選擇一條作為導航路線。本發明還提供了一種無人駕駛交通載具的導航尋徑裝置，以及交通載具。本發明的技術方案不通過深度或廣度搜索算法實現建立連通狀態樹，不需要經過來回往復的遍歷操作，僅需要針對地圖信息中的道路端點及道路信息進行刪除操作，算法復雜度低，運行效率高。

技術領域

本發明涉及一種無人駕駛交通載具的導航尋徑方法、裝置及車輛，屬于物聯網、無人駕駛領域。

背景技術

無人駕駛汽車能夠自動規劃行駛路徑，感知周圍的環境，自主進行決策，并控制車輛 的執行系統沿期望路徑行駛，最終到達目的地。而導航是無人駕駛技術的重要技術，現有 的導航技術均是基于地圖的尋徑，例如，BFS通過一種從起點開始不斷擴散的方式來遍歷 整個圖。只要從起點開始的擴散過程能夠遍歷到終點，那么起點和終點之間一定是連通的， 因此他們之間至少存在一條路徑，而由于BFS從中心開始呈放射狀擴散的特點，它所找到 的這一條路徑就是最短路徑。另一種方法是Dijkstra算法，其主要思想是從多條路徑中選擇最短的那一條，通過記錄每個點從起點遍歷到它所花費的當前最少長度，在此基礎上有人提出了A*算法，其主要思想是有方向地進行擴散，得到盡可能最短的路徑，它結合了Dijkstra和啟發式算法的優點，以從起點到該點的距離加上該點到終點的估計距離之和作為該點在遍歷隊列中的優先級。實踐證明，基本的圖搜索算法已經無法滿足互聯網地圖檢索實時響應這種性能要求，所以各家公司都有各自的預處理方法：分層或者預計算。具體采用何種方式，這取決于采取的加速算法相關。

注意到，現有的尋徑算法都是以駕駛起點為起點，通過遍歷的方式建立生長樹，這種 方式在連通性好的城市道路，其搜索尋徑效率和計算復雜度是可以接受的，但是在連通性 欠佳的地理區域，例如一些偏遠山區，或者人煙稀少的地區，那么現有的尋徑算法就顯得 復雜。如圖1所示，假設某一個駕駛路段中，導航從起點S到終點G。根據Dijkstra算法 或者RRT算法或者A*算法，都是以S作為起點往終點方向進行路徑遍歷，并且生成路徑樹， 樹根為S，如果某一個樹葉上出現了G所在的路徑，則識別出一條連通路徑，有些算法中 還加入了代價函數，以計算各條路徑的代價。這種尋徑方式在該場景下其效率明顯較低， 可能需要遍歷該地圖區域中的32條道路(1,2,3等標記為道路編號)才能尋找到連通路徑。

發明內容

為了解決在道路連通性欠優的非城區道路的無人駕駛汽車的導航尋徑的效率問題，本 發明提供了以下技術方案。

一種無人駕駛交通載具的導航尋徑方法，方法包括以下步驟：獲取當前所在的位置以 及目標所在的位置；以當前所在的位置以及目標所在的位置作為參照點，生成虛擬的地圖 范圍；獲取虛擬地圖范圍內的道路，包括道路編號即道路端點信息；修改虛擬地圖范圍中 不包含當前所在的位置以及目標所在的位置，且與虛擬地圖范圍相交的道路的連通性；刪 除不連通的道路，從連通的道路中選擇一條作為導航路線。

所述道路有至少兩個端點。

優選地，所虛擬的地圖范圍為矩形。

進一步，修改道路的連通性的方法是，將虛擬地圖范圍中不包含當前所在的位置以及 目標所在的位置，且與虛擬地圖范圍相交的道路的連通性修改為不連通。

更進一步，將虛擬地圖范圍中不包含當前所在的位置以及目標所在的位置，且與虛擬 地圖邊界相交的道路的一個端點修改為該道路與虛擬地圖邊界的交點，且將該端點修改為 NULL。

更為優選地，從虛擬地圖的一個位置起，刪除不連通的道路。