孫文彬，熊 婷

中國(guó)礦業(yè)大學(xué)(北京)地球科學(xué)與測(cè)繪工程學(xué)院，北京 100083

?

歷史數(shù)據(jù)和強(qiáng)化學(xué)習(xí)相結(jié)合的低頻軌跡數(shù)據(jù)匹配算法

孫文彬，熊 婷

中國(guó)礦業(yè)大學(xué)(北京)地球科學(xué)與測(cè)繪工程學(xué)院，北京 100083

針對(duì)低頻(采樣間隔大于1 min)軌跡數(shù)據(jù)匹配算法精度不高的問(wèn)題，提出了一種基于強(qiáng)化學(xué)習(xí)和歷史軌跡的匹配算法HMDP-Q，首先通過(guò)增量匹配算法提取歷史路徑作為歷史參考經(jīng)驗(yàn)庫(kù)；根據(jù)歷史參考經(jīng)驗(yàn)庫(kù)、最短路徑和可達(dá)性篩選候選路徑集；再將地圖匹配過(guò)程建模成馬爾科夫決策過(guò)程，利用軌跡點(diǎn)偏離道路距離和歷史軌跡構(gòu)建回報(bào)函數(shù)；然后借助強(qiáng)化學(xué)習(xí)算法求解馬爾科夫決策過(guò)程的最大回報(bào)值，即軌跡與道路的最優(yōu)匹配結(jié)果；最后應(yīng)用某市浮動(dòng)車軌跡數(shù)據(jù)進(jìn)行試驗(yàn)。結(jié)果表明：本文算法能有效提高軌跡數(shù)據(jù)與道路匹配精度；本算法在1 min低頻采樣間隔下軌跡匹配準(zhǔn)確率達(dá)到了89.2%；采樣頻率為16 min時(shí)，該算法匹配精度也能達(dá)到61.4%；與IVVM算法相比，HMDP-Q算法匹配精度和求解效率均優(yōu)于IVVM算法，16 min采樣頻率時(shí)本文算法軌跡匹配精度提高了26%。

低頻浮動(dòng)車數(shù)據(jù)；軌跡匹配；馬爾科夫決策過(guò)程；強(qiáng)化學(xué)習(xí)

隨著車載和手持GPS設(shè)備的普及，GPS軌跡數(shù)據(jù)(如浮動(dòng)車數(shù)據(jù)(floating car data，F(xiàn)CD)等)已成為交通狀態(tài)模擬分析的重要數(shù)據(jù)源之一。由于采集高頻軌跡數(shù)據(jù)通信成本高，因此，60%以上的GPS軌跡數(shù)據(jù)均屬于低頻采樣[1]。但低頻軌跡數(shù)據(jù)在采樣間隔內(nèi)可能會(huì)經(jīng)過(guò)多條道路和交叉口，增加了車輛行駛路線的不確定性，致使軌跡數(shù)據(jù)無(wú)法準(zhǔn)確地反映出車輛在路網(wǎng)中真實(shí)的行駛軌跡和狀態(tài)，降低了數(shù)據(jù)應(yīng)用價(jià)值。因此，如何根據(jù)低頻采樣GPS軌跡數(shù)據(jù)獲取車輛真實(shí)行駛路線已成為國(guó)內(nèi)外學(xué)者研究的重點(diǎn)內(nèi)容之一[2-15]。

文獻(xiàn)[2]設(shè)計(jì)了基于D-S證據(jù)理論的導(dǎo)航數(shù)據(jù)地圖匹配方法。文獻(xiàn)[4,7]在顧及軌跡曲線和路網(wǎng)相似性等因素的基礎(chǔ)上研究了高頻軌跡數(shù)據(jù)的匹配方法。文獻(xiàn)[6]設(shè)計(jì)了基于曲率積分約束的浮動(dòng)車匹配算法。文獻(xiàn)[16]在考慮路網(wǎng)幾何拓?fù)浣Y(jié)構(gòu)和時(shí)間、速度限制等因素的基礎(chǔ)上，構(gòu)造了ST-Matching軌跡數(shù)據(jù)匹配算法。文獻(xiàn)[17]在ST-Matching算法的基礎(chǔ)上，設(shè)計(jì)了基于鄰近GPS軌跡點(diǎn)相關(guān)性的最佳路徑選擇算法。文獻(xiàn)[18]采用條件隨機(jī)場(chǎng)方法結(jié)合上下文信息進(jìn)行低頻軌跡數(shù)據(jù)的匹配。文獻(xiàn)[5,19]將低頻GPS軌跡點(diǎn)數(shù)據(jù)作為輸入端，將待匹配路段作為隱馬爾科夫模型(hidden Markov model，HMM)的表現(xiàn)端，設(shè)計(jì)了基于HMM的低頻軌跡匹配算法。為避免HMM模型的“標(biāo)注偏移”問(wèn)題，文獻(xiàn)[20]采用條件隨機(jī)場(chǎng)(condition random fields，CRFs)實(shí)現(xiàn)了手機(jī)GPS定位數(shù)據(jù)與地圖的匹配。但上述算法均未使用歷史軌跡數(shù)據(jù)，導(dǎo)致GPS軌跡與道路網(wǎng)匹配的準(zhǔn)確率不高。文獻(xiàn)[3]基于武漢出租車數(shù)據(jù)構(gòu)建了歷史軌跡經(jīng)驗(yàn)庫(kù)，設(shè)計(jì)了軌跡數(shù)據(jù)的匹配算法。文獻(xiàn)[1,21]基于出租車群體的歷史軌跡數(shù)據(jù)和概率推斷模型，構(gòu)建基于歷史經(jīng)驗(yàn)的出行系統(tǒng)(history based route inference system,HIRS)，軌跡匹配準(zhǔn)確率和運(yùn)算效率都得到了提升，但HIRS算法的求解效率不高。為此，本文擬構(gòu)建基于強(qiáng)化學(xué)習(xí)和馬爾科夫決策過(guò)程的低頻軌跡匹配算法，以提高匹配的準(zhǔn)確率和求解效率。

