TWI583925B

TWI583925B - 路徑規劃方法及裝置

Info

Publication number: TWI583925B
Application number: TW104134306A
Authority: TW
Inventors: 汪洋
Original assignee: 百度在線網絡技術（北京）有限公司
Priority date: 2015-06-30
Filing date: 2015-10-20
Publication date: 2017-05-21
Also published as: HK1210828A1; TW201700955A; CN105043400B; CN105043400A

Description

路徑規劃方法及裝置

本發明實施例涉及地圖技術領域，尤其涉及路徑規劃方法及裝置。

目前，集定位、導航、娛樂等功能於一身的導航產品，逐漸成為車上的基本裝備。電子地圖路徑規劃作為導航中一項十分重要的功能，能夠從眾多到達目的地的各條路徑中，選擇較佳的行走路徑提供給車主，以使車主能夠快速方便的到達目的地。

路徑規劃的路線是由各個Link(路段)組織而成，一條路徑可包含多個Link資料。Link是圖商數據中最小的單位，用於表徵實際路網中的一條路段。LinkID欄位是Link資料在路網中的唯一標誌。目前路徑規劃的演算法主要過程是從起點的Link進行深度或廣度擴展，最終遍歷到終點的Link，以找到一條或多條較優的行走路徑。

現有技術在進行電子地圖路徑規劃時，通常是通過啟發函數減枝技術，來縮小遍歷的搜索空間。但是，一方面，目前的減枝策略都是基於圖商數據，搜索空間仍然很大；另一個方面，圖商數據的更新週期太長，而且圖商數據本身的準確性也很難保證，當某條路段正在維修或者已經廢棄時，圖商數據沒有更新，從而可能導致路徑規劃結果會將使用者引導到不通暢的路徑中，導致較差的用戶體驗。

本發明實施例提供一種路徑規劃方法及裝置，以對已有的路徑規劃技術進行優化，提高規劃速度以及規劃結果的準確度。

一方面，本發明實施例提供了一種路徑規劃方法，該方法包括：獲取包含有起點和終點的路徑規劃請求；根據該路徑規劃請求獲取該起點和終點之間路段的經驗權重集，其中該經驗權重集根據使用者的歷史路徑確定；根據該路段的經驗權重集，採用啟發式搜索演算法對該路徑規劃請求進行路徑規劃。

另一方面，本發明實施例還提供了一種路徑規劃裝置，該裝置包括：規劃請求獲取單元，用於獲取包含有起點和終點的路徑規劃請求；經驗權重獲取單元，用於根據該路徑規劃請求獲取該起點和終點之間路段的經驗權重集，其中該經驗權重集根據使用者的歷史路徑確定；路徑規劃單元，用於根據該路段的經驗權重集，採用啟發式搜索演算法對該路徑規劃請求進行路徑規劃。

本發明實施例提供的技術方案，能夠結合大量可靠的用戶歷史行走行為，採用啟發式搜索演算法進行路徑規劃，這樣不僅可以有效減小路徑規劃遍歷演算法的搜索空間，提高路徑規劃效率，而且在一定程度上也可克服因圖商數據更新慢或者部分資料錯誤所帶來的規劃準確度低的問題。

400‧‧‧歷史路徑類別劃分單元

405‧‧‧統計學習單元

410‧‧‧規劃請求獲取單元

420‧‧‧經驗權重獲取單元

430‧‧‧路徑規劃單元

第1圖是本發明實施例一提供的一種路徑規劃方法的流程示意圖；第2圖是本發明實施例二提供的一種對起點和終點之間各個路段的經驗權重集的線下確定方法的流程示意圖；第3圖是本發明實施例三提供的一種路徑規劃方法的流程示意圖；第4圖是本發明實施例四提供的一種路徑規劃裝置的結構示意圖。

下面結合附圖和實施例對本發明作進一步的詳細說明。可以理解的是，此處所描述的具體實施例僅僅用於解釋本發明，而非對本發明的限定。另外還需要說明的是，為了便於描述，附圖中僅示出了與本發明相關的部分而非全部結構。

在更加詳細地討論示例性實施例之前應當提到的是，一些示例性實施例被描述成作為流程圖描繪的處理或方法。雖然流程圖將各項操作(或步驟)描述成順序的處理，但是其中的許多操作可以被並行地、併發地或者同時實施。此外，各項操作的順序可以被重新安排。當其操作完成時該處理可以被終止，但是還可以具有未包括在附圖中的附加步驟。該處理可以對應於方法、函數、規程、子常式、副程式等等。

