路徑規劃方法和設備的製作方法
2023-07-05 16:01:36 4
路徑規劃方法和設備的製作方法
【專利摘要】本發明提供一種路徑規劃方法和設備。所述方法包括：獲取起點位置和終點位置；基於起點位置和終點位置，根據歷史路徑數據獲得至少一條經驗路徑作為第一路徑；根據當前用戶的行駛習慣從第一路徑中選擇最接近當前用戶的行駛習慣的路徑。根據本發明的路徑規劃方法和設備，可以規劃出更高效率的路徑。
【專利說明】
路徑規劃方法和設備
【技術領域】
[0001]本發明涉及位置服務領域。更具體地講，涉及一種路徑規劃方法和設備。
【背景技術】
[0002]隨著技術的發展，具有導航功能的消費電子產品(例如，導航儀、智慧型手機、車載電子設備等)越來越多，導航功能已經越來越多的深入到人們的生活之中。當用戶希望從一個位置移動到另一個位置時，可將起點位置和終點位置輸入到導航設備中，導航設備可自己或者藉助於遠程伺服器來向用戶提供路徑規劃服務。
[0003]然而，現有的路徑規劃通常僅是利用預定路徑規划算法，來規劃出相應的路徑。由於路徑規划算法對於實際路況考慮很少，現有的路徑規劃方法可能無法規劃處較為經濟和有效率的路徑。此外，不同的用戶的行駛習慣也存在很大差別，現有的路徑規劃技術所規劃出的路徑可能無法滿足不同用戶的需要，這是因為用戶以自己熟悉的方式行駛會更加安全和聞效。
[0004]因此，需要一種能夠提供具有更高行駛效率的路徑的路徑規劃技術。
【發明內容】
[0005]本發明的目的在於提供一種路徑規劃方法和設備，其通過收集不同導航設備的歷史路徑數據以及當前用戶的歷史總路徑數據，能夠提供具有更高的行駛效率的路徑。
[0006]本發明的一方面提供一種路徑規劃方法，包括:獲取起點位置和終點位置；基於起點位置和終點位置，根據歷史路徑數據獲得至少一條經驗路徑作為第一路徑；根據當前用戶的行駛習慣從第一路徑中選擇最接近當前用戶的行駛習慣的路徑。
[0007]可選地，歷史路徑數據包括從至少一個導航終端收集的歷史路徑的數據。
[0008]可選地，選擇最接近當前用戶的行駛習慣的路徑的步驟包括:獲得當前用戶的歷史總路徑的特徵值；獲得每條第一路徑的特徵值；計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度；選擇具有與當前用戶的歷史總路徑的特徵值最接近的特徵值的第一路徑。
[0009]可選地，當前用戶的歷史總路徑的特徵值表示:當前用戶的歷史總路徑的特徵參數的加權和的距離歸一化值。
[0010]可選地，第一路徑的特徵值表示:第一路徑的特徵參數的加權和的距離歸一化值。
[0011]可選地，通過路徑的特徵參數加權後的距離歸一化值來表示路徑的特徵值。
[0012]可選地，特徵參數包括下述項中的至少一個:低等級道路在路徑中所佔的距離比重、路徑中的轉向次數、路徑中的紅綠燈數量、經過路徑所花費的時間。
[0013]可選地，計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度的步驟包括:計算當前用戶的歷史總路徑的特徵參數加權後的距離歸一化值之和作為第一求和值；計算第一路徑的特徵參數加權後的距離歸一化值之和作為第二求和值；計算第一求和值與第二求和值之差的絕對值。
[0014]可選地，所述絕對值越小，則第一路徑的特徵值與當前用戶的歷史總路徑的特徵值越接近。
[0015]可選地，路徑的特徵值為包括路徑的特徵參數加權後的距離歸一化值作為元素的向量，其中，計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度的步驟包括:計算作為第一路徑的特徵值的向量與作為當前用戶的歷史總路徑的特徵值的向量之差的模。
[0016]可選地，所述模越小，則第一路徑的特徵值與當前用戶的歷史總路徑的特徵值越接近。
[0017]可選地，第一路徑還包括基於起點位置和終點位置根據預定算法從地圖數據得到的路徑。
[0018]本發明的另一方面提供一種路徑規劃設備，包括:接收單元，獲取起點位置和終點位置；路徑獲取單元，基於起點位置和終點位置，根據歷史路徑數據獲得至少一條經驗路徑作為第一路徑；路徑選擇單元，根據當前用戶的行駛習慣從第一路徑中選擇最接近當前用戶的行駛習慣的路徑。
[0019]可選地，歷史路徑數據包括從至少一個導航終端收集的歷史路徑的數據。
[0020]可選地，路徑選擇單元包括:第一特徵值獲取單元，獲得當前用戶的歷史總路徑的特徵值；第二特徵值獲取單元，獲得每條第一路徑的特徵值；接近度確定單元，計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度；路徑確定單元，選擇具有與當前用戶的歷史總路徑的特徵值最接近的特徵值的第一路徑。
[0021]可選地，當前用戶的歷史總路徑的特徵值表示:當前用戶的歷史總路徑的特徵參數的加權和的距離歸一化值。
[0022]可選地，第一路徑的特徵值表示:第一路徑的特徵參數的加權和的距離歸一化值。
[0023]可選地，通過路徑的特徵參數加權後的距離歸一化值來表示路徑的特徵值。
[0024]可選地，特徵參數包括下述項中的至少一個:低等級道路在路徑中所佔的距離比重、路徑中的轉向次數、路徑中的紅綠燈數量、經過路徑所花費的時間。
[0025]可選地，接近度確定單元計算當前用戶的歷史總路徑的特徵參數加權後的距離歸一化值之和作為第一求和值，計算第一路徑的特徵參數加權後的距離歸一化值之和作為第二求和值。並計算第一求和值與第二求和值之差的絕對值。
[0026]可選地，所述絕對值越小，則第一路徑的特徵值與當前用戶的歷史總路徑的特徵值越接近。
[0027]可選地，路徑的特徵值為包括路徑的特徵參數加權後的距離歸一化值作為元素的向量，其中，接近度確定單元計算作為第一路徑的特徵值的向量與作為當前用戶的歷史總路徑的特徵值的向量之差的模。
[0028]可選地，所述模越小，則第一路徑的特徵值與當前用戶的歷史總路徑的特徵值越接近。
[0029]可選地，第一路徑還包括基於起點位置和終點位置根據預定算法從地圖數據得到的路徑。
[0030]根據本發明的路徑規劃方法和設備，通過收集不同導航設備的歷史路徑數據獲得經驗路徑，並進一步結合當前用戶的歷史總路徑數據來選擇符合當前用戶的行駛習慣的路徑，從而能夠提供具有更聞的行駛效率的路徑。
[0031]將在接下來的描述中部分闡述本發明另外的方面和/或優點，還有一部分通過描述將是清楚的，或者可以經過本發明的實施而得知。
【專利附圖】
【附圖說明】
[0032]通過下面結合附圖進行的詳細描述，本發明的上述和其它目的、特點和優點將會變得更加清楚，其中:
[0033]圖1示出根據本發明的實施例的路徑規劃方法的流程圖；
[0034]圖2示出根據本發明的實施例的選擇最接近當前用戶的行駛習慣的路徑的方法的流程圖；
[0035]圖3示出根據本發明的實施例的路徑規劃設備的框圖；
[0036]圖4示出根據本發明的實施例的路徑規劃設備中的路徑選擇單元的框圖。
【具體實施方式】
[0037]現在，將參照附圖更充分地描述不同的示例實施例。
[0038]圖1示出根據本發明的實施例的路徑規劃方法的流程圖。
[0039]在步驟101，獲取用於路徑規劃的起點位置和終點位置。例如，可從用戶接收輸入的起點位置和終點位置。
[0040]在步驟102，基於起點位置和終點位置，根據歷史路徑數據獲得至少一條經驗路徑作為第一路徑。
[0041]歷史路徑數據包括多個用戶的導航終端的歷史路徑的數據。可以預先從不同的導航終端收集歷史路徑數據。例如，可以周期性地從不同的導航終端接收導航數據(即，路徑數據)來形成歷史路徑數據。這裡，導航數據包括每次導航的路徑的起點信息、終點信息、軌跡點信息。起點信息包括起點的位置信息和時間戳，終點信息包括終點的位置信息和時間戳，軌跡點信息包括路徑上各個點的位置信息和處於各個點時的時間戳。
[0042]基於起點位置和終點位置，通過使用數據挖掘方法可根據歷史路徑數據得到起點位置和終點位置之間的經驗路徑。具體地說，可首先基於歷史路徑數據獲得經驗路徑拓撲網絡，然後在獲得的經驗路徑拓撲網絡的基礎上，基於起點位置和終點位置通過預定路徑規划算法來規劃路徑。
[0043]此外，也可在歷史路徑數據的基礎上利用其他的現有經驗路徑挖掘方法來獲得經驗路徑，不再贅述。
[0044]在步驟103，根據當前用戶的行駛習慣從第一路徑中選擇最接近當前用戶的行駛習慣的路徑。
[0045]在本發明中，可通過當前用戶的歷史總路徑的特徵值來表示當前用戶的行駛習慣。例如，可以預先從當前用戶的一個或多個導航終端收集歷史總路徑。應該理解，當前用戶的歷史總路徑表示能夠收集到的當前用戶之前的歷史路徑的集合。可通過利用當前用戶的歷史總路徑的特徵值與各個第一路徑的特徵值的接近程度來選擇最接近當前用戶的行駛習慣的第一路徑。
[0046]路徑的特徵值通過從路徑提取的至少一個特徵參數加權後的距離歸一化值被表徵。例如，從路徑提取的特徵參數可以是下列參數中的至少一種:低等級道路在路徑中所佔的距離比重、路徑中的轉向次數、路徑中的紅綠燈數量、經過路徑所花費的時間。
[0047]對於任意一條路徑，可以得到特徵參數加權後的距離歸一化值(以下稱為，子特徵值)。
[0048]例如，對於參數「低等級道路在路徑中所佔的距離比重」(以下，表示為xl)，可以得到子特徵值Fl=al X xl/L。
[0049]對於參數「路徑中的轉向次數」(以下，表示為x2)，可以得到子特徵值F2=a2Xx2/L0
[0050]對於參數「路徑中的紅綠燈數量」(以下，表示為x3)，可以得到子特徵值F3=a3Xx3/L。
[0051]對於參數「經過路徑所花費的時間」(以下，表示為x4)，可以得到子特徵值F4=a4Xx4/L。
[0052]這裡，al、a2、a3、a4為權重，L為路徑的長度。
[0053]可以利用子特徵值Fl、F2、F3、F4中的至少一個來表徵路徑的特徵值F，從而從第一路徑中選擇最接近當前用戶的行駛習慣的路徑。
[0054]在一個實施例中，可通過「當前用戶的歷史總路徑的至少一個子特徵值之和」與「第一路徑的至少一個子特徵值之和」的差的絕對值來確定當前用戶的歷史總路徑的特徵值與各個第一路徑的特徵值的接近程度，該絕對值越小則表示越接近。
[0055]對於任意路徑，該路徑的至少一個子特徵值之和可被表示為下面的等式(I):
[0056]F=bl X Fl+b2 X F2+b3 X F3+b4 X F4(I)
[0057]這裡，bl、b2、b3、b4中的至少一個不為零(即，F1、F2、F3、F4中的至少一個被選用)，並且不為零的項的符號相同。bl、b2、b3、b4中不為零的項可以相同或者不同。
[0058]此時，當前用戶的歷史總路徑的特徵值與各個第一路徑的特徵值的接近程度FF可被表示為下面等式(2):
[0059]FF=|F，_F」| (2)
[0060]其中，F』為當前用戶的歷史總路徑的至少一個子特徵值之和，F』』為第一路徑的至少一個子特徵值之和。
[0061]在另一實施例中，對於任意路徑，該路徑的特徵值F可被表示為包括至少一個特徵參數加權後的距離歸一化值(即，至少一個子特徵值)作為元素的向量。
[0062]此時，通過計算對應於第一路徑的特徵值的向量與對應於當前用戶的歷史總路徑的特徵值的向量之差的模來確定各個第一路徑與當前用戶的行駛習慣的接近程度。模越小則表示越接近。與基於等式(2)的計算接近程度的方式相比，當前實施例可以避免特徵值差異較大但計算結果卻比較接近的情況。
[0063]例如，當路徑的特徵值被表示為具有F1、F2、F3、F4的向量時，第一路徑的特徵值與當前用戶的歷史總路徑的特徵值F之差的模FF可被表示為下面的等式(3):
[0064]
FF = V(F3/ - Fl〃)2 + (F2f - F2")2 + (F3, - F3〃)2 + (F47 - F4")2 (3)
[0065]i^，Fl，、F2，、F3，、F4，分別為第一路徑的 F1、F2、F3、F4，FI』』、F2』』、F3』』、F4』』分別為當前用戶的歷史總路徑的F1、F2、F3、F4。等式(3)示出了作為路徑的特徵值的向量包括F1、F2、F3、F4的情況，然而，應該理解，等式(3)可根據作為路徑的特徵值的向量所包括的子特徵值而改變。
[0066]此外，本發明不限於等式(2)和(3)所描述的確定當前用戶的歷史總路徑的特徵值與各個第一路徑的特徵值的接近程度的方法，也可根據其他方式來計算該接近程度。
[0067]如上所述，可通過當前用戶的歷史總路徑的特徵值F來表徵用戶的習慣。應該理解，將當前用戶的歷史路徑的集合形成的一條總路徑來計算特徵值F。這樣，例如，如果存在η (η為大於O的自然數)條當前用戶的歷史路徑，則等式(I)中L為所述η條歷史路徑的長度之和，xl為所述η條歷史路徑中的低等級道路的長度之和在L中所佔的比重，χ2為在所述η條路徑中的轉向次數之和，χ3為在所述η條路徑中的紅綠燈數量之和，χ4為經過所述η條路徑所花費的時間之和。
[0068]下面參照圖2來更詳細地描述步驟103。
[0069]圖2示出根據本發明的實施例的選擇最接近當前用戶的行駛習慣的路徑的方法的流程圖。
[0070]在步驟201，獲得當前用戶的歷史總路徑的特徵值。可根據上面的等式(I)來獲得當前用戶的歷史總路徑的特徵值。
[0071]在步驟202，獲得每條第一路徑的特徵值。可根據上面的等式(I)來獲得每條第一路徑的特徵值。
[0072]在步驟203，計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度。可基於上面的等式(2 )或等式(3 )來確定該接近程度。
[0073]在步驟204，根據第一路徑的特徵值與當前用戶的歷史總路徑的特徵值的接近程度，對所有的第一路徑進行排序，按照降序選擇預定數量的第一路徑；或者直接選擇具有與當前用戶的歷史總路徑的特徵值最接近的特徵值的第一路徑。
[0074]在本發明的另一實施例中，第一路徑還可進一步包括基於起點位置和終點位置根據預定算法從地圖數據的路徑拓撲網絡得到的路徑。即，第一路徑還可包括在不考慮歷史路徑數據的情況下利用路徑規划算法得到的路徑。
[0075]應該理解，根據本發明的上述方法可以被實現為電腦程式，當在計算機(例如，導航儀、智慧型手機、網絡伺服器、筆記本電腦、桌面電腦等)上執行所述電腦程式時執行所述方法。
[0076]圖3示出根據本發明的實施例的路徑規劃設備的框圖。
[0077]如圖3所示，根據本發明的實施例的路徑規劃設備300包括:接收單元310、路徑獲取單元320、路徑選擇單元330。
[0078]接收單元310獲取起點位置和終點位置。例如，接收單元310可經由輸入接口(例如，鍵盤、滑鼠、觸控螢幕等)接收用戶輸入的起點位置和終點位置。
[0079]路徑獲取單元320基於起點位置和終點位置，根據歷史路徑數據獲得至少一條經驗路徑作為第一路徑。
[0080]可選地，第一路徑還可包括基於起點位置和終點位置根據預定算法從地圖數據的路徑拓撲網絡得到的路徑。
[0081 ] 已經在前面定義了歷史路徑數據，將不再贅述。此外，可利用上述或現有的經驗路徑挖掘方法來獲得經驗路徑。
[0082]路徑選擇單元330根據當前用戶的行駛習慣從第一路徑中選擇最接近當前用戶的行駛習慣的路徑。路徑選擇單元330所選擇的路徑作為路徑規劃設備300所規劃出的路徑。
[0083]圖4示出根據本發明的實施例的路徑選擇單元330的框圖。
[0084]如圖4所示，路徑選擇單元330包括第一特徵值獲取單元331、第二特徵值獲取單元332、接近度確定單元333、路徑確定單元334。
[0085]第一特徵值獲取單元331獲得當前用戶的歷史總路徑的特徵值。當前用戶的歷史總路徑的特徵值可與前面定義的當前用戶的歷史總路徑的特徵值相同，不再贅述。
[0086]第二特徵值獲取單元332獲得每條第一路徑的特徵值。每條第一路徑的特徵值可與前面定義的第一路徑的特徵值相同，不再贅述。
[0087]接近度確定單元333，計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度。接近度確定單元333可基於上面的等式(2)或等式(3)來確定該接近程度。
[0088]路徑確定單元334根據第一路徑的特徵值與當前用戶的歷史總路徑的特徵值的接近程度，對所有的第一路徑進行排序，按照降序選擇預定數量的第一路徑。或者，路徑確定單元333直接選擇具有與當前用戶的歷史總路徑的特徵值最接近的特徵值的第一路徑。
[0089]根據本發明的示例性實施例的路徑規劃設備中的各個單元可被實現硬體組件。本領域技術人員根據限定的各個單元所執行的處理，可以例如使用現場可編程門陣列(FPGA)或專用集成電路(ASIC)來實現各個單元。
[0090]根據本發明的路徑規劃方法和設備，通過收集不同導航設備的歷史路徑數據獲得經驗路徑，並進一步結合當前用戶的歷史總路徑數據來選擇符合當前用戶的行駛習慣的路徑，從而能夠提供具有更聞的行駛效率的路徑。
[0091]儘管已經參照其示例性實施例具體顯示和描述了本發明，但是本領域的技術人員應該理解，在不脫離權利要求所限定的本發明的精神和範圍的情況下，可以對其進行形式和細節上的各種改變。
【權利要求】
1.一種路徑規劃方法，包括: 獲取起點位置和終點位置； 基於起點位置和終點位置，根據歷史路徑數據獲得至少一條經驗路徑作為第一路徑； 根據當前用戶的行駛習慣從第一路徑中選擇最接近當前用戶的行駛習慣的路徑。
2.根據權利要求1所述的路徑規劃方法，其中，歷史路徑數據包括從至少一個導航終端收集的歷史路徑的數據。
3.根據權利要求1所述的路徑規劃方法，其中，選擇最接近當前用戶的行駛習慣的路徑的步驟包括: 獲得當前用戶的歷史總路徑的特徵值； 獲得每條第一路徑的特徵值； 計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度； 選擇具有與當前用戶的歷史總路徑的特徵值最接近的特徵值的第一路徑。
4.根據權利要求3所述的路徑規劃方法，其中，通過路徑的特徵參數加權後的距離歸一化值來表示路徑的特徵值。
5.根據權利要求4所述的路徑規劃方法，其中，路徑的特徵參數包括下述項中的至少一個:低等級道路在路徑中所佔的距離比重、路徑中的轉向次數、路徑中的紅綠燈數量、經過路徑所花費的時間。
6.根據權利要求4所述的路徑規劃方法，其中，計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度的步驟包括: 計算當前用戶的歷史總路徑的特徵參數加權後的距離歸一化值之和作為第一求和值； 計算第一路徑的特徵參數加權後的距離歸一化值之和作為第二求和值； 計算第一求和值與第二求和值之差的絕對值。
7.根據權利要求6所述的路徑規劃方法，其中，所述絕對值越小，則第一路徑的特徵值與當前用戶的歷史總路徑的特徵值越接近。
8.根據權利要求4所述的路徑規劃方法，其中，路徑的特徵值為包括路徑的特徵參數加權後的距離歸一化值作為元素的向量， 其中，計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度的步驟包括:計算作為第一路徑的特徵值的向量與作為當前用戶的歷史總路徑的特徵值的向量之差的模。
9.根據權利要求8所述的路徑規劃方法，其中，所述模越小，則第一路徑的特徵值與當前用戶的歷史總路徑的特徵值越接近。
10.根據權利要求1所述的路徑規劃方法，其中，第一路徑還包括基於起點位置和終點位置根據預定算法從地圖數據得到的路徑。
11.一種路徑規劃設備，包括: 接收單元，獲取起點位置和終點位置； 路徑獲取單元，基於起點位置和終點位置，根據歷史路徑數據獲得至少一條經驗路徑作為第一路徑； 路徑選擇單元，根據當前用戶的行駛習慣從第一路徑中選擇最接近當前用戶的行駛習慣的路徑。
12.根據權利要求10所述的路徑規劃設備，其中，歷史路徑數據包括從至少一個導航終端收集的歷史路徑的數據。
13.根據權利要求10所述的路徑規劃設備，其中，路徑選擇單元包括: 第一特徵值獲取單元，獲得當前用戶的歷史總路徑的特徵值； 第二特徵值獲取單元，獲得每條第一路徑的特徵值； 接近度確定單元，計算當前用戶的歷史總路徑的特徵值與每條第一路徑的特徵值的接近程度； 路徑確定單元，選擇具有與當前用戶的歷史總路徑的特徵值最接近的特徵值的第一路徑。
14.根據權利要求13所述的路徑規劃設備，其中，通過路徑的特徵參數加權後的距離歸一化值來表示路徑的特徵值。
15.根據權利要求14所述的路徑規劃設備，其中，路徑的特徵參數包括下述項中的至少一個:低等級道路在路徑中所佔的距離比重、路徑中的轉向次數、路徑中的紅綠燈數量、經過路徑所花費的時間。
16.根據權利要求14所述的路徑規劃設備，其中，接近度確定單元計算當前用戶的歷史總路徑的特徵參數加權後的距離歸一化值之和作為第一求和值，計算第一路徑的特徵參數加權後的距離歸一化值之和作為第二求和值。並計算第一求和值與第二求和值之差的絕對值。
17.根據權利要求16所述的路徑規劃設備，其中，所述絕對值越小，則第一路徑的特徵值與當前用戶的歷史總路徑的特徵值越接近。
18.根據權利要求14所述的路徑規劃設備，其中，路徑的特徵值為包括路徑的特徵參數加權後的距離歸一化值作為元素的向量，其中，接近度確定單元計算作為第一路徑的特徵值的向量與作為當前用戶的歷史總路徑的特徵值的向量之差的模。
19.根據權利要求18所述的路徑規劃設備，其中，所述模越小，則第一路徑的特徵值與當前用戶的歷史總路徑的特徵值越接近。
20.根據權利要求11所述的路徑規劃設備，其中，第一路徑還包括基於起點位置和終點位置根據預定算法從地圖數據得到的路徑。
【文檔編號】G01C21/00GK104165625SQ201310183463
【公開日】2014年11月26日 申請日期:2013年5月17日 優先權日:2013年5月17日
【發明者】朱智青 申請人:北京百度網訊科技有限公司