TWI395928B

TWI395928B - 人工智慧規劃導航路線之方法

Info

Publication number: TWI395928B
Application number: TW98116684A
Authority: TW
Inventors: John Whitehead
Original assignee: Mitac Int Corp
Priority date: 2009-05-20
Filing date: 2009-05-20
Publication date: 2013-05-11
Also published as: TW201042239A

Description

人工智慧規劃導航路線之方法

本發明係關於利用全球導航衛星系統規劃導航路線之方法，尤指一種利用人工智慧於全球導航衛星系統中規劃導航路線之方法。

全球導航衛星系統(GNSS)，例如全球位置測定系統(GPS)、伽利略以及格洛納斯系統(GLONASS)皆可經由個人衛星提供導航訊號至一個人導航裝置。每個衛星皆會提供目前的時間及位置，接著個人導航裝置利用這些資訊從至少三個衛星決定目前位置(其為三邊測量)，且從每個衛星至個人導航裝置來決定距離，該個人導航裝置需藉由每個衛星之傳遞時間(該個人導航裝置得到訊號之時間)與目前時間做比較，其中一訊號欲抵達該個人導航裝置須經由衛星傳遞，其需傳遞之距離較長。

該個人導航系統之位置係藉由不同該全球衛星導航系統衛星從訊號傳遞位置被估算之，而該全球衛星導航系統衛星係可與一數位地圖結合，其包含大部分或全部之一鄰近座標。一般來說，該數位地圖以及地圖資料庫將包含一交叉點(節點)，每個節點係可藉由一個或更多個路線與一鄰近節點連接，且各自具有相關之一成本(cost)，該成本可用來量測旅程時間、距離或兩者合一之該成本。目前路線演算法利用一成本法由一起始節點至一目標節點來估算路線，該起始節點至該目標節點係可利用一重複步驟尋找一最小成本路線，該導航路線之該成本總合係沿虛擬地圖之路網，藉由增加在該導航路線上與每個調度有關之該成本找尋之，而依上述一使用者之偏好路線/行程之類形係藉由調整該成本規劃該路線類型，所以若該使用者偏好行駛高速公路，則高速公路每哩之該成本較低，換句話說每個路線分段係連接鄰近節點可具有一不同類型，則該類型可被利用於調整該路線分段之該成本，如此一路線分段之該成本總合係與一高速公路之內容一同估算，其整體之該成本皆較小，且可能呈現給該使用者更多結果以利參考。

然而對該使用者而言，以上所敘述得到之一偏好路線係為較普遍之方法。例如：該使用者可知道一特定行駛路段，或知道需執行少量繞道動作以避開交通擁塞之地段，另外，該使用者可能於平日或假日時偏好不同的路線行駛，但先前技術並無有關滿足上述情況之技術以得到相關資訊。因此，該使用者將會頻繁地脫離該個人導航系統所給予之導航路線，造成該個人系統需要經常改變導航路線亦如同虛設。

本發明係揭露一種利用一全球導航衛星系統(GNSS)之導航設備規劃導航路線的方法，其步驟如下：該導航設備係儲存一駕駛紀錄，其中該駕駛紀錄係包含對應於一駕駛員的行駛調度之複數個路線分段，該導航設備基於該駕駛紀錄中之該複數個路線分段決定一偏好路線分段，以及該導航設備產生包含該偏好路線分段之一導航路線。

本發明係揭露一種利用一全球導航衛星系統(GNSS)之導航設備規劃導航路線的方法，其步驟如下：該導航設備係儲存一駕駛紀錄，該駕駛紀錄包含對應一駕駛員的行駛調度之複數個路線分段，該導航設備根據一循環週期過濾該複數個路線分段，該導航設備過濾該複數個路線分段後，決定一偏好路線分段，以及該導航設備於一次該循環週期內之一事件內，產生包含該偏好路線分段之一導航路線。

一種利用一全球導航衛星系統(GNSS)之導航設備規劃導航路線的方法，其步驟如下：該導航設備係決定一第一導航路線，其中該第一導航路線係由一第一位置至一目標位置決定，當該導航設備從該第一導航路線偵測到一偏向時，該導航設備紀錄一替代導航路線，該導航設備由該第一位置至該目標位置間記錄一時間週期，以及該導航設備基於一預定標準利用該替代導航路線代替該第一導航路線。

