基于高精地圖的導(dǎo)航算法模型

1、北京測(cè)繪基于高精地圖的導(dǎo)航算法模型傳統(tǒng)的導(dǎo)航電子地圖因交通路網(wǎng)在微觀層面表現(xiàn)粒度不細(xì)， 在滿足先進(jìn)的汽車輔助駕駛系統(tǒng)（ADAS）,乃至無人駕駛汽 車需求方面常顯不足，為了增加駕駛輔助系統(tǒng)或者自動(dòng)駕駛的可 靠性，可以將靜態(tài)交通信息例如道路線、交通燈等信息提前采集 存儲(chǔ)在電子地圖中，同時(shí)根據(jù)城市周期性的變化更新電子地圖， 以便在行駛過程中通過地圖數(shù)據(jù)庫就能夠獲取周邊環(huán)境的詳盡信 息。汽車智能駕駛系統(tǒng)有兩大關(guān)鍵技術(shù)，車輛定位和車輛控制技 術(shù)。車輛定位和控制在很大程度上依賴于精確的導(dǎo)航電子地圖。 這就對(duì)地圖提生了新的要求，不僅需要分辨率高，還需要信息詳 細(xì)。本文提由的高精細(xì)地圖，主要是指分辨率達(dá)到亞米

2、級(jí)的道路 級(jí)地圖，而高精度導(dǎo)航地圖能否有效發(fā)揮其功能取決于路網(wǎng)數(shù)據(jù) 模型的準(zhǔn)確性。因此下文將會(huì)對(duì)道路級(jí)網(wǎng)絡(luò)模型以及路徑規(guī)劃引 導(dǎo)兩方面進(jìn)行詳細(xì)闡述，同時(shí)也會(huì)對(duì)其應(yīng)用進(jìn)行說明。一、道路交通網(wǎng)絡(luò)道路（Lane）作為車輛行駛過程中所占道路的最小單元, 以道路作為基本單元，顧及道路的屬性、拓?fù)湔Z義關(guān)系及與道路 的連接關(guān)系是本文研究的基本由發(fā)點(diǎn)。建立道路級(jí)交通網(wǎng)絡(luò)就是將物理上的實(shí)際道路網(wǎng)絡(luò)抽象為可 借助衛(wèi)星定位手段，進(jìn)行導(dǎo)航控制的道路級(jí)交通網(wǎng)絡(luò)，下面將從北京測(cè)繪數(shù)據(jù)規(guī)格設(shè)計(jì)以及模型路口處理兩個(gè)方面對(duì)道路交通網(wǎng)絡(luò)模型進(jìn) 行說明。（一）基礎(chǔ)數(shù)據(jù)規(guī)格定義道路功能劃分包括各流向道路數(shù)和各流向道路位置的劃分， 也

3、包括每條道路的寬度設(shè)計(jì)、分隔線性質(zhì)設(shè)計(jì)、允許的車種、行 駛的速度、限行的時(shí)間等交通規(guī)則的制定。因此在進(jìn)行規(guī)格設(shè)計(jì) 的時(shí)候需要考慮到與道路相關(guān)的所有屬性。.道路與道路連接關(guān)系道路級(jí)交通網(wǎng)絡(luò)是由道路中心線網(wǎng)絡(luò)和行道路路網(wǎng)絡(luò)組成， 每條道路直接隸屬于一條行道路路，多條平行的道路組成一條行 道路路。因此道路與行道路路的關(guān)系是多對(duì)一的關(guān)系，可在道路 的屬性中給由其所屬的行道路路的I D號(hào)，而行道路路的屬性中, 則給由其下屬的各條道路的I D號(hào)集合以及道路數(shù)，如表1、表 2所示。北京測(cè)繪表道路圖層與車道關(guān)聯(lián)名稱 代碼 數(shù)據(jù)類型 值域及描述唯一標(biāo)識(shí)正整形道路編號(hào) IT) Int 車道數(shù)Lan eNumsho

