基于HMM的電動汽車行車軌跡糾偏優化

劉偉東，趙 新，李 磊，劉小琛，李 丹

(1.國網天津市電力公司 電力科學研究院，天津 300021；2.國網天津市電力公司 營銷部，天津 300010)

0 引 言

由于電動汽車廣泛應用的基礎設施如充電設施較少，限制了電動汽車的進一步發展。電動汽車行車軌跡數據可應用在電動汽車充電設施的整體規劃中，精確的電動汽車行車軌跡數據可以結合城市規劃及交通情況，為充電設備選址規劃提供數據支撐[1-4]。特別是在無人駕駛電動汽車領域，精確的軌跡能夠確保無人駕駛汽車的高安全性[5-7]。行車軌跡的經緯度等定位數據信息變化頻繁，其可以結合GPS、電子地圖和可視化等技術進行軌跡繪制和定位的特點，從而可以將汽車行駛過程中不符合道路特征的定位數據信息進行糾偏，以正確獲得行車軌跡，進而獲得更為準確的定位數據，解決軌跡不準確等問題。現有文獻提出了基于數據擬合、概率統計和預測等方法以解決軌跡不準確問題，但還是存在定位頻率低引起定位軌跡信息不連續等問題。隱馬爾可夫模型(hidden Markov model，HMM)是一種統計模型，當前已有研究將其與物聯網技術集成應用在軌跡預測中[8-10]。本文將采用HMM模型進行電動汽車的行車過程中定位軌跡的數據不準確問題進行糾錯，并提出了隱馬爾可夫糾偏定位點優化算法以提升定位精度，可為電動汽車的充電設施的選址提供精確的行車軌跡數據來源。

1 相關理論

隱馬爾可夫模型是一種關于時間序列的概率模型，是經典的預測模型。其中的馬爾可夫鏈概念是指在給定已知信息和狀態的情況下，只使用當前信息去預測未知的信息，已知的信息稱為可見狀態鏈，未知的狀態稱為隱馬爾可夫鏈。其應用在預測方面，僅使用當前已知的狀態去預測未來的未知狀態，隱馬爾可夫模型的具體定義請參見文獻[10]，此處簡述本文用到的部分相關概念及定義如下

P(Xn+1=x|X0,X1,X2,…,Xn)=P(Xn+1|Xn)

(1)

式中：Xn代表當前的狀態，Xn+1代表在已知當前狀態的情況下Xn+1的狀態。Xn+1和Xn有關，與X0,X1,X2,…,Xn-1無關，這種假設性前提則是一階馬爾可夫鏈；如果未來狀態只與前兩個狀態有關，那么稱為二階馬爾可夫鏈；……，以此類推。

隱馬爾可夫模型用能觀察到的馬爾可夫可見狀態鏈去預測隱馬爾可夫鏈。針對車輛軌跡的糾偏問題，原理上屬于預測問題，可用隱馬爾可夫模型，即在已知監測位置信息的情況下來預測實際的行車軌跡位置信息，將偏離實際位置較大的定位數據進行剔除。

假設K為所有可見狀態鏈的狀態集合，G是所有可觀測到的狀態集合

K={q1,q2,…,qM},G={g1,g2,…,gN}

(2)

I為長度是t的狀態序列，O是對應觀測序列

I={i1,i2,…,it},O={o1,o2,…,ot}

(3)

設狀態數為N，觀測數為M，隱馬爾可夫模型(λ)通常用λ=(A,B,π) 表示。其中，A是狀態轉移概率矩陣，B是觀測概率矩陣，π是初始狀態概率向量，具體如下

A=[aij]M*M

(4)

式中：aij=P(it+1=qj|it=qi), 1≤i,j≤M。

B=[bj(k)]M*N

(5)

式中：bj(k)=P(ot=gk|it=qj), 1≤k≤N, 1≤j≤M。

π=(πi)

(6)

式中：πi=P(i1=qi), 1≤i≤M。

2 行車軌跡糾偏模型

