王美玲， 潘允輝

(北京理工大學 自動化學院， 北京 100081)

?

基于GIS與約束條件下的最優(yōu)路徑規(guī)劃研究

王美玲， 潘允輝

(北京理工大學 自動化學院， 北京 100081)

根據(jù)無人地面車輛自主導航的需求，提出一種給定任務(wù)點的約束條件下的最優(yōu)路徑實現(xiàn)方法. 首先基于地理信息系統(tǒng)(GIS)平臺構(gòu)建為車輛行駛提供先驗信息的GIS數(shù)據(jù)庫，并設(shè)計研究基于計算幾何的路段匹配算法，同時結(jié)合A*算法進行全局路徑規(guī)劃. 然后根據(jù)無人地面車輛的運動特性和對路口識別的需求提出了新的路口模型，同時為保證無人地面車輛行駛軌跡的平滑性和對路口識別的精確性，對路口軌跡和U-turn軌跡進行了算法設(shè)計. 最后提出了動態(tài)重規(guī)劃的行駛策略. 實際跑車實驗證明了該設(shè)計算法的有效性.

路徑規(guī)劃；GIS；路口模型；路段匹配算法；動態(tài)重規(guī)劃

無人地面車輛是未來智能交通系統(tǒng)與未來作戰(zhàn)系統(tǒng)的重要組成，如何規(guī)劃出可行駛的最優(yōu)路徑是無人地面車輛的核心技術(shù)之一. 路徑規(guī)劃為兩點之間提供一條可行并且最優(yōu)(或次優(yōu))的路徑，這條可行路徑通常會考慮路徑的長度、行駛中的避障以及燃油消耗等因素[1-2].

目前基礎(chǔ)性的路徑規(guī)劃研究主要針對全局路徑規(guī)劃和局部路徑規(guī)劃，然而路徑規(guī)劃時經(jīng)常需要給定途經(jīng)點，這樣具有約束條件下進行最優(yōu)路徑規(guī)劃同樣是無人地面車輛行駛的重要應(yīng)用.

SuperMap GIS是一款大型的地理信息系統(tǒng)軟件平臺，其網(wǎng)絡(luò)編輯和分析功能既為路徑規(guī)劃算法提供所需的網(wǎng)絡(luò)數(shù)據(jù)集， 同時也為路徑規(guī)劃算法的設(shè)計、實現(xiàn)和優(yōu)化帶來方便[3].

本文以無人地面車輛為載體，通過SuperMap平臺構(gòu)建GIS數(shù)據(jù)庫，為無人地面車輛的安全快速行駛提供所需的先驗信息和引導數(shù)據(jù)，結(jié)合約束條件和路口模型，利用道路匹配算法和路徑生成算法設(shè)計一條從起點出發(fā)，經(jīng)給定途徑點，到達目標點的最優(yōu)行駛路徑.

1 GIS數(shù)據(jù)庫的構(gòu)建

通過分析無人地面車輛自主行駛的特點，根據(jù)對道路和環(huán)境等先驗信息的應(yīng)用需求，基于SuperMap平臺，本文構(gòu)建適用于無人地面車輛應(yīng)用的GIS數(shù)據(jù)庫，其組成框圖如圖1所示.

由圖1可知，構(gòu)建的GIS數(shù)據(jù)庫主要由4部分組成：

① SuperMap平臺. 此平臺用于地圖數(shù)據(jù)存儲與編輯.

② 參照底圖. 選取分辨率精度為0.3 m的衛(wèi)星地圖作為底圖輸入，作為繪制“道路網(wǎng)絡(luò)”的參照底圖.

③ 網(wǎng)絡(luò)數(shù)據(jù)集. 由點數(shù)據(jù)集和線數(shù)據(jù)集構(gòu)成. 點數(shù)據(jù)集提供道路網(wǎng)絡(luò)中不同類型的節(jié)點，如十字路口點、交叉口入點、交叉口出點、車輛轉(zhuǎn)向點等. 線數(shù)據(jù)集提供道路網(wǎng)絡(luò)中不同類型的路段，這里的路段是指兩個節(jié)點之間具有完全相同道路屬性的一段道路. 此部分為無人地面車輛的路徑規(guī)劃提供基礎(chǔ)數(shù)據(jù)構(gòu)架.

④ 先驗信息. 由道路屬性、節(jié)點屬性和交通信息構(gòu)成. 道路屬性主要包括道路ID號、長度、寬度、車道線數(shù)量、是否可以并線、順行逆行方向以及變道信息等. 節(jié)點屬性主要包括起點、終點、路口點、交叉口的入點和出點、立交橋的入點和出點、小區(qū)及學校的入點和出點、U-turn點、拐彎點、停車點以及節(jié)點的ID號. 交通信息主要包括各類交通標識、交通管制區(qū)域、交通燈位置和限速區(qū)域.