電子或衛星導航系統於一虛擬地圖中由一定點至另一定點估算一導航路線，然後針對一使用者由一第一位置(如該使用者目前的位置)至一第二位置(如該使用者欲達到之目的地)提供導航路線。該導航路線可利用一預先定義之規則之設定來估算，例如由該使用者定義最短或最快之一偏好路線，以及該使用者偏好之路線類型，例如：偏好之公路、由A道路行駛至B道路以及虛擬地圖(virtual maps)之資料，其包含之資訊具有道路長度以及行駛速限，以便進一步基於該使用者之偏好以進行估算導航路線。該地圖資料庫可能包含一複數個節點以及一複數個路線分段，每個路線分段可能連接兩個鄰近之節點，以及可能對應一實際路線，例如一馬路、一高速公路及一橋樑等等。

該導航系統所估算之導航路線可能被動態資訊(如流量)所影響，故該導航系統可視情況引導該使用者進行轉向，以便將旅程所需時間能達到最小。

請參照第1圖，第1圖為本發明第一實施例規劃導航路線之方法流程圖。該方法利用一導航設備接收一定位訊號，例如全球位置測定系統(GPS)衛星、伽利略衛星或格洛納斯衛星，該導航設備可能包含一天線、一訊號處理器、一記憶體以及一顯示器，其中該天線用以接收該定位訊號，該訊號處理器用以處理該定位訊號，該記憶體用於儲存定位資料及繪圖軟體，而該顯示器用於顯示一地圖、一位置及一導航路線，其中該位置係位於該地圖中，而該導航路線係由該導航設備之該位置至一目的地所得到，當然，除了地圖之外，該導航設備亦可顯示一圖形使用者介面用以接收輸入(如一目的地住址)，而該導航設備之一使用者亦可於顯示器中調整該地圖之顯示(如平移及縮放)，該規劃導航路線之方法敘述於流程10，其包含下列步驟：

步驟100：開始；

步驟102：儲存一駕駛紀錄；

步驟104：決定一偏好路線分段；

步驟106：產生包含該偏好路線分段之一導航路線；

步驟108：結束。

流程10係為於該導航設備中規劃導航路線之方法，該導航設備係儲存一駕駛紀錄，該駕駛紀錄包含對應於一駕駛員之行駛調度之複數個路線分段(步驟102)，之後該導航設備基於該駕駛紀錄中之該複數個路線分段，可決定一偏好路線分段(步驟104)，其可能由一類神經網路演算法(Neural Network Algorithm)完成路線規劃及決定該偏好路線分段。所謂類神經網路(或稱人工神經網路)是一種應用類似於大腦神經突觸聯接的結構進行信息處理的數學模型。神經網路是一種運算模型，由大量的節點和之間相互聯接構成。每個節點代表一輸出函數，稱為激勵函數(activation function)。每兩個節點間的連接都代表一個對於通過該連接信號的加權值，稱之為成本(cost)。網路的輸出則依網路的連接方式，成本值和激勵函數的不同而不通。該類神經網路演算法可根據該偏好路線分段出現於該駕駛紀錄之一次數，藉以調整由該第一位置至該第二位置得到之該偏好路線分段之一成本，其中該次數可為一預先決定時間週期(如一個月)之總合，進一步來說，該次數可為駕駛員偏離一預先決定的路線分段而選擇走該偏好路線分段之次數，故該偏好路線分段則可取代該預先決定的路線分段，換句話說，若該導航設備計算一路線，該導航路線於初始時包含該偏好路線分段，也就是該偏好路線分段若為該預先決定的路線分段，如果該駕駛員選擇該偏好路線分段，該次數則不會增加，最後，該導航設備會產生包含該偏好路線分段之一路線(步驟106)，但在流程10中，該步驟106在其他實施例中可能不會執行。換句話說，決定該偏好路線分段後(步驟104)，於地圖中之該偏好路線分段之該成本會根據該次數被更新，之後產生包含該偏好路線分段之該導航路線(步驟106)，但在其他實施例中，該偏好路線分段於步驟104中便已決定，故該偏好路線分段之該成本可被設定成零。在此過程中，當決定一總路線時，該偏好路線分段可能提供較少之該成本給該總路線，且當利用演算法決定最短或最快之路線之該總路線時，該路線分段將因此被該導航設備選擇之，最後除了該偏好路線分段之該成本被自動更新外，該成本亦可根據該使用者輸入資訊進行更新。舉例來說，若該使用者標明一使用者專用之路線分段，則該使用者專用之路線分段之該成本可能會減少或被歸零。

