基于改進馬爾科夫鏈的移動軌跡預測方法

王澤天,高 嶺,高全力

(西安工程大學 計算機科學學院,陜西 西安 710048)

0 引 言

隨著通信技術及移動互聯網的成熟與發展,人工智能已經滲透到人們日常生活中的各個角落。特別是近十幾年來汽車逐漸走進千家萬戶,車流量越來越大,交通堵塞和事故頻發的問題開始凸顯,人們對智能交通的需求也就愈加強烈[1-2]。為了真正實現智能交通,更好地建設及深入研究車聯網就變得格外重要。而移動軌跡預測正是車聯網技術中的關鍵環節[3]。移動軌跡預測對于智能交通和人們的日常出行都有著重要作用,精確以及迅速地為駕駛員進行移動軌跡預測,有利于降低道路擁堵,提高出行效率[4-5]。

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

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

1 車輛軌跡數據處理

車輛在實際行駛過程中,其運動軌跡都不一樣,必須根據它們各自所特有的運動軌跡來構造狀態轉移矩陣。首先根據時間順序將收集到的全部車輛軌跡數據歸類,然后再按照車輛的不同運動軌跡對軌跡數據進行劃分。也就是,有多少不同的運動軌跡就有多少份軌跡數據[12]。

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

2 改進的移動軌跡預測算法

2.1 基本概念

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

(1)

2) 馬爾科夫鏈:馬爾科夫鏈是具有馬爾科夫屬性的一組離散隨機變量。具體地說,對于使用一維可數集作為索引集的概率空間(Ω,F,P)中的一組隨機變量X={Xn:n>0},并且該隨機變量的條件概率滿足以下條件關系[17-18]:

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

(2)

則Χ被稱為馬爾科夫鏈。

3)k步狀態轉移矩陣:用戶當前所處子網位置以及歷史移動軌跡生成的,描述位置狀態由一個狀態轉移到另一個狀態的概率,相當于用戶由一個位置轉移到另一個位置的概率,是馬爾科夫鏈預測的基礎。狀態轉移矩陣P為

(3)

其中:限制條件為

(4)

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

k步狀態轉移矩陣P(k)可表示為

(5)

2.2 馬爾科夫鏈算法

假設車輛行駛路徑中經過路口數為n,那么狀態轉移矩陣就是n×n的矩陣,其中元素pij所代表的概率是指車輛先行駛到i路口，接著行駛到j路口(j≤n),其表達式為

(6)

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

2.3 IMCTP算法

IMCTP算法的核心思想是利用已有信息中車輛行駛過次數最多的地點來預測接下來的地點，即

(7)

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

通過優化馬爾科夫鏈算法,給定一個閾值δ(閾值δ介于狀態轉移矩陣中最大的2個值之間)進行移動軌跡預測。假如最大值與次大值之差大于δ,那么車輛接下來通過的路口等于狀態轉移矩陣的最大值。當小于δ時,則根據最大值路口是否交通擁堵而采取不同的方法。可以分為最大值路口交通不擁堵、最大值路口交通擁堵2種不同情況。

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

2) 如果交通擁堵,則車輛會選擇走狀態轉移矩陣中的次大值路口。

算法的偽代碼如下所示:

input：車輛狀態轉移矩陣M，閾值δ，當前路口i；

output：下一個路口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算法的時間復雜度為O(n2),其中n代表網格中的路口總數。

3 實驗與分析

將IMCTP算法與馬爾科夫鏈的軌跡預測算法MC(Markov chain)[21]進行對比。以國內某市交通局發布的8 000多輛計程車在10 d內的8 390條移動軌跡數據為實驗數據。隨機選擇其中6 000條移動軌跡進行預測,其他移動軌跡用來測試預測精度。實驗中共有路徑138條,87個交叉路口。實驗的評價指標為預測精度(A),其計算公式為

A=an/tn

(8)

式中:an為實際行駛軌跡和預測軌跡相同的軌跡數量；tn為全部軌跡預測數量。主要分析預測精度和時間復雜度;車輛連續移動軌跡的預測精度和時間復雜度。

1) 從87個路口中隨機選擇7個,分別使用IMCTP算法、馬爾科夫鏈算法對軌跡預測精度進行對比,實驗結果如圖1所示。

圖 1 移動軌跡預測精度

從圖1可以看出，IMCTP算法比馬爾科夫鏈算法的軌跡預測精度更高。IMCTP算法的預測精度保持在75%左右,比馬爾科夫鏈算法的預測精度提高了約36%。這主要是因為馬爾科夫鏈算法沒有考慮到具體路況信息,導致預測精度偏低。

2) 分別使用IMCTP算法、馬爾科夫鏈算法,對6 000移動軌跡的未來7個路口進行連續軌跡預測,實驗結果如圖2所示。從圖2可以看出,2種預測算法的預測精度會在路口數不斷變多的過程中逐漸降低,但IMCTP算法相對保持更高的預測精度。這是因為在迭代計算的過程中,IMCTP算法每次的預測精度都較高。

圖 2 連續移動軌跡的預測精度

3) 一個優秀的算法不僅應具有較高的預測精度，還應該具有盡可能小的時間復雜度。因此，通過改變軌跡數量來分析2種算法的時間復雜度,結果如圖3所示。從圖3可知，隨著移動軌跡數量的增加,2種算法的預測時間也明顯增加,但IMCTP算法的預測時間相對較短。這是因為在車輛移動軌跡數據處理的過程中,刪除和修正了一些軌跡數據,從而減少了預測時間。

圖3 移動軌跡的預測時間

4) 圖4為移動軌跡在通過多個路口的預測時間。從圖4可知,隨著路口數增多,2種算法的預測時間都有所增加,但IMCTP算法比馬爾科夫鏈算法的預測時間較少。這是因為在預測每個路口時，IMCTP算法的預測時間都相對較短,從而迭代計算多個路口時的預測時間也就相應縮短。

圖 4 移動軌跡的連續預測時間

4 結 語

針對馬爾科夫鏈預測算法在預測移動軌跡結果選擇時可能出現的偶然性問題,提出了IMCTP算法。該算法首先采集車輛歷史軌跡數據及其發生的場景信息,并生成預測算法所需的數據源;然后利用馬爾科夫鏈算法計算狀態轉移概率,建立狀態轉移矩陣,得到移動軌跡;最后將得到的移動軌跡與真實數據進行對比。若存在出入,則將具體的路況信息加入到狀態轉移矩陣的計算中,進而對車輛下一個路口的預測進行修正。

對比實驗中,馬爾科夫鏈算法所獲得的預測精度遠小于理論值,導致這樣的預測結果可能是因為具體路況的差異。IMCTP算法的預測精度和時間復雜度比馬爾科夫鏈算法都有明顯進步,解決了馬爾科夫鏈算法在預測結果選擇時可能出現的偶然性問題,有效融合了車輛行駛過程中的具體路況信息,并可對部分預測結果進行修正,提高了軌跡預測的準確率。