建立的基于隱馬爾可夫的行車軌跡模型主要包括如下部分：

(1)可見狀態鏈：從待定位車輛的定位感知設備(例如GPS定位終端、手機位置傳感器等)中獲取電動汽車所在位置的經緯度。

(2)觀測序列：Y=(Yx|x=1,2,…,S)， 其中S代表有定位設備在S個位置處采集到的經緯度定位數據信息。如圖1所示，黑色實心點A、B、C、D為觀測序列。

圖1 行車軌跡模型中的相關序列

(3)交通道路路網節點：RN=(P,R)， 其中P=(pi|i=1,2,…,m) 表示道路上的結點，比如交叉路口、道路起點等，R=(rj|j=1,2,…,n) 代表軌跡中路網上的各條道路。如圖1所示，白色空心點P1～P6等為交通道路中的路網節點；圖1中各路網節點所在的道路即為路網上的各條道路rj。

(4)隱藏序列：Z=(zi|i=1,2,…,t)， 車輛所處真實位置，即為需要預測與糾偏的真實行車軌跡定位序列。

下面分別介紹該模型中的觀測概率、狀態轉移概率和初始狀態概率。

(7)

圖2 車輛軌跡觀測概率

(2)狀態轉移概率：與候選定位點之間的真實距離成正比，表示如下

p(px+1=zj|px=zi)∝e-α dij

(8)

式中：dij表示候選定位點zi與zj之間的距離，α是影響zi與zj之間最短距離元素的參數。

(3)初始狀態概率：p(y1|p1=z1)。

在時間t狀態為i的所有路徑 (i1,i2,…,it) 中概率最大的值是

δt(i)=maxP(it=i,it-1,…,i1,ot,ot-1,…,o1)
i=1,2,…,M

(9)

由此可推導得出δ

δt+1(i)=maxP(it+1=i,it,it-1,…,i1,ot+1,ot,…,o1|λ)=
max[δt(j)aji]bi(ot+1)
i=1,2,…,M;t=1,2,…,T-1; 1≤j≤M

(10)

那么在時間t狀態i的所有路徑中概率最大的第t-1個結點為

Ψt(i)=argmax[δt-1(j)aji]i=1,2,…,M

(11)

在此模型中，通過計算與位置點的距離來決定隱藏狀態點，應用Viterbi算法求解隱藏狀態點的觀測概率。

3 隱馬爾可夫糾偏定位點優化算法

由于HMM模型存在如下兩種假設：①齊次馬爾可夫假設；②觀測獨立性假設。齊次馬爾可夫指的是隱馬爾可夫鏈任意時刻的狀態只與它前一時刻的狀態有關；觀測獨立性指的是任意時刻的監測只依賴于該隱馬爾可夫鏈的狀態。在所構建的軌跡糾偏模型中，由于GPS信號、設備故障或網絡信號等原因導致的觀測到的定位位置出現偏差，這會導致采用傳統的基于HMM的行車軌跡糾偏方法的偏差相應增大。所以本文在應用隱馬爾可夫糾偏模型之前使用遺傳算法先對定位點進行優化，剔除偏差較大軌跡點，從而提升軌跡糾偏模型的準確率。具體如算法1所示：

算法1：隱馬爾可夫糾偏定位點優化算法

輸入：道路節點定位位置序列(P1、P2、……)

輸出：刪除偏移點后的優化權重W

步驟1 將行車軌跡中的第一個定位點作為權重點，設置權重點α值以及距離閾值D，進入步驟2。

步驟2 根據定位點和唯一權重點生成定位軌跡，進入步驟3。

步驟3 軌跡生成過程中，在出現定位偏差較大的定位點時，權重點根據公式W′=α*Pi+β*Pi-1進行更新(其中，α+β=1)，W′代表更新后的權重點。若此后的若干定位點沒有偏移，則判定這個定位點有效，加入軌跡中并且更新權重點，進入步驟4；否則，判定為偏移點并刪除，進入步驟5。

