基于HMM的電動(dòng)汽車行車軌跡糾偏優(yōu)化

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

(1.國(guó)網(wǎng)天津市電力公司 電力科學(xué)研究院，天津 300021；2.國(guó)網(wǎng)天津市電力公司 營(yíng)銷部，天津 300010)

0 引 言

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

1 相關(guān)理論

隱馬爾可夫模型是一種關(guān)于時(shí)間序列的概率模型，是經(jīng)典的預(yù)測(cè)模型。其中的馬爾可夫鏈概念是指在給定已知信息和狀態(tài)的情況下，只使用當(dāng)前信息去預(yù)測(cè)未知的信息，已知的信息稱為可見(jiàn)狀態(tài)鏈，未知的狀態(tài)稱為隱馬爾可夫鏈。其應(yīng)用在預(yù)測(cè)方面，僅使用當(dāng)前已知的狀態(tài)去預(yù)測(cè)未來(lái)的未知狀態(tài)，隱馬爾可夫模型的具體定義請(qǐng)參見(jiàn)文獻(xiàn)[10]，此處簡(jiǎn)述本文用到的部分相關(guān)概念及定義如下

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

(1)

式中：Xn代表當(dāng)前的狀態(tài)，Xn+1代表在已知當(dāng)前狀態(tài)的情況下Xn+1的狀態(tài)。Xn+1和Xn有關(guān)，與X0,X1,X2,…,Xn-1無(wú)關(guān)，這種假設(shè)性前提則是一階馬爾可夫鏈；如果未來(lái)狀態(tài)只與前兩個(gè)狀態(tài)有關(guān)，那么稱為二階馬爾可夫鏈；……，以此類推。

隱馬爾可夫模型用能觀察到的馬爾可夫可見(jiàn)狀態(tài)鏈去預(yù)測(cè)隱馬爾可夫鏈。針對(duì)車輛軌跡的糾偏問(wèn)題，原理上屬于預(yù)測(cè)問(wèn)題，可用隱馬爾可夫模型，即在已知監(jiān)測(cè)位置信息的情況下來(lái)預(yù)測(cè)實(shí)際的行車軌跡位置信息，將偏離實(shí)際位置較大的定位數(shù)據(jù)進(jìn)行剔除。

假設(shè)K為所有可見(jiàn)狀態(tài)鏈的狀態(tài)集合，G是所有可觀測(cè)到的狀態(tài)集合

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

(2)

I為長(zhǎng)度是t的狀態(tài)序列，O是對(duì)應(yīng)觀測(cè)序列

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

(3)

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

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)可見(jiàn)狀態(tài)鏈：從待定位車輛的定位感知設(shè)備(例如GPS定位終端、手機(jī)位置傳感器等)中獲取電動(dòng)汽車所在位置的經(jīng)緯度。

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

圖1 行車軌跡模型中的相關(guān)序列

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

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

下面分別介紹該模型中的觀測(cè)概率、狀態(tài)轉(zhuǎn)移概率和初始狀態(tài)概率。

(7)

圖2 車輛軌跡觀測(cè)概率

(2)狀態(tài)轉(zhuǎn)移概率：與候選定位點(diǎn)之間的真實(shí)距離成正比，表示如下

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

(8)

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

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

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

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

(9)

由此可推導(dǎo)得出δ

δ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)

那么在時(shí)間t狀態(tài)i的所有路徑中概率最大的第t-1個(gè)結(jié)點(diǎn)為

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

(11)

在此模型中，通過(guò)計(jì)算與位置點(diǎn)的距離來(lái)決定隱藏狀態(tài)點(diǎn)，應(yīng)用Viterbi算法求解隱藏狀態(tài)點(diǎn)的觀測(cè)概率。

3 隱馬爾可夫糾偏定位點(diǎn)優(yōu)化算法

