不確定環境下移動對象自適應軌跡預測方法

夏卓群 胡珍珍 羅君鵬 陳月月

1(綜合交通運輸大數據智能處理湖南省重點實驗室(長沙理工大學) 長沙 410114) 2(長沙理工大學計算機與通信工程學院 長沙 410114) 3(國防科學技術大學計算機學院 長沙 410114)

不確定環境下移動對象自適應軌跡預測方法

夏卓群1,2,3胡珍珍1,2羅君鵬1,2陳月月3

1(綜合交通運輸大數據智能處理湖南省重點實驗室(長沙理工大學) 長沙 410114)2(長沙理工大學計算機與通信工程學院 長沙 410114)3(國防科學技術大學計算機學院 長沙 410114)

已有的軌跡預測方法難以對移動對象運動軌跡進行準確地描述,尤其在復雜且不確定的車載自組織網絡(vehicular ad hoc network)(也稱車聯網)環境中.為了解決這一問題，提出基于變分高斯混合模型(variational Gaussian mixture model, VGMM)的環境自適應軌跡預測方法ESATP(environment self-adaptive prediction method based on VGMM).首先，在傳統高斯混合模型的基礎上使用變分貝葉斯推理近似方法處理混合高斯分布;其次設計變分貝葉斯期望最大化算法學習計算高斯混合模型參數，有效運用參數先驗信息得到更高精度預測模型；最后,針對輸入軌跡數據特征，使用參數自適應選擇算法自動調節參數組合，靈活調整混合高斯分量的個數和軌跡段大小.實驗結果表明：所提方法在實驗中表現出較高的預測準確性，可應用于車輛移動定位產品中.

環境自適應；變分高斯混合模型；參數自適應選擇算法；軌跡預測

智慧城市建設的飛速發展極大地推動了車載自組織網絡(vehicular ad hoc network, VANET)(也稱車聯網)及相關技術的廣泛應用.車聯網是由車輛位置、速度和路線等信息構成的巨大交互網絡.車聯網的誕生及發展對于車輛主動安全、智能交通管理、城市生活服務、應急救援等應用具有極大的幫助，而這些應用大都離不開對位置數據的分析與預測.實際交通環境的不確定性給獲取移動對象實時空間位置帶來了巨大的挑戰，如果運動環境突然惡化，通訊信號變得微弱，全球定位系統(global positioning system, GPS)的信號會出現短時中斷，致使GPS無法獲取實時位置信息.這將造成車輛軌跡數據丟失，影響數據在車聯網內傳遞，信息不能在車輛間共享，最終導致嚴重的交通事故.在此背景下，本文主要解決的科學問題是：如何在車聯網動態環境中移動網絡節點(移動車輛)位置復雜多變、網絡拓撲頻繁變化、交通信息的獲取難度增大的情況下，利用車輛歷史軌跡數據進行實時軌跡位置預測，為智能交通控制系統提供決策所需的基礎數據.

1 相關工作

移動對象軌跡預測算法或模型在近幾十年來受到國內外眾多專家、學者的關注和研究，取得了諸多成果，并被廣泛用于交通、軍事、醫療及日常生活服務等多個領域[1-5].如通過分析原始的GPS歷史位置數據、預測交通堵塞區域[1]；測量個體軌跡信息熵、預測人類動態行為[2].MyWay建立預測系統，分別使用單個用戶行為模型、集體用戶行為模型和結合個體與集體行為模型對移動用戶下一位置進行預測[3]，該方法的優勢在于只需共享個體移動配置文件，簡潔地表示用戶動作，而不是利用原始軌跡數據揭示用戶詳細的運動.根據機會路徑和目的地原則研究不確定性目的地，提供理想的改道路徑到達主要目的地[4].當前，移動對象不確定性軌跡預測方法主要分為基于模式預測方法、基于線性模型預測方法、基于非線性模型預測方法.基于模式的預測方法是通過頻繁模式挖掘找出軌跡典型模式，再根據軌跡模式進行預測[6-9].Deb等人[6]提出通過挖掘軌跡頻繁模式，找出與數據庫中已記錄的最頻繁路徑相匹配的運動模式，進而推斷最可能到達的下一個交叉口.該方法由于沒有考慮噪聲軌跡數據的影響，因此預測精度不高.常用的基于線性模型預測方法主要有基于貝葉斯模型預測方法[10-11]、基于Markov模型預測[12-14]或隱Markov模型預測方法[15-16]、基于多階Markov模型預測方法[17-18].Schreier等人[11]提出貝葉斯網絡中基于操作的長期軌跡預測和駕駛輔助系統危險程度評估方案，有效避免了車輛碰撞.非線性模型預測方法是指通過數學公式刻畫移動對象的運動軌跡，其中高斯模型[19-21]是常用的非線性預測模型.Heravi等人[20]結合線性回歸分析法和高斯過程回歸分析法對長期軌跡進行預測，經證明該方法所提模型參數少且穩定性強，但只適應于小規模數據集.針對復雜運動模式，Wiest等人[21]提出結合貝葉斯網絡和高斯混合模型預測車輛將要行駛的路徑，該方法預測精度較高且時間開銷較低.在本文的后續工作中，借鑒其利用貝葉斯網絡處理混合高斯模型來優化模型參數的方法，靈活調整混合高斯部件個數.一些學者利用軌跡的社會關系[22]、軌跡時空信息[23-24]進行預測.上述方法大都只考慮歷史軌跡、運動速度、方向、時間、地理特征等因素對預測精度的影響，很少研究動態環境對預測結果的影響.本文針對現有預測方法在動態環境中移動對象軌跡預測精度不高、實時性差的問題提出一種動態環境下自適應軌跡預測方法.本文所提方法通過向傳統高斯混合模型引入變分貝葉斯近似推理方法和自適應參數選擇算法，自動調節高斯混合模型高斯成分個數組合以適應當前環境，提高預測模型對復雜環境的魯棒性，維持高精度且時間開銷小.