1 基于強(qiáng)化學(xué)習(xí)的軌跡匹配算法原理

軌跡匹配問(wèn)題可描述如下：給定路網(wǎng)G={E，V}，其中E為邊集，V為頂點(diǎn)集；假設(shè)一輛浮動(dòng)車從t0到ti時(shí)刻包含n個(gè)GPS軌跡點(diǎn){pi|i=0,1,…,n}，軌跡匹配即求一條最可能的行車路徑T，使T位于G上。基于強(qiáng)化學(xué)習(xí)和歷史軌跡的匹配算法整體流程如圖1所示。算法主要包括3個(gè)部分：候選點(diǎn)集選取、候選路徑集選取、最優(yōu)路徑求解。候選點(diǎn)集選取時(shí)，首先根據(jù)GPS點(diǎn)的位置尋找路網(wǎng)中鄰近路段，然后將GPS點(diǎn)分別投影到對(duì)應(yīng)的路段上，形成候選點(diǎn)集。候選路徑集選取主要依據(jù)候選點(diǎn)之間是否存在歷史軌跡；若存在，則將歷史軌跡和候選點(diǎn)間最短路徑作為候選路徑；否則，則將最短路徑作為候選路徑集。在確定候選路徑集后，依據(jù)馬爾科夫決策過(guò)程和強(qiáng)化學(xué)習(xí)來(lái)獲取最佳的匹配路徑。其中，歷史經(jīng)驗(yàn)庫(kù)構(gòu)建、候選路徑選取、基于強(qiáng)化學(xué)習(xí)的最優(yōu)路徑求解是低頻軌跡數(shù)據(jù)匹配算法的關(guān)鍵。下面將對(duì)算法各主要實(shí)現(xiàn)步驟分別進(jìn)行詳細(xì)說(shuō)明。

圖1 基于強(qiáng)化學(xué)習(xí)的地圖匹配算法流程Fig.1 The flow chart of the map matching algorithm based on reinforcement learning

1.1 構(gòu)建歷史經(jīng)驗(yàn)庫(kù)

歷史軌跡是構(gòu)建馬爾科夫決策過(guò)程回報(bào)函數(shù)的重要基礎(chǔ)。因此，如何利用原始高頻采樣軌跡數(shù)據(jù)構(gòu)建歷史軌跡經(jīng)驗(yàn)庫(kù)則是首先需要完成的任務(wù)。軌跡數(shù)據(jù)中的每條GPS日志均記錄了一輛車在較長(zhǎng)時(shí)間段內(nèi)的GPS點(diǎn)位置信息，包括了多條行駛路徑信息。為此，需將GPS日志劃分成多條路段，保證每個(gè)路段只有唯一的起點(diǎn)和終點(diǎn)。GPS日志記錄劃分過(guò)程可參見(jiàn)文獻(xiàn)[21]。文獻(xiàn)[21]首先引入staypoint的概念，每個(gè)staypoint是上一路段終點(diǎn)和下一路段的起點(diǎn)；然后通過(guò)檢測(cè)GPS日志記錄中的staypoint可將日志拆分為多個(gè)連續(xù)的路段。最后，利用文獻(xiàn)[22]提出的增量算法將歷史高頻軌跡數(shù)據(jù)匹配到對(duì)應(yīng)的道路上，把匹配獲得的結(jié)果存入歷史經(jīng)驗(yàn)庫(kù)，作為構(gòu)建回報(bào)函數(shù)的基礎(chǔ)。

1.2 候選路徑集選取

