[發明專利]基于改進Kstar算法和深度學習的實時路徑規劃方法

有效

• 申請號: 202011386288.2
• 申請日: 2020-12-01
• 公開（公告）號: CN112748732B
• 公開（公告）日: 2022-08-05
• 發明（設計）人: 袁友偉;周威煒;葛云陽;鄢臘梅
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 朱亞冠

本發明公開基于改進Kstar算法和深度學習的實時路徑規劃方法。本發明將k?shortest paths問題結合到實時路徑規劃中，通過改進Kstar算法快速高效的找出k條優秀的待選路徑，并且提出更加合理的道路評估公式，綜合考量通過道路需要花費的時間和道路的擁堵指數，在找出最優路徑的同時，緩解交通壓力。使用改進的Kstar算法，將道路圖區域化，大幅提高啟發式搜索的速度，構造堆、路徑結構圖等高效的數據結構，優化了不必要的內存浪費，在與常規最優路徑算法時間復雜度接近的情況下快速得到多條待選路徑，有效減少不必要的導航路線規劃次數。

技術領域

本發明涉及計算機科學和智能交通系統技術領域，具體涉及一種基于改進Kstar算法和深度學習的實時路徑規劃方法。

背景技術

隨著城市發展和車輛普及，道路擁堵成為交通路徑規劃的重難點，因擁堵而造成的時間空間上的浪費以及經濟成本正在不斷增加，合理的實時最優路徑規劃已經成為智能交通領域發展的迫切需要。

實時最優路徑規劃是智能交通領域的重要組成，可以有效緩解交通壓力，降低交通擁堵程度，但是現有的簡單動態實時規劃已經無法應付復雜的實時交通環境，而復雜的動態實時規劃算法計算復雜度過高，同時現有的實時路徑規劃系統通常對同一路徑反復計算并且需要在路徑估值超出閾值后重新進行路徑規劃，這將需要花費更多的時間。現有的道路評估公式大部分只是簡單的對通過道路所花費的時間或者道路長度進行衡量，存在一段道路比較擁擠但是仍然將用戶引導至該路段的情況，這將會加重交通的壓力。

因此，本發明針對上述問題，為動態實時路徑規劃提供新的方法，改進現有技術方案中的不足。

發明內容

為了克服現有實時動態路徑規劃存在的缺陷，本發明公開了一種基于改進Kstar算法和深度學習的實時路徑規劃方法，將k-shortest paths問題結合到實時路徑規劃中，通過改進Kstar算法快速高效的找出k條優秀的待選路徑，并且提出更加合理的道路評估公式，綜合考量通過道路需要花費的時間和道路的擁堵指數，在找出最優路徑的同時，緩解交通壓力。為了解決現有技術的問題，本發明的技術方案包括以下步驟：

步驟(1)：設定更新周期；

步驟(2)：獲取用戶當前位置和目標位置；

步驟(3)：獲取當前位置與目標位置之間的地圖和所包含道路的相關歷史信息，將劃定成一個個區域，使用改進Kstar算法得到k條待選路徑。具體包括以下步驟：

步驟(3.1)：在地圖上確定并標記起點s與目標位置t：

步驟(3.2)：使用啟發式搜索，檢索出一條從初始位置s到目標位置t的一條最短路徑，啟發函數為：

f(n)＝h(n)+λd(n) 公式(1)

其中，n代表搜索過程中的一個點位，f(n)代表點位n的啟發值，d(n)代表初始位置s到點位n的曼哈頓距離，h(n)代表點位n的權重，λ表示調節權重的參數；

步驟(3.3)：將步驟(3.2)中檢索到的最短路徑劃分為樹邊(tree edge)，其余檢索過的路徑劃分為側邊(sidetrack edge)，對于最短路徑上的每一個頂點v都按照以下規則構造堆H(v)：

對于上述最短路徑上的每一個頂點v，判斷頂點v是否是起點s，若是則H(v)為空堆，否則令u為v的父節點，u為指向v的樹邊的起點，H(v)為H(u)的副本；同時判斷頂點v是否存在屬于側邊的入邊，若否則不做處理，若是則將上述入邊的起點x與頂點v構成集合(x,v)作為節點加入H(v),然后由于H(v)為H(u)的副本，所以將H(u)內所有節點加入到H(v)中；每個H(v)具有若干節點，但只有一個根節點，根節點只有一個子節點，所有節點根據權值大小按照升序排列，根節點的權值最小。

節點(x,v)權值公式如下：