2 移動對象自適應軌跡預測模型

動態環境下移動對象運動軌跡預測，主要包括4個步驟：1)原始位置數據獲取，通過車載移動終端收集車輛實時位置信息;2)歷史軌跡數據預處理，通過對歷史軌跡數據簡化、聚類和軌跡分段操作，去除噪聲軌跡和提取局部軌跡數據特征；3)軌跡數據建模，對時空軌跡數據進行降維操作、抽取運動模式，構建高效預測模型；4)軌跡在線預測，依據軌跡特征關聯，分析移動對象運動趨勢并運用預測模型模擬運動軌跡.

2.1軌跡數據預處理

Fig. 1 Chart of trajectory segment algorithm based on density圖1 基于密度的軌跡分割算法流程圖

由于GPS等移動定位設備接收到的關于移動對象位置信息的原始數據含有大量噪聲、冗余數據，不能直接用來進行軌跡預測，因此在使用變分高斯混合模型(variational Gaussian mixture model, VGMM)對軌跡數據建模之前需要預先對位置數據進行預處理操作.首先利用K-Means聚類方法對軌跡數據進行初步聚類，將數據進行分區.鑒于K-Means聚類方法對不規則形狀集的聚類效果差，對噪聲數據敏感，而基于密度的聚類方法對噪聲數據的處理比較好.因此本節接著利用基于密度的聚類方法對軌跡數據進一步聚類處理，去除原始軌跡數據中的噪聲數據.基于密度的聚類方法輸入鄰域半徑(Eps)和領域最少數據個數(MinPts)，確定核心點，然后根據點到核心點的距離將數據分類為核心點、噪聲點和邊緣點，因此將噪聲點分離開.其次運用基于密度的軌跡分割算法[9]進一步處理軌跡數據，提取局部軌跡數據特征，提高算法運行的時間效率.本文所提聚類方法的具體實現過程請讀者參考文獻[25],基于密度的軌跡分割方法采用廣度優先搜索策略實現，具體算法流程如圖1所示.

2.2基于VGMM預測模型訓練

(1)

其中，Z表示隱變量，D為觀測數據的維度，(μk,Λk)分別為第k個高斯分量的均值矩陣和精度矩陣.

使用VGMM模型對軌跡數據建模其實質就是要準確估計模型的參數，非高斯噪聲模型參數估計常采用變分貝葉斯近似學習方法估計.變分貝葉斯是在傳統貝葉斯推斷與(examinationmaximum)期望最大化(EM)迭代估計算法的基礎上引入變分近似理論而提出的一種學習方法，也叫變分貝葉斯期望最大算法(variationBayesianexaminationmaximum,VBEM)，有效地融合了EM迭代算法收斂速度快、求解過程簡單和貝葉斯推斷理論利用已有的先驗信息等優點，改善了傳統高斯混合模型采用EM迭代算法計算模型參數容易陷入局部最優解的不足.假設觀測數據集X={x1,x2,…,xN}，N個數據是獨立同分布的，已知所有參數的先驗分布，隱變量和參數分別由Z={z1,z2,…,zN}和θ={θ1,θ2,…,θN}表示，變分推理對數邊緣似然函數可近似表示為[27]

