TWI391628B - 導航系統及其路徑規劃方法，及其機器可讀取媒體 - Google Patents

Description

導航系統及其路徑規劃方法，及其機器可讀取媒體

本發明係有關於一種路徑規劃方法及其相關之導航系統，特別是有關於一種可以快速路徑重新規劃之路徑規劃方法及其相關之導航系統。

近年來，全球定位系統(Global Positioning System，GPS)被廣泛運用在各種電子裝置例如行動電話或是汽車的導航系統上，其係接收衛星訊號，並根據與各顆衛星的相對位置對擁有全球定位系統接收器的電子裝置作定位，以判定電子裝置的位置。使用者亦可以利用電子裝置中的導航軟體進行路徑規劃與導航作業。

一般而言，當使用者欲從一起點前往一目的地時，導航軟體可依據一特定演算法，規劃出一路徑，引導使用者知道行進方向。然而，當使用者未依照指定的行進方向前進時，此時重新路徑規劃的機制便會啟動，重新以目前位置，規劃出一條新的路徑前往目的地。由於重新路徑規劃的運算需要考慮許多不同的因素，例如兩點間的距離以及附近道路複雜度等等，所需的耗費的時間可能很長。若重新規劃的時間花費太久，使用者便無法得知應該往那個方向行進，有可能造成繞路或行進至不應該走的地方。因此，如何縮短重新規劃所需的時間是一個很重要的課題。

有鑑於此，本發明提供一種快速路徑重新規劃之路徑規劃方法及及其相關之導航系統，以解決上述的問題。

本發明實施例提供一種路徑規劃方法，適用於一具有導航系統之電子裝置，用以從一起點導航至一終點。路徑規劃方法包括下列步驟。首先，取得電子裝置之一目前位置，接著，找到相應目前位置之一決策點，其中決策點具有一規劃路徑所規劃之一指定行進方向以及複數可能行進方向。其次，產生相應可能行進方向至終點之複數候選路徑。接著，利用候選路徑之一者或規劃路徑，將電子裝置導航至終點。

本發明實施例另提供一種導航系統，適用於一電子裝置，包括一顯示單元、一處理單元以及一路徑規劃單元。處理單元取得電子裝置之一目前位置並找到相應目前位置之一決策點，其中決策點具有一規劃路徑所規劃之一指定行進方向以及複數可能行進方向。路徑規劃單元產生相應決策點之可能行進方向至終點之複數候選路徑。當行經決策點時，處理單元利用候選路徑之一者或規劃路徑，將電子裝置導航至終點。

本發明實施例更提供一種路徑規劃方法，適用於一具有導航系統之電子裝置，用以從一起點導航至一終點，包括下列步驟。首先，依據起點以及終點，規劃一第一路徑，其中第一路徑上至少包括一決策點，決策點具有第一路徑所規劃之一指定行進方向以及複數可能行進方向。當行進於起點以及決策點之間時，預先規劃決策點之可能行進方 向至終點之複數對應第二候選路徑。當行進至決策點且偏離第一路徑所規劃之指定行進方向時，選取第二候選路徑中之一替代路徑替換第一路徑，並以替代路徑將電子裝置導航至終點。

本發明上述方法可以透過程式碼方式收錄於實體媒體中。當程式碼被機器載入且執行時，機器變成用以實行本發明之裝置。

為使本發明之上述和其他目的、特徵、和優點能更明顯易懂，下文特舉出較佳實施例，並配合所附圖式，作詳細說明如下。

本發明實施例中提供一種導航系統及其相關之路徑規劃方法，適用於一電子裝置，用以於電子裝置行經偏離原先規劃的路徑時，快速地以預先規劃好的路徑取代原先規劃的路徑，可縮短路徑重新規劃所需的時間。