理論上軌跡數(shù)據(jù)均應(yīng)位于道路上，但由于GPS定位誤差等因素的影響，致使GPS點(diǎn)偏離真實(shí)的路網(wǎng)，因此需要將GPS點(diǎn)匹配到路網(wǎng)上。本文依據(jù)鄰近性原則選取待匹配GPS點(diǎn)的候選點(diǎn)集。候選點(diǎn)選取過(guò)程如下：查找GPS點(diǎn)誤差范圍內(nèi)的鄰近道路，計(jì)算GPS點(diǎn)在鄰近道路上的投影點(diǎn)，將投影點(diǎn)作為候選點(diǎn)；若投影點(diǎn)位于道路的延長(zhǎng)線上，則選取距離該投影點(diǎn)最近的道路頂點(diǎn)作為候選點(diǎn)。

由于相鄰候選點(diǎn)間可能存在多條路徑，需要判斷是否存在同時(shí)經(jīng)過(guò)它們的歷史軌跡；如果存在，則將它們和候選點(diǎn)間的最短路徑加入候選路徑集中。如圖2，GPS點(diǎn)候選點(diǎn)c1、c2間存在很多路徑，如果在歷史經(jīng)驗(yàn)庫(kù)中存在L1、L2、L33條路徑同時(shí)經(jīng)過(guò)候選點(diǎn)c1、c2，則將L1、L2、L3以及c1、c2最短路徑作為它們的候選路徑集；若不存在，則將它們的最短路徑作為候選路徑。此外，需根據(jù)可達(dá)性對(duì)候選路徑進(jìn)行篩選，即候選路徑不應(yīng)該超過(guò)車輛在該時(shí)間間隔內(nèi)能夠行駛的最大距離，從而形成更加符合現(xiàn)實(shí)的候選路徑集。

1.3 基于強(qiáng)化學(xué)習(xí)的全局最優(yōu)路徑求解

如何在相鄰的GPS點(diǎn)間多條候選路徑中選取一條路徑，使組成的路徑最接近真實(shí)的行車軌跡，是本算法需解決的關(guān)鍵問(wèn)題。馬爾科夫決策過(guò)程是隨機(jī)動(dòng)態(tài)系統(tǒng)的最優(yōu)決策過(guò)程，是解決該類問(wèn)題的有力工具之一。為此，本文將軌跡匹配問(wèn)題轉(zhuǎn)換為馬爾科夫決策過(guò)程，采用強(qiáng)化學(xué)習(xí)中Q-learning算法求解連續(xù)GPS點(diǎn)序列的全局最優(yōu)解，通過(guò)不斷試錯(cuò)的方法獲得經(jīng)驗(yàn)知識(shí)，然后根據(jù)經(jīng)驗(yàn)知識(shí)完善行動(dòng)策略，進(jìn)而完成軌跡數(shù)據(jù)的匹配。

1.3.1 馬爾科夫決策過(guò)程

馬爾科夫決策過(guò)程(Markovdecisionprocesses，MDPs)包含一個(gè)環(huán)境狀態(tài)集S，行為(agent)集合A，以及狀態(tài)之間的轉(zhuǎn)移概率P和在某個(gè)狀態(tài)下執(zhí)行行為的期望回報(bào)R組成。在t時(shí)刻，環(huán)境(environment)發(fā)送一個(gè)狀態(tài)信號(hào)st∈S給agent；agent做出行為(action)at∈A(st)；行為反過(guò)來(lái)影響環(huán)境，改變其狀態(tài)，同時(shí)得到一個(gè)即時(shí)的回報(bào)(reward)；重復(fù)上述過(guò)程，直到滿足設(shè)定退出條件為止。

軌跡匹配轉(zhuǎn)換為MDP過(guò)程的描述如下：

(1) 狀態(tài)(state)：在每次決策過(guò)程中，agent均位于某個(gè)GPS候選點(diǎn)上，因此某時(shí)刻agent所處的GPS候選點(diǎn)即為MDP的狀態(tài)。

(2) 決策(action)：agent選擇連接當(dāng)前候選點(diǎn)和下一個(gè)候選點(diǎn)的路徑。

(3) 回報(bào)值(reward)：評(píng)估action選出的路徑優(yōu)劣性，將評(píng)估結(jié)果作為回報(bào)值。

(4) 轉(zhuǎn)移概率P：依據(jù)回報(bào)值不斷更新轉(zhuǎn)移概率，回報(bào)值大的狀態(tài)其對(duì)應(yīng)的轉(zhuǎn)移概率大。

agent在不斷進(jìn)行決策、狀態(tài)轉(zhuǎn)移的同時(shí)，根據(jù)得到的回報(bào)值更新對(duì)環(huán)境的認(rèn)知，進(jìn)而影響決策過(guò)程，直到獲得最優(yōu)路徑為止。

1.3.2 強(qiáng)化學(xué)習(xí)算法

