崔俊杰,張衛(wèi)正

(1. 鄭州輕工業(yè)大學(xué),河南 鄭州 450002;2. 鄭州輕工業(yè)大學(xué)計算機(jī)與通信工程學(xué)院,河南 鄭州 450002)

1 引言

當(dāng)前國民經(jīng)濟(jì)快速增長,私家車數(shù)量與日俱增,導(dǎo)致城市交通情況逐漸惡劣,交通事故率呈遞增狀態(tài)。為了緩解道路擁堵狀況,規(guī)劃出眾多環(huán)形立交橋起到一定的分支車流作用,但環(huán)形路線沒有臨時更改路線的調(diào)整空間。因此在車輛駕駛過程中,如何幫助用戶挑選出最優(yōu)路線,從根本上提高行駛效率已成為當(dāng)前該研究領(lǐng)域的主要課題之一。

制造商在生產(chǎn)汽車時,每輛車內(nèi)都安裝了智能導(dǎo)航設(shè)備,導(dǎo)航會根據(jù)交互指令,提供給駕駛?cè)藛T從出發(fā)點(diǎn)到目的地的行駛路線。一般情況下導(dǎo)航系統(tǒng)可被劃分成主機(jī)和顯示終端兩個部分,運(yùn)行導(dǎo)航程序時,內(nèi)置衛(wèi)星導(dǎo)航天線根據(jù)傳輸?shù)男l(wèi)星數(shù)據(jù),即可給出該車輛的詳細(xì)位置,隨后導(dǎo)航主機(jī)將位置數(shù)據(jù)放置到地圖數(shù)據(jù)中進(jìn)行匹配,根據(jù)人機(jī)交互指令將車輛當(dāng)前信息顯示在終端,便于后續(xù)導(dǎo)航。車輛導(dǎo)航的路徑規(guī)劃問題就是在導(dǎo)航地圖上找到從起點(diǎn)到終點(diǎn)的最佳路徑。在實(shí)際應(yīng)用中,當(dāng)交通路況發(fā)生變化時,最佳路徑搜索也應(yīng)該發(fā)生變化。駕駛?cè)藛T不僅可以利用車輛導(dǎo)航技術(shù)獲得最終目的地位置,還可實(shí)時了解最優(yōu)路線的路況信息。

為此,本文提出車輛駕駛環(huán)形軌跡人機(jī)交互導(dǎo)航仿真模型研究,首先采用D-S證據(jù)理論(D-S Evidence Theory)構(gòu)建一個非空集合識別框,判定當(dāng)前車輛的基本行駛方向,通過地圖匹配算法確定當(dāng)前車輛位置信息;其次利用Dijkstra(迪克斯特拉算法)計算最短距離路徑,對導(dǎo)航模型中的路線進(jìn)行規(guī)劃,最后利用無跡卡爾曼濾波(UKF)對數(shù)據(jù)信息進(jìn)行融合處理,完成最終導(dǎo)航。

2 駕駛車輛定位

行駛環(huán)形軌跡是一個連續(xù)過弧的路程,所以必須到達(dá)目前節(jié)點(diǎn)才能到下一個路段,因此針對環(huán)形人機(jī)交互導(dǎo)航模型來說,提取匹配路線時,需要結(jié)合歷史數(shù)據(jù),從根本上提升匹配精度,減少模型匹配計算量。本文采用D-S證據(jù)理論構(gòu)建一個非空集合識別框,便有

U={A1,A2,…,An}

(1)

式中,Ai(1≤i≤n)代表當(dāng)前車輛在i號路線上行駛。集合中所有元素之間都相互排斥,根據(jù)證據(jù)理論判定當(dāng)前車輛行駛方向[2,3],并將其作為原始證據(jù)。考慮到GPS定位可能存在的誤差,便將詳細(xì)的位置信息描述為

di=[l1(l2+l3+l4+l5)]/5

(2)

式中,di表示置信橢圓在第i條路線上的位置信息,l1代表橢圓中心點(diǎn)在該路線上的實(shí)際投影距離,而l2、l3、l4、l5則分別表示橢圓軸的端點(diǎn),在第i條路線上的投影距離,當(dāng)距離取值為0時,可得知li取其中最小值。

假設(shè)用m1描述位置信息證據(jù)在U上的mass函數(shù),可得出

(3)

(4)

c1,i與m1、m2一樣,為mass函數(shù)中特指向量,μ表示證據(jù)距離特征。

將m1和m2融合成為一個mass函數(shù)m得出

(5)

(6)

3 車輛駕駛環(huán)形軌跡路徑規(guī)劃