實施例一

第1圖是本發明實施例一提供的一種路徑規劃方法的流程示意圖。本實施例可適用於導航終端中電子地圖路徑規劃的情況。該方法可以由路徑規劃裝置來執行，該裝置可由軟體實現，集成於為導航產品提供導航服務的伺服器中。參見第1圖，本實施例提供的路徑規劃方法具體包括如下操作：操作110、獲取包含有起點和終點的路徑規劃請求。

具體的，導航終端可通過人機交互的方式，接收使用者觸發的路徑規劃請求，該請求包含使用者想要行走的路徑的起點和終點。例如，可提供對應於路徑規劃的人機交互介面，該介面中包括第一輸入框、第二輸入框和確認按鈕；如果接收到使用者對確認按鈕的觸發操作，則生成路徑規劃請求，發送至伺服器。該請求包含的起點為用戶在第一輸入框中的輸入資訊，終點為使用者在第二輸入框中的輸入資訊。

操作120、根據路徑規劃請求獲取該起點和終點之間路段的經驗權重集，其中經驗權重集根據使用者的歷史路徑確定。

所謂歷史路徑指的是使用者走過的路徑。在本實施例中，在執行操作120之前，需線下預先執行如下操作：基於設定的資料採擷演算法：對具有相同該起點和終點的多條歷史路徑進行統計學習，以得到該多條歷史路徑中該路段的出現頻次，和/或，包含有該路段的關聯路段組的出現頻次；根據該出現頻次確定該路段的經驗權重集。

作為一種具體實施方式，經驗權重集可僅為一個經驗權重。例如，該經驗權重可以是該多條歷史路徑中該路段的出現頻次。當然，該經驗權重也可以是根據該多條歷史路徑中路段的出現頻次和包含有該路段的關聯路段組的出現頻次，得到的一個值。該值用於表徵該起點和終點的最優路徑要經過該路段的概率大小。出現頻次越高，該值也就越大。

作為另一種具體實施方式，經驗權重集可為多個經驗權重組合的集合。該集合可包括：包含有該路段的關聯路段組的出現頻次(視為第一經驗權重)；和/或，該路段在關聯路段組中其他路段出現下的條件出現頻次(視為第二經驗權重)。例如，關聯路段組AB的出現頻次2/5，路段B的出現頻次為3/4，則路段A在關聯路段組AB中其他路段B出現下的條件出現頻次為：2/5÷3/4=8/15。

操作130、根據該路段的經驗權重集，採用啟發式搜索演算法對路徑規劃請求進行路徑規劃。

目前，採用啟發式搜索演算法，對路徑規劃請求進行路徑規劃的過程包括：在電子地圖所能提供的該起點和終點之間的所有路段中，先從與起點連接的各個路段處開始搜索，對這些路段進行重要度評估，並從中挑選出評估結果較優的第一組規劃路段；然後，繼續搜索與第一組規劃路段連接的各個擴展路段，對這些擴展路段進行重要度評估，並從中挑選出評估結果較優的第二組規劃路段；進而按照該策略繼續搜索下去，直到終點。最後，可根據得到的各組規劃路段，確定出該起點到終點的最優路徑。啟發式搜索技術可以省略大量無謂的搜索路徑，提高了搜索效率。在啟發式搜索中，對各個路段的重要度評估是十分重要的。採用了不同的評估策略可以達到不同的效果。

在現有技術中，通常是基於啟發函數對各個路段進行重要度評估的，每個路段都有一個啟發函數值。對於第n個路段而言，其啟發函數值可以是從第n個路段到終點的最低耗散路徑(也即最優路徑)的估計耗散值；或者是與估計耗散值成反比的其他值。對於前者而言，啟發函數值越小，最優路徑越有可能經過第n個路段，該路段的重要度越高；對於後者而言，則是啟發函數值越大，最優路徑越有可能經過第n個路段，該路段的重要度越高。

目前，啟發函數值往往僅根據電子地圖提供的圖商數據計算得到的，例如基於圖商數據中對搜索路段的長度、路段(例如是高速道路，還是普通道路)等描述資訊，得到該搜索路段的啟發函數值。所以，採用已有路徑規劃技術，雖然會根據評估結果減掉對部分無效路徑的搜索，但是由於評估演算法的局限性，使得評估結果並不十分可靠，使得搜索空間仍然可能很大，搜索結果也不是很準確。