該導航設備可比較一實際時間與一估計時間藉以產生一比較結果，其中該實際時間係沿包含該偏好路線分段之該導航路線從一起始位置至一目的地位置之行駛時間，而該估計時間係與沿包含一預先決定的路線之該導航路線從該起始位置至該目的地位置之行駛時間，於是一成本係分配至該偏好路線分段，且可根據該比較結果做調整，若該實際時間小於該估計時間，則分配至該偏好路線分段之該成本便會減少；若該實際時間大於該估計時間，則分配至該偏好路線分段之該成本便會增加，故該偏好路線分段可提供較少之該成本至該總路線，且當該導航設備利用演算法決定該最短路線或該最快路線時，該偏好路線分段可能藉由該導航設備被選擇之。

請參照第2圖，其為本發明第二實施例規劃導航路線之方法流程圖。該方法適用於一導航設備，該導航設備接收一定位訊號，例如全球位置測定系統衛星、伽利略衛星或格洛納斯衛星，該規劃導航路線之方法敘述於流程20，其包含下列步驟：

步驟200：開始；

步驟202：儲存一駕駛紀錄；

步驟204：根據一循環週期過濾該駕駛紀錄之複數個路線分段；

步驟206：決定一偏好路線分段；

步驟208：於該循環週期中之一事件內，產生包含該偏好路線分段之一導航路線；

步驟210：結束。

流程20係為於該導航設備中規劃導航路線之方法，該導航設備係儲存一駕駛紀錄，該駕駛紀錄包含對應於一駕駛員行駛調度之複數個路線分段(步驟202)，然後該導航設備根據一循環週期過濾複數個路線分段(步驟204)，該循環週期係對應一每日相同週期、一每週相同週期、一每月相同週期以及一每年相同週期，舉例來說在平日、週休或是每年的國定假日期間之交通尖峰時期中，該使用者欲行駛不同路線，該導航設備經過濾後可於該複數個路線分段中決定一偏好路線分段(步驟206)，最後該導航設備在該循環週期中之一事件內可產生包含該偏好路線分段之一路線，舉例來說在每日交通尖峰時間內，該導航設備可產生包含一路線分段(該交通尖峰時間之該偏好路線分段)之該導航路線，其中該導航路線係具有較少之交通流量，或者在週休期間中，該導航設備可產生包含一路線分段之該導航路線，其中當該使用者行駛之該導航路線不受自身行程約束時，該使用者可依個人偏好沿著一風景區之路線前進。

請參照第3圖，其為本發明第三實施例規導航劃路線之方法流程圖。該方法適用於一導航設備，該導航設備接收一定位訊號，例如全球位置測定系統衛星、伽利略衛星或格洛納斯衛星，該規劃導航路線之方法敘述於流程30，其包含下列步驟：步驟300：開始；步驟302：由第一位置至第二位置決定一第一導航路線；步驟304：由該第一導航路線偵測到一偏向；步驟306：由第一位置至第二位置記錄一替代導航路線；步驟308：基於一預定標準利用該替代導航路線代替該第一導航路線；步驟310：結束。