在導(dǎo)航中輸入最終目的地,交互指令會立刻給出到達(dá)該地的多條路線,有的路線是避開紅綠燈,有的路線是避開高峰堵車路段,而車輛路徑規(guī)劃會在最大程度上提高車輛的行駛效率,選擇最優(yōu)路線[4-7]。

本文利用Dijkstra算法對導(dǎo)航模型中的路線進(jìn)行規(guī)劃,計算步驟如下:

假設(shè)有帶權(quán)有向圖為G=(B,E),其中B表示包括n個節(jié)點(diǎn)的數(shù)據(jù)集合,E代表存有m條弧的集合,(y,b)是E集合中從y到b的弧線,W(y,b)的弧(y,b)的正權(quán)值,那么將節(jié)點(diǎn)劃分為兩組,第一組是已經(jīng)確定了是最短距離的節(jié)點(diǎn)集合S,原始狀態(tài)為集合中僅有一個起始源點(diǎn)b0,第二組是不確定是不是最短距離的集合(B-S),計算過程中每算出一個最短距離路徑b0,就將bk轉(zhuǎn)至S集合中,直到所有節(jié)點(diǎn)都是最短距離為止。

將di(1≤i≤n)作為目前所找到的從源點(diǎn)b0到其它節(jié)點(diǎn)bi的最短路徑長度,如果從b0到bi之間有環(huán)形路徑,那么di為弧(b0,bi)的權(quán)值,反之沒有則令di為∞。

假設(shè)第一條最短路徑為(b0,bj),那么j則滿足

dj=min{di|bi∈B}

(7)

上述計算得知,下一條最短路徑終點(diǎn)即為(b0,bk),或是(b0,bj,bk)。

根據(jù)上式計算結(jié)果可知,假設(shè)S是已經(jīng)計算出的最短距離集合,那么下一條路經(jīng)的節(jié)點(diǎn)則是S集合中的節(jié)點(diǎn)之一,長度計算式便有

dj=min{di|bi∈B-S}

(8)

經(jīng)過多次最短路徑計算后,終點(diǎn)bj最終也轉(zhuǎn)至S集合中,然后對所有的節(jié)點(diǎn)進(jìn)行bi∈B-S計算,更新di有

di=min{di,dj+W(bj,bi)}

(9)

根據(jù)上式可計算出對應(yīng)集合中源點(diǎn)b0到所有節(jié)點(diǎn)的最短距離,如圖1所示,其中圖1(a)為帶權(quán)有向圖,(b)表示集合中源點(diǎn)b0到其它點(diǎn)的距離顯示圖。

圖1 最短距離路徑樹

其中詳細(xì)的算法描述如下:

步驟一:將集合中節(jié)點(diǎn)劃分為三個部分,表示為d(b)、k(b)、p(b),已知d(b)是集合S中所有節(jié)點(diǎn)的最短距離,k(b)便表示為其中任意變量(布爾型),用來表示節(jié)點(diǎn)b的最短路徑是否求解出,p(b)是b的后繼節(jié)點(diǎn)指針。將三個信息量初始化計算便有

(10)

步驟二:掃描k(b)=false的所有節(jié)點(diǎn),從集合中挑選出一個有最小路徑長度的節(jié)點(diǎn)b,得出:

d(b)=min{d(bi)|k(bi)=false,bi∈B}

(11)

式中,k(b)=true。

步驟三:對k(w)=false且鄰接于節(jié)點(diǎn)b的節(jié)點(diǎn)w進(jìn)行監(jiān)測,如果滿足d(w)>d(b)+W(b,w)條件,可描述為

d(w)=d(b)+W(b,w)

(12)

步驟四:反復(fù)計算步驟二、三,直到得出k(E)=true;

步驟五:由E開始遍歷后繼節(jié)點(diǎn)指針p直至源點(diǎn)S,即獲得S到E的最短距離路徑,便有

PSE={b0=S,b1,…,bk=E}

(13)

其中,bi=p(bi+1),i=0,1,…,k-1。

4 人機(jī)交互導(dǎo)航仿真模型構(gòu)建

利用無跡卡爾曼濾波(UKF)對最優(yōu)路徑信息進(jìn)行融合處理,完成最終導(dǎo)航。計算車輛的狀態(tài)和對應(yīng)誤差協(xié)方差矩陣初始值[8]

(14)

(15)

(16)

(17)

模型中的所有數(shù)據(jù)節(jié)點(diǎn)都具有周期性[9],每個周期含有Sigma點(diǎn)計算、狀態(tài)更新、觀測更新的三個主要流程,計算時根據(jù)上一周期所得的車輛軌跡、狀態(tài)等信息,做對應(yīng)的模型估計,將所有信息進(jìn)行融合,得出新的估計取值和導(dǎo)航模型的誤差協(xié)方差矩陣[10-13]

