改進(jìn)的D-S證據(jù)推理地圖匹配算法

李昊天，張 宇

(東北電力大學(xué)電氣工程學(xué)院，吉林 吉林 132012)

中國(guó)正經(jīng)歷著空前未有的城市化進(jìn)程，高速的發(fā)展將會(huì)塑造和定義與之匹配的基礎(chǔ)設(shè)施，未來(lái)會(huì)出現(xiàn)更多戰(zhàn)略位置上的交通轉(zhuǎn)換樞紐，也會(huì)出現(xiàn)更多類似的超復(fù)雜路網(wǎng).目前，很多地圖匹配算法都可以較好的解決非復(fù)雜道路的匹配問(wèn)題，特別是近幾年出現(xiàn)的一些基于隱馬爾可夫模型的地圖匹配算法，其匹配準(zhǔn)確率基本在90%以上，在某些特定條件下甚至可以接近100%，但在復(fù)雜的道路拓?fù)浣Y(jié)構(gòu)下準(zhǔn)確率就會(huì)大幅度降低，特別是錯(cuò)綜復(fù)雜的道路交叉口區(qū)域[1-3].

對(duì)于該問(wèn)題，在這種復(fù)雜的道路拓?fù)浣Y(jié)構(gòu)下，使用一些復(fù)合的方法進(jìn)行匹配往往能取得較好的準(zhǔn)確率.模糊神經(jīng)網(wǎng)絡(luò)的方法主要通過(guò)對(duì)隸屬函數(shù)的描述以及界定候選路段的誤差模型，該方法的魯棒性極佳，但計(jì)算過(guò)于繁瑣且缺乏理論根據(jù)，實(shí)用性不好[4-5].貝葉斯多假設(shè)技術(shù)根據(jù)道路緩沖區(qū)域內(nèi)的候選路段生成偽量測(cè)值，并推導(dǎo)出一組假設(shè)值，該方法一樣可以得到很高的準(zhǔn)確率，但由于缺少初始匹配方法，在一定程度上會(huì)影響后續(xù)的匹配結(jié)果[6-7].擴(kuò)展卡爾曼濾波法是基于卡爾曼濾波中的一種假設(shè)，同時(shí)考慮系統(tǒng)誤差特征，分析經(jīng)濾波后的系統(tǒng)誤差特征能否滿足該假設(shè)的分布來(lái)執(zhí)行地圖匹配，該方法在道路交叉口的穩(wěn)定性較好，但是沒(méi)有綜合考慮道路拓?fù)浣Y(jié)構(gòu)和人為因素，因此效果不是很理想[8-9].基于D-S證據(jù)理論的算法，首先利用位置與方向信息分別構(gòu)造基本概率分配函數(shù)，再將二者融合為一個(gè)新函數(shù)，然后比較該函數(shù)值的大小，最后選取函數(shù)值最大的候選路段作為最佳匹配路段，該方法只考慮兩種信息，準(zhǔn)確率不是很高[10-11].為了獲得更高的匹配精度，適應(yīng)復(fù)雜的道路交叉口，對(duì)原有D-S證據(jù)推理算法進(jìn)行改進(jìn)，并引入一個(gè)新的證據(jù)——?dú)v史匹配程度，綜合考慮道路拓?fù)浣Y(jié)構(gòu)和車輛信息進(jìn)行地圖匹配.當(dāng)車輛處于十字形交叉路口時(shí)，接下來(lái)車輛可能會(huì)出現(xiàn)直行或者轉(zhuǎn)彎兩種行為，如果車輛繼續(xù)保持直行，那么歷史匹配程度證據(jù)所占的權(quán)重相對(duì)較大；如果車輛此時(shí)進(jìn)行左轉(zhuǎn)彎或者右轉(zhuǎn)彎，那么歷史匹配程度所占的權(quán)重相對(duì)較小.當(dāng)車輛進(jìn)入T字形交叉路口時(shí)，分為兩種情況進(jìn)行分析，第一種情況是車輛接下來(lái)可能出現(xiàn)直行或轉(zhuǎn)彎行為，可以根據(jù)路面實(shí)際禁行情況判斷是否引入歷史匹配程度作為新的證據(jù)進(jìn)一步提高改進(jìn)算法的匹配準(zhǔn)確率；第二種情況是車輛只能轉(zhuǎn)彎，此時(shí)不用考慮歷史匹配程度，若該路口禁止左轉(zhuǎn)彎，則匹配結(jié)果不會(huì)出現(xiàn)錯(cuò)誤.通過(guò)仿真測(cè)試與其他三種算法進(jìn)行對(duì)比，改進(jìn)算法的單點(diǎn)匹配耗時(shí)更少，匹配準(zhǔn)確率更高，可以滿足道路交叉口的匹配需求.