lnp(X)=F(q(Z,θ))+
KL(q(Z,θ)‖p(Z,θ|X))，

(2)

其中：

KL(q(Z,θ)‖p(Z,θ|X))=

式(2)等號右邊第2項KL(q(Z,θ)‖p(Z,θ|X))≥0為q(Z,θ)與p(Z,θ|X)之間的KL散度.要想求得對數似然函數的最小值，需要首先計算KL散度的最小值，然而計算KL散度的最小值難度較大且繁瑣，因此，只能計算自由能量F(q(Z,θ))的最大值.

計算隱參數概率(expectationstep,E-step)

(3)

其中,E(zn k)=rn k.

利用E-step計算得到的隱參數概率來計算變分高斯混合參數聯合概率，迭代這2個步驟直到隱參數概率達到最大值，并將取得最大概率時的參數組合為最佳參數組合進行參數更新(maximizationstep,M-step)

m0,(β0Λk)-1)W(Λk|w0,v0))]，

(4)

其中，參數m0表示先驗均值,β0為協方差矩陣梯度系數，W0為先驗精度值，v0為威沙特分布自由度初始值.

參數更新：

通過變分貝葉斯近似推理方法處理高斯混合模型求得觀測數據集服從近似高斯混合分布：

(5)

其中，mk，ηk分別為第k個分量的均值、精度，其中ηk為

(6)

(7)

其中:

).

(8)

式(8)為軌跡變分高斯混合回歸模型，基本思想是：1)利用式(7)對軌跡數據利用概率密度函數建模，通過基于密度聚類和分割方法對訓練軌跡數據進行分析與處理；2)利用變分貝葉斯近似推理迭代計算高斯混合模型參數，依據符合變分高斯混合分布數據的條件分布得到K個高斯分量的回歸函數；3)利用式(8)將回歸函數加權混合完成軌跡回歸預測.

3 基于VGMM的環境自適應軌跡預測算法

3.1工作原理

本文提出的基于VGMM模型的環境自適應軌跡預測算法以變分高斯混合模型為基礎，抽象出與VGMM模型相對應的復雜軌跡模式，通過運用變分查詢算法解決GMM模型的權重、均值和精度這3個參數的估計問題完成軌跡預測.運用VGMM模型對復雜軌跡運動模式建模的過程中，首先需要對海量位置數據進行分段，將用于訓練的軌跡劃分成不同的段，用{Si,i=1,2,…,N}表示.同時，采用網格序列表示軌跡化簡軌跡，用{Oi,i=1,2,…,K}表示.然后，模型訓練學習，利用變分貝葉斯期望最大化法迭代計算模型參數得到近似后驗概率分布，設計歷史軌跡與未來軌跡的條件概率密度函數.最后運用條件概率密度函數設計未來軌跡關于歷史軌跡的回歸預測函數.軌跡預測階段，輸入測試軌跡數據集，利用模型訓練過程中得到的回歸預測函數計算預測值.

3.2參數自適應選擇

基于VGMM模型軌跡預測模型選擇，與軌跡所在區域大小密切相關.軌跡預測模型的精度主要受VGMM模型參數λ={α,μ,η,v}、軌跡分段的大小segsize這2個因素的影響.在實際應用中，由于運動環境的不確定性，導致移動對象運動狀態隨時發生改變，因此相鄰軌跡點的間隔大小不一致，這就導致了由輸入產生軌跡數據丟失的問題.為了解決這一問題，本文采用參數自適應選擇算法使得軌跡完整.參數自適應調整過程如下，圖2為參數自適應選擇算法流程圖:

Fig. 2 Flow of parameters self-adaptive selection algorithm圖2 參數自適應選擇算法流程圖

3.3基于VGMM環境自適應軌跡預測

ESATP-VGMM包含2個階段：1)訓練階段，將經過參數自適應選擇算法處理的移動對象歷史軌跡數據作為訓練數據集，發現軌跡典型運動模式，并以此建立基于變分高斯混合模型的高效預測模型；2)預測階段，運用訓練階段得到的預測模型對移動對象未來小段時間內運動軌跡進行預測.基于VGMM的環境自適應軌跡預測算法偽代碼如算法1所示：

算法1. 基于VGMM的環境自適應軌跡預測算法.

輸入：訓練數據集 Ttrain=(X,Y)、測試數據集Ttest=(X*,Y*)、軌跡集T={T1,T2,…,Tn}；

輸出：軌跡預測平均誤差RMSE.

