一種基於移動導航系統的路徑搜索方法
2023-04-23 07:10:26
專利名稱：一種基於移動導航系統的路徑搜索方法
技術領域：
本發明涉及移動導航中的路徑搜索領域，特別地，涉及一種基於移動導航 系統的路徑搜索方法。
背景技術：
移動導航系統一般分為以下幾個模塊:導航數據載入，導航地圖顯示，導 航路徑搜索，導航提示分析模塊。移動導航系統通過GPS設備實時接收當前位置，在導航過程中有時需要進 行路徑重算，並且由於行動裝置的硬體資源受限，所以對路徑搜索算法的效率 和內存消耗方面要求較嚴格。在導航路徑搜索中，當前一般採用的方法主要是基於Dijkstm算法進行搜索 的，該方法是面向路徑搜索的通用型方法，沒有充分利用導航系統的特徵，並 且在搜索的擴散過程中需要記錄的節點數較多，耗費的內存較多，並且效率較 低，特別是在移動導航系統中， 一般的行動裝置硬體資源受限，更加突出了傳 統方法的資源耗費和效率較低問題。發明內容本發明的目的在於針對現有技術的不足，提供一種基於移動導航系統的路 徑搜索方法。應用本發明的方法，搜索過程中擴展的節點數大大減少，這樣便 減少了內存的佔用，提高搜索效率。本發明的目的是通過以下技術方案來實現的 一種基於移動導航的路徑搜 索方法，包括以下步驟選取目標點；將目標點和出發點的坐標轉化為投影坐 標，綁定到地圖上道路網絡中最近的路上；記錄當前目標點作為下次目標點綁 定的啟發信息；根據綁定後的出發點和目標點以及當前的行駛方向，該方向以 正北作為0度，來自GPS模塊，轉化為弧度單位，在路網上進行拓撲路徑搜索。路徑搜索完畢，返回搜索結果。本發明的有益效果是本發明充分利用了目標點的坐標位置已知的信息， 通過啟發搜索，減少搜索擴散過程中擴散的節點數，從而減少搜索過程載入內 存的數據量，提高搜索效率。測試發現，在搜索距離出發點不超過半個路網的 半徑距離內的目標點時，使用本發明的擴散節點數是一般方法擴散節點數的 25%;而在超過了半個路網之外的目標點的搜索上，其擴散節點數也可達到一般 方法的50%;從而擴散節點數大幅減少，載入的內存成相應減少，效率得到提 高。
圖1是本發明基於移動導航系統的路徑搜索方法流程圖； 圖2是綁定道路流程圖。
具體實施方式
本發明所依據的原理是將道路網絡的拓撲鄰接信息提取出來作路徑分析， 道路網絡包含拓撲節點和拓撲邊結構，邊中含有長度信息，作為路徑搜索時的 權重信息，拓撲節點和拓撲邊存有網絡對象的鄰接關係。利用目標點坐標位置 已知的信息作為啟發信息，利用當前節點到目標點的直線距離作為搜索過程的 啟發值，加快搜索。本發明的路徑搜索方法，包含以下步驟1. 選取目標點可通過觸摸筆在地圖上選取，也可通過選取興趣點，設為目標點；出 發點是根據GPS模塊實時地位得到的當前位置；2. 出發點和目標點綁定到最近道路 將目標點和出發點轉化為投影坐標，綁定到地圖上道路網絡中最近的路上；記錄當前目標點作為下次目標點綁定的啟發信息，初始設置上次 目標點為位置為(0， 0);2.1先綁定目標點，判斷當前目標點是否在上次的目標點附近(如在容忍距離50米內)，若是，則直接使用上次綁定結果，不需要進行綁定，否則轉綁定(綁定步驟見下)；2.2根據目標點的綁定結果(包含綁定到路的距離，綁定到的路的GRL (地理資源定位)信息，綁定到路上的位置)，判定目標點是否在 搜索路網上，若不在，則轉4;否則更新上次目標點綁定結果，轉 下步；2.3綁定出發點，出發點位置來自GPS模塊的當前位置，也即導航設 備當前位置，和目標點不同，這裡直接進行綁定，若綁定結果判斷 出發點不在路網上，則轉4;否則轉下步；3.搜索路徑3.1轉化綁定點為拓撲節點對-該拓撲節點對含以下信息節點坐標位置，出發點到節點方向 (正北為0弧度)，出發點到當前節點實際距離；;根據所在的道路GRL得到對應的網絡拓撲邊，分別記錄出發點和目標點對應的拓撲節點對，記錄綁定的點到該拓撲邊的兩個端節點的距離；3.2判斷出發點和目標點是否在同一條網絡邊上，若是，則轉3.3;否則轉3.4; 3.3兩點同邊的特殊情況處理若當前方向cur一diK0，認為是不考慮方向信息，則直接取出出 發點和目標點之間的路段信息，將該路段信息轉為路徑結果，轉4;否則，計算得出發點到目標點的直線方向dirl，比較cur一dir和 dirl，如果兩個方向的角度偏差在(-90， 90)度，取出出發點與目 標點之間的路段信息，轉為路徑結果，轉4;否則，計算得出發點與目標點之間的中間節點，該節點滿足條 件從出發點到該節點方向dir2和dirl反向(相差超過90度)， 取得路段road_segment—sm(出發點start到中間點middle)和路段 roacLsegmenLme(中間點middle到目標點end),將路段信息轉為路 徑結果，轉4; 3.4根據GPS當前前進方向，調整出發點拓撲點對如果當前GPS方向O，表示不關注方向；不做調整，否則，根 據前進方向，選擇出發拓撲點對中的方向較接近GPS前進方向的 拓撲節點作為出發節點； 3.5搜索拓撲最短路徑拓撲邊以道路長度作為權重；最短路徑搜索算子的中間搜索對象為PathNode,PathNode含有 如下信息是否終點b—target,當前對應拓撲節點nw—node,路徑 對應上個PathNode: previousjathNode,累計出發點到當前節點距 離accu—weight—from， 當前節點至lj目標點啟發值accu—weight—to; 3.5.1準備出發拓撲點根據出發點拓撲點對，即當前綁定到的最近道路對應的拓撲 邊的兩個拓撲端點，生成出發PathNode,插入待擴展節點集合 extandable—nodes, extandable—nodes集合中對象的先後關係採用 accu—weight—from + accu一weight一to做比較； 3.5.2準備目標拓撲點根據目標點拓撲點對，生成兩個PathNode,插入目標 PathNode集合target—nodes;並記錄目標點位置target_pos，作 為啟發值搜索之用； 3.5.3路徑擴散搜索初始化-初始化當前搜索結果current—result為無效； 3.5.4從extandable—nodes 中取出第 一 個PathNode作為 currentjath一node，判斷current_path—node是否目標點，若是， 記錄當前搜索結果為有效current—result,轉3.5.8;否則，轉3.5.5擴散當前節點取出所有和current_path_node對應拓撲節點cur_nw—node鄰 接並且以cuiLnw—node為起始節點的拓撲邊集合adjacent—edges; 通過鄰接邊adjacent一edges取得當前nw一node的鄰居節點集合； 3.5.6判斷鄰接節點neighbour—nw_node是否待擴展節點對每個令卩居節點neighbour_nw_node，判斷neighbour—node 是否在待擴展節點集合expandable一nodes中；若不在，則新生成一個PathNode-other_path—node;否貝廿，從expandable—nodes中取出對應於neighbour_nw—node 的PathNode作為other_path—node;若neighbour_nw_node是已經擴展過的節點(visited—nodes)或 者otherjpath_node->accu—weight—from accu—weight—from + neighbour—nw—edge->length,也即當前累計長度比新的累計長度 來得更短，則不做更新，轉3.5.8;3.5.7 設置 other_path—node,更新待擴展節點集合 expandable—nodes:otherjpath_node->previous_path_node=current_path_node， other_path—node_>accu_weight—from = current_path—node->accu—weight—from + neighbour_nw_edge->length; other_path_node->accu_weight_to -— neighbour—nw—node->pos 至廿 target_pos 的直線距離；將 other_path—node插入或者更新expandable—nodes;3.5.8 將current_path—node插入已擴展節點集合visited—nodes,轉 3.5.4;3.5.9判斷當前搜索結果是否有效若current—result無效，轉4;否則，轉下步； 3.5.10路徑生成根據當前記錄節點 current_path—node ， 通過 cunrent_path—node->previous_path—node 逐個得至!]經過的 nw—edge,插入路徑隊列deque_topo_path的前端，生成路徑搜 索結果currrent_result; 4.路徑搜索完畢，返回搜索結果； 綁定道路，包含以下步驟1. 生成選擇矩形框 根據當前點的坐標位置curjos，生成選擇矩形框cur_rect;2. 搜索選擇矩形框內地理對象使用cur一rect在地圖數據中進行搜索，若cur—rect包含了當前地圖的 範圍矩形map一rect，則轉7;否則，根據地圖數據已建立的網格索引，得到cur一rect對應的網格 中的所有道路對象roads;若roads為空，將cur一rect按1.5的比例擴大，轉2;3. 初始化綁定結果根據cur_pos附近100米作為容忍距離計算得容忍框tol—rect;初始化cur_pos到綁定道路bind_road的最近距離min一dis =無窮大；bind—road 初始化為空對象；4. 判斷mads集合是否為空若為空，轉7，否則，轉5;5. 使用tol一rect過濾roads從roads中取出一條road,每條road記錄了本身控制點所在的範圍 road—bound;判斷road—bound是否和tol_rect相交，若相交，轉6;否貝廿， 轉4;6. 計算當前最短距離，更新綁定結果計算cur_pos到road的最短距離cur—dis，如果cur—dis length = 617.08米，判斷neighbour—node不在擴展節點集合expandable—nodes中，則新生成一 個PathNode-other_path_node;10. 設置otherj)ath一node，更新expandable—nodes: other_path—node->previous_path_node=current_path_node, otherjpath—node->accu—weight_from=urrent_path_node->accu_weight_from + neighbour_nw—edge->length;other_path—node->accu_weight_to = neighbour一nw一node->pos (3531328.2, 13350005.1)到targetjos (3533340.3,1335664.2)的直線距離(7442米)； 將other_path—node插入expandable—nodes;處理下個neighbour—nw—node直至U當前neighbour—nw—node集合處理完；11. 將currentjath—node插入已擴展節點集合visited—nodes，轉7，取下個擴 散節點；12. 判斷currentj"esult是否有效，若無效，轉14;否則，轉13;13. 路徑生成 根據當前記錄節點current_path_node(accu—weight—from= 8107,556， accu_weight—to = 0, 坐標位置 (3533118.1, 1336657.07);通過currrent_path—node->previous_path—node逐個得到經過的nw—edge,插入路徑隊列deque_topo_path的前端，生成路徑搜索結果currrent—result;14. 搜索完畢，返回搜索結果。 實施例2:以杭州城市為例，當前出發位置為(30,26331，120.12111)，方向為 (107.94度),選取目標點為(30.27751， 120.18615)。 轉化為投影坐標結果為出發點投影位置位置為(3531330.1， 13349507.2)，目標點投影位置為(3533340.3, 1335664.2);方向為1.88391弧度； 綁定到最近道路結果為出發點最近道路為浙大路，綁定距離為23米，目標點綁定最近道路為凱旋路，綁定距離為47米； 路徑搜索結果為擴散節點數為55，路徑總長為8107.556米，路徑經過道路為依次為 浙大路-》曙光路-》體育場路-》凱旋路； 上述實施例用來解釋說明本發明，而不是對本發明進行限制，在本發明的 精神和權利要求的保護範圍內，對本發明作出的任何修改和改變，都落入本發 明的保護範圍。
權利要求
1. 一種基於移動導航的路徑搜索方法，其特徵在於，包括以下步驟A.選取目標點，可通過觸摸筆在地圖上選取，也可通過選取興趣點，設為目標點；出發點是根據GPS模塊實時地位得到的當前位置。B.將目標點和出發點的坐標轉化為投影坐標，綁定到地圖上道路網絡中最近的路上；記錄當前目標點作為下次目標點綁定的啟發信息，初始設置上次目標點位置為(0，0)。a)先綁定目標點，判斷當前目標點是否在上次的目標點附近，所述目標點附近為在距離目標點50米的範圍內，若是，則直接使用上次綁定結果，不需要進行綁定，否則綁定。b)根據目標點的綁定結果判定目標點是否在搜索路網上，若不在，則轉D；否則更新上次目標點綁定結果，轉下步；所述綁定結果包含綁定到路的距離，綁定到的路的GRL信息，綁定到路上的位置。c)綁定出發點，出發點位置來自GPS模塊的當前位置，也即導航設備當前位置，和目標點不同，這裡直接進行綁定，若綁定結果判斷出發點不在路網上，則轉D；否則轉下步。C.根據綁定後的出發點和目標點以及當前的行駛方向，該方向以正北作為0度，來自GPS模塊，轉化為弧度單位，在路網上進行拓撲路徑搜索。a)將兩個綁定的點轉化為兩對拓撲節點對根據所在的道路GRL得到對應的網絡拓撲邊，分別記錄出發點和目標點對應的拓撲節點對，記錄綁定的點到該拓撲邊的兩個端節點的距離。b)判斷出發點和目標點是否在同一條網絡邊上，若是，則轉f)；否則轉g)。c)兩點同邊的特殊情況處理若當前方向cur_dir為負值，認為是不考慮方向信息，則直接取出出發點和目標點之間的路段信息，將該路段信息轉為路徑結果，轉D；否則，計算得出發點到目標點的直線方向dir1，比較cur_dir和dir1，如果兩個方向的角度偏差在-90～90°，取出出發點與目標點之間的路段信息，轉為路徑結果，轉步驟D；否則，計算得出發點與目標點之間的中間節點，該節點滿足條件從出發點到該節點方向dir2和dir1反向，取得出發點到中間點的路段road_segment_sm和中間點到目標點的路段road_segment_me，將路段信息轉為路徑結果，轉步驟D。d)根據GPS當前前進方向，調整出發點拓撲點對；如果當前GPS方向為負值，表示不關注方向；不做調整，否則，根據前進方向，選擇出發拓撲點對中的方向較接近GPS前進方向的拓撲節點作為出發節點。e)搜索拓撲最短路徑，拓撲邊以道路長度作為權重；最短路徑搜索算子的中間搜索對象為PathNode，PathNode含有如下信息是否終點b_target，當前對應拓撲節點nw_node，路徑對應上個PathNodeprevious_pathNode，累計出發點到當前節點距離accu_weight_from，當前節點到目標點啟發值accu_weight_toi.準備出發拓撲點prepareStartNodes根據出發點拓撲點對，即當前綁定到的最近道路對應的拓撲邊的兩個拓撲端點，生成出發PathNode，插入待擴展節點集合extandable_nodes，extandable_nodes集合中對象的先後關係採用accu_weight_from+accu_weight_to做比較。ii.準備目標拓撲點prepareTargetNodes根據目標點拓撲點對，生成兩個PathNode，插入目標PathNode集合target_nodes；並記錄目標點位置target_pos，作為啟發值搜索之用。iii.路徑擴散搜索searchPath初始化當前搜索結果current_result為無效。iv.從extandable_nodes中取出第一個PathNode作為current_path_node，判斷current_path_node是否目標點，若是，記錄當前搜索結果為有效current_result，轉viii；否則，轉v。v.擴散當前PathNode取出所有和current_path_node對應拓撲節點cur_nw_node鄰接並且以cur_nw_node為起始節點的拓撲邊集合adjacent_edges；通過鄰接邊adjacent_edges取得當前nw_node的鄰居節點集合。vi.對每個鄰居節點neighbour_nw_node，判斷neighbour_node是否在待擴展節點集合expandable_nodes中，若不在，則新生成一個PathNode——other_path_node；否則，從expandable_nodes中取出對應於neighbour_nw_node的PathNode作為other_path_node；若neighbour_nw_node是已經擴展過的節點或者other_path_node-＞accu_weight_from＜＝current_path_node-＞accu_weight_from+neighbour_nw_edge-＞length，也即當前累計長度比新的累計長度來得更短，則不做更新，轉viii。vii.設置other_path_node，更新expandable_nodesother_path_node-＞previous_path_node＝current_path_nodeother_path node-＞accu_weight_from＝current_path_node-＞accu_weight_from+neighbour_nw_edge-＞length；other_path_node-＞accu_weight_to＝neighbour_nw_node-＞pos到target_pos的直線距離；將other_path_node插入或者更新expandable_nodes。viii.將current_path_node插入已擴展節點集合visited_nodes，轉iv；ix.判斷current_result是否有效，若無效，轉D；否則，轉下步；x.路徑生成根據當前記錄節點current_path_node，通過currrent_path_node-＞previous_path_node逐個得到經過的nw_edge，插入路徑隊列deque_topo_path的前端，生成路徑搜索結果currrent_result。D.路徑搜索完畢，返回搜索結果。
2. 根據權利要求1所述的路徑搜索方法，其特徵在於，所述步驟C中的vii步，擴 散節點 current_path_node 的權重比較和更新是根據 current_path_node->accu—weight—from+current_path—node->nw__node至'J目禾示位置 target_pos的直線距離。
3. 根據權利要求2所述的路徑搜索方法，其特徵在於，所述目標點位置targetjos 是已知的明確信息，須由調用者傳入。
4. 根據權利要求1所述的路徑搜索方法，其特徵在於，所述步驟B的a)中，所 述綁定包括以下步驟(1) 根據當前點的坐標位置curj)os，生成選擇矩形框cur_reCt。(2) 使用cur一rect在地圖數據中進行搜索，若cur_reCt包含了當前地圖的範圍 矩形map—rect,則轉入步驟(7);否則，根據地圖數據已建立的網格索引，得到 cmirect對應的網格中的所有道路對象roads;若roads為空，將cur_rect按1.5的 比例擴大，轉入步驟(2);(3) 根據curjos附近100米作為容忍距離算出容忍框toLrect;初始化curjos到綁定道路bind_road的最近距離min_dis =無窮大；bind—road初始化為 空對象。(4) 判斷roads集合是否為空，若為空，轉入步驟(7)，否則，轉入步驟(5)。(5) 從roads中取出一條road,每條road記錄了本身控制點所在的範圍 road—bound;判斷road—bound是否和toLrect相交，若相交，轉入步驟(6);否貝'J， 轉入步驟(4)。(6) 求得cur_pos到road的最短距離cur—dis，如果cur—dis < min_dis;更新 min_dis = cur—dis;更新bind—road為road;轉入步驟(4);(7) 返回當前綁定的道路bind—road,以及當前綁定的距離min—dis。 5.根據權利要求4所述的道路綁定方法，其特徵在於，所述步驟(2)中，圖層 上的道路圖層採用網格索引方法，快速定位；綁定預先設置容忍距離為100米， 通過容忍矩形框過濾大部分不相關道路對象，加快綁定過程。
全文摘要
本發明公開了一種基於移動導航系統的路徑搜索方法，基於導航系統的特性——利用目標點位置已知的信息，作為搜索過程的啟發信息，利用該啟發信息重新設計路徑搜索方法，使得搜索過程中擴展的節點數大大減少，這樣便減少了內存的佔用，提高搜索效率。
文檔編號G01C21/34GK101261136SQ20081006070
公開日2008年9月10日 申請日期2008年4月25日 優先權日2008年4月25日
發明者徐亞娟, 李山亭, 範先迪, 蔣衛星, 趙國榮, 奇 陳, 黃群山 申請人:浙江大學