流程30係為於該導航設備中規劃路線之方法，該導航設備可從一第一位置至一目標位置決定一第一導航路線(步驟302)，當從該第一位置至該目標位置決定該第一導航路線時，該導航設備可從該第一位置至該目標位置間決定一最短路線，或者從該第一位置至該目標位置間決定一最快路線(步驟304-306)，而該替代導航路線根據一調度被記錄之，該導航設備可藉由偵測該調度或藉由偵測一位置從該第一路線偵測該偏向(該調度係與該第一導航路線之複數個第一調度不同)，而該位置係於一路線上而非沿著該第一路線，該複數個第一路線分段可從該替代路線之複數個替代路線分段被更改或替換，隨著該使用者沿該替代路線行駛，該導航設備可沿著該替代路線，從該第一位置移動至該目標位置決定一時間週期，最後該導航設備可基於一預定標準，利用該替代路線代替該第一路線(步驟308)，該預定標準係可為沿著該替代路線，從該第一位置移動至該目標位置之該時間週期，其小於沿著該第一路線，從該第一位置移動至該目標位置之一估計時間。如上述第1圖之實施例，可將步驟308省略，該偏向之該成本根據該偏向被記錄之次數進行減少或歸零之動作，而當該偏向減少或歸零之後，從該第一位置至該第二位置產生一路線，可自動決定或利用該替代路線。

本發明估算導航路線之方法與先前技術之估算導航路線之方法不同之處在於新的方法可得到使用者之偏好及了解路況，以便提供屬於該使用者本身專屬之導航路線規劃，其與習知該導航設備之操作模式不同，該系統可利用類神經網路演算法，也就是人工智慧之一形式來調整路線之演算法，該完成導航路線規劃之方法可利用駕駛紀錄來「得到」資訊藉以調整該成本，進而給予特定道路之規劃及路線種類。

該系統可沿一特定道路與時間比較以估算實際完成旅行所需時間，而該估算方法係利用隱藏式設定，若該實際旅程時數少於該估計旅程時數，則該成本可針對那些特殊路線被調整，使增加該成本以利將來可被使用；若該實際旅程時數大於該估計旅程時數，則該成本另可針對那些特殊路線被調整，使減少該成本以利將來可被使用。

若該使用者知道一替代道路，但卻選擇行駛該導航系統所提供之導航路線，該使用者可能得先遵照該導航系統所提供之導航路線行駛以替代該使用者本身偏好之路線，針對上述狀況，該成本可依該使用者偏好進行調整，使該導航系統日後可依照該使用者偏好提供導航路線規劃。

該系統亦可分辨出一天中之時間單位、一星期中之天數單位、一個月中之星期單位或是一年中之月份單位，而該系統可在這些單位中得到在假日、週休假期以及平日不同時段中之交通尖峰時間，以提供專屬該使用者之導航路線規劃。

以上所述僅為本發明之較佳實施例，凡依本發明申請專利範圍所做之均等變化與修飾，皆應屬本發明之涵蓋範圍。

10-30．．．流程

100-108、200-210、300-310．．．步驟

第1圖為本發明第一實施例規劃路線之方法流程圖。

第2圖為本發明第二實施例規劃路線之方法流程圖。

第3圖為本發明第三實施例規劃路線之方法流程圖。

10．．．流程

100-108．．．步驟

Claims