① C=?, F=?;

② 分離軌跡點和噪聲點，軌跡數據基于密度的聚類得到m個聚類簇并存放到集合C中,C=Tracluster(T);

③ 發現隱藏軌跡點和提取軌跡典型運動模式,基于密度的軌跡分割得到軌跡段集合F=Trasegment(C);

④ 參數自適應選擇算法，調整軌跡段大小trasegsize,補充完整軌跡,得到完整軌跡集S=paraselect(F);

⑤ 將軌跡映射到網格中，轉換為軌跡鏈表示transform(S);

⑥ 采用K-Means聚類初始化VGMM模型參數VGMM_para=K-means(Ttrain);

⑦ 模型訓練，使用VBEM算法迭代學習估計模型參數M_para=VBEM(Ttrain,VGMM_para);

⑧ 計算軌跡預測步數i=n-d；

⑨ 軌跡預測，Tpr表示預測軌跡點，Tre表示真實軌跡點

fori=1tol

Tpr=predict(M)；

e[i]=callRMSE(Tpr,Tre)；

endfor

由于本章對預測模型學習訓練都是通過最優化邊緣似然來獲取模型所需參數，而每次的梯度計算都要對協方差矩陣求逆，因此所提算法的時間復雜度在模型訓練階段為O(n3L)，n為軌跡數量，L表示梯度計算的次數，軌跡預測階段的時間復雜度與預測軌跡數量n有關，時間復雜度取值范圍為[O(n2),O(nlogn)].

4 實驗與結果

本節將使用真實交通場景中車輛位置數據進行一系列的實驗，對所提方法的性能進行評估.

4.1數據集與實驗環境

本實驗數據采用微軟亞洲研究院Geolife項目[30]的數據集，包含23 667 828個軌跡點，總長度達1 292 951 km.每個軌跡點包含了移動對象的時空位置信息，本文將軌跡數據集分成2個子數據集，其中訓練數據集和測試數據集的分配比例為9∶1.實驗使用MATLAB 2014a環境，數據庫為SQL Server 2008.實驗硬件平臺為：Intel?CoreTM2 Duo P8700 2.53 GHz CPU，2 GB內存，操作系統為Windows 7.為了方便比較不同參數條件、不同算法的優劣，性能評價指標使用以下標準，該標注廣泛應用于多標簽分類研究中[31].

(9)

2) 準確率(accuracy).定義為真正的軌跡點在預測軌跡點集合中出現的頻次，如果預測軌跡點就是真實的軌跡點，則p(l)=1，否則p(l)=0.

).

(10)

3) 可信度(reliability).定義為所有的預測軌跡點中概率最大的點不是真實軌跡點出現的頻次，如果預測軌跡點是真實的軌跡點，則預測誤差e(l)=0，否則e(l)=1.

).

(11)

4) 平均精度(averageprecision).給定預測軌跡點，平均預測精度定義為

其中，p(i)=1表示預測點i是真實的軌跡點.

4.2VGMM模型性能評估

本節對預測模型VGMM模型的性能進行評估.在軌跡預測過程中，合適的選擇參數有助于靈活調節參數組合、優化模型性能(比如高斯混合模型混合分量的個數K、軌跡分段大小segtrasize).本節主要研究這些參數是如何影響模型的性能.

首先，研究軌跡段大小β=30的情況下，混合分量個數K從5增加到20的變化對模型的影響.接下來的實驗主要測驗混合分量個數對預測誤差、準確性、平均精度及可信度的影響.圖3所示，VGMM獲得最好性能，在相同觀測軌跡長度下，其預測平均誤差在K=15時獲得最小，而且隨著觀察軌跡長度的增加，預測模型預測誤差快速下降，高斯混合分量個數在K=15所在曲線表現出明顯的優勢，最小可達到30 m以下.高斯混合元組個數K對平均精度的影響如圖4所示，相同觀測軌跡長度下預測模型獲得最大平均預測精度在K=15時.

Fig. 3 Prediction error under different observable length of input trajectories圖3 不同軌跡長度下混合分量對預測誤差的影響

Fig .4 Average precision under different observable length of input trajectories圖4 不同輸入歷史軌跡長度下平均精度比較

Fig. 5 Accuracy comparison of different observable length of input trajectories圖5 不同輸入歷史軌跡長度下準確性比較

