TWI453374B - 特定區域之行動式導航路徑規劃方法 - Google Patents

Description

特定區域之行動式導航路徑規劃方法

本發明是有關於一種行動式導航系統及其路徑規劃方法，特別是指一種應用於一特定區域之行動式導航系統及其路徑規劃方法。

現今運用於道路導航的全球衛星導航系統(Global Positioning System,GPS)，其所使用的電子地圖大多僅侷限應用於一般開放性道路上，而對於公園、賣場、風景區或校園等等特定區域之內部道路，往往不在全球衛星導航系統執行路徑規劃時的規劃條件內，因此，對於使用者而言，其所得到的路徑規劃結果並不一定會是最佳路徑，舉例來說，參閱圖1，當一使用者欲由城市A前往城市B，而且於城市A與城市B之間有一風景區C，在現今技術之下，全球衛星導航系統將會規劃使用者以路徑S1由城市A前往城市B，然而，若是全球衛星導航系統於規劃路徑時可以考慮風景區內部路徑的話，以路徑S2由城市A前往城市B相較於路徑S1而言，可以得到較短之距離，因此，可見現今全球衛星導航系統之路徑規劃技術仍存有盲點。

而一般而言，導航路徑規劃的演算法往往被歸類為旅行業務員問題(travelling salesman problem)，因此，由演算法基本理論可以得知此類問題的計算複雜度為一高於非確定性多項式問題(NP-Hard)，所以計算付雜度相當高且硬體運算成本亦相對較高。此外，系統開發廠商開發導航系統時，往往需要支付所需的地理資訊系統(Geographic Information System,GIS)之商業授權金，因此，會增加系統開發的成本支出。

綜合上述，如何有效規劃一特定區域之內部路徑，並可以降低路徑規劃所需的成本，對於現今導航路徑規劃技術而言，仍是相當值得相關領域之人士研究改善的議題之一。

因此，本發明之目的，即在提供一種特定區域之行動式導航路徑規劃方法，適用於以一處理器接收一起始節點與一終止節點的座標值，其包含以下步驟：

(A)組配該處理器，根據該起始節點與該終止節點的座標值，以計算出至少一個中間節點座標值的範圍；

(B)組配該處理器，根據該中間節點座標值的範圍，以得到一路徑矩陣與一節點陣列；

(C)組配該處理器，根據該路徑矩陣以判斷在該起始節點與該終止節點間是否有路徑連接，若是，則該處理器得到一導航路徑規劃結果，若否，執行步驟(D)；

(D)組配該處理器，由該節點陣列得到一更新後的節點陣列，並根據該更新後的節點陣列得到一與該起始節點有路徑連接之中間節點；

(E)組配該處理器，判斷所得到之中間節點是否與該終止節點有路徑連接，若是，則該處理器得到一導航路徑規劃結果，若否，則以中間節點作為更新後的起始節點P，並跳回至步驟(D)。

此外，本發明另外提供一種特定區域之行動式導航系統，適用於接收一起始節點與一終止節點的座標值，其包含：一儲存單元，儲存一地圖資料與一顯示資訊；一處理單元，與該儲存單元電連接，並接收該地圖資料與該顯示資訊，以計算得到一導航路徑規劃結果；及一顯示單元，與該處理單元電連接，以接收該導航路徑規劃結果及該顯示資訊，並將其顯示之。

於是，本發明之功效在於藉由一低計算複雜度之特定區域之行動式導航路徑規劃方法，以降低對應之行動式導航系統所需要之硬體成本，此外，由於該特定區域之內部節點座標為預先儲存，所以，即使在難以接收衛星訊號之處(例如：室內或地下室)，本發明依然可以得到該導航路徑規劃之結果，因此，本發明亦可應用於室內導航路徑規劃。

有關本發明之相關申請專利特色與技術內容，在以下配合參考圖式之一個較佳實施例的詳細說明中，將可清楚的呈現。

