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

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

0 引 言

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

1 相關(guān)理論

隱馬爾可夫模型是一種關(guān)于時間序列的概率模型，是經(jīng)典的預(yù)測模型。其中的馬爾可夫鏈概念是指在給定已知信息和狀態(tài)的情況下，只使用當(dāng)前信息去預(yù)測未知的信息，已知的信息稱為可見狀態(tài)鏈，未知的狀態(tài)稱為隱馬爾可夫鏈。其應(yīng)用在預(yù)測方面，僅使用當(dāng)前已知的狀態(tài)去預(yù)測未來的未知狀態(tài)，隱馬爾可夫模型的具體定義請參見文獻(xiàn)[10]，此處簡述本文用到的部分相關(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無關(guān)，這種假設(shè)性前提則是一階馬爾可夫鏈；如果未來狀態(tài)只與前兩個狀態(tài)有關(guān)，那么稱為二階馬爾可夫鏈；……，以此類推。

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

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

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

(2)

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

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

(3)

設(shè)狀態(tài)數(shù)為N，觀測數(shù)為M，隱馬爾可夫模型(λ)通常用λ=(A,B,π) 表示。其中，A是狀態(tài)轉(zhuǎn)移概率矩陣，B是觀測概率矩陣，π是初始狀態(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)可見狀態(tài)鏈：從待定位車輛的定位感知設(shè)備(例如GPS定位終端、手機(jī)位置傳感器等)中獲取電動汽車所在位置的經(jīng)緯度。

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

圖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ù)測與糾偏的真實(shí)行車軌跡定位序列。

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

(7)

圖2 車輛軌跡觀測概率

(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)。

在時間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)

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

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

(11)

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

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

由于HMM模型存在如下兩種假設(shè)：①齊次馬爾可夫假設(shè)；②觀測獨(dú)立性假設(shè)。齊次馬爾可夫指的是隱馬爾可夫鏈任意時刻的狀態(tài)只與它前一時刻的狀態(tài)有關(guān)；觀測獨(dú)立性指的是任意時刻的監(jiān)測只依賴于該隱馬爾可夫鏈的狀態(tài)。在所構(gòu)建的軌跡糾偏模型中，由于GPS信號、設(shè)備故障或網(wǎng)絡(luò)信號等原因?qū)е碌挠^測到的定位位置出現(xiàn)偏差，這會導(dǎo)致采用傳統(tǒng)的基于HMM的行車軌跡糾偏方法的偏差相應(yīng)增大。所以本文在應(yīng)用隱馬爾可夫糾偏模型之前使用遺傳算法先對定位點(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 將行車軌跡中的第一個定位點(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 軌跡生成過程中，在出現(xiàn)定位偏差較大的定位點(diǎn)時，權(quán)重點(diǎn)根據(jù)公式W′=α*Pi+β*Pi-1進(jìn)行更新(其中，α+β=1)，W′代表更新后的權(quán)重點(diǎn)。若此后的若干定位點(diǎn)沒有偏移，則判定這個定位點(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分別針對行車軌跡中存在的起始點(diǎn)偏移、中間點(diǎn)丟失和單個偏移點(diǎn)等常見情況進(jìn)行說明。假設(shè)選取權(quán)重初始值w(0≤w≤1)， 下一個權(quán)重點(diǎn)更新為W2=P1*(1-w)+P2*w。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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