(18)

(19)

(20)

5 仿真研究

為驗(yàn)證本文算法是否能在環(huán)形駕駛中快速安全完成導(dǎo)航,首先對環(huán)形軌跡安全車速進(jìn)行測試,以確保車輛在環(huán)形道路中能夠安全行駛。實(shí)驗(yàn)中位移單位為米,單位時間為秒,速度單位為m/s,加速度單位為m/s2,環(huán)形弧度用(red)表示,其中觀測噪聲協(xié)方差取值為10-3I,數(shù)據(jù)采集周期T以及縮放因子k取值分別為0.02、0。本文仿真環(huán)境參照重慶某天的下午4點(diǎn)22分,從大龍山公園到玉祥門,此時交通路況處于下班高峰期,路況較為復(fù)雜且多變。車輛參數(shù)如表1所示

表1 車輛仿真參數(shù)

5.1 環(huán)形軌跡安全車速測試

車輛在環(huán)形軌跡中,當(dāng)車速處于導(dǎo)航推薦的最高車速以內(nèi)時,車輛質(zhì)心側(cè)偏的角度就為0,此時車輛轉(zhuǎn)向角度為完全理想取值,如圖2所示,車輛正常速度行駛會出現(xiàn)在理想軌跡或內(nèi)側(cè)滑軌跡,內(nèi)側(cè)滑軌跡照比外側(cè)滑軌跡來說是相對安全的,因此內(nèi)側(cè)滑軌跡可以稱之為期望取值,反之如果車速過快導(dǎo)致外側(cè)滑,便可能出現(xiàn)側(cè)翻等危險,為此本文得出了環(huán)形軌跡的安全車速公式

圖2 環(huán)形軌跡轉(zhuǎn)向側(cè)滑

(21)

式中ωr0代表理想的環(huán)形角速度,c0則被描述為車輛在理想軌跡運(yùn)動下的轉(zhuǎn)向行駛速度,R代表質(zhì)心偏向角。

結(jié)合實(shí)際環(huán)境信息,根據(jù)式(21)計算出車輛過彎的安全期望車速以及轉(zhuǎn)向角,以期望速度作為衡量車輛出現(xiàn)側(cè)滑閾值的標(biāo)準(zhǔn),當(dāng)車輛在環(huán)形軌跡中行駛時速度峰值高于期望轉(zhuǎn)向角時,即判定為不安全車速[15],及時通過可視化界面提醒駕駛?cè)藛T。

5.2 人機(jī)交互導(dǎo)航效果分析

圖3為導(dǎo)航結(jié)果。該車輛的軌跡數(shù)據(jù)包括了高架橋和將近一半道路網(wǎng)絡(luò),并且網(wǎng)絡(luò)中含有多個環(huán)形路線。

圖3 最佳導(dǎo)航軌跡示意圖

從圖3中標(biāo)記路線為大龍山公園到玉祥門的最佳路線,可知方法能根據(jù)實(shí)時路況給出相應(yīng)的導(dǎo)航路線,在路況輕松的時間段需13分鐘路程,全程3.5公里、有3個紅路燈,路經(jīng)柏樹堡立交、松石大道等主干路,但因松石大道下班高峰期時,路況較為緊張會出現(xiàn)相應(yīng)的交通堵塞,并不能順暢通過,所以在D-S證據(jù)理論基礎(chǔ)上計算軌跡序列的備選路線集合,進(jìn)行路線分段。

圖4中標(biāo)注出了軌跡序列的備選路段集,通過交互指令在終端顯示,備選路線較為輕松路況需要14分鐘路程,全程3.9公里、途經(jīng)9個紅綠燈,路經(jīng)龍山立交、余松路。備選路線僅比最佳路線多0.1公里,可以避免松石大道交通堵塞,但多了6個紅綠燈,車輛駕駛中需要用戶自己抉擇。說明本文導(dǎo)航模型可完全避免導(dǎo)航失誤的同時,具有較高的智能實(shí)用性。

圖4 車輛導(dǎo)航模型備選軌跡

6 結(jié)論

為緩解擁擠的城市交通道路網(wǎng)行車壓力,本文提出車輛駕駛環(huán)形軌跡人機(jī)交互導(dǎo)航仿真模型研究。首先利用地圖匹配算法,確定當(dāng)前車輛位置信息,其次根據(jù)不同長度的路徑節(jié)點(diǎn),構(gòu)建Dijkstra最短距離路徑,規(guī)劃車輛駕駛路線,最后通過無跡卡爾曼濾波對數(shù)據(jù)信息進(jìn)行融合處理,完成最終導(dǎo)航。