1 改進(jìn)方法

1.1 基本概率分配函數(shù)

根據(jù)D-S證據(jù)推理，用樣本空間U來(lái)表示所有候選道路的集合：U={A1，A2，…，An}，設(shè)i=1，2，…，n，Ai代表車輛在第i條候選路段上行進(jìn).設(shè)j=1，2，3，代表第j個(gè)證據(jù)，用初始定位點(diǎn)P的距離和角度作為D-S證據(jù)推理中的兩個(gè)基本證據(jù)，令其函數(shù)為ej，i.當(dāng)j=1時(shí)，距離證據(jù)函數(shù)

(1)

公式中：di為定位點(diǎn)P到該點(diǎn)在第i條路段上投影點(diǎn)的直線距離，該值越小證據(jù)越重要.當(dāng)j=2時(shí)，角度證據(jù)函數(shù)

(2)

公式中：βi為車輛此時(shí)行進(jìn)方向與候選路段方向之間的角度，該值越小證據(jù)越重要.根據(jù)上述證據(jù)公式，構(gòu)建基本概率分配函數(shù)，表示證據(jù)j對(duì)命題“道路Ai是候選路段”的重要程度，如公式(3)所示.

(3)

圖1 算法流程圖

1.2 分布式證據(jù)融合

改進(jìn)算法先將距離證據(jù)與角度證據(jù)進(jìn)行第一次融合，根據(jù)道路拓?fù)浣Y(jié)構(gòu)判斷車輛接下來(lái)可能出現(xiàn)的行為，決定是否引入歷史匹配程度再進(jìn)行融合.該融合方式可以減弱人為證據(jù)的重要程度，增強(qiáng)客觀證據(jù)的重要程度，而且當(dāng)證據(jù)數(shù)量較少時(shí)計(jì)算過(guò)程相對(duì)簡(jiǎn)單.在地圖匹配算法的現(xiàn)實(shí)應(yīng)用中，不規(guī)則的真實(shí)路段在數(shù)字地圖中需要借助直線段來(lái)模擬，而且每個(gè)司機(jī)的駕駛習(xí)慣不盡相同，導(dǎo)致其經(jīng)過(guò)同一道路交叉口時(shí)的行車軌跡也有所差異，因此角度信息證據(jù)受人為因素的影響較大，而歷史匹配程度和距離作為證據(jù)則不易受人為因素影響，所以改進(jìn)算法中采用該模型，算法流程圖如圖1所示.

根據(jù)D-S證據(jù)合成公式，先將之前得到的距離證據(jù)和角度證據(jù)在樣本空間U上的基本概率分配函數(shù)m1(Ai)和m2(Ai)融合為一個(gè)新的函數(shù)m(Ai)，表示命題“道路Ai是候選路段”的重要程度為

(4)

公式中：K為沖突因子，表明證據(jù)之間互相沖突的程度，K值越小，說(shuō)明證據(jù)之間互相沖突的程度越小.

由于D-S證據(jù)推理中的證據(jù)過(guò)少會(huì)致使匹配結(jié)果不理想，并且容易導(dǎo)致錯(cuò)誤情況的出現(xiàn)，所以改進(jìn)算法在這里引入了第三個(gè)證據(jù)——?dú)v史匹配程度.首先定義歷史匹配程度參數(shù)，該值為前一個(gè)定位點(diǎn)經(jīng)過(guò)第一次融合后的基本概率分配函數(shù)值mp，當(dāng)j=3時(shí)，

(5)

為歷史匹配程度證據(jù)函數(shù).

