基于改進(jìn)馬爾科夫鏈的移動(dòng)軌跡預(yù)測(cè)方法

王澤天,高 嶺,高全力

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710048)

0 引 言

隨著通信技術(shù)及移動(dòng)互聯(lián)網(wǎng)的成熟與發(fā)展,人工智能已經(jīng)滲透到人們?nèi)粘Ｉ钪械母鱾€(gè)角落。特別是近十幾年來汽車逐漸走進(jìn)千家萬(wàn)戶,車流量越來越大,交通堵塞和事故頻發(fā)的問題開始凸顯,人們對(duì)智能交通的需求也就愈加強(qiáng)烈[1-2]。為了真正實(shí)現(xiàn)智能交通,更好地建設(shè)及深入研究車聯(lián)網(wǎng)就變得格外重要。而移動(dòng)軌跡預(yù)測(cè)正是車聯(lián)網(wǎng)技術(shù)中的關(guān)鍵環(huán)節(jié)[3]。移動(dòng)軌跡預(yù)測(cè)對(duì)于智能交通和人們的日常出行都有著重要作用,精確以及迅速地為駕駛員進(jìn)行移動(dòng)軌跡預(yù)測(cè),有利于降低道路擁堵,提高出行效率[4-5]。

由于移動(dòng)軌跡預(yù)測(cè)與用戶本身以及地域之間關(guān)系密切,所以在移動(dòng)軌跡預(yù)測(cè)方面的研究多是結(jié)合城市路網(wǎng)信息和具體位置路況進(jìn)行分析[6]。LIU等[7]提出了1種循環(huán)對(duì)數(shù)雙線性模型,通過模擬歷史序列中的短期和長(zhǎng)期上下文,實(shí)現(xiàn)多種類型的軌跡預(yù)測(cè)。程媛等[8]提出了基于非參數(shù)密度估計(jì)的不確定軌跡終點(diǎn)預(yù)測(cè)方法,通過KS (kolmogorov-smirnov)檢驗(yàn)方法與具有相同起點(diǎn)的不確定軌跡模型進(jìn)行匹配,實(shí)現(xiàn)不同條件下的軌跡預(yù)測(cè)。陳思靜等[9]提出了基于馬爾科夫鏈的車輛軌跡預(yù)測(cè)方法,通過車載自組織網(wǎng)絡(luò)的特殊應(yīng)用場(chǎng)景以及車輛移動(dòng)的規(guī)律性,實(shí)現(xiàn)對(duì)車輛軌跡的預(yù)測(cè)。喬少杰等[10]提出了基于高斯混合模型的軌跡預(yù)測(cè)方法,通過高斯非線性概率統(tǒng)計(jì)模型,實(shí)現(xiàn)準(zhǔn)確而高效的軌跡預(yù)測(cè)。夏卓群等[11]提出1種環(huán)境自適應(yīng)車輛軌跡預(yù)測(cè)方法,通過歷史軌跡數(shù)據(jù)構(gòu)造虛擬參考點(diǎn),利用高斯混合模型訓(xùn)練數(shù)據(jù)集,實(shí)現(xiàn)具有環(huán)境自適應(yīng)性的車輛軌跡預(yù)測(cè)方法。但是上述方法多是直接采用歷史軌跡數(shù)據(jù)實(shí)現(xiàn)預(yù)測(cè),對(duì)具體路況信息考慮不充分,導(dǎo)致預(yù)測(cè)精度不高。為此,本文在傳統(tǒng)馬爾科夫鏈方法的基礎(chǔ)上,通過對(duì)車輛軌跡數(shù)據(jù)的處理并融入具體路況信息,實(shí)現(xiàn)對(duì)車輛移動(dòng)軌跡更加精準(zhǔn)的預(yù)測(cè)。