一種利用一全球導航衛星系統(GNSS)之導航設備規劃導航路線的方法，其包含：該導航設備儲存一駕駛紀錄，該駕駛紀錄包含對應於一駕駛員的行駛調度之複數個路線分段；該導航設備基於該駕駛紀錄中之該複數個路線分段決定一偏好路線分段；該導航設備產生包含該偏好路線分段之一導航路線；該導航設備分配一成本給複數個路線分段中的每一路線分段；以及根據於該駕駛紀錄中該駕駛員開過該偏好路線分段之一次數調整該偏好路線分段之該成本。
如請求項1所述之方法，其中該偏好路線分段係由一第一位置至一第二位置之軌跡決定。
如請求項1所述之方法，其中該導航設備基於一類神經網路演算法，根據該駕駛紀錄決定該偏好路線分段。
如請求項3所述之方法，其中該類神經網路演算法根據該偏好路線分段出現於該駕駛紀錄之一次數，藉以調整由該第一位置至第二位置之軌跡中該偏好路線分段之一成本。
如請求項1所述之方法，更包含：該導航設備比較一實際時間與一估計時間；以及根據該比較結果調整一分配於該偏好路線分段之成本。
如請求項5所述之方法，其中該實際時間係為沿該導航路線，從一第一位置移動至一第二位置之時間。
如請求項6所述之方法，其中該導航路線包括該偏好路線分段。
如請求項5所述之方法，其中該估計時間係為沿一預定導航路線，從一第一位置移動至一第二位置之時間。
如請求項8所述之方法，其中該預定導航路線不包括該偏好路線分段。
如請求項5所述之方法，其中若該實際時間小於該估計時間，分配至該偏好路線分段之該成本便會減少。
如請求項5所述之方法，其中若該實際時間大於該估計時間，分配至該偏好路線分段之該成本便會增加。
如請求項1所述之方法，其中該複數個路線分段以及該偏好路線分段係對應實際路線分段。
如請求項1所述之方法，其中該導航設備係為一採用全球位置測定系統(GPS)之導航設備。
一種利用一全球導航衛星系統(GNSS)之導航設備規劃路線的方法，其包含：該導航設備儲存一駕駛紀錄，該駕駛紀錄包含對應一駕駛員的行駛調度之複數個路線分段；該導航設備根據一循環週期過濾該複數個路線分段；該導航設備過濾該複數個路線分段後，根據過濾出來的路線分段決定一偏好路線分段；該導航設備於該循環週期中之一事件內，產生包含該偏好路線分段之一導航路線；該導航設備分配一成本給複數個路線分段中的每一路線分段；以及根據於該駕駛紀錄中該駕駛員開過該偏好路線分段之一次數調整該偏好路線分段之該成本。
如請求項14所述之方法，其中該偏好路線分段係由一第一位置至一第二位置之軌跡決定。
如請求項14所述之方法，其中該導航設備基於一類神經網路演算法，根據該駕駛紀錄決定該偏好路線分段。
如請求項14所述之方法，其中該循環週期係對應一每日相同時間之週期。
如請求項14所述之方法，其中該循環週期係對應一每週相同時間之週期。
如請求項14所述之方法，其中該循環週期係對應一每月相同時間之週期。
如請求項14所述之方法，其中該循環週期係對應一每年相同時間之週期。
如請求項14所述之方法，其中該複數個路線分段及該偏好路線分段係對應實際路線分段。
如請求項14所述之方法，其中該導航設備係為一採用全球位置測定系統(GPS)之導航設備。
一種利用一全球導航衛星系統(GNSS)之導航設備規劃導航路線的方法，其包含：該導航設備決定一第一導航路線，而該第一導航路線係由一第一位置至一第二位置決定；當該導航設備從該第一導航路線偵測到一偏向時，該導航設備離開該第一導航路線，沿著一替代導航路線行駛且記錄該替代導航路線；該導航設備由該第一位置至該第二位置間記錄一時間週期；以及該導航設備基於一預定標準利用該替代導航路線代替該第一導航路線。
如請求項23所述之方法，該第一導航路線包含從該第一位置至該第二位置間決定之一最短路線。
如請求項23所述之方法，該第一導航路線包含從該第一位置至該第二位置間決定之一最快路線。
如請求項23所述之方法，其中記錄該替代導航路線之方法包括由該替代導航路線之複數個替代導航路線分段替代該第一導航路線之複數個第一導航路線分段。
如請求項23所述之方法，其中當該導航設備從該第一導航路線偵測到一軌跡時記錄該替代導航路線。
如請求項27所述之方法，其中該第一路線包含由該導航設備偵測到之一調度，該調度係不同於該第一路線之複數個第一調度。
如請求項27所述之方法，其中該第一路線係包含由該導航設備偵測到之一位置，該位置係位在一路線分段而非沿該第一導航路線得之。
如請求項27所述之方法，其中該預定標準係包含該時間週期，其係為沿該替代導航路線，從第一位置移動至該第二位置之時間。
如請求項30所述之方法，其中該時間週期較一估計時間週期短。
如請求項31所述之方法，其中該估計時間係為沿該第一導航路線，從第一位置移動至該第二位置之時間。
如請求項27所述之方法，其中該第一導航路線以及該替代導航路線分段係對應實際路線分段。
如請求項27所述之方法，其中該導航設備係為一採用全球位置測定系統(GPS)之導航設備。