將e3，i帶入到公式(3)中可以算出歷史匹配程度的基本概率分配函數(shù)m3(Ai).對(duì)各個(gè)候選路段而言，歷史匹配程度證據(jù)的區(qū)別在于上一個(gè)定位點(diǎn)和當(dāng)前定位點(diǎn)是否在同一條候選路段上，如果是，那么mp為前一個(gè)定位點(diǎn)經(jīng)過(guò)一次融合后的函數(shù)值，否則mp=0.

運(yùn)用該模型繼續(xù)進(jìn)行融合，將公式(4)中距離和角度融合得到的函數(shù)m(Ai)作為一個(gè)新的函數(shù)，與歷史匹配程度證據(jù)的基本概率分配函數(shù)m3(Ai)加以融合，得到函數(shù)m′(Ai)為

(6)

若K=1，則認(rèn)為相互融合的證據(jù)是完全不兼容的，此時(shí)不能利用上述公式進(jìn)行融合.對(duì)于完全沖突的證據(jù)而言，重要度高的證據(jù)明顯更加具有優(yōu)勢(shì)，但是沖突產(chǎn)生的起因尚不清楚，也不應(yīng)該全盤否認(rèn)重要度低的證據(jù).改進(jìn)算法對(duì)沖突因子K進(jìn)行賦值處理，并適當(dāng)降低K值，取值時(shí)考慮車輛在路網(wǎng)中的實(shí)際位置.由于改進(jìn)算法主要討論車輛在道路交叉口區(qū)域內(nèi)的匹配情況，根據(jù)歷史匹配程度，若車輛出現(xiàn)轉(zhuǎn)彎趨勢(shì)，令沖突因子K=0.9，反之令沖突因子K=0.8，最后通過(guò)計(jì)算得出函數(shù)值最大的候選路段即為車輛當(dāng)前行進(jìn)的路段.

2 仿真測(cè)試

首先對(duì)算法的單點(diǎn)匹配時(shí)間進(jìn)行仿真分析，分別從不同的道路交叉口共選取60個(gè)定位點(diǎn)數(shù)據(jù)測(cè)試算法，四種算法的單點(diǎn)匹配時(shí)間對(duì)比如圖2所示.隨著定位點(diǎn)個(gè)數(shù)的逐漸增加，算法的單點(diǎn)匹配時(shí)間幾乎都在一定范圍內(nèi)不規(guī)則波動(dòng)，與其他三種算法比較可知，改進(jìn)算法消耗的時(shí)間大致在1 ms～2 ms之間波動(dòng)，可以滿足地圖匹配算法對(duì)于時(shí)效性的需求.

接下來(lái)驗(yàn)證改進(jìn)的D-S證據(jù)推理算法在高頻采樣下的匹配效果，對(duì)不同采樣時(shí)間間隔下的算法匹配準(zhǔn)確率進(jìn)行仿真，其變動(dòng)規(guī)律如圖3所示.對(duì)于1 s間隔的采樣數(shù)據(jù)，算法具有極佳的匹配準(zhǔn)確率，隨著時(shí)間間隔的不斷增加，算法的匹配準(zhǔn)確率呈下滑走向，最后漸漸趨于平穩(wěn).

圖2 單點(diǎn)匹配時(shí)間比較圖3 匹配準(zhǔn)確率與采樣間隔的關(guān)系曲線

為了進(jìn)一步驗(yàn)證該算法的匹配精度，分別與上述三種地圖匹配算法的精度進(jìn)行對(duì)比，并統(tǒng)計(jì)各算法的最低準(zhǔn)確率和平均準(zhǔn)確率，如表1所示.通過(guò)分析未能正確匹配的定位點(diǎn)特征，發(fā)現(xiàn)造成錯(cuò)誤匹配的原因主要有兩個(gè)方面：第一是車輛存在繞行的情況，即車輛在行駛過(guò)程中兩次或多次經(jīng)過(guò)了同一個(gè)道路交叉口，導(dǎo)致算法忽略了該部分的候選路段，使得經(jīng)過(guò)融合后的函數(shù)值更小；第二可能是真實(shí)路網(wǎng)中存在某些路段，但是在電子地圖上這些路段沒(méi)有正確顯示出來(lái)，在這種情況下，定位點(diǎn)只能強(qiáng)行匹配到更符合的候選路段上，以致造成了錯(cuò)誤情況的出現(xiàn).

表1 匹配準(zhǔn)確率對(duì)比