在馬爾科夫決策過(guò)程中，回報(bào)值最大對(duì)應(yīng)的路徑為軌跡數(shù)據(jù)最佳匹配路徑。由于強(qiáng)化學(xué)習(xí)利用了蒙特卡羅抽樣方法和動(dòng)態(tài)規(guī)劃單步迭代方法的優(yōu)點(diǎn)，克服了蒙特卡羅策略演化問(wèn)題和動(dòng)態(tài)規(guī)劃隨狀態(tài)數(shù)增加時(shí)復(fù)雜性呈指數(shù)增加的缺點(diǎn)；因此本文采用強(qiáng)化學(xué)習(xí)算法中Q-learning方法進(jìn)行最佳匹配路徑的尋找。但強(qiáng)化學(xué)習(xí)算法要求agent初始狀態(tài)具有唯一性。軌跡數(shù)據(jù)中第一個(gè)GPS點(diǎn)的候選點(diǎn)不唯一(每個(gè)GPS點(diǎn)對(duì)應(yīng)若干個(gè)候選點(diǎn))。因此，需要虛構(gòu)一個(gè)虛擬點(diǎn)，設(shè)定虛擬點(diǎn)到第一個(gè)GPS候選點(diǎn)的路徑長(zhǎng)度都為1。軌跡匹配從虛擬點(diǎn)開(kāi)始，agent通過(guò)一次決策可到達(dá)第一個(gè)GPS點(diǎn)對(duì)應(yīng)的候選點(diǎn)，再依據(jù)馬爾科夫決策過(guò)程依次選擇后續(xù)的道路節(jié)點(diǎn)，直到完成軌跡與路網(wǎng)的匹配。

Q-learning算法是在狀態(tài)轉(zhuǎn)移概率和獎(jiǎng)懲未知的情況下來(lái)估計(jì)最優(yōu)策略的Q值。Q值函數(shù)是在環(huán)境狀態(tài)st時(shí)執(zhí)行動(dòng)作at的評(píng)價(jià)函數(shù)與按最優(yōu)動(dòng)作序列執(zhí)行時(shí)得到強(qiáng)化信號(hào)折扣的和

(1)

式中，rt+1為在狀態(tài)st執(zhí)行動(dòng)作at到達(dá)狀態(tài)st+1時(shí)獲得的瞬時(shí)獎(jiǎng)懲值；γ為折扣率，保證返回的獎(jiǎng)懲是有限的；A為狀態(tài)st+1時(shí)可執(zhí)行的動(dòng)作集。

為了簡(jiǎn)化計(jì)算過(guò)程，本文采取單步Q學(xué)習(xí)策略，即學(xué)習(xí)過(guò)程中，首先根據(jù)狀態(tài)st選擇執(zhí)行動(dòng)作at，然后觀察下一個(gè)狀態(tài)st+1，收到瞬時(shí)獎(jiǎng)懲信號(hào)rt+1，根據(jù)Q學(xué)習(xí)更新規(guī)則更新Q值，再根據(jù)st+1執(zhí)行動(dòng)作at+1，重復(fù)上述過(guò)程直至滿足設(shè)定的退出條件為止。

1.3.3 回報(bào)函數(shù)

agent執(zhí)行策略a，從狀態(tài)s變?yōu)闋顟B(tài)s′時(shí)，都會(huì)得到一個(gè)回報(bào)函數(shù)R，agent是要獲取最大化的累積回報(bào)。本文算法中回報(bào)函數(shù)R由歷史經(jīng)驗(yàn)回報(bào)值R1,偏移距離回報(bào)值R2組成，均需要?dú)w一化處理，計(jì)算公式如下

R=k1×R1+k2×R2

(2)

式中，R為回報(bào)函數(shù)；k1、k2表示權(quán)重系數(shù)，k1與K2的和為1；R1為歷史經(jīng)驗(yàn)回報(bào)值；R2為偏移距離回報(bào)值。

計(jì)算歷史經(jīng)驗(yàn)路徑回報(bào)值R1時(shí)，需統(tǒng)計(jì)每條候選路徑在歷史經(jīng)驗(yàn)庫(kù)中出現(xiàn)的次數(shù)作為流行度popular(Li)，計(jì)算見(jiàn)式(3)，其中，n表示候選路徑Li被歷史軌跡經(jīng)過(guò)的次數(shù)

popular(Li)=n

(3)

(4)

偏移距離回報(bào)值R2是指候選點(diǎn)和GPS點(diǎn)之間偏移距離，表達(dá)公式如下

(5)

式中，D(pi,ci)表示GPS點(diǎn)pi和候選點(diǎn)ci之間的距離；k、d、e是比例因子。

2 算法驗(yàn)證

為了驗(yàn)證算法的正確性和有效性，本文應(yīng)用某市的浮動(dòng)車軌跡數(shù)據(jù)(2013年8月1日—8月31日2000多輛出租車的GPS數(shù)據(jù)，共一千多萬(wàn)個(gè)GPS點(diǎn))和OpenstreetMap路網(wǎng)數(shù)據(jù)進(jìn)行了試驗(yàn)。試驗(yàn)中，首先將高頻采樣數(shù)據(jù)(采樣頻率為30 s)與地圖數(shù)據(jù)進(jìn)行匹配，獲取車輛真實(shí)的行駛軌跡；然后將高頻采樣軌跡數(shù)據(jù)進(jìn)行抽稀，分別構(gòu)建了采樣間隔為1 min、2 min、4 min、8 min和16 min的低頻數(shù)據(jù)集；接著利用本文算法將低頻數(shù)據(jù)集分別匹配到地圖中；最后對(duì)比分析高頻采樣軌跡數(shù)據(jù)與低頻采樣數(shù)據(jù)匹配結(jié)果差異，計(jì)算匹配的準(zhǔn)確率。