作為一種具體實現方式，可將已有的啟發函數評估法，結合使用者的用路經驗，進行路徑規劃。示例性的，利用路段的經驗權重集，來修正現有技術所設計的啟發函數。具體的，操作130包括：根據如下公式，修正路段的啟發函數值F _new：F _new=F+△

其中，F為路段的原始啟發函數值；△為基於路段的經驗權重集確定的修正值。如果F是估計耗散值，則修正值應與經驗權重集中的經驗權重成負相關關係；反之，如果F是直接用於描述路段重要度大小的數值，則修正值應與經驗權重集中的經驗權重成正相關關係。

較佳的，如果獲取到的經驗權重集為多個權重，則還可利用本次路徑規劃中已確定的規劃路段，對獲取到的經驗權重集進行篩選，提取出其中特定關聯路段組的出現頻次，和/或，該路段在特定關聯路段組中其他路段出現下的條件出現頻次；然後，僅根據提取結果確定修正值。其中，特定關聯路段組為：當前正在被搜索的路段與已確定的規劃路段所組成的路段組。例如，已確定的規劃路段為A和F，路段K作為路段F的擴展路段正在被搜索，則在修正路段K的啟發函數值時，對應的特定關聯路段組為FK、AK、AFK。

由於路段的經驗權重是基於大量用戶的用路經驗得到的，可靠性較強，因此作為本實施例的另一種實現方式，還可僅根據路段的經驗權重集，生成對路段的重要度評估結果，例如該結果為上述修正值△。

本實施例提供的技術方案，能夠結合大量可靠的用戶歷史行走行為，採用啟發式搜索演算法進行路徑規劃，這樣不僅可以有效減小路徑規劃遍歷演算法的搜索空間，提高路徑規劃效率，而且在一定程度上也可克服因圖商數據更新慢或者部分資料錯誤所帶來的規劃準確度低的問題。

實施例二

本實施例在上述實施例一的基礎上，對起點和終點之間各個路段的經驗權重集的線下確定方法作詳細介紹。參見第2圖，該確定方法具體包括如下操作：操作210、獲取最近預設時間段內多個用戶走過的多條歷史路徑，構成路徑集。

由於本發明實施例是根據使用者的用路經驗，來進行路徑規劃，所以使用者的歷史路徑也應是最近一段時間內使用者走過的路徑。如果歷史路徑距離當前時間太過久遠，會降低學習的準確度。該預設時間段可以是最近一個月或者半年，可由開發人員自行設定。

該歷史路徑可以是導航使用者在完成一次行程後，觸發導航終端主動上報的，也可是伺服器通過設置在導航終端的路徑監控元件，即時監控得到的。

操作220、按照相同起點和終點，對路徑集中的歷史路徑進行類別劃分。

每條歷史路徑可以使用Link集合L={L1,L2,L3...Ln}表示，其中L1,L2,L3...Ln分別表示線路中的不同Link。將獲取到的近一周(時間可以控制)的全部歷史路徑作為路徑集Tw，以起終點的標準對Tw進行分類，則Tw可分為由不同起終點組成的路徑子集{Ts1e1,Ts2e2,Ts3e3...Tsnen}，其中路徑子集Tsnen代表路徑集Tw中起點為sn且終點為en的多條歷史路徑組成的集合。

操作230、基於設定的資料採擷演算法，對具有相同起點和終點的多條歷史路徑進行統計學習，得到所學習的多條歷史路徑中路段的經驗權重集。

具體的學習過程，可以是：基於設定的資料採擷演算法：對具有相同起點和終點的多條歷史路徑進行統計學習，以得到該多條歷史路徑中路段的出現頻次，和/或，包含有該路段的關聯路段組的出現頻次；根據該出現頻次確定該路段的經驗權重集。

所謂路段的出現頻次指的是：路段在該多條歷史路徑中出現的概率；所謂關聯路段組的出現頻次指的是：關聯路段組中的所有路段同時出現在同一條歷史路徑的概率。

例如：某起點和終點之間共有5條歷史路徑：A-B-C-D、A-B-C-G、B-C-E-G、C-E-F-G、D-E-F-G。這5條歷史路徑共有路段A、B、C、D、E、F和G這7個路段。對於路段B而言，出現在了3條歷史路徑中，所以出現頻次為3/7；包含有路段B的關聯路段組AB，出現在了2條歷史路徑中，所以出現頻次為2/7：包含有路段B的關聯路段組BC，出現在了3條歷史路徑中，所以出現頻次為3/7。

