[發明專利]基于時間擴展的路徑規劃方法、系統、設備及存儲介質

有效

• 申請號: 202010842827.2
• 申請日: 2020-08-20
• 公開（公告）號: CN111928867B
• 公開（公告）日: 2021-04-30
• 發明（設計）人: 譚黎敏;俞銘琪
• 申請（專利權）人: 上海西井信息科技有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 上海隆天律師事務所 31282
• 代理人: 鐘宗

1.一種基于時間擴展的路徑規劃方法，其特征在于，包括如下步驟：

獲取路徑規劃的初始參數和二維空間地圖，所述初始參數包括起始地的空間坐標、起始時間和目的地的空間坐標，所述二維空間地圖中包括多個空間節點，每個所述空間節點具有一二維的空間坐標；

將二維空間地圖擴展到三維時空地圖，其中，第一維度和第二維度分別為所述二維空間地圖的兩個維度，第三維度為時間，所述三維時空地圖的時間范圍以所述起始時間為起點；

根據所述起始地的空間坐標和所述起始時間確定所述三維時空地圖中的起始地時空節點，根據所述目的地的空間坐標和所述三維時空地圖的時間范圍確定所述三維時空地圖中的目的地直線；

基于A Star路徑規劃算法，在所述三維時空地圖中從所述起始地時空節點開始依次搜索下一個路徑節點，以獲得從所述起始地到所述目的地的最短路徑；

所述將二維空間地圖擴展到三維時空地圖之后，還包括如下步驟：

在所述二維空間地圖中找到最遠的兩個空間節點；

從最遠的兩個空間節點出發使用深度優先遍歷方法依次搜索次遠的空間節點，并迭代生成四維矩陣，所述四維矩陣中的第一維度和第二維度分別為所述二維空間地圖的兩個維度，第三維度對應于時間，第四維度對應于每個空間節點到其鄰接節點的到達難度指標；

當所述二維空間地圖中所有的空間節點遍歷之后，將整體四維場景壓縮回三維時空地圖，所述每個空間節點到其他各個空間節點的距離為第四維度所有值的平均，作為每個空間節點的到達難度指標；

在所述三維時空地圖中搜索下一個路徑節點時，采用的啟發函數根據所述三維時空地圖中各個空間節點的到達難度指標計算得到。

2.根據權利要求1所述的基于時間擴展的路徑規劃方法，其特征在于，在所述三維時空地圖中搜索下一個路徑節點時，對下一個路徑節點的選擇設置時空約束條件，所述時空約束條件包括：可供搜索的下一個時空節點包括根據當前時空節點的空間坐標與下一時刻確定的時空節點以及根據當前時空節點的空間上鄰接節點的空間坐標與下一時刻確定的節點。

3.根據權利要求1所述的基于時間擴展的路徑規劃方法，其特征在于，所述計算每個空間節點到其鄰接節點的到達難度指標，包括計算每個空間節點到其鄰接節點的曼哈頓距離或旅行時間，作為所對應的到達難度指標。

4.根據權利要求1所述的基于時間擴展的路徑規劃方法，其特征在于，在所述二維空間地圖中找到最遠的兩個空間節點，包括在所述二維空間地圖中尋找曼哈頓距離最遠或者旅行時間最長的兩個空間節點。

5.根據權利要求1所述的基于時間擴展的路徑規劃方法，其特征在于，所述方法應用于多車路徑規劃，且在所述三維時空地圖中搜索下一個路徑節點時，當前規劃的車輛與已規劃的車輛不能在同一時刻經過同一空間節點。

6.根據權利要求5所述的基于時間擴展的路徑規劃方法，其特征在于，所述方法應用于多車路徑規劃，且在所述三維時空地圖中搜索下一個路徑節點時，采用如下步驟建立封閉列表：

根據預設的車輛路徑規劃順序，獲取已規劃的車輛路徑的數據；

確定已規劃的車輛路徑在各個空間節點的通過時間；

根據已規劃的車輛路徑在各個空間節點的通過時間和所對應的空間節點的空間坐標，確定鎖閉節點；

將所述鎖閉節點加入封閉列表。

7.根據權利要求6所述的基于時間擴展的路徑規劃方法，其特征在于，所述封閉列表還包括預設的默認鎖閉節點，所述默認鎖閉節點所對應的時間為所述三維時空地圖的時間范圍。

8.根據權利要求1所述的基于時間擴展的路徑規劃方法，其特征在于，所述獲取路徑規劃的初始參數之后，還包括如下步驟：

計算所述起始地到所述目的地的旅行時間；

根據所述起始時間和所述旅行時間定義所述三維時空地圖的時間范圍。