2 約束條件下的路徑規(guī)劃算法

路徑規(guī)劃算法主要由3部分組成：①基于計算幾何的路段匹配算法；②關(guān)鍵點序列的產(chǎn)生算法；③A*算法.

2.1 基于計算幾何的路段匹配算法

為了便于量測導航距離和導航時間，首先需要將任務(wù)點的大地坐標轉(zhuǎn)換為WGS84-UTM投影坐標，然后利用下述基于計算幾何的路段匹配算法完成各點的路段匹配.

假設(shè)正在匹配的任務(wù)點為P，構(gòu)造一個以P為圓心，半徑可調(diào)(半徑越小，搜索時間越短)的圓形候選區(qū)域. 為了提高候選路段的置信度，同時方便后續(xù)算法的計算，本文選擇一個以P為中心，以100邊形模擬半徑為200 m的圓的多邊形作為候選區(qū)域. 利用垂直投影方式遍歷候選區(qū)域內(nèi)的所有路段，通過隊列排序，輸出點P匹配的路段信息.

路段匹配算法流程框圖如圖2所示.

在求解點P到當前候選路段的最短距離時，存在以下兩種情況：

① 所作垂直投影點的坐標落在候選路段上. 此時直接取點P到候選路段的距離為最短距離；

② 所作垂直投影點的坐標落在候選路段外. 此時取點P到候選路段較近端點的距離為最短距離.

利用路段匹配算法找出道路網(wǎng)絡(luò)中所有任務(wù)點對應(yīng)的匹配路段，存儲其相應(yīng)信息.

2.2 關(guān)鍵點序列的產(chǎn)生算法

在規(guī)劃出最短路徑之前，需要先獲得一串由所經(jīng)路段的起點或終點組成的節(jié)點序列，本文稱之為關(guān)鍵點序列，其算法步驟如下：

① 判斷任務(wù)點的狀態(tài)屬性，若為起點或者終點，直接將此任務(wù)點加入到關(guān)鍵點序列中；若為途經(jīng)點，則進行步驟2；

② 分別計算當前任務(wù)點與其匹配路段起點和終點的距離，若前者距離大于后者距離，則將該任務(wù)點的匹配路段終點視為候選關(guān)鍵點；反之，則將該任務(wù)點的匹配路段起點視為候選關(guān)鍵點；

③ 將步驟2中提取的候選關(guān)鍵點與當前關(guān)鍵點序列中最后加入的關(guān)鍵點作比較，若不為同一點，則將此候選關(guān)鍵點加入關(guān)鍵點序列中；若是同一點，則忽略此點，預防序列中存在重復關(guān)鍵點；

④ 對所有任務(wù)點重復以上步驟，生成關(guān)鍵點序列.

由于A*算法具有搜索深度較小，搜索的節(jié)點數(shù)少，占用的存儲空間少等特點，因此本文基于此算法來完成整個行駛路徑的全局規(guī)劃.

3 路徑生成

3.1 路口行車軌跡設(shè)計

隨著城市建設(shè)的發(fā)展，城市道路日趨復雜，原有的交通電子地圖的中心線模型已經(jīng)不能表達城市道路網(wǎng)和行車規(guī)則[4-6]，為了使規(guī)劃的路徑能夠更好地適用于無人地面車輛的行駛，本文提出一種帶有路口距離屬性的雙線路口模型，如圖3所示. 在道路網(wǎng)絡(luò)中，通過線數(shù)據(jù)集只能計算當前點與路段節(jié)點的距離，在圖4中，若車輛行駛方向為A到B，以傳統(tǒng)道路模型算法，則當車輛行駛到點O1時才表示進入路口，在這種情況下相當于將路口滯后了，對于交通燈識別、行人避障等會產(chǎn)生很大影響. 因此本文提出利用GIS數(shù)據(jù)庫提前存儲先驗信息，在計算路口距離時考慮斑馬線外沿A點到路口節(jié)點O1的距離(若左轉(zhuǎn)，則考慮圖5中點A到路口節(jié)點O1的距離)，使得無人地面車輛在行駛到點A時即進入路口模式(此時距離為負)，直至行駛到下一個斑馬線的外沿時距離值恢復為正，負距離值表示無人地面車輛行駛在路口內(nèi). 此模型使得最終生成的路徑能夠滿足3個要求：一是符合并能表達現(xiàn)代城市道路的行車規(guī)則；二是保證無人地面車輛路口識別的準確性；三是生成的導航路線符合無人地面車輛的運動學特性[7-8].