作為本實施例的一種較佳實施方式，設定的資料採擷演算法為頻繁項集演算法(也即apriori演算法)。具體的，基於該演算法，對具有相同起點和終點的多條歷史路徑進行統計學習，得到所學習的多條歷史路徑中各個路段的經驗權重集，包括：1、將具有相同起點和終點的多條歷史路徑組成一個集合，集合中的每個元素是一條歷史路徑。

2、基於預設的最小支持度臨界值，挖掘該集合中的頻繁K項集。

具體的，頻繁1項集包括：集合中出現頻次大於最小支持度臨界值的各個路段；例如，頻繁1項集包括：A、C、D、E；頻繁2項集包括：集合中出現頻次大於最小支持度臨界值的由兩個路段組成的關聯路段組；例如，頻繁2項集包括：AC、CD、AE；頻繁3項集包括：集合中出現頻次大於最小支持度臨界值的由三個路段組成的關聯路段組；例如，頻繁3項集包括：ACE。

其中，K的大小能夠由該最小支持度臨界值和該集合確定。頻繁K項集中的各個元素均被視為一個頻繁項，例如A、C、D、E、AC、CD、AE、ACE均是頻繁項。出現頻次也即支持度。

3、基於預設的最小置信度臨界值，挖掘頻繁K項集中的強關聯規則。

得到的每個強關聯規則包括：左側路段和右側路段。這兩側路段組成的頻繁項為強關聯路段組。左側路段可以是一個路段或多個路段，而右側路段僅為一個路段。每一個強關聯規則的右側路段與左側路段之間具有強關聯性，其含義是如果用戶走了左側路段，則很大程度上要走右側路段。

強關聯規則的支援度大於最小支援度臨界值，置信度大於最小置信度臨界值，其中，強關聯規則的支援度為：規則中兩側路段組成的強關聯路段組在該多條歷史路徑組成的集合中的出現頻次；強關聯規則的置信度為：右側路段在左側路段在該多條歷史路徑組成的集合中出現下的條件出現頻次。

例如，某個頻繁項為關聯路段組AE，關聯路段組AE的出現頻次大於最小支持度臨界值，路段E在路段A出現下的條件出現頻次大於最小置信度臨界值，則A->E為一個強關聯規則。其中，路段A為左側路段，路段E為右側路段。

再例如，某個頻繁項為關聯路段組DJK，關聯路段組DJK的出現頻次大於最小支持度臨界值，路段K在路段DJ出現下的條件出現頻次大於最小置信度臨界值，則DJ->K為一個強關聯規則。其中，路段DJ為左側路段，路段K為右側路段。

4、根據強關聯規則的支援度和置信度，確定所學習的多條歷史路徑中對應路段的經驗權重集。

具體的，如果路段為強關聯規則中的右側路段，則該路段的經驗權重集包括：該強關聯規則的支援度和置信度。

本實施例通過對使用者歷史路徑進行分析，挖掘出同一個起終點的頻繁Link項集合，用來進一步降低圖遍歷的搜索空間。同時，因為基於了用戶近期真實的使用者經驗，資料的正確性是可以保障的，可以彌補圖商數據更新時間長且資料不準確的問題。

實施例三

第3圖是本發明實施例三提供的一種路徑規劃方法的流程示意圖。本實施例以上述所有實施例為基礎，提供一較佳實施例。參見第3圖，該方法具體包括如下操作：操作310、獲取最近預設時間段內多個用戶走過的多條歷史路徑，構成路徑集。

操作320、按照相同起點和終點，對路徑集中的歷史路徑進行類別劃分。

操作330、基於頻繁項集演算法，對具有相同起點和終點的多條歷史路徑構成的集合進行強關聯規則挖掘學習。

在本實施例中，在挖掘學習過程中，可僅先挖掘出頻繁2項集；然後從頻繁2項集中挖掘強關聯規則。這樣，規則中的左側路段和右側路段均為一個路段。

操作340、根據強關聯規則的支援度和置信度，確定所學習的多條歷史路徑中對應路段的經驗權重集，並進行儲存。