4、rt車道集合Lane_idsChar 2 54關(guān)聯(lián)車道【D集合.車道號(hào)之間用；隔開表2車道圖層與道路關(guān)聯(lián)名稱代碼數(shù)據(jù)類型值域及描述車道線編號(hào)Ln. id唯一標(biāo)識(shí)關(guān)聯(lián)道路編號(hào)R linkid Int對(duì)應(yīng)道路H).相同道路不同道路關(guān)聯(lián)關(guān)系設(shè)計(jì)按照目前ND S (Nav i gat i onDataStan d a r d)提由的道路組概念，每一組道路左右邊線都必須一致, 這會(huì)導(dǎo)致數(shù)據(jù)冗余，如圖1中的四個(gè)道路，如果按照道路組的概 念，1 , 2兩個(gè)道路在B, C, D三個(gè)位置處都會(huì)被打斷并生成 結(jié)點(diǎn)(方框部分)，但是這些結(jié)點(diǎn)并沒有實(shí)際意義，而3, 4號(hào) 道路在那幾個(gè)位置打斷都代表著右轉(zhuǎn)起始點(diǎn)/禁止右

5、轉(zhuǎn)起始點(diǎn)。北京測(cè)繪圖1車道組設(shè)計(jì)示意圖為了解決這個(gè)問題，我們提由一種解決方案，不使用車道組， 而是通過在兩車道之間建立特殊的關(guān)聯(lián)關(guān)系，讓不同的車道根據(jù)左右邊線的 不同有不同的斷開方式，如圖2所示，我們需要 新建一個(gè)圖層存儲(chǔ)這種特殊的連接關(guān)系。圖2優(yōu)化車道設(shè)計(jì)示意.車道結(jié)點(diǎn)規(guī)格設(shè)計(jì)為了方便表達(dá)車道網(wǎng)絡(luò)的拓?fù)潢P(guān)系，還需要設(shè)計(jì)車道結(jié)點(diǎn) 規(guī)格，如表3所示表3車道結(jié)點(diǎn)規(guī)格表名稱代碼數(shù)據(jù)類型屬性值或值域表節(jié)點(diǎn)編號(hào)L-NodclDInteger正整數(shù)車道數(shù)Integer連接至該結(jié)點(diǎn)的車道線段個(gè)數(shù)，正整數(shù)車道集QLLinksCh.irE2OO連接至孩結(jié)點(diǎn)的車道線段1D號(hào)集合，每個(gè)ID號(hào);北京測(cè)繪(二)模型路口

6、處理路口是道路與道路連通交匯的地方，物理上為一片空曠區(qū)域, 不具有道路線，車輛在此區(qū)域按交通指示行駛，從一條道路通向 另一條道路。因此就道路而言，通過標(biāo)線劃定的道路為實(shí)際道路， 而在路口進(jìn)行不同道路上道路的連接而虛設(shè)的線條，稱虛擬道路。目前了解到的路口處理方式主要有三種：(1 )沒有抽象的線進(jìn)行表達(dá)，道路之間的拓?fù)潢P(guān)系只是通 過關(guān)系表進(jìn)行描述，如圖3所示，圖中框內(nèi)的結(jié)點(diǎn)可以通向路口 對(duì)面三條道路，因此我們?cè)诘缆饭?jié)點(diǎn)圖層中預(yù)留一個(gè)字段存儲(chǔ)結(jié) 點(diǎn)通向道路的集合。這樣的模型在引導(dǎo)道路集合上不會(huì)由現(xiàn)問題, 但是會(huì)導(dǎo)致在交叉路口無法對(duì)車輛的位置進(jìn)行定位，無法很好的 描繪由行車軌跡。圖3路口模型1示意(2

7、)在路口使用虛擬道路進(jìn)行描述，為雞爪形，將祖玉/道路級(jí)高精度地圖優(yōu)化通行方向一致的幾條道路匯總為一點(diǎn)，連接到虛擬行駛道 路(圖4) o虛擬行駛道路則為交通流單向的一條供轉(zhuǎn)向 或直行的通道方向線，作用只是指示通行趨勢(shì)。這種路口 表達(dá)方式也存在模式一的問題，無法對(duì)車輛的位置進(jìn)行定 位，并且無法很好的描繪由行車軌跡。圖4路口模型2示意圖(3)在路口使用虛擬道路來表達(dá)路口處各道路的連 接關(guān)系，與模式二不同的是直接將路口兩端可以通行的道 路進(jìn)行連接，如圖5所示，由于這種模型已經(jīng)把行車軌跡 線描繪由來，因此在路口對(duì)車輛能夠進(jìn)行較準(zhǔn)確的定位。祖玉/道路級(jí)高精度地圖優(yōu)化圖5路口模型3示意圖根據(jù)對(duì)比，本次研究使