圖4 算法模擬仿真圖

為了驗(yàn)證改進(jìn)算法的性能，選取吉林市財(cái)富廣場(chǎng)及其周邊區(qū)域的復(fù)雜道路作為模擬測(cè)試路線，這段路線包含十字形和T字形兩種道路交叉口，同時(shí)設(shè)定高頻采樣的時(shí)間間隔為1 s，其定位點(diǎn)匹配仿真模擬的結(jié)果如圖4所示，車輛的初始位置位于左下角，經(jīng)緯度坐標(biāo)為(126.566 4，43.845 5).由于測(cè)試道路出現(xiàn)重疊現(xiàn)象，為了便于區(qū)分，使用黑色空心圓和藍(lán)色空心圓表示初始定位點(diǎn)，紅色空心圓和綠色空心圓表示匹配位置點(diǎn)，由圖4可知：改進(jìn)算法能夠較為精準(zhǔn)的確定出車輛當(dāng)前所在的實(shí)際位置.

初始定位點(diǎn)序列、匹配點(diǎn)序列以及實(shí)際道路選取點(diǎn)序列的經(jīng)緯度比較,如表2所示.從表2數(shù)據(jù)可知，匹配點(diǎn)的經(jīng)緯度和實(shí)際道路的經(jīng)緯度大致相同，只有略微差距，同理可以得出改進(jìn)算法的性能可以滿足道路交叉口的匹配需求.

表2 經(jīng)緯度比較

(續(xù))表2

車輛行駛過(guò)程中經(jīng)過(guò)的道路交叉口示意圖，如圖5所示.表3～表8分別是選取車輛經(jīng)過(guò)的六個(gè)道路交叉口的基本概率分配函數(shù)m(Ai)和m′(Ai).通過(guò)分析表中數(shù)據(jù)可以看出，兩個(gè)證據(jù)經(jīng)過(guò)一次融合后的函數(shù)值有時(shí)相差甚微，不能直接判斷出車輛在哪條候選路段上行駛，此時(shí)通過(guò)引入新的證據(jù)進(jìn)行二次融合比較函數(shù)值m′((Ai)的大小，可以確定當(dāng)前時(shí)刻車輛所在的候選路段.綜上所述，算法經(jīng)過(guò)兩次融合后的匹配準(zhǔn)確率有所提升，可以減少錯(cuò)誤匹配情況的出現(xiàn)，提高算法性能，滿足地圖匹配的實(shí)際需求.

圖5 道路交叉口示意圖

基本概率分配函數(shù)候選路段A1候選路段A2候選路段A3候選路段A4m(Ai)0.42620.09130.41360.0689m'(Ai)0.21030.15940.57750.0528

表4 道路交叉口2融合后的函數(shù)結(jié)果

表5 道路交叉口3融合后的函數(shù)結(jié)果

表6 道路交叉口4融合后的函數(shù)結(jié)果

表7 道路交叉口5融合后的函數(shù)結(jié)果

表8 道路交叉口6融合后的函數(shù)結(jié)果

3 結(jié) 語(yǔ)

為了適應(yīng)錯(cuò)綜相連的道路交叉口，提高算法整體運(yùn)行效率，改進(jìn)算法對(duì)基本證據(jù)函數(shù)進(jìn)行合理簡(jiǎn)化，構(gòu)建基本概率分配函數(shù)，在距離信息與角度信息兩個(gè)證據(jù)的基礎(chǔ)之上引入第三個(gè)證據(jù)——?dú)v史匹配程度證據(jù).通過(guò)仿真實(shí)驗(yàn)分析，改進(jìn)算法的單點(diǎn)匹配時(shí)間和匹配準(zhǔn)確率均有所增益，可以滿足復(fù)雜的道路交叉口.

改進(jìn)算法主要適用于道路交叉口，如果車輛長(zhǎng)時(shí)間沒(méi)有經(jīng)過(guò)道路交叉口，可能致使匹配出現(xiàn)錯(cuò)誤，難以修正車輛的位置.在后續(xù)的研究中，可以綜合考慮城市交通規(guī)則等限制因素，充分利用道路信息來(lái)進(jìn)行匹配，以擺脫對(duì)道路交叉口的依賴，并進(jìn)一步優(yōu)化算法整體的性能.