從上述模型與傳統(tǒng)道路模型的對比可以觀察出上述模型為無人地面車輛提供的導航行駛軌跡不再是一個直角彎，而是由轉(zhuǎn)彎半徑限制出的一個圓弧，這對于無人地面車輛的控制有著十分重要的意義，提高了無人地面車輛行駛的流暢性；同時利用斑馬線與路口中心點的距離屬性將“路口內(nèi)”和“路口外”兩種情況區(qū)分得更加明確，由此屬性經(jīng)算法計算后得到的路口軌跡既能保證無人地面車輛對路口識別的精確性，同時又將轉(zhuǎn)彎半徑增大，更利于車輛的運動. 需要說明的是模型中只表示了雙向路線，多條車道時需要根據(jù)GIS數(shù)據(jù)庫存儲的車道數(shù)量、車道寬度等屬性，結(jié)合頂層決策命令和視覺感知信息共同確定的.

模型的算法實現(xiàn)如下：

以圖4為例，假設(shè)前一個路口直行通過，當前路口拐彎(以右轉(zhuǎn)為例). 設(shè)路口中心點O2坐標為(X，Y)；無人地面車輛所在當前道路R0和將要駛?cè)氲哪繕说缆稲i；路口所有道路的方向角為{θi，i=1，2，…，n}；車輛最小轉(zhuǎn)彎半徑Rmin_turn；道路寬度屬性Lwidth；斑馬線中點至路口中心點的距離屬性Dright(直行和右轉(zhuǎn)，此時對應(yīng)的路口中心節(jié)點為O2)和Dleft(左轉(zhuǎn)，此時對應(yīng)的路口中心節(jié)點為O1，如圖4所示).

① 讀取GIS數(shù)據(jù)庫中點B和點C所在道路的道路寬度，取其小者，表示為Lwidth，若此時通過路口狀態(tài)為右轉(zhuǎn)則取Lwidth=0.75Lwidth(右轉(zhuǎn)半徑小于左轉(zhuǎn)半徑)；

② 由點O2、B和C分別確定點B和C所在道路方向，結(jié)合步驟1求得的Lwidth，確定在BO2連線上的點S1坐標和在CO2連線上的點S2坐標；

③ 由點S1、S2和其切線方向(即兩點各自所在的道路方向)確定圓心點O坐標和半徑大小R；

④ 根據(jù)無人地面車輛運動模型特點，轉(zhuǎn)彎時存在最小轉(zhuǎn)彎半徑，用Rmin_turn來表示，若Rmin_turn

⑤ 選取合適的步長(即以多大的間隔生成路點)求取點B和點S1之間的路點坐標；

⑥ 讀取GIS數(shù)據(jù)庫中CO2的距離值，求取點C坐標，再以直線軌跡方式求取點S2和點C之間的路點坐標.

圖5所示為連續(xù)兩個路口轉(zhuǎn)彎的情況，前一個路口左轉(zhuǎn)，第二個路口右轉(zhuǎn).

對于不規(guī)則的路口，其構(gòu)造的“道路網(wǎng)絡(luò)”路線多、結(jié)點多，相對于正常路口模型較復雜，但是在路徑生成算法中原理相同. 如圖6所示為不規(guī)則路口中的“道路網(wǎng)絡(luò)”，圖7所示為所有可能行駛的路線.

3.2 U-turn軌跡設(shè)計

若在U-turn處的路徑生成模式與路口路徑的生成模式相同，則相當于在U-turn處將兩段圓弧拼接在一起，在拼接處往往會出現(xiàn)“尖角”，如圖8所示.

這樣的“尖角”會影響無人地面車輛的運動控制，也會影響車輛行駛的平滑性，因此本文提出以Hermite插值的方式來生成U-turn軌跡.

Hermite插值方法能保證節(jié)點處的函數(shù)值相等，也就保證了函數(shù)的連續(xù)性，與其它插值方式相比，它又結(jié)合了函數(shù)的導數(shù)值，能夠保證節(jié)點處的導數(shù)值相等，提高了插值的精度和光滑度.

以生成路口路徑的方式找到U-turn的入彎點和出彎點，結(jié)合橫向路段的中點，以此3點進行Hermite插值，生成的U-turn軌跡如圖9所示.