特定區域之行動式導航路徑規劃方法

在說明本發明之特定區域之行動式導航路徑規劃方法之前，合先述明有關定義如下：

在一特定區域中(例如：校園或是風景區)，在導航路徑規劃的一起點(Start Point)與一終點(End Point)分別被設定為一起始節點P_s 與一終止節點P_e ，並且路徑規劃之結果即為最短路徑，也就是將各個節點從起點到終點以及中間必要的節點，路徑上所有兩個節點間距離加總的結果為最小值。以下，將以圖形理論(Graph Theory)加以進一步說明：

定義一 ：假設一特定區域中共有n個節點為{P₁ ,P₂ ,…,P_n }，每個節點P_i (i=1,2,…,n)都有一個對應的座標值(x_i ,y_i )，其中，每一座標值(x_i ,y_i )可以由實際的經緯度位置來加以表示。舉例來說，參閱圖2，節點5與15的座標值分別為(1,1)與(5,4)。

定義二 ：假設一特定區域中n個節點為{P₁ ,P₂ ,…,P_n }，每兩個節點P_i 與P_j (i,j=1,2,…,n)間的距離D(i,j)可以依不同情況而表示如下：

(1)D(i,j)=0，其中P_i 與P_j 為相同之節點；

(2)D(i,j)=∞，其中P_i 與P_j 為不同之節點且兩者之間無相連路徑；及

(3)D(i,j)=L，其中P_i 與P_j 表示不同節點且有路徑相連且兩點距離為L。

所以，對於一具有n個節點的特定區域，其節點間的距離以一維度為n×n的路徑矩陣(Path Matrix)M來表示。

根據上述的定義，聯合參閱圖2、3，本發明之特定區域之路徑規劃方法之一較佳實施例，適用於以一處理器接收一起始節點P_s 與一終止節點P_e 的座標值，其包含以下步驟：

步驟91是組配該處理器，根據該起始節點P_s 與該終止節點P_e 的座標值分別為(x_s ,y_s )與(x_e ,y_e )，以計算出介於該起始節點P_s 與該終止節點P_e 間的至少一個中間節點P_r 座標值(x_r ,y_r )的範圍如下方程式(F .1)、(F .2)所示：

min(x _s ,x _e ) x _r max(x _s ,x _e ).....(F .1)

min(y _s ,y _e ) y _r max(y _s ,y _e ).....(F .2)

舉例來說，假設一起始節點為P₅ (1,1)與一終止節點為P₁₅ (5,4)，則

1 x _r 5.....(F .3)

1 y _r 4.....(F .4)

步驟92是組配該處理器，根據方程式(F .1)、(F .2)，得到該特定區域中符合方程式(F .1)、(F .2)的所有中間節點P_r (r=1,2,…,n)，並由該等中間節點P_r (r=1,2,…,n)形成一節點陣列V，並且以該節點陣列V中所有元素做為一矩陣之行元素與列元素，以得到一路徑矩陣。

承上例，符合方程式(F .3)、(F .4)之x_r 與y_r 範圍的節點共有P₄ (1,3)、P₇ (2,4)、P₈ (2,1)、P₉ (3,3)、P₁₂ (4,3)、P₁₃ (4,2)、P₁₆ (5,1)，其中，該節點陣列V為{P₅ ,P₁₅ ,P₄ ,P₇ ,P₈ ,P₉ ,P₁₂ ,P₁₃ ,P₁₆ }。而該路徑矩陣M如下表1所示：

此時，該路徑矩陣M的維度大小從16×16降為9×9。

步驟93是組配該處理器，根據該路徑矩陣M，以判斷在該起始節點P_s 與該終止節點P_e 間是否有路徑連接，若是，則該處理器得到該導航路徑規劃結果，若否，執行步驟94。

承上例，該處理器判斷該起始節點為P₅ 與該終止節點為P₁₅ 間並無路徑連接，因為在該路徑矩陣M中，D(5,15)=∞，也就是說，根據上述定義二，該起始節點P₅ 與該終止節點P₁₅ 之間無相連路徑，繼續執行步驟94。