2.1 試驗(yàn)數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理直接影響地圖匹配算法的精度和性能。為了實(shí)現(xiàn)軌跡與路網(wǎng)數(shù)據(jù)的高效匹配，需要對(duì)路網(wǎng)數(shù)據(jù)和浮動(dòng)車軌跡數(shù)據(jù)進(jìn)行處理，流程如圖2所示。利用OpenstreetMap數(shù)據(jù)構(gòu)建路網(wǎng)拓?fù)浣Y(jié)構(gòu)；處理后的路網(wǎng)共有19 974條邊和22 672個(gè)節(jié)點(diǎn)。由于GPS點(diǎn)存在“漂移”問(wèn)題，因此，應(yīng)利用緩沖區(qū)分析剔除軌跡數(shù)據(jù)中的“漂移”點(diǎn)。本文采用兩級(jí)緩沖區(qū)技術(shù)[21]剔除漂移的GPS點(diǎn)，具體流程如下：首先利用緩沖區(qū)刪除偏離道路300 m以上的GPS點(diǎn)，然后利用小尺度緩沖區(qū)對(duì)距離道路300 m以內(nèi)的數(shù)據(jù)點(diǎn)進(jìn)行過(guò)濾(緩沖區(qū)半徑由式(6)計(jì)算獲得)；再分別設(shè)置浮動(dòng)車軌跡數(shù)據(jù)的瞬時(shí)速度和經(jīng)緯度位置變化閾值的上限，剔除超過(guò)閾值的GPS點(diǎn)；最后為了消除由于浮動(dòng)車靜止或低速運(yùn)行時(shí)GPS定位精度不高造成的“假行駛”現(xiàn)象，需要根據(jù)車輛行駛模式剔除上述的GPS軌跡點(diǎn)數(shù)據(jù)。

(6)

圖2 數(shù)據(jù)預(yù)處理流程圖Fig.2 The flow chart of the map matching algorithm based on reinforcement learning

其中，路網(wǎng)定位誤差為α，車輛定位誤差最大為β，高速公路單向路寬為ω，車寬為m。本文假定路網(wǎng)精度為α=10 m，車輛最大定位誤差β為50 m，出租車寬度為1.6 m，道路寬度依據(jù)城市道路等級(jí)確定。

2.2 試驗(yàn)結(jié)果

浮動(dòng)車系統(tǒng)沒(méi)有相應(yīng)輔助設(shè)備記錄車輛的真實(shí)行駛路徑；但高頻采樣數(shù)據(jù)與真實(shí)行駛路徑非常相近，采用增量法可實(shí)現(xiàn)軌跡數(shù)據(jù)與道路的正確匹配。文獻(xiàn)[12—15]均將高頻采樣軌跡數(shù)據(jù)當(dāng)作為真實(shí)行駛路徑(ground truth)，即將高頻軌跡匹配結(jié)果作為真值來(lái)衡量低頻軌跡數(shù)據(jù)匹配的準(zhǔn)確率，本文也采用該標(biāo)準(zhǔn)進(jìn)行相關(guān)試驗(yàn)分析(圖3)。

為了衡量匹配精確度，使用文獻(xiàn)[17]中的標(biāo)準(zhǔn)評(píng)價(jià)軌跡數(shù)據(jù)匹配的準(zhǔn)確度，具體公式如下

(7)

式中，TG為高采樣率匹配路段；Tm為低采樣率匹配路段；LCR(TG,Tm)為路段TG、Tm最長(zhǎng)重合路段。

為了獲取最優(yōu)的匹配效果，試驗(yàn)測(cè)試分析了歷史軌跡和偏離道路權(quán)重對(duì)匹配結(jié)果的影響。k1分別取0.1、0.2、…、0.9，對(duì)應(yīng)k2分別取0.9、0.8、…、0.1；1、2、4、8min采樣間隔的軌跡匹配準(zhǔn)確率情況如圖4所示(偏移權(quán)重公式中d=250，k=1，e=1.4)。由圖4可知，歷史經(jīng)驗(yàn)路徑回報(bào)值在總回報(bào)值中所占比重小于0.6時(shí)，匹配準(zhǔn)確度隨著歷史經(jīng)驗(yàn)路徑回報(bào)值比重的增大而增大；當(dāng)超過(guò)0.6時(shí)，隨著偏移距離回報(bào)值的比重減小，軌跡匹配的準(zhǔn)確率也隨之下降。由此可見(jiàn)，當(dāng)k1=0.6時(shí)，低頻軌跡數(shù)據(jù)匹配的準(zhǔn)確率最高；因此，將回報(bào)函數(shù)中k1確定為0.6，k2確定為0.4。