針對(duì)馬爾科夫鏈預(yù)測(cè)算法在預(yù)測(cè)結(jié)果選擇時(shí)可能出現(xiàn)的偶然性問題,本文提出了改進(jìn)的馬爾科夫鏈移動(dòng)軌跡預(yù)測(cè)(IMCTP)算法。該方法首先采集車輛歷史軌跡數(shù)據(jù)及其發(fā)生的場(chǎng)景信息,并生成預(yù)測(cè)算法所需的數(shù)據(jù)源;然后利用馬爾科夫鏈算法計(jì)算狀態(tài)轉(zhuǎn)移概率,建立狀態(tài)轉(zhuǎn)移矩陣,得到移動(dòng)軌跡;最后將得到的移動(dòng)軌跡與真實(shí)數(shù)據(jù)進(jìn)行對(duì)比，若存在出入,則將具體的路況信息加入到狀態(tài)轉(zhuǎn)移矩陣的計(jì)算中,進(jìn)而修正對(duì)車輛下一個(gè)路口的預(yù)測(cè)。

1 車輛軌跡數(shù)據(jù)處理

車輛在實(shí)際行駛過程中,其運(yùn)動(dòng)軌跡都不一樣,必須根據(jù)它們各自所特有的運(yùn)動(dòng)軌跡來構(gòu)造狀態(tài)轉(zhuǎn)移矩陣。首先根據(jù)時(shí)間順序?qū)⑹占降娜寇囕v軌跡數(shù)據(jù)歸類,然后再按照車輛的不同運(yùn)動(dòng)軌跡對(duì)軌跡數(shù)據(jù)進(jìn)行劃分。也就是,有多少不同的運(yùn)動(dòng)軌跡就有多少份軌跡數(shù)據(jù)[12]。

對(duì)于收集到的車輛軌跡數(shù)據(jù),先要進(jìn)行極端或異常數(shù)據(jù)的刪除或者更正。另外,因衛(wèi)星定位系統(tǒng)偶爾出現(xiàn)的差錯(cuò),導(dǎo)致它所提供的車輛坐標(biāo)位置不是車輛的真實(shí)坐標(biāo)。因此,在對(duì)車輛軌跡數(shù)據(jù)預(yù)測(cè)之前一定要先刪除其中不正確的車輛坐標(biāo)。導(dǎo)致衛(wèi)星定位系統(tǒng)發(fā)生定位錯(cuò)誤的因素有很多,例如車輛在偏遠(yuǎn)山區(qū)，信號(hào)不能完全覆蓋的農(nóng)村，或者是周圍障礙物阻擋了信號(hào)的傳輸?shù)?。解決上述問題的方法有:①刪除異常軌跡數(shù)據(jù)。通過設(shè)定一個(gè)時(shí)間標(biāo)準(zhǔn)，如1 min,若發(fā)送相鄰2次衛(wèi)星定位的時(shí)間差小于1 min,就可以把這條軌跡數(shù)據(jù)當(dāng)成異常軌跡數(shù)據(jù)直接去除。②添加軌跡數(shù)據(jù)。相反的,若發(fā)送相鄰2次衛(wèi)星定位的時(shí)間差大于1 min,就依據(jù)車輛的平均速度,增添1條軌跡數(shù)據(jù)。③針對(duì)一些特殊情況,如交通事故、臨時(shí)停車,使得發(fā)送相鄰2次衛(wèi)星定位的時(shí)間差大于1 min,則先把該軌跡數(shù)據(jù)進(jìn)行修正,使其貼近真實(shí)軌跡數(shù)據(jù),減少后序工作中不必要的麻煩[13-14]。

2 改進(jìn)的移動(dòng)軌跡預(yù)測(cè)算法

2.1 基本概念

1) 路徑概率:P1和P2是2個(gè)連續(xù)的路口,P1、P2之間的n條路徑分別用S1,S2,…,Sn表示，L為該路徑的長(zhǎng)度。所有路口都有幾個(gè)可行的路口,P1至P2選擇St的路徑概率見式(1)[15-16]:

(1)