在整個路徑生成過程中，其耗費時間主要與全局搜索匹配到的路段個數(shù)有關(guān)，匹配到的路段數(shù)越多，則耗時越長，反之亦然. 由于本文的著重點并不是規(guī)劃時間的長短，因此沒有對此部分做太多的優(yōu)化，匹配到的路段數(shù)與耗時比例大約為10∶1(s).

4 路徑重規(guī)劃

靜態(tài)路徑規(guī)劃在行駛車輛遇到特殊情況的時候就失去了實際的引導意義，如前方道路阻斷或是檢測到前方道路存在禁行標志，此時就需要在線動態(tài)規(guī)劃.

針對上述情況，本文提出如下在線重新規(guī)劃設(shè)計流程(圖10)：

5 實驗驗證

本文以江蘇省常熟市福溪路部分道路網(wǎng)絡(luò)為對象，通過讀取任務(wù)點，得到從起點經(jīng)途經(jīng)點到達終點的最優(yōu)路徑.

其中，實驗平臺采用美國北極星全地形山地車作為車體底盤，經(jīng)過對車體改裝，實現(xiàn)按鈕、油門、檔位以及剎車的自動控制. 整個系統(tǒng)所包含感知設(shè)備主要有：3D激光雷達、2D激光雷達、毫米波雷達、全景攝像頭、廣角攝像頭、長焦攝像頭、編碼器以及組合導航設(shè)備等. 組合導航設(shè)備采用SPAN-CPT，是一款集成GPS+INS的緊耦合組合導航定位系統(tǒng).

表1所示為任務(wù)點的屬性列表.

表1 任務(wù)點屬性列表

其中屬性1提供的屬性中，0表示此點為起點，1表示此點為途經(jīng)點，2表示此點為終點；屬性2提供的屬性中，1表示沒有特殊屬性，2表示此點前后一定距離內(nèi)社會車輛較多，3表示此點前后一定距離內(nèi)為限速區(qū)域，4表示此點前方為U-turn點，5表示此點處有交通標識.

圖11所示為無人地面車輛行駛所選區(qū)域構(gòu)建的道路網(wǎng)絡(luò).

圖12所示為讀取的任務(wù)點在道路網(wǎng)絡(luò)中的位置. 圖13為加入道路模型后的路徑規(guī)劃結(jié)果. 其中，紅色路線表明前方是直行路段；綠色路線表明前方路口將進入左轉(zhuǎn)；藍色路線表明前方路口將進入右轉(zhuǎn). 圖14為車輛右轉(zhuǎn)和左轉(zhuǎn)時的軌跡，U-turn如圖9所示，可以看出，車輛在路口轉(zhuǎn)彎的時候不再是直角彎，而是處理后的圓弧. 表2列舉了規(guī)劃出的路徑中3個拐彎點的入點坐標、出點坐標和轉(zhuǎn)彎半徑，以及U-turn的入點和出點坐標.

屬性點拐彎1拐彎2拐彎3U-turn入彎點/(°)出彎點/(°)120.77887120.7790831.5909031.59086120.78124120.7815131.5881531.58809120.78323120.7833731.5889631.58894120.77680120.7769031.5901731.59002半徑/m15.33024318.5699649.504948

表3給出了每個任務(wù)點在道路網(wǎng)絡(luò)中匹配到的道路的ID號，以及在保證不走重復路線的前提下，連續(xù)的兩個任務(wù)點之間距離最短的3條可通行路線長度.

表3 匹配道路的ID號和路徑長度

實驗中無人地面車輛行駛的實際路線總長約2 358 m，路徑規(guī)劃時匹配到的路段數(shù)為53條，規(guī)劃耗時約6.8 s，行駛最高時速40 km，行駛中涉及交通標識檢測、交通燈識別、障礙物躲避、行人檢測、側(cè)方停車、終點停止線檢測以及社會車輛跟隨等任務(wù)，全程耗時約11 min，無人工干預，順利通過所有任務(wù)點，行駛穩(wěn)定平順.

6 結(jié) 論

在給定任務(wù)點的約束條件下，本文提出方法首先將任務(wù)點的大地坐標轉(zhuǎn)化為適用于路徑規(guī)劃的平面坐標，利用路段匹配算法獲得關(guān)鍵點序列；基于提出的雙線路口模型，結(jié)合GIS數(shù)據(jù)庫提供的先驗信息，設(shè)計出一條符合無人地面車輛運動特性的行駛軌跡，對車輛完成路口識別起到重要作用. 對U-turn軌跡進行特殊處理，以及對車輛進行動態(tài)重規(guī)劃保障了無人地面車輛的自主行駛. 本文設(shè)計的最優(yōu)路徑實現(xiàn)方法已經(jīng)應(yīng)用于本實驗的無人地面車輛中，并參加了國家自然基金委組織的中國智能車未來挑戰(zhàn)賽以及總裝備部組織的跨越險阻地面無人平臺挑戰(zhàn)賽.