圖3 候選路徑的選取Fig.3 The selection of candidate path

圖4 不同采樣率下k1值對(duì)地圖匹配準(zhǔn)確率的影響Fig.4 Algorithm accuracy of different k1 under different sampling rate

為了驗(yàn)證匹配結(jié)果的正確性，本文將低頻軌跡與高頻軌跡數(shù)據(jù)的匹配結(jié)果進(jìn)行了可視化表達(dá)，如圖5所示(高頻數(shù)據(jù)采樣間隔為30s；低頻軌跡數(shù)據(jù)采樣間隔為2min)。圖5中，藍(lán)色圓點(diǎn)表示原始軌跡中GPS點(diǎn)，橙色點(diǎn)表示低頻采樣間隔GPS點(diǎn)，藍(lán)色軌跡線為低頻采樣軌跡匹配的最優(yōu)路徑。圖5(a)和5(b)分別表示在交叉路口和立交橋的匹配結(jié)果。

圖5 匹配結(jié)果的可視化表達(dá)效果Fig.5 Visualization of trajectory mapping results

為了測(cè)試算法匹配的準(zhǔn)確率，對(duì)比分析了該算法(historyMarkovdecisionprocessesQ-learning，HMDP-Q)與IVMM(interactivevoting-basedmapmatching)[17]在不同采樣頻率下匹配情況。IVMM算法是應(yīng)用最廣泛的低頻軌跡數(shù)據(jù)匹配算法之一，該算法考慮了鄰近和次鄰近GPS軌跡點(diǎn)對(duì)匹配結(jié)果的影響，算法匹配精度優(yōu)于ST-Matching等方法。為此，本文對(duì)比分析了HMDP-Q與IVMM算法匹配精度，結(jié)果如圖6所示。采樣頻率為1min時(shí)，HMDP-Q算法匹配準(zhǔn)確率達(dá)89.2%，而IVMM匹配準(zhǔn)確率為73%；隨著采樣間隔的增大，HMDP-Q和IVMM算法匹配準(zhǔn)確率均呈下降的趨勢(shì)；當(dāng)采樣間隔為16min時(shí)，HMDP-Q算法匹配準(zhǔn)確率為61.4%，而IVMM匹配準(zhǔn)確率僅為34%。各采樣頻率的HMDP-Q匹配準(zhǔn)確率均高于IVMM算法。與IVMM算法相比，HMDP-Q算法加入歷史軌跡庫(kù)，充分考慮了司機(jī)習(xí)慣性路段選擇，利用強(qiáng)化學(xué)習(xí)提取出了稀疏數(shù)據(jù)條件下的路段相關(guān)性，從而提高了浮動(dòng)車軌跡數(shù)據(jù)匹配的準(zhǔn)確率。

圖6 不同采樣率下HMDP-Q和IVMM算法準(zhǔn)確率對(duì)比Fig.6 Algorithm accuracy of HMDP-Q and IVMM under different sampling rate

此外，本文利用普通筆記本計(jì)算機(jī)(具體配置如下：Inteli3CPU，2.30GHz，4GB內(nèi)存)測(cè)試分析了HMDP-Q算法的運(yùn)行效率，結(jié)果如圖7所示。由圖7可知，隨著軌跡數(shù)據(jù)采樣間隔的增大，HMDP-Q算法和IVVM算法求解所需時(shí)間均呈下降的趨勢(shì)；當(dāng)軌跡采樣頻率為12min時(shí)，HMDP-Q和IVVM算法求解所需時(shí)間基本相當(dāng)；當(dāng)軌跡采樣頻率小于12min時(shí)，HMDP-Q算法求解效率優(yōu)于IVVM算法，且軌跡采樣時(shí)間間隔越小，相對(duì)于IVVM算法而言，HMDP-Q求解效率越高。

圖7 不同采樣率下HMDP-Q和IVMM算法運(yùn)行時(shí)間對(duì)比Fig.7 Consuming time of HMDP-Q and IVMM under different sampling rate

3 結(jié) 論

針對(duì)低頻軌跡數(shù)據(jù)匹配精確不高的缺陷，本文提出了一種基于強(qiáng)化學(xué)習(xí)和歷史軌跡的低頻軌跡數(shù)據(jù)匹配算法。首先根據(jù)高頻軌跡數(shù)據(jù)建立歷史軌跡經(jīng)驗(yàn)數(shù)據(jù)庫(kù)，然后以歷史軌跡經(jīng)驗(yàn)數(shù)據(jù)庫(kù)和GPS點(diǎn)偏移距離作為回報(bào)函數(shù)構(gòu)建馬爾科夫決策模型，并引入強(qiáng)化學(xué)習(xí)來(lái)進(jìn)行馬爾科夫決策過(guò)程求解。應(yīng)用浮動(dòng)車軌跡數(shù)據(jù)和OpenstreetMap路網(wǎng)數(shù)據(jù)進(jìn)行了試驗(yàn)。試驗(yàn)結(jié)果表明：隨著采樣間隔增大，HMDP-Q和IVMM匹配的準(zhǔn)確率均呈下降的趨勢(shì)；HMDP-Q算法的匹配準(zhǔn)確率明顯高于IVMM算法；在采樣率為1min的低頻浮動(dòng)車軌跡數(shù)據(jù)下匹配精度達(dá)到89.2%，即使采樣率為16min，其匹配精度也能達(dá)到61.4%；算法解算效率也明顯高于IVMM算法。