2) 馬爾科夫鏈:馬爾科夫鏈?zhǔn)蔷哂旭R爾科夫?qū)傩缘囊唤M離散隨機(jī)變量。具體地說,對(duì)于使用一維可數(shù)集作為索引集的概率空間(Ω,F,P)中的一組隨機(jī)變量X={Xn:n>0},并且該隨機(jī)變量的條件概率滿足以下條件關(guān)系[17-18]:

p(Xt+1|Xt,…,X1)=p(Xt+1|Xt)

(2)

則Χ被稱為馬爾科夫鏈。

3)k步狀態(tài)轉(zhuǎn)移矩陣:用戶當(dāng)前所處子網(wǎng)位置以及歷史移動(dòng)軌跡生成的,描述位置狀態(tài)由一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的概率,相當(dāng)于用戶由一個(gè)位置轉(zhuǎn)移到另一個(gè)位置的概率,是馬爾科夫鏈預(yù)測(cè)的基礎(chǔ)。狀態(tài)轉(zhuǎn)移矩陣P為

(3)

其中:限制條件為

(4)

基于歷史移動(dòng)軌跡,能夠得出相鄰子網(wǎng)間的轉(zhuǎn)移概率(條件概率),條件概率之上再加條件概率,可得出k步狀態(tài)轉(zhuǎn)移矩陣[19-20]。

k步狀態(tài)轉(zhuǎn)移矩陣P(k)可表示為

(5)

2.2 馬爾科夫鏈算法

假設(shè)車輛行駛路徑中經(jīng)過路口數(shù)為n,那么狀態(tài)轉(zhuǎn)移矩陣就是n×n的矩陣,其中元素pij所代表的概率是指車輛先行駛到i路口，接著行駛到j(luò)路口(j≤n),其表達(dá)式為

(6)

式中：Nij代表依次通過相鄰的i路口和j路口的軌跡數(shù)。在k步狀態(tài)轉(zhuǎn)移矩陣中每行代表用戶當(dāng)前所在的子網(wǎng)絡(luò),每列代表用戶在k步后到達(dá)的子網(wǎng)絡(luò),矩陣中的每個(gè)元素表示由當(dāng)前子網(wǎng)絡(luò)轉(zhuǎn)移到下一個(gè)子網(wǎng)絡(luò)的概率, 因此, 每行中最大的列即為預(yù)測(cè)結(jié)果。再將預(yù)測(cè)結(jié)果繼續(xù)代入狀態(tài)轉(zhuǎn)移矩陣進(jìn)行迭代, 確定各個(gè)位置的預(yù)測(cè)值,并給出具有最大概率的預(yù)期位置, 從而預(yù)測(cè)出完整的移動(dòng)軌跡。將用馬爾科夫鏈算法得到的車輛移動(dòng)軌跡與實(shí)際的車輛移動(dòng)軌跡進(jìn)行對(duì)比,發(fā)現(xiàn)預(yù)測(cè)的結(jié)果和真實(shí)的結(jié)果有明顯的誤差。 這是由于馬爾科夫預(yù)測(cè)算法每次都會(huì)選擇最大值, 但當(dāng)最大值和次大值之間的差過小時(shí),實(shí)際行駛過程中選擇最大值路口與次大值路口相比是偶然的。所以僅利用馬爾科夫鏈算法對(duì)車輛進(jìn)行軌跡預(yù)測(cè)不夠準(zhǔn)確。

2.3 IMCTP算法

IMCTP算法的核心思想是利用已有信息中車輛行駛過次數(shù)最多的地點(diǎn)來預(yù)測(cè)接下來的地點(diǎn)，即

(7)

式中：Pk為車輛選擇不同路口的概率。表1為車輛A的狀態(tài)轉(zhuǎn)移矩陣。通過表1可以看出,假設(shè)A當(dāng)前處在路口3,那么接下來A必然會(huì)走路口2。但是在實(shí)際行駛中,A通過路口3以后只有1次經(jīng)過了路口2,這或許是一個(gè)偶然情況。假設(shè)A當(dāng)前處在路口2,按照狀態(tài)轉(zhuǎn)移矩陣,A有5次選擇走路口3，4次選擇走路口4,這幾乎等同于走路口3的頻率。因此車輛A走路口3還是走路口4并不確定。

