[發明專利]大規模可通行區域駕駛地圖的構建方法及其無人駕駛應用方法

有效

• 申請號: 201810333301.4
• 申請日: 2018-04-13
• 公開（公告）號: CN108763287B
• 公開（公告）日: 2021-11-12
• 發明（設計）人: 趙君嶠;張興連;賀旭東;孫路;李軍;黃業韡;葉晨;馮甜甜
• 申請（專利權）人: 同濟大學
• 主分類號: G06F16/29
• 分類號: G06F16/29;G01C21/34
• 代理公司: 上海科律專利代理事務所(特殊普通合伙) 31290
• 代理人: 葉鳳

1.一種大規模可通行區域駕駛地圖的構建方法，其特征在于，包括如下步驟：

步驟1、采集車系統上，使用多線激光雷達對道路環境進行掃描，利用高差實現地面濾除與障礙物分割，得到實時的道路邊界障礙物分布圖；結合差分全球衛星導航系統與慣性導航設備提供的高精度位姿信息，對多幀的道路邊界障礙物分布進行可通行區域概率格網建圖；

步驟2、采集車系統上，在概率格網建圖過程中根據雷達幀數與采集車運動變化量進行自適應的子圖分塊構建，并引入R-Tree將不同大小的子圖作為結點構建空間索引；實時根據R-Tree將遠離采集車的結點移出內存并存儲在磁盤上，并同時將磁盤中已存在的臨近采集車的結點讀回內存，從而實現建圖過程中的內存動態調度，實現大規模建圖；

步驟3、在建圖暫停后將R-Tree及其所有結點數據存儲到磁盤；其繼續由采集車建圖系統讀取并恢復建圖過程，從而實現對已建圖區域的更新和擴展建圖，采集車系統實現了地圖大規模建圖和更新的自動化；

步驟1中的概率格網地圖根據建圖范圍分配固定大小的內存空間，因此受內存大小限制難以擴展到大規模場景下的建圖應用；因此，為了實現大規模建圖，對概率格網地圖進行自適應分塊，構建子圖；對所述子圖構建R-Tree空間索引，實現子圖的動態調度機制的方法實現內存占用基本恒定；

詳述如下：

2.1地圖自適應分塊

提出一種自適應的地圖分塊方法，其綜合了雷達掃描幀數量與采集車運動變化量，在建圖過程中自動對格網地圖進行分塊；首先，初始子圖范圍為以當前位置為中心點，范圍a₀*a₀的正方形區域；當有效掃描幀數超過設定閾值或采集車運動到子圖范圍外，則完成當前子圖構建；對子圖分配ID，并創建該子圖的最小外包圍矩形(MBR)，作為一個結點插入到R-Tree中；同時新建一個子圖并初始化用于接收數據，相鄰子圖含有重疊部分；

2.2基于R-Tree的內存動態調度

所述R-Tree是一棵動態平衡搜索樹，R-Tree及其各類變種的平均操作復雜度為對數階，從而對MBR所表示的空間對象進行索引的插入、更新、刪除和搜索操作；

2.2.1 R-Tree的維護

所述R-Tree中每一個結點包含1至n個由子圖編號ID與空間對象的MBR組成的單元；其中n為可調參數，用于聚類臨近單元從而降低索引數據量；向R-Tree內新增子圖結點時，遵循使R-Tree結點MBR重疊區域最小的原則，選擇插入位置添加新結點，將子圖ID作為結點的唯一標識索引，由子圖的空間坐標計算x_min、y_min與x_max、y_max范圍屬性，確定子圖的MBR；

2.2.2內存動態調度方法

在實時建圖過程中，當子圖分塊被添加至R-Tree中后，同時基于R-Tree進行空間查詢，搜索車輛當前位置附近的n張子圖，將其余子圖按標識ID寫出轉移保存到磁盤并從內存中去除；當車輛移動到已建圖區域時，通過R-Tree索引搜索結點編號，由磁盤讀取對應的子圖分塊并加載到內存中，進行格網地圖更新；如此，子圖在內存、磁盤中進行動態的移出與回讀，實現內存的動態調度，保證了建圖系統的內存占用恒定，從而實現了大規模建圖。

2.根據權利要求1所述的一種大規模可通行區域駕駛地圖的構建方法，其特征在于，步驟3中所述建圖系統利用動態調度方法，根據當前位置坐標恢復到上一次的建圖流程中：當建圖完成后，將生成的可通行區域地圖文件輸出，同時存儲地圖的起始位置坐標及子圖分塊信息的R-Tree空間索引至磁盤；

需進行地圖擴展或更新時，讀取磁盤中的子圖文件、以及對應的R-Tree空間索引與起始位置配置信息，將建圖系統恢復到前次建圖流程中，在已有的建圖區域的基礎上，從任意位置對地圖進行多次概率更新與新區域擴展建圖，達到增量式建圖與自動更新，從而實現大規模地圖的建圖和維護。

3.一種大規模可通行區域駕駛地圖構建后其在無人駕駛應用方法，其特征在于，采集車系統在建圖完成之后，將R-Tree及其所有子圖數據上傳至服務器，提供地圖在線分發服務；服務器響應多個無人車客戶端的并發請求，利用R-Tree索引快速搜索無人車客戶端所臨近的子圖結點，并對子圖進行融合，實時發送給無人車，從而輔助其進行超越可見范圍內的高精度可通行區域地圖，輔助無人駕駛的決策和規劃過程；

包括步驟：

4.1基于位置的客戶端搜索請求

當無人駕駛中客戶端向服務器發送地圖請求時，基于用戶的位置，服務器端利用與子圖數據對應的R-Tree進行鄰近子圖搜索，將查詢到符合距離條件的子圖數據作為融合對象；

4.2基于R-Tree的子圖搜索

在給出一個以客戶端車身周邊范圍為L*W的矩形作為空間目標搜索矩形的搜索請求后，從R-Tree的根節點進行遞歸遍歷，通過以平均時間復雜度O(logN)的方式自頂向下遍歷R-Tree所包含的結點指針，進行空間多邊形包含查詢，快速查詢獲取車輛當前位置附近的n張子圖索引ID；N為索引數據總數；

4.3子圖融合

對包含重疊區域的n個子圖根據時間戳分配值w_i，將最終可通行區域地圖格網的概率p_i進行加權平均，i＝1,2...n，得到障礙物概率值表示結果p′；取概率閾值θ作為障礙分類依據，將p′θ的格網單元標記為障礙物，則可獲得無人車可通行區域的二值地圖；根據無人車客戶端的位姿，獲得當前位姿下的可通行區域無人車局部地圖，為駕駛決策與路徑規劃提供高精度的分析參考，對車輛自身傳感器的感知范圍、障礙結果進行補充；

4.4在線分發

系統基于地圖引擎，響應多客戶端的地圖請求，實現快速的地圖下載與緩存，滿足無人駕駛的實時性需求。