[發明專利]一種導航引擎的快速重新規劃路徑的方法

在審

• 申請號: 201510430898.0
• 申請日: 2015-07-21
• 公開（公告）號: CN105651290A
• 公開（公告）日: 2016-06-08
• 發明（設計）人: 王廣飛
• 申請（專利權）人: 上海趣駕信息科技有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 上海三和萬國知識產權代理事務所(普通合伙) 31230
• 代理人: 陳偉勇

技術領域

本發明涉及導航系統領域，尤其涉及導航方法。

背景技術

導航軟件中，偏離路徑后重新規劃路徑是基本功能，但由于嵌入式機器 受制于機器性能的影響，無法與PC相提并論。對于城市復雜道路，用戶很可 能不慎偏離路徑，如果重新走從自車端往目的地端探索的流程，會大大增加 導航重新規劃路徑的時間，導致不能給用戶提供及時的引導，最終可能導致 更加嚴重的繞路現象。

因此，縮短重新規劃路徑時間，讓用戶及時回到原有路徑顯得非常有必 要。現有的導航系統采用的導航方法路徑規劃時間長，內存消耗量大。

發明內容

本發明的目的在于提供一種導航引擎的快速重新規劃路徑的方法，以解 決上述至少一個技術問題。

本發明所解決的技術問題可以采用以下技術方案來實現：

一種導航引擎的快速重新規劃路徑的方法，其特征在于，通過實時監測 車輛是否偏離已經規劃好的路徑，自車偏離路徑后重新規劃路徑，利用已經 規劃好的路徑信息與自車端探索的路徑信息進行對接，生成重新規劃的路徑。

本發明相較傳統的路徑規劃方法，縮短了算路時間，減少了內存消耗。

一種導航引擎的快速重新規劃路徑的方法，包括如下步驟，

步驟一，監測車輛狀態：導航引導過程中時刻檢測自車是否處于已規劃 好的路徑上，已規劃好的路徑為原路徑；

步驟二，根據車輛狀態控制重新規劃路徑線程狀態，如果步驟一中檢測 到自車不在已規劃好的路徑上，則觸發重新規劃路徑線程；

步驟三，重新規劃路徑前期準備：將自車位置一定范圍內的原路徑道路 進行標記，并讀取自車周邊的道路數據，供探索使用；

步驟四，路徑探索：以自車位置為起點，運用算法限定探索范圍的同時， 運用算法進行正向路徑探索，直到探索到對接原路徑的至少2條路徑，從中 擇優選取一條最佳路徑作為重新規劃的路徑；

步驟五，路徑組織：組織探索的路徑信息，重新利用原路徑已組織好的 信息，將其組合成完整的路徑信息，供導航引擎使用。

作為一種優選方案，步驟四中，運用Djstra算法進行正向路徑探索，用 A*算法限定探索范圍，直到探索到對接原路徑的8條路徑。

本發明通過限定探索到與原路徑對接的路徑數，便于尋找出最佳路徑。

步驟三中，首先在導航的引導信息中獲取車輛所在位置。確定的位置作 為路徑規劃的起始位置。

步驟三中，對原路徑道路進行標記時，將原路徑中從自車位置到目的地 區間內，標記不少于40％的道路作為對接道路。通過與原路徑進行對接，縮 短算路時間。

優選為，標記50％的道路作為對接道路。

通過自車位置到目的地的直線距離作為標記對接道路范圍的依據，當自 車位置到目的地的直線距離小于500米時，標記不大于60％原路徑的道路作 為對接道路；

當自車位置到目的地的直線距離大于10千米時，標記不少于70％，且不 大于90％原路徑的道路作為對接道路；

當自車位置到目的地的直線距離不小于500米，且不大于10千米時，標 記不少于50％，且不大于70％原路徑的道路作為對接道路。

本發明通過針對不同的自車位置到目的地的直線距離作為標記對接道路 范圍的依據，可以有效的縮短探索的時間，減少內存消耗。因為當目的地與 自車位置直線距離較小時，原路徑與重新規劃的路徑易產生較大的偏差，故 控制對接道路的范圍，可以有效的縮短探索的時間。當目的地與自車位置的 直線距離較小時，原路徑與重新規劃的距離通過擴大對接道路的范圍，可以 有效的減少探索時間。

步驟四中，對接道路中，找出距離車輛最遠的一條道路，并以此條道路 作為基準道路，計算對接原路徑的至少2條路徑到基準道路的代價，選擇代 價最小的路徑作為最終的規劃道路。代價最小的路徑可以實現至少2種情況； 以最短的路徑到達目的地，或者是最快的時間到達目的地。

作為一種優選方案，一種導航引擎的快速重新規劃路徑的方法，包括如 下步驟，

步驟一，監測車輛狀態：導航引導過程中時刻檢測自車是否處于已規劃 好的路徑上，已規劃好的路徑為原路徑；

步驟二，根據車輛狀態控制重新規劃路徑線程狀態，如果步驟一中檢測 到自車不在已規劃好的路徑上，則觸發重新規劃路徑線程；