如圖5所示，在相同的觀察軌跡長度下，當高斯混合元組個數K從5增加到15，預測準確性明顯提高，但當K進一步增加，預測精度開始下降，這表明高斯混合分量個數為15時，預測模型的精度最好.從圖6可以觀察到，預測模型的預測可信度在軌跡長度length=10時，預測可信度不高都為10%，隨著軌跡點數的增加預測可信度提高；同時在相同的軌跡長度的情況下，預測可信度隨混合分量的個數K從5到15逐漸提高，然而Kgt;15之后預測可信度保持基本不變，從圖6中可以看到K=15的曲線預測可信度最高，且最高接近80%.混合分量過少時，預測模型不能將所有的運動模型包括在內，導致預測結果差，然而混合分量的個數也不宜過多，混合分量過多會導致模型建立時間增加，甚至可能引起高的時空訓練代價.鑒于這些因素，在接下來的實驗中統一設置高斯混合元組個數K=15.

Fig. 6 Reliability comparison of different observable length of input trajectories圖6 不同輸入歷史軌跡長度下預測可信度比較

Fig. 7 Prediction error under different size of trajectory segment圖7 不同軌跡段大小下預測誤差比較

接下來考慮不同軌跡段大小β(K=15)的情況下進行軌跡預測，研究其是如何影響預測模型的性能.如圖7所示，預測誤差隨軌跡段大小β增大而下降，然而在β=30之后略有上升，這是因為軌跡段大小增大，軌跡段可能包含了不滿足軌跡段劃分條件的軌跡點，因此預測誤差增加.從圖8～10可以了解到，預測準確性、預測可信度和平均精度隨著β的增加而提高，但是在軌跡段大小β=30之后開始下降,這表明軌跡段大小β應該大到能夠放下足夠多的軌跡以至于包含足夠多的運動模式，然而β太大而不能發現隱藏的軌跡模式，導致預測精度不高.

Fig. 8 Accuracy with different size of trajectory segment圖8 不同軌跡段大小準確性比較

Fig. 9 Reliability under different size of trajectory segment圖9 不同軌跡段大小預測可靠性比較

Fig.10 Average precision with different size of trajectory segment圖10 不同軌跡段大小平均精度比較

4.3與已有預測模型或方法的比較

Fig. 11 Effect of randomly changing environment to prediction error, prediction reliability, and accuracy圖11 環境變化對預測誤差、預測可信度和準確性的影響

接下來比較本文所提預測算法(VGMM-ESATP)與基于高斯混合模型軌跡預測算法(Gaussian mixture model trajectory prediction, GMTP)[21]和基于Markov模型軌跡預測算法(Markov model trajectory predic-tion, MTP)[14].GMTP預測方法是一種利用高斯混合模型對軌跡數據建模，然后根據軌跡概率分布進行軌跡預測；MTP預測方法是借鑒Markov鏈無后效性的思想，計算移動對象狀態轉移概率，建立轉移概率矩陣，并根據當前的轉移概率與已有的轉移概率矩陣對比進行軌跡預測.本文所提方法與GMTP預測算法的不同之處是本文使用VBEM算法進行模型參數估計和參數自適應選擇算法靈活調整參數組合，該方法能夠彌補GMTP方法參數估計出現過擬合或者局部最優的不足，而且還能改善GMTP方法在非高斯噪聲中預測精度下降的問題.MTP預測算法與另外2種預測方法的差異除了模型不同之外，還缺少軌跡數據預處理操作，因此預測結果受噪聲影響較大.本節仿真數據統一使用微軟亞洲研究院Geolife項目的數據集，運用4.2節得到的參數高斯混合分量個數K=15和軌跡段大小β=30對模型性能進行比較評價.

1) 動態環境下預測結果分析.實際交通環境是隨機變化的而不是恒定不變的，車輛的運動軌跡間隔也不是均勻的，在這種情況下采用傳統高斯混合模型進行預測很難得到高精度的預測結果，因此我們提出基于變分高斯混合模型環境自適應軌跡預測方法，其能夠自動調整高斯混合元組的個數以適應不同的環境.通過分析比較隨機變化環境下以上所提3種算法的預測誤差、預測可信度、準確性來證明所提方法的優勢.設環境參考值n從4到-14動態變化，觀察訓練數據集大小對預測結果的影響.如圖11所示,本文所提預測算法優于GMTP和MTP.從圖11(a)可以看出ESATP預測方法平均預測誤差均小于35 m，而GMTP預測算法的預測誤差都在40 m以上，MTP的預測誤差更是在50 m以上.這是因ESATP算法采用變分貝葉斯推理方法和參數自適應選擇算法自動調整高斯混合元組個數，降低了模型對環境的敏感度.圖11(b)表現了動態環境對預測算法的可信度的影響，ESATP的預測可信度均在90%以上;GMTP次之在83%以上;最差的是MTP算法，其可信度最高只達到83%.圖11(c)隨機變化環境對預測準確性的影響，ESATP預測準確率最高且穩定；GMTP雖然也很高，但波動比較大不穩定;MTP預測準確率最低，不超過30%.