例如，挖掘出頻繁2項集有：AB、BE、BD、CE、DK這四個關聯路段組，且從中挖掘出如下三條強關聯規則：A->B，B->E，C->E。則可確定所學習的多條歷史路徑中：路段B的經驗權重集包括如下兩個經驗權重：關聯路段組AB在該多條歷史路徑中的出現頻次；路段B在路段A出現下的條件出現頻次；路段E的經驗權重集包括如下四個經驗權重：關聯路段組BE在該多條歷史路徑中的出現頻次；路段E在路段B出現下的條件出現頻次；關聯路段組CE在該多條歷史路徑中的出現頻次；路段E在路段C出現下的條件出現頻次。

對於路段如A、C、D或者K而言，由於上述挖掘到的任何一個強關聯規則的右側路段均不包含該路段，則所學習的多條歷史路徑中該路段的經驗權重集為空。

上述操作310-操作340可預先線下執行完畢。

操作350、獲取包含有目標起點和目標終點的路徑規劃請求。

操作360、根據路徑規劃請求獲取所儲存的與該目標起點和目標終點對應的多條目標歷史路徑中路段的經驗權重；操作370、根據獲取到的路段的經驗權重集，採用啟發式搜索演算法對該路徑規劃請求進行路徑規劃。

具體的，如果當前被搜索的路段為本次路徑規劃中已被確定的規劃路段的擴展路段，且該路段屬於該多條目標歷史路徑中的一個路段，則根據如下公式，修正該路段的啟發函數值F _new：F _new=F+α×(β×S+γ×C)

其中，F為該路段的原始啟發函數值；α為第一調節因數，β為第二調節因數，γ為第三調節因數；S為該多條目標歷史路徑中該路段和該規劃路段組成的目標關聯路段組的出現頻次，C為該多條目標歷史路徑中該路段在該規劃路段出現下的條件出現頻次。

在本實施例中，通過經驗權重可以拉開路段之間啟發函數值的差距，對於一些重要度評估較差的擴展路徑可以直接去掉，減小搜索範圍；同時通過引入了經驗權重，規劃路段的正確性得到了保障，能有效緩解圖商數據不一致的問題。

實施例四

第4圖是本發明實施例四提供的一種路徑規劃裝置的結構示意圖。參見第4圖，該裝置的具體結構如下：規劃請求獲取單元410，用於獲取包含有起點和終點的路徑規劃請求；經驗權重獲取單元420，用於根據該路徑規劃請求獲取該起點和終點之間路段的經驗權重集，其中該經驗權重集根據使用者的歷史路徑確定；路徑規劃單元430，用於根據該路段的經驗權重集，採用啟發式搜索演算法對該路徑規劃請求進行路徑規劃。

示例性的，本實施例提供的裝置還包括統計學習單元405，用於：基於設定的資料採擷演算法：對具有相同該起點和終點的多條歷史路徑進行統計學習，以得到該多條歷史路徑中該路段的出現頻次，和/或，包含有該路段的關聯路段組的出現頻次；根據該出現頻次確定該路段的經驗權重集。

示例性的，該資料採擷演算法為頻繁項集演算法；如果該路段為基於該頻繁項集演算法得到的強關聯規則中的右側路段，則該路段的經驗權重集包括：該強關聯規則的支援度和置信度。

示例性的，本實施例提供的裝置還包括歷史路徑類別劃分單元400，用於：獲取最近預設時間段內多個用戶走過的多條歷史路徑，構成路徑集；按照相同起點和終點，對該路徑集中的歷史路徑進行類別劃分。

示例性的，該路徑規劃單元430，具體用於：根據如下公式，修正該路段的啟發函數值F _new：F _new=F+△

其中，該F為該路段的原始啟發函數值；該△為基於該路段的經驗權重集確定的修正值。

示例性的，該路段為本次路徑規劃中已被確定的規劃路段的擴展路段；按照如下公式計算該△：△=α×(β×S+γ×C)

其中，該α為第一調節因數，該β為第二調節因數，該γ為第三調節因數；該S為該多條歷史路徑中該路段和該規劃路段組成的目標關聯路段組的出現頻次，該C為該多條歷史路徑中該路段在該規劃路段出現下的條件出現頻次。

上述產品可執行本發明任意實施例所提供的方法，具備執行方法相應的功能模組和有益效果。

注意，上述僅為本發明的較佳實施例及所運用技術原理。本領域技術人員會理解，本發明不限於這裡所述的特定實施例，對本領域技術人員來說能夠進行各種明顯的變化、重新調整和替代而不會脫離本發明的保護範圍。因此，雖然通過以上實施例對本發明進行了較為詳細的說明，但是本發明不僅僅限於以上實施例，在不脫離本發明構思的情況下，還可以包括更多其他等效實施例，而本發明的範圍由所附的申請專利範圍決定。