通過優(yōu)化馬爾科夫鏈算法,給定一個(gè)閾值δ(閾值δ介于狀態(tài)轉(zhuǎn)移矩陣中最大的2個(gè)值之間)進(jìn)行移動(dòng)軌跡預(yù)測(cè)。假如最大值與次大值之差大于δ,那么車輛接下來通過的路口等于狀態(tài)轉(zhuǎn)移矩陣的最大值。當(dāng)小于δ時(shí),則根據(jù)最大值路口是否交通擁堵而采取不同的方法?？梢苑譃樽畲笾德房诮煌ú粨矶?、最大值路口交通擁堵2種不同情況。

1) 如果交通不擁堵,則認(rèn)為車輛通過的下一路口仍然等于狀態(tài)轉(zhuǎn)移矩陣中的最大值。

2) 如果交通擁堵,則車輛會(huì)選擇走狀態(tài)轉(zhuǎn)移矩陣中的次大值路口。

算法的偽代碼如下所示:

input：車輛狀態(tài)轉(zhuǎn)移矩陣M，閾值δ，當(dāng)前路口i；

output：下一個(gè)路口j。

路口A←矩陣中第i行值最大的路口，大小記為v1，路口B←矩陣中第i行值第二大的路口，大小記為v2

if |v1-v2| >δthen

i←路口A

else then

if路口A交通不擁堵 then

j←A

else then

j←B

end if

end if

可以看出IMCTP算法的時(shí)間復(fù)雜度為O(n2),其中n代表網(wǎng)格中的路口總數(shù)。

3 實(shí)驗(yàn)與分析

將IMCTP算法與馬爾科夫鏈的軌跡預(yù)測(cè)算法MC(Markov chain)[21]進(jìn)行對(duì)比。以國(guó)內(nèi)某市交通局發(fā)布的8 000多輛計(jì)程車在10 d內(nèi)的8 390條移動(dòng)軌跡數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)。隨機(jī)選擇其中6 000條移動(dòng)軌跡進(jìn)行預(yù)測(cè),其他移動(dòng)軌跡用來測(cè)試預(yù)測(cè)精度。實(shí)驗(yàn)中共有路徑138條,87個(gè)交叉路口。實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)為預(yù)測(cè)精度(A),其計(jì)算公式為

A=an/tn

(8)

式中:an為實(shí)際行駛軌跡和預(yù)測(cè)軌跡相同的軌跡數(shù)量；tn為全部軌跡預(yù)測(cè)數(shù)量。主要分析預(yù)測(cè)精度和時(shí)間復(fù)雜度;車輛連續(xù)移動(dòng)軌跡的預(yù)測(cè)精度和時(shí)間復(fù)雜度。

1) 從87個(gè)路口中隨機(jī)選擇7個(gè),分別使用IMCTP算法、馬爾科夫鏈算法對(duì)軌跡預(yù)測(cè)精度進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果如圖1所示。

圖 1 移動(dòng)軌跡預(yù)測(cè)精度

從圖1可以看出，IMCTP算法比馬爾科夫鏈算法的軌跡預(yù)測(cè)精度更高。IMCTP算法的預(yù)測(cè)精度保持在75%左右,比馬爾科夫鏈算法的預(yù)測(cè)精度提高了約36%。這主要是因?yàn)轳R爾科夫鏈算法沒有考慮到具體路況信息,導(dǎo)致預(yù)測(cè)精度偏低。