Fig. 12 Accuracy comparison in constant environment圖12 恒定環境下預測準確性比較

2) 恒定環境下預測結果分析.比較恒定環境下ESATP，GMTP和MTP之間的預測準確率、預測誤差和預測可信度.結果如圖12～14所示.從圖12和圖14可以得出恒定環境下不同訓練數據集ESATP和GMTP的預測準確率和預測可信度非常的接近，這是由于恒定環境下GMTP和ESATP算法中高斯混合模型分量個數只受訓練數據集的影響，因此相同訓練數據集GMTP與ESATP的預測準確率幾乎相同.從圖13可以看到恒定環境下ESATP，GMTP和MTP的預測誤差.其中，ESATP的預測誤差略優于GMTP；MTP的預測誤差還是比較大，這是由于MTP沒有對軌跡數據進行聚類處理，沒有考慮軌跡間的相似性問題，因此預測誤差比其他2種算法的預測誤差都大.

Fig.13 Error comparison in constant environment圖13 恒定環境下預測誤差比較

Fig. 14 Reliability comparison in constant environment圖14 恒定環境下預測可信度比較

Fig .15 Prediction time comparison among typical trajectory prediction algorithms圖15 典型軌跡預測算法時間性能比較

4.4預測時間比較

為了再進一步驗證所提方法的性能，觀察不同測試軌跡集的算法預測時間代價.圖15中，ESATP的預測時間比GMTP的稍長，相比于MTP 算法要低得多.GMTP預測時間比ESATP小是因為ESATP方法中軌跡分段發現隱藏運動模式和參數自適應選擇算法自動調整高斯混合元組個數以適應不斷變化的環境過程中需要消耗較多的時間，因此，預測時間要比GMTP高一點.然而，EASTP比MTP算法的預測時間要少得多是因為EASTP利用高斯函數能夠一次刻畫多個軌跡點，因此要比MTP的預測時間小.

5 總 結

本文針對動態環境下很難對目標運動軌跡進行準確地描述，且軌跡數據中存在非高斯噪聲，提出基于變分高斯混合模型環境自適應軌跡預測方法.為了預測動態環境中移動對象軌跡位置，首先運用聚類方法和軌跡分割方法優化軌跡源數據；其次，通過變分貝葉斯推理-期望最大化算法估計預測模型參數，得到更優的模型參數，并結合參數自適應選擇算法調整參數組合，使預測模型能夠適應不同的環境.實驗結果表示所提的預測方法在保持較低的時間開銷的同時預測精度較高.

在未來的研究工作中，除了考慮環境等客觀影響因素之外，還將考慮駕駛員個人駕駛習慣和偏好主觀影響因素對軌跡預測準確率的影響，進一步提高預測精度.

[1]Wang Zuchao, Lu Min, Yuan Xiaoru. Visual traffic jam analysis based on trajectory data[J]. IEEE Trans on Visualization and Computer Graphics, 2013, 19(2): 2159-2168

[2]Song Chaoming, Qu Zehui, Blumm N, et al. Limits of predictability in human mobility[J]. America Association for the Advancement of Science, 2010, 327(5968): 1018-1021

[3]Trasarti R, Guidotti R, Monreale A, et al. Myway: Location prediction via mobility profiling[J]. Information Systems, 2015, 64: 350-367

[4]Horvitz E, Krumm J. Some help on the way: Opportunistic routing under uncertainty[C]Proc of the 2012 ACM Conf on Ubiquitous Computting. New York: ACM, 2012: 371-380

[5]Xu Lingwei, Wu Chunlei, Wang Jingjin. A performance analysis of vehicle-to-vehicle communication system in the Internet of vehicle[J]. Netinfo Security, 2014 (7): 61-64 (in Chinese)(徐凌偉, 吳春雷, 王景景. 車聯網中車-車通信系統性能分析[J]. 信息網絡安全, 2014 (7): 61-64)

[6]Deb S, Jia C, Fong S. On-road directional trajectory prediction by junction-based pattern mining from GPS data[C]Proc of Int Conf on Machine Intelligent and Research Advancement. Piscataway, NJ: IEEE, 2013: 253-257