步驟94是組配該處理器，由該節點陣列V中移除該起始節點P_s 與該終止節點P_e ，得到一更新後的節點陣列V'，並根據該更新後的節點陣列V'得到一與該起始節點P_s 有路徑連接之中間節點P_r 。

承上例，該處理器將由該節點陣列V中移除該起始節點P₅ 與該終止節點P₁₅ ，因此，該更新後的節點陣列為：

V'={P₄ ,P₇ ,P₈ ,P₉ ,P₁₂ ,P₁₃ ,P₁₆ }；

步驟95是組配該處理器，根據該更新後的節點陣列V'得到一與該起始節點P_s 有路徑連接之中間節點P_r 。

承上例，該處理器由該節點陣列V'得到一與該起始節點P₅ 有路徑連接之中間節點P₄ 。

步驟96是組配該處理器，判斷步驟94中所得到之中間節點P_r 是否與該終止節點P_e 有路徑連接，若是，則該處理器得到一導航路徑規劃結果，若否，則以中間節點P_r 作為更新後的起始節點P'_s ，並跳回至步驟94。

承上例，該中間節點P₄ 與該起始節點P₅ 有路徑連接，但是該中間節點P₄ 與該終止節點P₁₅ 沒有路徑連接，因此，該處理器將該中間節點P₄ 設定為更新後的起始節點P'_s =P₄ ，並跳回至步驟94。

重複地，該處理器由該節點陣列V'得到一與該起始節點P₄ 有路徑連接之中間節點P₇ 。然後，該中間節點P₇ 與該起始節點P₄ 有路徑連接，且該中間節點P₇ 與該終止節點P₁₅ 也有路徑連接，因此，該處理器得到一導航路徑規劃結果為P₅ →P₄ →P₇ →P₁₅ 。

而且該處理器依據該路徑矩陣M可以得到該P₅ →P₄ 之距離為2，P₄ →P₇ 之距離為1.4，P₇ →P₁₅ 之距離為3，所以，該導航路徑規劃結果之總距離為2+1.4+3=6.4。

一般而言，在一特定區域中，通常其範圍不大且各節點之間的距離差距也並不大，所以本較佳實施例根據一深度搜尋(Depth First Search,DFS)以尋找導航路徑規劃結果，因此只要該處理器能得到一導航路徑規劃結果，其與最佳之導航路徑規劃結果相差不大。所以，由本發明之特定區域之行動式導航路徑規劃方法所得到之導航路徑規劃結果可視為一較佳解。

此外，依據步驟91與步驟92所簡化的搜尋節點數目為k，則步驟93、94、95所產生的計算次數T為：

T=2×(k+(k-1)+(k-2)+…+2+1).....(F .5)

因此，本發明之特定區域之行動式導航路徑規劃方法的計算複雜度為O(k ² )。

值得說明的是，本發明之特定區域之行動式導航路徑規劃方法亦可以一電腦程式實現，並儲存於一電腦媒體(例如：一光碟片或一硬式磁碟)中。

特定區域之行動式導航系統

參閱圖4，本發明之特定區域之行動式導航系統，適用於接收一起始節點P_s 與一終止節點P_e 的座標值，其包含：一儲存單元51、一處理單元52，及一顯示單元53。

該儲存單元51與該處理單元52電連接，以將一地圖資料傳送至該處理單元52中，該處理單元52根據該地圖資料，以計算得到一導航路徑規劃結果，同時，該處理單元52由該儲存單元51中得到對應之一組顯示資訊，然後，該處理單元52將該導航路徑規劃結果、該組顯示資訊輸出至該顯示單元53中，該顯示單元53與該處理單元52電連接並用以顯示該導航路徑規劃結果及對應之該組顯示資訊。