由于實驗場地和比賽環(huán)境中參雜的不穩(wěn)定因素較少，如基本沒有行人，社會車輛較少等，本文路徑規(guī)劃以路徑長度為主要考慮因素，如何融合更多的影響因素，使得最終的行駛路徑能夠達到最短距離、最少時間、最少耗費是下一步研究內(nèi)容.

[1] Wang Y， Wang S， Tan M， et al. Real-time dynamic Dubins-Helix method for 3-D trajectory smoothing[J]. IEEE Trans Control Syst Technol， 2015，23(2):730-736.

[2] Wang Y， Wang S， Tan M. Path generation of autonomous approach to a moving ship for unmanned vehicles[J]. IEEE Trans Ind Electron， 2015，23(2):730-736.

[3] 程林，王美玲，張毅.一種基于SuperMap GIS的改進Dijkstra算法[J].地球信息科學學報，2010，12(5):649-654.

Cheng Lin， Wang Meiling， Zhang Yi. An improved Dijkstra algorithm based on supermap GIS[J]. Journal of Geo-Information Science， 2010，12(5):649-654.(in Chinese)[4] 尤淑撐，嚴泰來.基于人工神經(jīng)網(wǎng)絡(luò)面插值的方法研究[J].測繪學報，2000，29(1):30-34.

You Shucheng，Yan Tailai. A study on artificial neural network based surface interpoliation[J]. Acta Geodaetica et Cartographica Sinica， 2000，29(1):30-34.(in Chinese)

[5] 王曦鳴.軍用無人車的路徑規(guī)劃與仿真研究[D].北京：北京交通大學，2010.

Wang Ximing. The path planning and simulation research of military unmanned vehicle[D]. Beijing: Beijing Jiaotong University， 2010. (in Chinese)

[6] 王延亮，張玉娟.城市導航電子地圖的道路模型[J].測繪與空間地理信息，2005，28(3)：62-64.

Wang Yanling， Zhang Yujuan. The road model of city navigation electronic map[J]. Geomatics and Spatial Information Technology，2005，28(3)：62-64.(in Chinese)

[7] 姜巖，趙熙俊，龔建偉，等.簡單城市環(huán)境下地面無人駕駛系統(tǒng)的設(shè)計研究[J].機械工程學報，2012，48(20):103-112.

Jiang Yan， Zhao Xijun， Gong Jianwei， et al. System design of self-driving in simplified urban environments[J].Journal of Mechanical Engineering，2012，48(20):103-112.(in Chinese)

[8] 張浩杰，龔建偉，姜巖，等.基于變維度狀態(tài)空間的增量啟發(fā)式路徑規(guī)劃方法研究[J].自動化學報，2013，39(10):1602-1610.

Zhang Haojie， Gong Jianwei， Jiang Yan， et al.Research on incremental heuristic path planner with variable dimensional state space[J]. Acta Automatica Sinica， 2013，39(10):1602-1610. (in Chinese)

(責任編輯：李兵)

Research on Optimal Path Planning with Constraints Based on GIS

WANG Mei-ling， PAN Yun-hui

(School of Automation， Beijing Institute of Technology， Beijing 100081， China)

According to the requirements of unmanned ground vehicle(UGV) autonomous navigation， an implementation method was proposed for path optimization with given task points as constraints. Firstly， a geographic information system (GIS) database was built based on the GIS platform to provide priori information for UGV. And then a road-matching algorithm was designed based on the computational geometry. Simultaneously the static and dynamic path planning was conducted combining with A*algorithm. Secondly， a new crossroads model was proposed according to the movement characteristics of UGV and the demand in recognizing the intersection. An algorithmic design for the intersection tracks and U-turn tracks was conducted to smooth the UGV’s driving routes and to ensure the accuracy of intersection recognition. At last， a dynamic re-planning driving strategy was put forward. The validity of designed algorithm was verified by actual car experiments.

path planning; GIS; crossroads model; road-matching algorithm; dynamic re-planning

2015-04-13

國家自然科學基金資助項目(61173076)；國家自然科學基金重大研究計劃培育資助項目(91120003)

王美玲(1970—)，女，教授，博士生導師，E-mail:wangml@bit.edu.cn.

潘允輝(1991—)，男，碩士生，E-mail:pyhforever@163.com.

TP 242.6; P 208

A

1001-0645(2016)08-0851-07

10.15918/j.tbit1001-0645.2016.08.014