[7]Chen Ling, Lü Mingqi, Ye Qian, et al. A personal route prediction system based on trajectory data mining [J]. Information Sciences, 2011,11(35): 1264-1284

[8]Ying J C, Lee W C, Weng T C, et al. Semantic trajectory mining for location prediction[C]Proc of the 19th ACM SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2011: 34-43

[9]Qiao Shaojie, Han Nan, Zhu W, et al. Traplan: An effective three-in-one trajectory-prediction model in transportation networks [J]. IEEE Trans on Intelligent Transportation Systems, 2014,16(3): 1188-1198

[10]Guo Chao, Li Kun, Wang Yongyan, et al. A location index for range query in real-time location system [J].Journal of Computer Research and Development, 2011, 48(10): 1908-1917 (in Chinese)(郭超, 李坤, 王永炎, 等. 面向實時定位系統的位置區域索引[J]. 計算機研究與發展, 2011, 48(10): 1908-1917)

[11]Schreier M, Willert Volker, Adamy J. Bayesian, maneuver-based, long-term trajectory prediction and criticality assessment for driver assistance system[C]Proc of IEEE Int Conf on Intelligent Transportation System. Piscataway, NJ: IEEE, 2014: 334-341

[12]Qiao Shaojie, Tang Changjie, Jin Huidong, et al. PutModel: Prediction of uncertain trajectories in moving objects databases[J]. Applied Intelligence, 2010, 33(3): 370-386

[13]Li Wen, Xia Shixiong, Liu Feng, et al. Location prediction algorithm based on movement tendency [J]. Journal of Communications, 2014, 2(35): 46-62 (in Chinese)(李雯, 夏士雄, 劉峰, 等. 基于運動趨勢的移動對象位置預測[J]. 通信學報, 2014, 2(35): 46-62)

[14]Ziebart B D, Maas A L, Dey A K, et al. Navigate like a cabbie: Probabilistic reasoning from observed context-aware behavior[C]Proc of the 10th Int Conf on Ubiquitous computing. New York: ACM, 2008: 322-331

[15]Guo Limin, Ding Zhiming, Hu Zelin, et al. Uncertain path prediction of moving objects on road networks[J]. Journal of Computer Research and Development, 2010, 47(1): 104-112 (in Chinese)(郭黎敏, 丁治明, 胡澤林, 等. 基于路網的不確定性軌跡預測[J]. 計算機研究與發展, 2010, 47(1): 104-112)

[16]Qiao Shaojie, Shen Dayong, Wang Xiaoteng, et al. A self-adaptive parameter selection trajectory prediction approach via hidden Markov models[J]. IEEE Trans on Intelligent Transportation System, 2015, 16(1): 284-296

[17]Qiao Shaojie, Li Tianrui, Han Nan, et al. Self-adaptive trajectory prediction model for moving objects in big data environment [J]. Journal of Software, 2015, 26(11): 2869-2883 (in Chinese)(喬少杰, 李天瑞, 韓楠, 等. 大數據環境下移動對象自適應軌跡預測模型[J]. 軟件學報, 2015, 26(11): 2869-2883)

[18]Lü Mingqi, Chen Ling, Chen Gencai. Position prediction based on adaptive multi-order Markov model [J]. Journal of Computer Research and Development, 2010, 47(10): 1764-1770 (in Chinese)(呂明琪, 陳嶺, 陳根才. 基于自適應多階Markov模型的位置預測[J]. 計算機研究與發展, 2010, 47(10): 1764-1770)

[19]Chen Meng, Yu Xiaohui, Liu Yang. Mining moving patterns for prediction next location [J]. Information Systems, 2015, 54(C):156-168

[20]Heravi E J, Khanmohammadi S. Long term trajectory prediction of moving objects using Gaussian process[C]Proc of the 1st IEEE 2011 Int Conf on Robot, Vision and Signal Processsing. Piscataway, NJ: IEEE, 2011: 228-232

[21]Wiest J, H?ffken M, Kre?el U, et al. Probabilistic trajectory prediction with Gaussian mixture models [C]Proc of Intelligent Vehicles Symp. Piscataway, NJ: IEEE, 2012, 5(3): 141-146

[22]Qiao Shaojie, Jin Kun, Han Nan, et al. GMTP: A trajectory prediction algorithm based on Gaussian mixture model [J]. Journal of Software, 2015, 26(5):1048-1063 (in Chinese)(喬少杰, 金琨, 韓楠, 等. GMTP: 基于高斯混合模型的軌跡預測算法[J]. 軟件學報, 2015, 26(5): 1048-1063)