Claims

一種路徑規劃方法，其特徵在於，包括：獲取包含有起點和終點的路徑規劃請求；設定資料採擷演算法，該資料採擷演算法為頻繁項集演算法，如果該路段為基於該頻繁項集演算法得到的強關聯規則中的右側路段，則該路段的經驗權重集包括：該強關聯規則的支援度和置信度；根據該路徑規劃請求獲取該起點和終點之間路段的經驗權重集，其中該經驗權重集根據使用者的歷史路徑確定；根據該路段的經驗權重集，採用啟發式搜索演算法對該路徑規劃請求進行路徑規劃。
如申請專利範圍第1項所述的方法，其特徵在於，在根據該路徑規劃請求獲取該起點和終點之間路段的經驗權重集之前，還包括：基於設定的該資料採擷演算法，對具有相同該起點和終點的多條歷史路徑進行統計學習，以得到該多條歷史路徑中該路段的出現頻次，和/或，包含有該路段的關聯路段組的出現頻次；根據該出現頻次確定該路段的經驗權重集。
如申請專利範圍第2項所述的方法，其特徵在於，在對具有相同該起點和終點的多條歷史路徑進行統計學習之前，還包括：獲取最近預設時間段內多個用戶走過的多條歷史路徑，構成路徑集；按照相同起點和終點，對該路徑集中的歷史路徑進行類別劃分。
如申請專利範圍第2項至第3項中任一項所述的方法，其特徵在於，根據該路段的經驗權重集，採用啟發式搜索演算法對該路徑規劃請求進行路徑規劃，包括：根據如下公式，修正該路段的啟發函數值F _new：F _new=F+△其中，該F為該路段的原始啟發函數值；該△為基於該路段的經驗權重集確定的修正值。
如申請專利範圍第4項所述的方法，其特徵在於，該路段為本次路徑規劃中已被確定的規劃路段的擴展路段；按照如下公式計算該△：△=α×(β×S+γ×C)其中，該α為第一調節因數，該β為第二調節因數，該γ為第三調節因數；該S為該多條歷史路徑中該路段和該規劃路段組成的目標關聯路段組的出現頻次，該C為該多條歷史路徑中該路段在該規劃路段出現下的條件出現頻次。
一種路徑規劃裝置，其特徵在於，包括：規劃請求獲取單元，用於獲取包含有起點和終點的路徑規劃請求；經驗權重獲取單元，用於根據該路徑規劃請求獲取該起點和終點之間路段的經驗權重集，其中該經驗權重集根據使用者的歷史路徑確定，以及其中資料採擷演算法被設定，該資料採擷演算法為頻繁項集演算法，如果該路段為基於該頻繁項集演算法得到的強關聯規則中的右側路段，則該路段的經驗權重集包括：該強關聯規則的支援度和置信度；路徑規劃單元，用於根據該路段的經驗權重集，採用啟發式搜索演算法對該路徑規劃請求進行路徑規劃。
如申請專利範圍第6項所述的裝置，其特徵在於，還包括統計學習單元，用於：基於設定的該資料採擷演算法，對具有相同該起點和終點的多條歷史路徑進行統計學習，以得到該多條歷史路徑中該路段的出現頻次，和/或，包含有該路段的關聯路段組的出現頻次；根據該出現頻次確定該路段的經驗權重集。
如申請專利範圍第7項所述的裝置，其特徵在於，還包括歷史路徑類別劃分單元，用於：獲取最近預設時間段內多個用戶走過的多條歷史路徑，構成路徑集；按照相同起點和終點，對該路徑集中的歷史路徑進行類別劃分。
如申請專利範圍第7項至第8項中任一項所述的裝置，其特徵在於，該路徑規劃單元，具體用於：根據如下公式，修正該路段的啟發函數值F _new：F _new=F+△其中，該F為該路段的原始啟發函數值；該△為基於該路段的經驗權重集確定的修正值。
如申請專利範圍第9項所述的裝置，其特徵在於，該路段為本次路徑規劃中已被確定的規劃路段的擴展路段；按照如下公式計算該△：△=α×(β×S+γ×C)其中，該α為第一調節因數，該β為第二調節因數，該γ為第三調節因數；該S為該多條歷史路徑中該路段和該規劃路段組成的目標關聯路段組的出現頻次，該C為該多條歷史路徑中該路段在該規劃路段出現下的條件出現頻次。