第1圖顯示依據本發明實施例之導航系統。依據本發明實施例之導航系統可以適用於具有導航功能之一電子裝置，如電腦系統與可攜式裝置等。導航系統100至少包括一儲存單元110、一顯示單元120、一路徑規劃單元130與一處理單元140。儲存單元110係用以儲存包括相應至少一特定區域，如地區或國家之圖資資料。其中，圖資資料可以包括門牌地址、地標、景點、與/或道路及道路資訊等。顯示單元120係用以顯示相關資料，如使用者操作介面、路徑規劃結果、與相關導航資訊。處理單元140可以 為具有路徑規劃能力之一導航引擎。使用者可以透過使用者操作介面輸入導航情況，如一起點、一終點、與/或至少一經過點等。處理單元140可以依據輸入之起點、經過點以及終點，進行路徑規劃，從而得到路徑規劃結果。使用者可以依據路徑規劃結果進行導航至目的地。值得注意的是，導航系統100可更包括一訊號接收單元(未顯示)，用以接收衛星接收訊號。處理單元140可以依據接收之訊號計算電子裝置的目前位置。路徑規劃單元130可依據電子裝置的目前位置，找到規劃路徑中相應於目前位置的一決策點(decision point)C，並預先規劃決策點C的其他可能行進方向到終點的所有規劃路徑，再將規劃結果儲存於儲存單元110。決策點C具有由規劃路徑所規劃之一指定行進方向以及多個可能行進方向。舉例來說，請參照第2A圖以及第2B圖，第2A圖以及第2B圖顯示依據本發明實施例之路徑規劃結果示意圖。如第2A圖所示，顯示單元120中顯示由起點S至終點D的一規劃路徑P。其中，X表示電子裝置的目前位置，C表示一決策點。請注意，於本實施例中，決策點C係為目前位置之下一交又路口，因此，當電子裝置行經某一決策點C時，會有多個可能行進方向。如第2B圖所示，決策點C除了具有規劃路徑P所規劃之一指定行進方向1(向右轉)之外，另外包括可能行進方向2(直行)以及3(向左轉)。換言之，當電子裝置行經決策點C時，可能會依行進方向1、2或3繼續前進。當電子裝置的目前位置符合路徑規劃結果中的規劃時，處理單元 140可以繼續依據原有之路徑規劃結果提供導航功能，行進至目的地(即終點D)。當電子裝置的目前位置不符合路徑規劃結果中的規劃時，處理單元140可以依據電子裝置的目前位置重新進行路徑規劃，此時處理單元140將執行本發明之路徑規劃方法，其細節將於後說明。

第3圖顯示一依據本發明實施例之路徑規劃方法之流程圖。依據本發明實施例之路徑規劃方法可以適用於具有導航功能之一電子裝置，如電腦系統與可攜式裝置等。

首先，如步驟S310，導航開始，依據使用者設定的起點以及終點，產生一規劃路徑P。接著，如步驟S320，依據電子裝置之目前位置，找到相應目前位置的一決策點，並規劃出決策點的其他可能行進方向所對應的候選路徑。其中，每一候選路徑係以行進方向至終點進行路徑規劃所產生。當行經決策點時，如步驟S330，判斷電子裝置是否偏離規劃路徑P。若電子裝置未偏離規劃路徑P(步驟S330的否)，如步驟S340，便可刪除候選路徑，接著執行步驟S370。若電子裝置偏離規劃路徑P(步驟S330的是)，亦即電子裝置未依指定行進方向前進，如步驟S350，依據電子裝置的目前位置選擇其中一條候選路徑作為替代路徑。並且，如步驟S360，以選取的候選路徑(替代路徑)取代原規劃路徑P，將電子裝置導航至終點。接著，如步驟S370，判斷導航是否結束。亦即，是否已到達目的地。若導航已經結束(步驟S360的是)，則結束流程。若導航尚未結束(步驟S360的否)，便返回步驟S320，依據電子裝置之目前位 置，找到相應目前位置的下一決策點，並規劃出下一決策點的其他可能行進方向所對應的候選路徑。

舉例來說，請參考第4A圖以及第4B圖，第4A圖以及第4B圖顯示依據本發明實施例之路徑規劃之示意圖。如第4A圖所示，顯示一由起點S至終點D的一規劃路徑P。其中，X表示電子裝置的目前位置，C表示相應於目前位置的一決策點C，並且決策點C具有規劃路徑P所規劃之一指定行進方向1以及可能行進方向2以及3。因此，當電子裝置行經起點S與決策點C之間時，路徑規劃單元130規劃出決策點C的其他可能行進方向2以及3所對應的至終點D的候選路徑P2以及P3。候選路徑P2以及P3將被預先儲存於儲存單元110中。若電子裝置行經決策點C時，依據指定行進方向1前進，表示未偏離航線，因此便可刪除預先規劃的候選路徑P2以及P3，以原先規劃的路徑P繼續導航至終點D。

反之，若電子裝置行經決策點C時，依據行進方向2或3前進，表示偏離航線，此時便依據電子裝置之目前位置，選擇預先規劃的候選路徑P2或P3，用以取代原先的規劃的路徑P，並以取代後的路徑P2或P3，將電子裝置導航至終點D。