[23]Huang C C, Manh H N, Hwang T H. Vehicle trajectory prediction across non-overlapping camera networks[C]Proc of IEEE Int Conf on Connected Vehicles and Expo. Piscataway, NJ: IEEE, 2013: 375-380

[24]Lei P R, Shen T J, Peng W C, et al. Exploring spatial-temporal trajectory model for location prediction [C]Proc of the 12th IEEE Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2011: 58-67

[25]Birant D, Kut A. ST-DBSCAN: An algorithm for clustering spatial-temporal data[J]. Data amp; Knowledge Engineering, 2007, 60(1): 208-221

[26]Chan A, Li F W B. Utilizing massive spatiotemporal sample for efficient and accurate trajectory prediction[J]. IEEE Trans on Mobile Computing, 2013,12(12): 2346-2359

[27]Xu Dingjie, Shen Chen, Shen Feng. Variational Bayesian learning for parameter estimation of mixture of Gaussian [J]. Journal of Shanghai Jiao Tong University, 2013, 47(7): 1120-1125 (in Chinese)(徐定杰, 沈忱, 沈鋒. 混合高斯分布的變分貝葉斯學習參數估計[J].上海交通大學學報, 2013, 47(7): 1120-1125)

[28]Mishra H K, Sekhar C C. Variational Gaussian mixture models for speech emotion recognition[C]Proc of the 7th IEEE Int Conf on Advances in Pattern Recognition. Piscataway, NJ: IEEE, 2009: 183-232

[29]Nasios N, Bors A G. Variational learning for Gaussian mixture models [J]. IEEE Trans on System Man and Cybernetics—Part B: Cybernetics, 2006, 36(4): 849-862

[30]Zheng Yu, Xie Xing, Ma Weiming. GeoLife: A collaborative social networking service among user, location and trajectory [J]. Bulletin of the Technical Committee on Data Engineering, 2010, 33(2): 32-39

[31]Ye M, Shou D, Lee W C, et al. On the semantic annotation of place in location-based social networks[C]Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2011: 520-528

XiaZhuoqun, born in 1977. PhD. Associate professor at Changsha University of Science and Technology. His main research interests include wireless networks, VANET, smart grid.

HuZhenzhen, born in 1988. Master candidate at Changsha University of Science and Technology. Her main research interest is intelligence transportation system.

LuoJunpeng, born in 1992. Master candidate at Changsha University of Science and Technology. His main research interest is intelligent transportation.

AdaptiveTrajectoryPredictionforMovingObjectsinUncertainEnvironment

Xia Zhuoqun1,2,3, Hu Zhenzhen1,2, Luo Junpeng1,2, and Chen Yueyue3

1(Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation (Changsha University of Science and Technology), Changsha 410114)2(School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410114)3(College of Computer, National University of Defense Technology, Changsha 410114)

The existing methods for trajectory prediction are difficult to describe the trajectory of moving objects in complex and uncertain environment accurately. In order to solve this problem, this paper proposes an self-adaptive trajectory prediction method for moving objects based on variation Gaussian mixture model (VGMM) in dynamic environment (ESATP). Firstly, based on the traditional mixture Gaussian model, we use the approximate variational Bayesian inference method to process the mixture Gaussian distribution in model training procedure. Secondly, variational Bayesian expectation maximization iterative is used to learn the model parameters and prior information is used to get a more precise prediction model. This algorithm can take a priory information. Finally, for the input trajectories, parameter adaptive selection algorithm is used automatically to adjust the combination of parameters, including the number of Gaussian mixture components and the length of segment. Experimental results perform that the ESATP method in the experiment shows high predictive accuracy, and maintains a high time efficiency. This model can be used in products of mobile vehicle positioning.

environment adaptive; variational Gaussian mixture model (VGMM); parameter adaptive selection algorithm; trajectory prediction

her bachelor and master degrees in computer science and technology from National University of Defense Technology (NUDT), Changsha in 2013 and 2015, respectively. PhD candidate in the College of Computer, NUDT. Her main research interests include mobile sensing and task assignment.

2017-05-08；

2017-08-10

國家自然科學基金項目(61572514)；湖南省自然科學基金項目(14JJ7043)；湖南省交通廳科技進步與創新項目(201405)

This work was supported by the National Natural Science Foundation of China (61572514), the Natural Science Foundation of Hunan Province of China (14JJ7043), and the Transportation Department Technological Progress and Innovation Fund of Hunan Province of China (201405).

胡珍珍(1102439691@qq.com)

(xiazhuoqun@sina.com)

TP391