由于HMM模型存在如下兩種假設(shè)：①齊次馬爾可夫假設(shè)；②觀測(cè)獨(dú)立性假設(shè)。齊次馬爾可夫指的是隱馬爾可夫鏈任意時(shí)刻的狀態(tài)只與它前一時(shí)刻的狀態(tài)有關(guān)；觀測(cè)獨(dú)立性指的是任意時(shí)刻的監(jiān)測(cè)只依賴于該隱馬爾可夫鏈的狀態(tài)。在所構(gòu)建的軌跡糾偏模型中，由于GPS信號(hào)、設(shè)備故障或網(wǎng)絡(luò)信號(hào)等原因?qū)е碌挠^測(cè)到的定位位置出現(xiàn)偏差，這會(huì)導(dǎo)致采用傳統(tǒng)的基于HMM的行車軌跡糾偏方法的偏差相應(yīng)增大。所以本文在應(yīng)用隱馬爾可夫糾偏模型之前使用遺傳算法先對(duì)定位點(diǎn)進(jìn)行優(yōu)化，剔除偏差較大軌跡點(diǎn)，從而提升軌跡糾偏模型的準(zhǔn)確率。具體如算法1所示：

算法1：隱馬爾可夫糾偏定位點(diǎn)優(yōu)化算法

輸入：道路節(jié)點(diǎn)定位位置序列(P1、P2、……)

輸出：刪除偏移點(diǎn)后的優(yōu)化權(quán)重W

步驟1 將行車軌跡中的第一個(gè)定位點(diǎn)作為權(quán)重點(diǎn)，設(shè)置權(quán)重點(diǎn)α值以及距離閾值D，進(jìn)入步驟2。

步驟2 根據(jù)定位點(diǎn)和唯一權(quán)重點(diǎn)生成定位軌跡，進(jìn)入步驟3。

步驟3 軌跡生成過(guò)程中，在出現(xiàn)定位偏差較大的定位點(diǎn)時(shí)，權(quán)重點(diǎn)根據(jù)公式W′=α*Pi+β*Pi-1進(jìn)行更新(其中，α+β=1)，W′代表更新后的權(quán)重點(diǎn)。若此后的若干定位點(diǎn)沒(méi)有偏移，則判定這個(gè)定位點(diǎn)有效，加入軌跡中并且更新權(quán)重點(diǎn)，進(jìn)入步驟4；否則，判定為偏移點(diǎn)并刪除，進(jìn)入步驟5。

步驟4 輸出權(quán)重W′。

步驟5 輸出權(quán)重W。

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

(1)起始點(diǎn)偏移

如圖3所示，假設(shè)實(shí)心黑色點(diǎn)為定位設(shè)備監(jiān)測(cè)到的定位點(diǎn)，空心白色點(diǎn)為權(quán)重點(diǎn)。如果定位點(diǎn)P1、P2與P3之間的距離超過(guò)了設(shè)定的正常距離閾值，則可能P1與P2發(fā)生了偏移，這時(shí)需要為P3重新生成權(quán)重點(diǎn)W2；通過(guò)判斷后面連續(xù)的點(diǎn)之間是否有偏差來(lái)判定前述的點(diǎn)偏移情況，如果沒(méi)有異常則這些點(diǎn)的軌跡正常。如果判定P1和P2發(fā)生了偏移，則刪除P1和P2點(diǎn)。

圖3 行車軌跡中起點(diǎn)偏移

(2)中間因?yàn)槟承┰蚴ザㄎ稽c(diǎn)

如圖4所示，GPS定位設(shè)備本身、汽車供電設(shè)備電路故障等其它原因?qū)е滦熊囓壽E中間部分沒(méi)有定位信息，但是除去這部分后分開的兩部分行車軌跡都是正常的情況。

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

圖5 行車軌跡中存在單個(gè)偏移點(diǎn)

(3)有單個(gè)偏移點(diǎn)

如圖5所示，首先算法檢測(cè)出定位軌跡中偏移點(diǎn)P4，則更新權(quán)重點(diǎn)為W2；接著檢測(cè)出偏移點(diǎn)P5，則刪除W2；然后在接下來(lái)的軌跡如果沒(méi)有偏移點(diǎn)，則更新權(quán)重點(diǎn)為W1，并且判定P4點(diǎn)為單個(gè)偏移點(diǎn)進(jìn)行刪除。