值得說明的是，該地圖資料包括一特定區域中之每一節點之座標值，而該顯示資訊包括該特定區域中每一節點對應之圖片資訊以及語音資訊。

舉例來說，本較佳實施例利用前述特定區域之行動式導航路徑規劃方法 ，根據該起始節點P_s 的座標值、該終止節點P_e 的座標值、以及該特定區域中之每一節點之座標值以得到並顯示出該導航路徑規劃結果與對應之該組顯示資訊。

較佳地，在本實施例中，該儲存單元51是一記憶卡(Storage Card)，該處理單元52是一Intel PXA270中央處理器(CPU)，及該顯示單元53是一薄膜電晶體液晶顯示器(TFT-LCD)。

綜合上述，本發明提出一具有低計算複雜度的特定區域之行動式導航路徑規劃方法，以降低對應之行動式導航系統所需要之硬體成本，此外，本發明將一特定區域(例如：學校)中多數個定點之座標以及照片等資訊預先儲存，然後根據每個節點所對應之座標，以進行特定區域之導航路徑規劃，由於該特定區域之內部節點座標為預先儲存，所以，即使在難以接收衛星訊號之處(例如：室內或地下室)，本發明依然可以得到該導航路徑規劃之結果，因此，本發明亦可應用於室內導航路徑規劃。故確實可以達成本發明之目的。

惟以上所述者，僅為本發明之較佳實施例而已，當不能以此限定本發明實施之範圍，即大凡依本發明申請專利範圍及發明說明內容所作之簡單的等效變化與修飾，皆仍屬本發明專利涵蓋之範圍內。

51．．．儲存單元

52．．．處理單元

53．．．顯示單元

91~96．．．步驟

圖1是一先前技術之路徑規劃示意圖；

圖2是一特定區域之行動式導航路徑規劃之範例；

圖3是本發明之特定區域之行動式導航路徑規劃方法之流程圖；及

圖4是本發明之特定區域之行動式導航系統之方塊圖。

91~96‧‧‧步驟

Claims (4)

1. 一種特定區域之行動式導航路徑規劃方法，適用於以一處理器接收一起始節點與一終止節點的座標值，其包含以下步驟：(A)組配該處理器，根據該起始節點與該終止節點的座標值，以計算出至少一個中間節點座標值的範圍；(B)組配該處理器，根據該中間節點座標值的範圍，以得到一路徑矩陣與一節點陣列；(C)組配該處理器，根據該路徑矩陣以判斷在該起始節點與該終止節點間是否有路徑連接，若是，則該處理器得到一導航路徑規劃結果，若否，執行步驟(D)；(D)組配該處理器，由該節點陣列得到一更新後的節點陣列，並根據該更新後的節點陣列得到一與該起始節點有路徑連接之中間節點；(E)組配該處理器，判斷所得到之中間節點是否與該終止節點有路徑連接，若是，則該處理器得到一導航路徑規劃結果，若否，則以中間節點作為更新後的起始節點P，並跳回至步驟(D)。
2. 依據申請專利範圍第1項所述之特定區域之行動式導航路徑規劃方法，其中，在該步驟(D)中，是組配該處理器，以移除該起始節點與該終止節點，進而得到該更新後的節點陣列。
3. 依據申請專利範圍第1項所述之特定區域之行動式導航路徑規劃方法，其中，在該步驟(A)中，該中間節點之x座標值的範圍為大於該起始節點與該終止節點之x座標值的最小值，且小於該起始節點與該終止節點之x座標值的最大值，該中間節點之y座標值的範圍為大於該起始節點與該終止節點之y座標值的最小值，且小於該起始節點與該終止節點之y座標值的最大值。
4. 依據申請專利範圍第3項所述之特定區域之行動式導航路徑規劃方法，其中，在該步驟(B)中，根據符合該中間節點之x、y座標值的範圍之所有中間節點，得到該節點陣列，並且以該節點陣列之所有元素做為一矩陣之行元素與列元素，以得到該路徑矩陣。