如第4B圖所示，假設電子裝置於行經決策點C後朝行進方向2前進，已偏離航線，則處理單元140將依據計算出的目前位置，自動將行進方向2所規劃出的候選路徑P2取代原先的規劃的路徑P進行導航。類似地，當電子裝 置行經決策點C與決策點C’之間時，路徑規劃單元130規劃出決策點C’的其他可能行進方向4以及5所對應的至終點D的候選路徑P4以及P5。候選路徑P4以及P5將被預先儲存於儲存單元110中。若電子裝置行經決策點C’時，依據指定行進方向前進，便可刪除預先規劃的候選路徑P4以及P5，以原先規劃的路徑P2繼續導航至終點D。若電子裝置行經決策點C’時，依據行進方向4或5前進，表示偏離航線，此時便依據電子裝置之目前位置，選擇預先規劃的候選路徑P4或P5，取代原先的規劃的路徑P2，並以取代後的路徑P4或P5，將電子裝置導航至終點D。

綜上所述，依據本發明之導航系統及路徑規劃方法，藉由電子裝置之目前位置，找到並預先規劃下一個具有多個可能行進方向的決策點所有到終點的路徑，當電子裝置行經決策點並產生偏離航線時，可立刻以預先規劃好的路徑取代原有的路徑，無須重新計算並規劃出新路徑，可縮短重新路徑規劃所需的時間。

本發明之方法，或特定型態或其部份，可以以程式碼的型態包含於實體媒體，如軟碟、光碟片、硬碟、或是任何其他機器可讀取(如電腦可讀取)儲存媒體，其中，當程式碼被機器，如電腦載入且執行時，此機器變成用以參與本發明之裝置。本發明之方法與裝置也可以以程式碼型態透過一些傳送媒體，如電線或電纜、光纖、或是任何傳輸型態進行傳送，其中，當程式碼被機器，如電腦接收、載入且執行時，此機器變成用以參與本發明之裝置。當在一 般用途處理器實作時，程式碼結合處理器提供一操作類似於應用特定邏輯電路之獨特裝置。

雖然本發明已以較佳實施例揭露如上，然其並非用以限定本發明，任何熟悉此項技藝者，在不脫離本發明之精神和範圍內，當可做些許更動與潤飾，因此本發明之保護範圍當視後附之申請專利範圍所界定者為準。

100‧‧‧導航系統

110‧‧‧儲存單元

120‧‧‧顯示單元

130‧‧‧路徑規劃單元

140‧‧‧處理單元

S‧‧‧起點

C、C’‧‧‧決策點

D‧‧‧終點

X‧‧‧目前位置

P、P2~P5‧‧‧規劃路徑

1－5‧‧‧行進方向

S310－S370‧‧‧執行步驟

第1圖係顯示依據本發明實施例之導航系統。

第2A圖以及第2B圖係顯示依據本發明實施例之路徑規劃結果示意圖。

第3圖係顯示一依據本發明實施例之路徑規劃方法之流程圖。

第4A圖以及第4B圖係顯示依據本發明實施例之路徑規劃之示意圖。

S310－S370‧‧‧執行步驟

Claims (14)