步驟4 輸出權重W′。

步驟5 輸出權重W。

下面結合圖3、圖4和圖5分別針對行車軌跡中存在的起始點偏移、中間點丟失和單個偏移點等常見情況進行說明。假設選取權重初始值w(0≤w≤1)， 下一個權重點更新為W2=P1*(1-w)+P2*w。

(1)起始點偏移

如圖3所示，假設實心黑色點為定位設備監測到的定位點，空心白色點為權重點。如果定位點P1、P2與P3之間的距離超過了設定的正常距離閾值，則可能P1與P2發生了偏移，這時需要為P3重新生成權重點W2；通過判斷后面連續的點之間是否有偏差來判定前述的點偏移情況，如果沒有異常則這些點的軌跡正常。如果判定P1和P2發生了偏移，則刪除P1和P2點。

圖3 行車軌跡中起點偏移

(2)中間因為某些原因失去定位點

如圖4所示，GPS定位設備本身、汽車供電設備電路故障等其它原因導致行車軌跡中間部分沒有定位信息，但是除去這部分后分開的兩部分行車軌跡都是正常的情況。

圖4 行車軌跡中丟失部分中間定位信息

圖5 行車軌跡中存在單個偏移點

(3)有單個偏移點

如圖5所示，首先算法檢測出定位軌跡中偏移點P4，則更新權重點為W2；接著檢測出偏移點P5，則刪除W2；然后在接下來的軌跡如果沒有偏移點，則更新權重點為W1，并且判定P4點為單個偏移點進行刪除。

4 實驗與性能分析

本文的實驗平臺通過開發的Java程序調用百度地圖API獲取定位車輛的行車軌跡原始GPS定位數據。實驗過程中選擇了天津市國家電網天津市電力公司附近區域的路段，進行了20次的行車軌跡記錄實驗。在實驗數據預處理階段，將路段根據行車道路分段進行數據預處理，分段刪除偏移點。經過對每段收集原始經緯度信息與提出的基于HMM的行車軌跡糾偏優化模型在準確度方面進行了對比，具體實驗相關參數配置和實驗結果見下面的分析。

4.1 實驗參數設置

具體的實驗參數見表1。在實驗中設定初始權值w為0.8，w值越大表示更新權重點越接近最新定位點，主要是考慮到實際行車過程中，權重點的選擇更應該與后續定位點之間的距離越近，更符合實際的行車軌跡特征。閾值距離D的選取主要是根據行車過程中的平均時速來給定。

表1 參數設置

4.2 實驗結果分析

圖6展示了軌跡數據與處理前與處理后定位準確度的對比，因為經過預處理后刪除了偏移點，行車軌跡的定位準確率得到了較好的提升。

圖6 軌跡數據預處理前后定位準確率對比

圖7 軌跡數據預處理后使用隱馬爾可夫糾偏模型前后定位準確度對比

由圖7可以看出，與沒有使用糾偏算法進行數據預處理的隱馬爾可夫模型相比，經過軌跡預處理之后使用隱馬爾可夫模型的軌跡糾偏方法在不同的路段其準確率均率均達到90%及以上，實驗結果表明本文方法的可行性和魯棒性。

5 結束語

本文研究提出了一種行車軌跡糾偏優化方法，該方法結合電子地圖并采用隱馬爾可夫模型和Viterbi算法對預處理過后的行車軌跡進行糾偏，建立了軌跡糾偏模型，通過使用遺傳算法先對原始定位點進行優化，以剔除偏差較大的異常行車數據。實驗結果表明本文提出的基于HMM的行車軌跡糾偏優化方法能夠提高電動汽車的行車軌跡準確性，并提升了其軌跡數據的應用價值。該方法可以為電動汽車的充電樁位置選址提供科學的數據依據，并能夠給自動駕駛提供精確的定位信息并提高自動駕駛行車路徑的采集信息準確度。由于當前算法僅在單機環境中進行算法和性能測試，未來考慮構建云平臺環境下的糾偏優化算法應用系統。