[發明專利]路徑網絡圖生成方法及裝置、電子設備和存儲介質

有效

• 申請號: 202010532971.6
• 申請日: 2020-06-12
• 公開（公告）號: CN111678527B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 陳建興;潘余昌
• 申請（專利權）人: 北京京東乾石科技有限公司
• 主分類號: G01C21/32
• 分類號: G01C21/32
• 代理公司: 北京律智知識產權代理有限公司 11438
• 代理人: 王輝;闞梓瑄

本公開是關于一種路徑網絡圖生成方法及裝置、電子設備以及計算機可讀存儲介質，涉及自動駕駛技術領域，可以應用于生成自動駕駛車輛的路由網絡拓撲圖的場景。該路徑網絡圖生成方法包括：獲取初始路徑拓撲圖，并基于初始路徑拓撲圖確定起點集合和終點集合；確定初始路徑拓撲圖中的可分裂節點，對可分裂節點進行分裂處理，以生成分裂路徑子圖；根據起點集合和終點集合分別確定虛擬起點和虛擬終點，并根據虛擬起點、虛擬終點和分裂路徑子圖生成虛擬路徑子圖；將虛擬路徑子圖和分裂路徑子圖添加至初始路徑拓撲圖中，以生成目標路徑拓撲圖。本公開可以控制復雜路網下路由的求解規模，并將回環問題設計到路由拓撲網絡之中。

技術領域

本公開涉及自動駕駛技術領域，具體而言，涉及一種路徑網絡圖生成方法、路徑網絡圖生成裝置、電子設備以及計算機可讀存儲介質。

背景技術

在自動駕駛或者輔助駕駛中，路由需要從起點到終點找到一條最優的行駛路徑。路由的基礎是構建一張包含路網信息的拓撲網絡，網絡中道路被抽象成節點(node)，道路的聯通關系被抽象成邊(edge)，道路和道路之間距離、路況等信息構成了邊的代價(cost)。現有技術中，路由拓撲網絡是根據道路基本的拓撲信息構建而成。

需要說明的是，在上述背景技術部分公開的信息僅用于加強對本公開的背景的理解，因此可以包括不構成對本領域普通技術人員已知的現有技術的信息。

發明內容

本公開的目的在于提供一種路徑網絡圖生成方法、路徑網絡圖生成裝置、電子設備以及計算機可讀存儲介質，進而至少在一定程度上克服現有的路由網絡無法解決回環問題且在復雜路網下路由求解規模過大的問題。

本公開的其他特性和優點將通過下面的詳細描述變得顯然，或部分地通過本發明的實踐而習得。

根據本公開的第一方面，提供一種路徑網絡圖生成方法，包括：獲取初始路徑拓撲圖，并基于初始路徑拓撲圖確定起點集合和終點集合；確定初始路徑拓撲圖中的可分裂節點，對可分裂節點進行分裂處理，以生成分裂路徑子圖；根據起點集合和終點集合分別確定虛擬起點和虛擬終點，并根據虛擬起點、虛擬終點和分裂路徑子圖生成虛擬路徑子圖；將虛擬路徑子圖和分裂路徑子圖添加至初始路徑拓撲圖中，以生成目標路徑拓撲圖。

可選的，基于初始路徑拓撲圖確定起點集合和終點集合，包括：確定物理起點的起點位置坐標，并獲取物理起點的起點搜索范圍；根據起點位置坐標和起點搜索范圍確定與物理起點對應的多個起始節點，并根據多個起始節點生成起點集合；確定物理終點的終點位置坐標，并獲取物理終點的終點搜索范圍；根據終點位置坐標和終點搜索范圍確定與物理終點對應的多個終止節點，并根據多個終止節點生成終點集合。

可選的，確定初始路徑拓撲圖中的可分裂節點，對可分裂節點進行分裂處理，以生成分裂路徑子圖，包括：判斷物理起點和物理終點是否處于同一目標節點；如果物理起點和物理終點處于同一目標節點，則將目標節點確定為可分裂節點；對可分裂節點進行分裂處理，以生成第一分裂節點和第二分裂節點；確定與目標節點關聯的關聯節點，并根據關聯節點生成第一分裂節點和第二分裂節點分別對應的分裂連接邊；根據第一分裂節點、第二分裂節點和分裂連接邊生成分裂路徑子圖。

可選的，分裂連接邊包括第一分裂連接邊和第二分裂連接邊，根據關聯節點生成第一分裂節點和第二分裂節點分別對應的分裂連接邊，包括：分別確定與關聯節點對應的前驅節點和后繼節點；生成前驅節點與第一分裂節點之間的第一分裂連接邊，并將第一分裂連接邊對應的第一邊代價添加至第一分裂連接邊；生成前驅節點與第二分裂節點之間的第二分裂連接邊，并將第二分裂連接邊對應的第二邊代價添加至第二分裂連接邊；生成第一分裂節點與第二分裂節點之間的第三分裂連接邊，并將第三分裂連接邊對應的第三邊代價添加至第三分裂連接邊。

可選的，虛擬子圖包括分裂節點，根據虛擬起點、虛擬終點和分裂路徑子圖生成虛擬路徑子圖，包括：根據虛擬起點、虛擬終點和分裂節點確定虛擬連接邊；確定虛擬連接邊對應的虛擬邊代價，并將虛擬邊代價添加至虛擬連接邊；根據虛擬起點、虛擬終點和虛擬連接邊生成虛擬路徑子圖。