1. 一種路徑規劃方法，適用於一具有導航系統之電子裝置，用以從一起點導航至一終點，包括下列步驟：取得該電子裝置之一目前位置；找到一規劃路徑上相應該目前位置之一決策點，其中該決策點具有該規劃路徑所規劃之一指定行進方向以及複數可能行進方向；產生相應該等可能行進方向至該終點之複數候選路徑；以及利用該等候選路徑之一者或該規劃路徑，將該電子裝置導航至該終點，其中該利用該等候選路徑之一者或該規劃路徑導航至該終點之步驟更包括當行進至該決策點且偏離該規劃路徑所規劃之該指定行進方向時，以該等候選路徑之一者替換該規劃路徑，並以該替換之候選路徑導航至該終點。
2. 如申請專利範圍第1項所述之路徑規劃方法，其中該等候選路徑係產生於行進於該起點以及該決策點之間時。
3. 如申請專利範圍第1項所述之路徑規劃方法，其中該利用該等候選路徑之一者或該規劃路徑導航至該終點之步驟，更包括：若行進至該決策點且未偏離該規劃路徑所規劃之該指定行進方向時，刪除該等候選路徑，繼續以該規劃路徑導航至該終點。
4. 如申請專利範圍第3項所述之路徑規劃方法，更包括：規劃一下一決策點之複數可能行進方向對應之複數第二候選路徑，其中該下一決策點係位於該決策點以及該終點之間；以及當行進至該下一決策點且偏離該規劃路徑所規劃之該指定行進方向時，以該等第二候選路徑之一者替換該規劃路徑，並以該替換之第二候選路徑導航至該終點。
5. 一種導航系統，適用於一電子裝置，包括：一顯示單元：一處理單元，取得該電子裝置之一目前位置並找到相應該目前位置之一決策點，其中該決策點具有一規劃路徑所規劃之一指定行進方向以及複數可能行進方向；以及一路徑規劃單元，產生相應該決策點之該等可能行進方向至該終點之複數候選路徑，其中當行經該決策點時，該處理單元利用該等候選路徑之一者或該規劃路徑，將該電子裝置導航至該終點且其中該處理單元更於行進至該決策點且偏離該規劃路徑所規劃之該指定行進方向時選擇該等候選路徑之一者替換該規劃路徑，並以該替換之候選路徑導航至該終點。
6. 如申請專利範圍第5項所述之導航系統，其中該等候選路徑係於行進於該起點以及該決策點之間時，由該路徑規劃單元所產生。
7. 如申請專利範圍第5項所述之導航系統，其中當該 電子裝置行進至該決策點且未偏離該規劃路徑所規劃之該指定行進方向時，該處理單元刪除該等候選路徑，繼續以該規劃路徑導航至該終點。
8. 如申請專利範圍第7項所述之導航系統，其中該路徑規劃單元更規劃下一決策點之複數可能行進方向對應之複數第二候選路徑，其中該下一決策點係位於該決策點以及該終點之間，且當行進至該下一決策點且偏離該規劃路徑所規劃之該指定行進方向時，該處理單元以該等第二候選路徑之一者替換該規劃路徑，並以該替換之第二候選路徑導航至該終點。
9. 一種路徑規劃方法，適用於一具有導航系統之電子裝置，用以從一起點導航至一終點，包括下列步驟：依據該起點以及該終點，規劃一第一路徑，其中該第一路徑上至少包括一決策點，該決策點具有該第一路徑所規劃之一指定行進方向以及複數可能行進方向；當行進於該起點以及該決策點之間時，預先規劃該決策點之該等可能行進方向至該終點之複數對應第二候選路徑；以及當行進至該決策點且偏離該第一路徑所規劃之該指定行進方向時，選取該等第二候選路徑中之一替代路徑替換該第一路徑，並以該替代路徑將該電子裝置導航至該終點。
10. 如申請專利範圍第9項所述之路徑規劃方法，其中該選取該等第二候選路徑中之該替代路徑之步驟更包括：取得該電子裝置之一目前位置；以及 依據該目前位置，由該等第二候選路徑中得到該替代路徑。
11. 如申請專利範圍第9項所述之路徑規劃方法，更包括：依據該目前位置，找到一相應之第一決策點，其中該第一決策點具有該替代路徑所規劃之一指定行進方向以及複數可能行進方向；規劃該第一決策點之該等可能行進方向對應之複數第三候選路徑；以及當行進至該第一決策點且偏離該替代路徑所規劃之該指定行進方向時，以該等第三候選路徑之一者替換該第一路徑，並以該替換之第三候選路徑導航至該終點。
12. 如申請專利範圍第9項所述之路徑規劃方法，更包括：若行進至該決策點且未偏離該第一路徑所規劃之該指定行進方向時，刪除該等第二候選路徑，繼續以該第一路徑導航至該終點。
13. 如申請專利範圍第12項所述之路徑規劃方法，更包括：規劃下一決策點之複數可能行進方向對應之複數第三候選路徑，其中該下一決策點係位於該決策點以及該終點之間；以及當行進至該下一決策點且偏離該第一路徑所規劃之該指定行進方向時，以該等第三候選路徑之一者替換該第一 路徑，並以該替換之第三候選路徑導航至該終點。
14. 一種機器可讀取媒體，儲存一程式碼用以執行時致使一裝置執行一路徑規劃方法，該方法包括下列步驟：產生一規劃路徑，其中該裝置依據該規劃路徑進行一導航；取得該裝置之一目前位置；找到相應該目前位置之一決策點，其中該決策點具有一規劃路徑所規劃之一指定行進方向以及複數可能行進方向；產生相應該等可能行進方向至該終點之複數候選路徑；以及利用該等候選路徑之一者或該規劃路徑，將該裝置導航至該終點，其中該利用該等候選路徑之一者或該規劃路徑導航至該終點之步驟更包括當行進至該決策點且偏離該規劃路徑所規劃之該指定行進方向時，以該等候選路徑之一者替換該規劃路徑，並以該替換之候選路徑導航至該終點。