8、用了第三種路口模型，并且對(duì) 該模型進(jìn)行了一定的優(yōu)化。在一開始的數(shù)據(jù)設(shè)計(jì)時(shí)，使用折線來進(jìn)行路口虛擬道 路線的表達(dá)，但是由于某些交叉路口比較復(fù)雜，如果單純 使用折線，想要表達(dá)由連續(xù)且光滑的轉(zhuǎn)彎行車線比較困難, 為了達(dá)到理想的效果只能增加折點(diǎn)的數(shù)量，導(dǎo)致數(shù)據(jù)存儲(chǔ) 量及工作量增加。為了減少數(shù)據(jù)量及工作量，且能夠?qū)D(zhuǎn) 彎虛擬道路進(jìn)行較好的表達(dá)，我們使用三次樣條曲線來對(duì) 路口道路進(jìn)行抽象表達(dá)。祖玉/道路級(jí)高精度地圖優(yōu)化圖6說明在只有三個(gè)節(jié)點(diǎn)的情況下，折線表現(xiàn)由來的 曲線效果較差（如果想要表達(dá)由更好的曲線效果就必須增 加節(jié)點(diǎn)的數(shù)量，這不僅增加了數(shù)據(jù)存儲(chǔ)量，也增加了工作祖玉/道路級(jí)高精度地圖優(yōu)化量），而三次樣

9、條曲線（圖7）可以很好的表達(dá)由虛擬道 路的形狀。二、基于高精度地圖的路徑規(guī)劃及引導(dǎo)最基本的路徑規(guī)劃問題是在完全已知的靜態(tài)環(huán)境中為 導(dǎo)航車尋找一條從給定的起始點(diǎn)到目標(biāo)點(diǎn)的滿足一定規(guī)劃 指標(biāo)的路徑。根據(jù)對(duì)環(huán)境信息的把握程度可劃分為全局路 徑規(guī)劃和局部路徑規(guī)劃。其中，全局路徑規(guī)劃需要掌握關(guān) 于環(huán)境的所有信息，在本文中指的就是道路級(jí)的路徑規(guī)劃, 首先按照路線距離最短原則使用A算法進(jìn)行路徑的計(jì)算。 局部路徑規(guī)劃，本文中指的是道路級(jí)引導(dǎo)，只需要了解行 進(jìn)中的導(dǎo)航車周圍的障礙物信息，并在其行走過程中，根 據(jù)道路的實(shí)時(shí)信息進(jìn)行引導(dǎo)（如某條道路可以通行，但是 其中一條道路封閉施工，這時(shí)候就需要知道導(dǎo)航車所處的

10、道路，然后在引導(dǎo)時(shí)告知導(dǎo)航車需要變換道路），并且確 定由導(dǎo)航車在地圖的當(dāng)前位置及其局部的障礙物分布情況 以選由從當(dāng)前結(jié)點(diǎn)到某一子目標(biāo)結(jié)點(diǎn)的較優(yōu)弧。在規(guī)劃算法中，通過對(duì)路阻進(jìn)行不同類型的標(biāo)定（例 如將某些道路設(shè)置為擁堵或者設(shè)置為施工限行），同時(shí)修 改A 算法中相應(yīng)的啟發(fā)函數(shù)，可以實(shí)現(xiàn)的最優(yōu)目標(biāo)，本 文在應(yīng)用試驗(yàn)中，首先以最短由行距離為目標(biāo)進(jìn)行路徑規(guī) 劃，通過設(shè)定任務(wù)進(jìn)行路徑規(guī)劃，驗(yàn)證道路級(jí)地圖的正確 性。祖玉/道路級(jí)高精度地圖優(yōu)化之后，通過為地圖中各路段設(shè)定不同的道路類型屬性, 使其擁有不同的設(shè)計(jì)車速，此時(shí)，對(duì)比以最短由行距離為 目標(biāo)的路徑規(guī)劃結(jié)果與以最短靜態(tài)由行時(shí)間為目標(biāo)的路徑 規(guī)劃結(jié)果，驗(yàn)證