2) 分別使用IMCTP算法、馬爾科夫鏈算法,對(duì)6 000移動(dòng)軌跡的未來7個(gè)路口進(jìn)行連續(xù)軌跡預(yù)測(cè),實(shí)驗(yàn)結(jié)果如圖2所示。從圖2可以看出,2種預(yù)測(cè)算法的預(yù)測(cè)精度會(huì)在路口數(shù)不斷變多的過程中逐漸降低,但I(xiàn)MCTP算法相對(duì)保持更高的預(yù)測(cè)精度。這是因?yàn)樵诘?jì)算的過程中,IMCTP算法每次的預(yù)測(cè)精度都較高。

圖 2 連續(xù)移動(dòng)軌跡的預(yù)測(cè)精度

3) 一個(gè)優(yōu)秀的算法不僅應(yīng)具有較高的預(yù)測(cè)精度，還應(yīng)該具有盡可能小的時(shí)間復(fù)雜度。因此，通過改變軌跡數(shù)量來分析2種算法的時(shí)間復(fù)雜度,結(jié)果如圖3所示。從圖3可知，隨著移動(dòng)軌跡數(shù)量的增加,2種算法的預(yù)測(cè)時(shí)間也明顯增加,但I(xiàn)MCTP算法的預(yù)測(cè)時(shí)間相對(duì)較短。這是因?yàn)樵谲囕v移動(dòng)軌跡數(shù)據(jù)處理的過程中,刪除和修正了一些軌跡數(shù)據(jù),從而減少了預(yù)測(cè)時(shí)間。

圖3 移動(dòng)軌跡的預(yù)測(cè)時(shí)間

4) 圖4為移動(dòng)軌跡在通過多個(gè)路口的預(yù)測(cè)時(shí)間。從圖4可知,隨著路口數(shù)增多,2種算法的預(yù)測(cè)時(shí)間都有所增加,但I(xiàn)MCTP算法比馬爾科夫鏈算法的預(yù)測(cè)時(shí)間較少。這是因?yàn)樵陬A(yù)測(cè)每個(gè)路口時(shí)，IMCTP算法的預(yù)測(cè)時(shí)間都相對(duì)較短,從而迭代計(jì)算多個(gè)路口時(shí)的預(yù)測(cè)時(shí)間也就相應(yīng)縮短。

圖 4 移動(dòng)軌跡的連續(xù)預(yù)測(cè)時(shí)間

4 結(jié) 語(yǔ)

針對(duì)馬爾科夫鏈預(yù)測(cè)算法在預(yù)測(cè)移動(dòng)軌跡結(jié)果選擇時(shí)可能出現(xiàn)的偶然性問題,提出了IMCTP算法。該算法首先采集車輛歷史軌跡數(shù)據(jù)及其發(fā)生的場(chǎng)景信息,并生成預(yù)測(cè)算法所需的數(shù)據(jù)源;然后利用馬爾科夫鏈算法計(jì)算狀態(tài)轉(zhuǎn)移概率,建立狀態(tài)轉(zhuǎn)移矩陣,得到移動(dòng)軌跡;最后將得到的移動(dòng)軌跡與真實(shí)數(shù)據(jù)進(jìn)行對(duì)比。若存在出入,則將具體的路況信息加入到狀態(tài)轉(zhuǎn)移矩陣的計(jì)算中,進(jìn)而對(duì)車輛下一個(gè)路口的預(yù)測(cè)進(jìn)行修正。

對(duì)比實(shí)驗(yàn)中,馬爾科夫鏈算法所獲得的預(yù)測(cè)精度遠(yuǎn)小于理論值,導(dǎo)致這樣的預(yù)測(cè)結(jié)果可能是因?yàn)榫唧w路況的差異。IMCTP算法的預(yù)測(cè)精度和時(shí)間復(fù)雜度比馬爾科夫鏈算法都有明顯進(jìn)步,解決了馬爾科夫鏈算法在預(yù)測(cè)結(jié)果選擇時(shí)可能出現(xiàn)的偶然性問題,有效融合了車輛行駛過程中的具體路況信息,并可對(duì)部分預(yù)測(cè)結(jié)果進(jìn)行修正,提高了軌跡預(yù)測(cè)的準(zhǔn)確率。