4 實(shí)驗(yàn)與性能分析

本文的實(shí)驗(yàn)平臺(tái)通過(guò)開發(fā)的Java程序調(diào)用百度地圖API獲取定位車輛的行車軌跡原始GPS定位數(shù)據(jù)。實(shí)驗(yàn)過(guò)程中選擇了天津市國(guó)家電網(wǎng)天津市電力公司附近區(qū)域的路段，進(jìn)行了20次的行車軌跡記錄實(shí)驗(yàn)。在實(shí)驗(yàn)數(shù)據(jù)預(yù)處理階段，將路段根據(jù)行車道路分段進(jìn)行數(shù)據(jù)預(yù)處理，分段刪除偏移點(diǎn)。經(jīng)過(guò)對(duì)每段收集原始經(jīng)緯度信息與提出的基于HMM的行車軌跡糾偏優(yōu)化模型在準(zhǔn)確度方面進(jìn)行了對(duì)比，具體實(shí)驗(yàn)相關(guān)參數(shù)配置和實(shí)驗(yàn)結(jié)果見(jiàn)下面的分析。

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

具體的實(shí)驗(yàn)參數(shù)見(jiàn)表1。在實(shí)驗(yàn)中設(shè)定初始權(quán)值w為0.8，w值越大表示更新權(quán)重點(diǎn)越接近最新定位點(diǎn)，主要是考慮到實(shí)際行車過(guò)程中，權(quán)重點(diǎn)的選擇更應(yīng)該與后續(xù)定位點(diǎn)之間的距離越近，更符合實(shí)際的行車軌跡特征。閾值距離D的選取主要是根據(jù)行車過(guò)程中的平均時(shí)速來(lái)給定。

表1 參數(shù)設(shè)置

4.2 實(shí)驗(yàn)結(jié)果分析

圖6展示了軌跡數(shù)據(jù)與處理前與處理后定位準(zhǔn)確度的對(duì)比，因?yàn)榻?jīng)過(guò)預(yù)處理后刪除了偏移點(diǎn)，行車軌跡的定位準(zhǔn)確率得到了較好的提升。

圖6 軌跡數(shù)據(jù)預(yù)處理前后定位準(zhǔn)確率對(duì)比

圖7 軌跡數(shù)據(jù)預(yù)處理后使用隱馬爾可夫糾偏模型前后定位準(zhǔn)確度對(duì)比

由圖7可以看出，與沒(méi)有使用糾偏算法進(jìn)行數(shù)據(jù)預(yù)處理的隱馬爾可夫模型相比，經(jīng)過(guò)軌跡預(yù)處理之后使用隱馬爾可夫模型的軌跡糾偏方法在不同的路段其準(zhǔn)確率均率均達(dá)到90%及以上，實(shí)驗(yàn)結(jié)果表明本文方法的可行性和魯棒性。

5 結(jié)束語(yǔ)

本文研究提出了一種行車軌跡糾偏優(yōu)化方法，該方法結(jié)合電子地圖并采用隱馬爾可夫模型和Viterbi算法對(duì)預(yù)處理過(guò)后的行車軌跡進(jìn)行糾偏，建立了軌跡糾偏模型，通過(guò)使用遺傳算法先對(duì)原始定位點(diǎn)進(jìn)行優(yōu)化，以剔除偏差較大的異常行車數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明本文提出的基于HMM的行車軌跡糾偏優(yōu)化方法能夠提高電動(dòng)汽車的行車軌跡準(zhǔn)確性，并提升了其軌跡數(shù)據(jù)的應(yīng)用價(jià)值。該方法可以為電動(dòng)汽車的充電樁位置選址提供科學(xué)的數(shù)據(jù)依據(jù)，并能夠給自動(dòng)駕駛提供精確的定位信息并提高自動(dòng)駕駛行車路徑的采集信息準(zhǔn)確度。由于當(dāng)前算法僅在單機(jī)環(huán)境中進(jìn)行算法和性能測(cè)試，未來(lái)考慮構(gòu)建云平臺(tái)環(huán)境下的糾偏優(yōu)化算法應(yīng)用系統(tǒng)。