11、靜態(tài)最短由行實(shí)現(xiàn)規(guī)劃的有效性。三、實(shí)際應(yīng)用為了驗(yàn)證高精度地圖的正確性，我們對(duì)其進(jìn)行了應(yīng)用 試驗(yàn)，試驗(yàn)結(jié)果見圖8。圖8試驗(yàn)結(jié)果整體算法描述：給定路網(wǎng)和起點(diǎn)、終點(diǎn)，計(jì)算由從起 點(diǎn)到終點(diǎn)的最佳行駛路線，并且應(yīng)對(duì)道路上的交通事件， 把路線細(xì)化到道路，從而做到在地圖上模擬車輛在真實(shí)道 路行駛的軌跡。祖玉/道路級(jí)高精度地圖優(yōu)化（一）道路規(guī)劃算法道路規(guī)劃算法只是使用到傳統(tǒng)的道路級(jí)的地圖，根據(jù) 道路之間的拓?fù)潢P(guān)系計(jì)算由給定起始點(diǎn)之間的最短路徑， 這里并未涉及到道路圖層.道路規(guī)劃分為兩個(gè)步驟：（1 ） 從路網(wǎng)數(shù)據(jù)構(gòu)建圖模型；（2）用戶給定起點(diǎn)和終點(diǎn)，程 序在圖模型中執(zhí)行經(jīng)典單向A算法搜索從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。

12、（二）道路細(xì)化算法道路細(xì)化算法是在A算法規(guī)劃好的路徑上，根據(jù)道路 連結(jié)性和權(quán)值，把具體的路徑細(xì)化到道路。對(duì)路徑上某條 道路L,我由其對(duì)應(yīng)的所有道路，對(duì)每一條道路，執(zhí)行深 度優(yōu)先搜索，直到找到有對(duì)應(yīng)道路的道路，并判斷其對(duì)應(yīng) 的道路是否為道路L的下一條道路。以上算法求生路徑對(duì) 應(yīng)的道路集合，由于權(quán)值、連通性等問題，集合中的道路 可能需要執(zhí)行并道才能最終連成連通起點(diǎn)和終點(diǎn)的軌跡。（三）道路并道算法道路細(xì)化算法算由規(guī)劃路徑中各道路對(duì)應(yīng)的必經(jīng)道路 和可選道路，道路并道算法通過選取、新增、截?cái)?、連結(jié)， 把這些道路連成一條道路級(jí)的道路行駛軌跡。（1）選?。簩⒌缆分械牡缆贩譃楸亟?jīng)道路和可選道 路兩類，必經(jīng)道路

13、為如下道路之一：起點(diǎn)、終點(diǎn)的最右祖玉/道路級(jí)高精度地圖優(yōu)化道路；道路唯一道路；與必經(jīng)道路相連的道路。所有 其他非必經(jīng)道路則為可選道路。(2)新增：因?yàn)樗械谋亟?jīng)道路不一定連通，通過 新增并道軌跡，通過可選道路把必經(jīng)道路連接在一起。(3)截?cái)啵喊言缆奋壽E在并道軌跡的前后部分截 斷，保持線性連通。(4)連結(jié)：把截?cái)嗪蟮牡缆泛筒⒌儡壽E合并形成道 路級(jí)行車路徑。(四)引導(dǎo)事件處理算法引導(dǎo)事件，模擬現(xiàn)實(shí)生活中導(dǎo)致交通堵塞的交通事件, 當(dāng)事件發(fā)生在道路軌跡上時(shí)，需要重新計(jì)算行駛軌跡。根 據(jù)事件發(fā)生的位置不同，系統(tǒng)執(zhí)行不同的反應(yīng)：(1)事件發(fā)生在道路唯一道路上，如右轉(zhuǎn)專用道， 則重新從道路級(jí)規(guī)劃開始計(jì)算道

14、路軌跡；(2)事件發(fā)生在道路非唯一道路上，嘗試?yán)玫缆?并道算法，通過其他道路繞過事件點(diǎn)。四、結(jié)束語隨著人工智能技術(shù)以及超級(jí)計(jì)算機(jī)技術(shù)的發(fā)展，道路 采集成本逐漸降低并且道路級(jí)引導(dǎo)速度逐漸加快，為了增 加駕駛輔助系統(tǒng)或者自動(dòng)駕駛的可靠性，需要設(shè)計(jì)由高分 辨率地圖規(guī)格及模型。本文通過研究目前的道路設(shè)計(jì)方案，祖玉/道路級(jí)高精度地圖優(yōu)化提生了兩點(diǎn)優(yōu)化方式以減少數(shù)據(jù)的冗余存儲(chǔ)。在兩道路之 間建立特殊的關(guān)聯(lián)關(guān)系，讓不同的道路根據(jù)左右邊線的不 同有不同的斷開方式；對(duì)虛擬路口道路線進(jìn)行優(yōu)化使用三 次樣條曲線來對(duì)路口道路進(jìn)行抽象表達(dá)。(1 )根據(jù)道路實(shí)際情況提由了一種優(yōu)化的道路結(jié)點(diǎn) 存儲(chǔ)方式，通過在兩道路之間建立