[1] ZHENG Kai, ZHENG Yu, XIE Xing, et al. Reducing Uncertainty of Low-Sampling-Rate Trajectories[C]∥Proceedings of the IEEE 28th International Conference on Data Engineering. Washington, DC, USA: IEEE, 2012: 1144-1155.

[2] 王美玲, 程林. 浮動(dòng)車地圖匹配算法研究[J]. 測(cè)繪學(xué)報(bào), 2012, 41(1): 133-138. DOI: 10.13485/j.cnki.11-2089.2014.0030.

WANG Meiling, CHENG Lin. Study on Map-matching Algorithm for Floating Car[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 133-138. DOI: 10.13485/j.cnki.11-2089.2014.0030.

[3] 李珂, 楊楊, 邱雪松. 城市汽車導(dǎo)航中一種改進(jìn)的D-S證據(jù)理論地圖匹配算法[J]. 測(cè)繪學(xué)報(bào), 2014, 43(2): 208-213, 220. DOI: 10.13485/j.cnki.11-2089.2014.0030.

LI Ke, YANG Yang, QIU Xuesong. An Improved Map Matching Algorithm Based on D-S Evidence Theory in City Vehicle Navigation[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(2): 208-213, 220. DOI: 10.13485/j.cnki.11-2089.2014.0030.

[4] 唐爐亮, 常曉猛, 李清泉. 出租車經(jīng)驗(yàn)知識(shí)建模與路徑規(guī)劃算法[J]. 測(cè)繪學(xué)報(bào), 2010, 39(4): 404-409.

TANG Luliang, CHANG Xiaomeng, LI Qingquan. The Knowledge Modeling and Route Planning Based on Taxi’ Experience[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 404-409.

[5] 李清泉, 黃練. 基于GPS軌跡數(shù)據(jù)的地圖匹配算法[J]. 測(cè)繪學(xué)報(bào), 2010, 39(2): 207-212.

LI Qingquan, HUANG Lian. A Map Matching Algorithm for GPS Tracking Data[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(2): 207-212.

[6] 唐進(jìn)君, 劉芳. 基于路徑預(yù)測(cè)的不確定性推理組合地圖匹配算法[J]. 測(cè)繪學(xué)報(bào), 2010, 39(5): 546-550.

TANG Jinjun, LIU Fang. A Driver Route Prediction Based Map-matching Algorithm Integrating Uncertain Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(5): 546-550.

[7] 曾喆, 李清泉, 鄒海翔, 等. 曲率積分約束的GPS浮動(dòng)車地圖匹配方法[J]. 測(cè)繪學(xué)報(bào), 2015, 44(10): 1167-1176. DOI:10.11947/j.AGCS.2015.20140352.

ZENG Zhe, LI Qingquan, ZOU Haixiang, et al. Curvature Integration Constrained Map Matching Method for GPS Floating Car Data[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10): 1167-1176. DOI:10.11947/j.AGCS.2015.20140352.

[8] 唐進(jìn)君, 曹凱. 一種自適應(yīng)軌跡曲線地圖匹配算法[J]. 測(cè)繪學(xué)報(bào), 2008, 37(3): 308-315. DOI: 10.3321/j.issn:1001-1595.2008.03.008.

TANG Jinjun, CAO Kai. An Adaptive Trajectory Curves Map-matching Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(3): 308-315. DOI: 10.3321/j.issn:1001-1595.2008.03.008.

[9] DAI Jian, DING Zhiming, XU Jiajie. Context-Based Moving Object Trajectory Uncertainty Reduction and Ranking in Road Network[J]. Journal of Computer Science and Technology, 2016, 31(1): 167-184.

[10] SCHULZE G, HORN C, KERN R. Map-Matching Cell Phone Trajectories of Low Spatial and Temporal Accuracy[C]∥Proceedings of the IEEE 18th International Conference on Intelligent Transportation Systems. Washington, DC, USA: IEEE, 2015: 180-187.

[11] CHEN Ling, TANG Yanlin, LV Mingqi, et al. Partition-Based Range Query for Uncertain Trajectories in Road Networks[J]. GeoInformatica, 2015, 19(1): 61-84.

[12] DING Zhiming, YANG Bin, GüTING R H, et al. Network-Matched Trajectory-Based Moving-Object Database: Models and Applications[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4): 1918-1928.

[13] CHIANG M F, ZHU Wenyuan, PENG W C, et al. Distant-Time Location Prediction in Low-Sampling-Rate Trajectories[C]∥Proceedings of the IEEE 14th International Conference on Mobile Data Management. Washington, DC: IEEE, 2013: 350-359.

[14] LI Yang, HUANG Qixing, KERBER M, et al. Large-scale Joint Map Matching of GPS Traces[C]∥Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2013: 1320-1321.

[15] CHIANG M F, LIN Y H, PENG W C, et al. Inferring Distant-Time Location in Low-Sampling-Rate Trajectories[C]∥Proceedings of the 19th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2013: 1234-1241.

[16] LOU Yin, ZHANG Chengyang, ZHENG Yu, et al. Map-Matching for Low-Sampling-Rate GPS Trajectories[C]∥Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, USA: ACM, 2009: 352-361.

[17] YUAN Jing, ZHENG Yu, ZHANG Chengyang, et al. An Interactive-Voting Based Map Matching Algorithm[C]∥Proceedings of the 2010 Eleventh International Conference on Mobile Data Management. Washington, DC, USA: IEEE, 2010: 43-52.

[18] YANG Jian, MENG Liqiu. Feature Selection in Conditional Random Fields for Map Matching of GPS Trajectories[M]∥GARTNER G, HUANG Haosheng. Progress in Location-Based Services 2014. Switzerland: Springer International Publishing, 2015: 121-135.

[19] NEWSON P, KRUMM J. Hidden Markov Map Matching through Noise and Sparseness[C]∥Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, USA: ACM, 2009: 336-343.

[20] HUNTER T, ABBEEL P, BAYEN A. The Path Inference Filter: Model-Based Low-Latency Map Matching of Probe Vehicle Data[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(2): 507-529.

[21] ZHENG Yu, ZHANG Lizhu, XIE Xing, et al. Mining Interesting Locations and Travel Sequences from GPS Trajectories[C]∥Proceedings of the 18th International Conference on World Wide Web. New York, USA: ACM, 2009: 791-800.

[22] BRAKATSOULAS S, PFOSER D, SALAS R, et al. On Map-Matching Vehicle Tracking Data[C]∥Proceedings of the 31st International Conference on Very Large Data Bases. New York, USA: ACM, 2005: 853-864.

(責(zé)任編輯：陳品馨)

A Low-Sampling-Rate Trajectory Matching Algorithm in Combination of History Trajectory and Reinforcement Learning

SUN Wenbin,XIONG Ting

College of Geosciences and Surveying Engineering, China University of Mining and Technology(Beijing), Beijing 100083, China

In order to improve the accuracy of low frequency (sampling interval greater than 1 minute) trajectory data matching algorithm, this paper proposed a novel matching algorithm termed HMDP-Q (History Markov Decision Processes Q-learning). The new algorithm is based on reinforced learning on historic trajectory. First, we extract historic trajectory data according to incremental matching algorithm as historical reference, and filter the trajectory dataset through the historic reference, the shortest trajectory and the reachability. Then we model the map matching process as the Markov decision process, and build up reward function using deflected distance between trajectory points and historic trajectories. The largest reward value of the Markov decision process was calculated by using the reinforced learning algorithm, which is the optimal matching result of trajectory and road. Finally we calibrate the algorithm by utilizing city’s floating cars data to experiment. The results show that this algorithm can improve the accuracy between trajectory data and road. The matching accuracy is 89.2% within 1 minute low-frequency sampling interval, and the matching accuracy is 61.4% when the sampling frequency is 16 minutes. Compared with IVVM (Interactive Voting-based Map Matching), HMDP-Q has a higher matching accuracy and computing efficiency. Especially, when the sampling frequency is 16 minutes, HMDP-Q improves the matching accuracy by 26%.

low-sampling-rate floating car data; trajectory matching; Markov decision process; reinforcement learning

The National Natural Science Foundation of China (No.41671383)

XIONG Ting

孫文彬，熊婷.歷史數(shù)據(jù)和強(qiáng)化學(xué)習(xí)相結(jié)合的低頻軌跡數(shù)據(jù)匹配算法[J].測(cè)繪學(xué)報(bào)，2016,45(11)：1328-1334.

10.11947/j.AGCS.2016.20160046.

SUN Wenbin,XIONG Ting.A Low-Sampling-Rate Trajectory Matching Algorithm in Combination of History Trajectory and Reinforcement Learning[J]. Acta Geodaetica et Cartographica Sinica,2016,45(11):1328-1334. DOI:10.11947/j.AGCS.2016.20160046.

P208

A

1001-1595(2016)11-1328-07

國(guó)家自然科學(xué)基金(41671383)

2016-02-01

修回日期： 2016-10-01

孫文彬(1977—)，男，博士，副教授，研究方向?yàn)槿螂x散格網(wǎng)理論、智能計(jì)算、并行計(jì)算。First author： SUN Wenbin(1977—)，male,PhD, associate professor, majors in global discrete grids, intelligence computing, parallel computing.

E-mail： swb1996@126.com

熊婷

E-mail： 391074727@qq.com