關(guān)泉珍，鮑 泓，史志堅(jiān)

（北京聯(lián)合大學(xué)北京市信息服務(wù)工程重點(diǎn)實(shí)驗(yàn)室，北京 100101）

?

基于A*算法的駕駛地圖路徑規(guī)劃實(shí)現(xiàn)

關(guān)泉珍，鮑 泓，史志堅(jiān)

（北京聯(lián)合大學(xué)北京市信息服務(wù)工程重點(diǎn)實(shí)驗(yàn)室，北京 100101）

［摘 要］采用高精度地圖構(gòu)建技術(shù)還原路況信息，結(jié)合A*算法使智能車(chē)能夠在導(dǎo)航不起作用的情況下按照規(guī)劃路徑進(jìn)行無(wú)障礙行駛。將高精度地圖用柵格數(shù)據(jù)模型表示，在標(biāo)記為有障礙的柵格模型中，為機(jī)器人尋找一條恰當(dāng)?shù)膹钠鹗键c(diǎn)到目標(biāo)點(diǎn)的運(yùn)動(dòng)路徑，且可以使機(jī)器人在運(yùn)動(dòng)過(guò)程中安全、無(wú)碰撞地繞過(guò)障礙物。通過(guò)在無(wú)人駕駛智能車(chē)平臺(tái)上仿真實(shí)驗(yàn)表明，這種方法具有形式簡(jiǎn)單規(guī)范、一致性好并容易在計(jì)算機(jī)中實(shí)現(xiàn)的優(yōu)點(diǎn)。

［關(guān)鍵詞］路徑規(guī)劃；自主導(dǎo)航；高精度地圖；A*算法；柵格數(shù)據(jù)模型

引言

無(wú)人駕駛汽車(chē)是一種智能汽車(chē)，也稱(chēng)之為輪式移動(dòng)機(jī)器人［1］，是在沒(méi)有人類(lèi)參與的情況下，依靠車(chē)內(nèi)的計(jì)算機(jī)系統(tǒng)，通過(guò)智能駕駛系統(tǒng)來(lái)實(shí)現(xiàn)無(wú)人駕駛的功能［2］。它是一個(gè)集環(huán)境信息感知、智能規(guī)劃決策、輔助及自主駕駛等多種功能于一體的綜合車(chē)輛系統(tǒng)［3］，路徑規(guī)劃是無(wú)人駕駛汽車(chē)導(dǎo)航的基本環(huán)節(jié)之一。它是按照某一性能指標(biāo)搜索一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)或近似最優(yōu)的無(wú)碰路徑。對(duì)于路徑規(guī)劃來(lái)說(shuō)，往往與無(wú)人駕駛汽車(chē)所處的空間位置和傳感器所感知的周?chē)h(huán)境信息密切相關(guān)。根據(jù)無(wú)人駕駛汽車(chē)傳感器對(duì)周?chē)h(huán)境信息知道的程度不同，可分為兩種類(lèi)型:第一種是環(huán)境信息完全知道的宏觀路徑規(guī)劃也叫全局路徑規(guī)劃；第二種是環(huán)境信息完全未知或部分未知，通過(guò)雷達(dá)、攝像頭等傳感器對(duì)無(wú)人駕駛汽車(chē)的工作環(huán)境進(jìn)行探測(cè)，獲取障礙物的位置、形狀和尺寸等信息的局部路徑規(guī)劃。全局路徑規(guī)劃可使所規(guī)劃的路徑達(dá)到最優(yōu)，局部路徑規(guī)劃則可使機(jī)器人完成實(shí)時(shí)避障。目前常用的移動(dòng)機(jī)器人全局路徑規(guī)劃方法很多，主要有蟻群算法［4］、粒子群算法［5］、遺傳算法［6］等，此外GPS也是智能車(chē)輛進(jìn)行全局規(guī)劃的重要手段之一，目前主要采用GPS/INS組合的導(dǎo)航技術(shù)。對(duì)蟻群算法來(lái)說(shuō)，它存在收斂速度慢，容易陷入局部最優(yōu)等缺陷；粒子群優(yōu)化算法雖然具有通用性強(qiáng)、不依賴(lài)于問(wèn)題、原理簡(jiǎn)單、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，但粒子群算法計(jì)算效率偏低，且抗噪能力差；遺傳算法存在編程實(shí)現(xiàn)比較復(fù)雜，且參數(shù)的選擇大部分是依靠經(jīng)驗(yàn)等缺點(diǎn)。對(duì)GPS來(lái)說(shuō)，雖然無(wú)人駕駛汽車(chē)通過(guò)GPS/INS等傳感器能全天候?qū)崟r(shí)感知車(chē)輛在環(huán)境中的位置，提供準(zhǔn)確的車(chē)輛行駛方向、速度、加速度等車(chē)輛自身狀態(tài)信息，但由于GPS的工作依賴(lài)于衛(wèi)星信號(hào)，因此，在衛(wèi)星信號(hào)不佳或信號(hào)無(wú)法獲取的情況下將會(huì)失效［7］，INS也會(huì)出現(xiàn)信號(hào)漂移等問(wèn)題。

以上算法都存在編程實(shí)現(xiàn)較復(fù)雜等缺點(diǎn)。本文結(jié)合人類(lèi)駕駛員駕駛經(jīng)驗(yàn)，提出采用高精度地圖構(gòu)建技術(shù)還原路況信息，結(jié)合A*算法使智能車(chē)能夠在導(dǎo)航不起作用的情況下按照規(guī)劃路徑進(jìn)行無(wú)障礙行駛。將高精度地圖用柵格數(shù)據(jù)模型表示，在標(biāo)記為有障礙的柵格模型中，為機(jī)器人尋找一條恰當(dāng)?shù)膹钠鹗键c(diǎn)到目標(biāo)點(diǎn)的運(yùn)動(dòng)路徑。高精度地圖的獲取可通過(guò)專(zhuān)業(yè)做地圖的公司采集處理或者由人類(lèi)駕駛員駕駛智能汽車(chē)遍歷一塊區(qū)域內(nèi)的所有車(chē)道，將傳感系統(tǒng)如64線(xiàn)激光雷達(dá)或攝像機(jī)等采集到的行駛軌跡、道路環(huán)境等信息經(jīng)過(guò)濾波、融合等算法處理，就得到了這一區(qū)域的道路網(wǎng)絡(luò)綜合信息。

1　駕駛地圖柵格化

在車(chē)輛導(dǎo)航系統(tǒng)中，電子地圖數(shù)據(jù)庫(kù)、路徑規(guī)劃和路徑引導(dǎo)是3個(gè)相輔相成的重要模塊。為了實(shí)現(xiàn)路徑規(guī)劃和路徑引導(dǎo)，首先需要一個(gè)電子地圖數(shù)據(jù)庫(kù)的支持。對(duì)于無(wú)人駕駛汽車(chē)，除了需要電子地圖上常見(jiàn)的道路形態(tài)和路邊環(huán)境信息，還需要抽象的道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，用于宏觀層面上合理的路徑規(guī)劃和微觀層面上精確的路徑引導(dǎo)。比之目前一般的導(dǎo)航設(shè)備，無(wú)人駕駛將使用完全不同的地圖數(shù)據(jù)。精確到米的低端地圖（如圖1）只能給人類(lèi)駕駛員領(lǐng)路，無(wú)人駕駛智能車(chē)要的是厘米級(jí)的精度（如圖2）所示。應(yīng)用差分定位技術(shù)的全球衛(wèi)星定位系統(tǒng)和慣性導(dǎo)航組合可以為無(wú)人駕駛車(chē)的行駛提供厘米級(jí)的導(dǎo)航信息，但由于在發(fā)達(dá)城市越來(lái)越長(zhǎng)的隧道興建和連續(xù)高層的遮擋，全球衛(wèi)星定位系統(tǒng)和慣性導(dǎo)航組合系統(tǒng)進(jìn)入隧道不能滿(mǎn)足一定精度的要求以及在大型隧道內(nèi)不能長(zhǎng)期定位的缺點(diǎn)［7］，使得采用高精度地圖匹配技術(shù)［8］來(lái)克服以上缺點(diǎn)成為當(dāng)務(wù)之急。

無(wú)人駕駛車(chē)輛的工作環(huán)境與一般機(jī)器人應(yīng)用存在如下幾點(diǎn)不同:不具備已知的環(huán)境地圖，環(huán)境信息主要來(lái)自于車(chē)載傳感器系統(tǒng)的實(shí)時(shí)感知結(jié)果，而各個(gè)傳感器只能提供局部不完整的環(huán)境信息。因此，在車(chē)輛行駛過(guò)程中，即使環(huán)境是靜態(tài)的，規(guī)劃系統(tǒng)面對(duì)的局部環(huán)境信息也是在不斷更新的；此外，環(huán)境中可能存在較多的動(dòng)態(tài)障礙物，易造成規(guī)劃結(jié)果不可行；這些特點(diǎn)對(duì)規(guī)劃系統(tǒng)的實(shí)時(shí)性提出了更高的要求，而高精度地圖無(wú)疑對(duì)智能車(chē)的行駛起到了很大的幫助作用。

對(duì)于高精度地圖來(lái)說(shuō)，道路網(wǎng)絡(luò)的幾何坐標(biāo)信息為智能汽車(chē)提供了定位和路徑引導(dǎo)的依據(jù)，利用高精度的道路網(wǎng)信息，將GPS/INS或其他傳感器的定位結(jié)果匹配到高精度地圖的道路網(wǎng)絡(luò)上，實(shí)現(xiàn)車(chē)輛位置糾正。當(dāng)推算定位指示車(chē)輛在地圖上的某一位置時(shí)，車(chē)輛位置可以被調(diào)整到地圖上的絕對(duì)位置，這樣做會(huì)消除累積誤差，直到下一次地圖匹配步驟。在每一個(gè)連續(xù)的系統(tǒng)周期中完成這個(gè)過(guò)程，就能實(shí)時(shí)得到更加準(zhǔn)確的車(chē)輛位置。地圖匹配技術(shù)的應(yīng)用有兩個(gè)前提，即:用于匹配的數(shù)字地圖包含高精度的道路位置坐標(biāo)以及被定位的車(chē)輛正在道路網(wǎng)中行駛。對(duì)于前者而言，高精度地圖無(wú)疑是滿(mǎn)足這一要求的。當(dāng)滿(mǎn)足上述條件時(shí)，就可以把定位數(shù)據(jù)和車(chē)輛運(yùn)行軌跡同高精度地圖所提供的道路位置信息進(jìn)行比較，通過(guò)適當(dāng)?shù)钠ヅ溥^(guò)程確定出車(chē)輛最可能的行駛路段以及車(chē)輛在該路段的最大可能位置。［9］

1.1駕駛地圖與柵格地圖的關(guān)系

柵格地圖對(duì)應(yīng)投影坐標(biāo)系統(tǒng)，高精度地圖對(duì)應(yīng)地理空間坐標(biāo)系。

投影坐標(biāo)系統(tǒng)（Projection coordinate system）:使用基于X，Y值的坐標(biāo)系統(tǒng)來(lái)描述地球上某個(gè)點(diǎn)所處的位置。這個(gè)坐標(biāo)系是從地球的近似橢球體投影得到的，它對(duì)應(yīng)于某個(gè)地理坐標(biāo)系（地理空間坐標(biāo)系:使用基于經(jīng)緯度坐標(biāo)描述地球上某一點(diǎn)所處的位置。某一個(gè)地理坐標(biāo)系是基于一個(gè)基準(zhǔn)面來(lái)定義的?；鶞?zhǔn)面是利用特定橢球體對(duì)特定地區(qū)地球表面的逼近，因此每個(gè)國(guó)家或地區(qū)均有各自的基準(zhǔn)面，也稱(chēng)球面坐標(biāo)。平面坐標(biāo)系統(tǒng)地圖單位通常為米，也稱(chēng)非地球投影坐標(biāo)系統(tǒng)，或者是平面直角坐標(biāo)。投影坐標(biāo)系由以下兩項(xiàng)參數(shù)確定:地理空間坐標(biāo)系以及投影方法。下面用公式（1）來(lái)表示地理空間坐標(biāo)系和投影坐標(biāo)系統(tǒng)的關(guān)系:

式中（B，L）是橢球面上某一點(diǎn)的大地經(jīng)緯度，而（X，Y）是該點(diǎn)投影到平面上的直角坐標(biāo)。

把地球上的點(diǎn)位換算到平面上，稱(chēng)為地圖投影。地圖投影的方法有很多，本文中采用的是高斯—克呂格投影（又稱(chēng)高斯正形投影），簡(jiǎn)稱(chēng)高斯投影。它是由德國(guó)數(shù)學(xué)家高斯提出，由克呂格改進(jìn)的一種分帶投影方法。它成功解決了將橢球面轉(zhuǎn)換為平面的問(wèn)題。通過(guò)高斯投影，將中央子午線(xiàn)的投影作為縱坐標(biāo)軸，用x表示，將赤道的投影作橫坐標(biāo)軸，用y表示，兩軸的交點(diǎn)作為坐標(biāo)原點(diǎn)，由此構(gòu)成的平面直角坐標(biāo)系稱(chēng)為高斯平面直角坐標(biāo)系，［10］如圖3所示。

1.2坐標(biāo)轉(zhuǎn)換算法

將GPS-84坐標(biāo)轉(zhuǎn)換成平面坐標(biāo)的方法有兩種:一是先將WGS-84的大地坐標(biāo)轉(zhuǎn)換為1954年北京大地坐標(biāo)或1980年國(guó)家大地坐標(biāo)，而后通過(guò)投影變換（如高斯投影變換）轉(zhuǎn)換成平面直角坐標(biāo)（如圖4所示）；另一種方式是先將經(jīng)緯度坐標(biāo)以WGS-84的參考橢球?yàn)榛鶞?zhǔn)進(jìn)行高斯投影，前一種方法計(jì)算過(guò)程較復(fù)雜，計(jì)算機(jī)耗時(shí)相對(duì)要長(zhǎng)一些，但其計(jì)算精度要高于后一種方法，后一方法簡(jiǎn)化了公式［11-12］，提高了計(jì)算效率和可操作性。這種方法適用于實(shí)時(shí)性要求較高的情況，如實(shí)時(shí)車(chē)輛導(dǎo)航和監(jiān)控系統(tǒng)。本文著重討論后一種坐標(biāo)轉(zhuǎn)換算法。

WGS-84的經(jīng)緯度（維度:B，經(jīng)度:L）坐標(biāo)高斯投影到平面坐標(biāo)（x，y）上，高斯—克呂格投影的正算公式（高斯—克呂格投影正算公式是把大地坐標(biāo)換算成高斯—克呂格投影平面上的直角坐標(biāo)）如公式（2）、公式（3）、公式（4）、公式（5）、公式（6）所示:

式中C0、C1、C2、C3是與點(diǎn)位無(wú)關(guān)而僅與橢球參數(shù)有關(guān)的常系數(shù)，L0為中央子午線(xiàn)經(jīng)度，X為自赤道量起的子午線(xiàn)弧長(zhǎng)，N為卯酉圈曲率半徑。

高斯—克呂格投影的反算公式（高斯—克呂格反算公式是把高斯—克呂格投影平面直角坐標(biāo)換算到橢球面上的大地坐標(biāo)）如公式（7）、公式（8）、公式（9）、公式（10）所示:

式中

式中Bf為底點(diǎn)緯度，K0、K1、K2、K3、K4、K5是與點(diǎn)位無(wú)關(guān)而僅與橢球參數(shù)有關(guān)的常系數(shù)。

事實(shí)證明，高斯—克呂格投影正反算公式能夠進(jìn)行任意帶之間的坐標(biāo)變化，并且轉(zhuǎn)換精度高，迭代計(jì)算收斂速度快，效率高。由于地圖投影變形是球面轉(zhuǎn)化成平面的必然結(jié)果，沒(méi)有變形的投影是不存在的。對(duì)某一地圖投影來(lái)說(shuō)，不存在這種變形，就必然存在另一種或兩種變形。在制圖時(shí)則可以做到:在有些投影圖上沒(méi)有角度或面積變形；在有些投影圖上沿某一方向無(wú)長(zhǎng)度變形。高斯—克呂格投影具有等角性質(zhì)，比較適合用于測(cè)制地形圖，且適用于多種比例尺，便于編制成套比例尺的地形圖，并且由于投影帶經(jīng)差不大，經(jīng)緯網(wǎng)同直角坐標(biāo)網(wǎng)的偏差較小，閱讀和使用較方便。此外，坐標(biāo)和子午線(xiàn)收斂角數(shù)值，只要計(jì)算一帶，其他帶都可以通用，可以大大減少計(jì)算工作量。

1.3駕駛地圖的柵格化表示

柵格數(shù)據(jù)結(jié)構(gòu)又稱(chēng)為網(wǎng)格數(shù)據(jù)或者柵格數(shù)據(jù)，是以規(guī)則的陣列來(lái)表示空間地物或現(xiàn)象分布的數(shù)據(jù)組織。每個(gè)網(wǎng)格作為一個(gè)像元或像素，由行、列號(hào)定義，并包含一個(gè)代碼，表示該像素的屬性類(lèi)型或量值。每個(gè)柵格都存儲(chǔ)了它所覆蓋的表面部分的值。一個(gè)指定像元包含一個(gè)值，因此，表面的詳細(xì)程度取決于柵格像元的大小。同其他模型相比，柵格模型比較簡(jiǎn)單、高效。一般柵格模型多用于區(qū)域性的、小比例尺的應(yīng)用，本文將高精度地圖用柵格數(shù)據(jù)模型表達(dá)如圖5所示。

簡(jiǎn)單說(shuō)，柵格是單波段，任何柵格分析（處理）都是信息有損的處理。在定義柵格單元的大小時(shí)，需要平衡信息的精確性和數(shù)據(jù)量之間的矛盾。柵格單元代表的尺度越小，表達(dá)的信息就越精確。柵格單元代表的尺度越大，存儲(chǔ)數(shù)據(jù)所需要的空間就更少，同時(shí)，表達(dá)的信息也就不精確。柵格數(shù)據(jù)集像元的位深度容量（像素深度）決定著特定柵格文件可以存儲(chǔ)的值的范圍，該范圍可根據(jù)公式2n計(jì)算得出（其中，n表示位深度）。例如，一個(gè)8位的柵格可以具有256個(gè)不同的值（范圍從0至255）。柵格數(shù)據(jù)的表達(dá)如圖6所示。在本文中柵格數(shù)據(jù)只有兩類(lèi)信息:分別是障礙物和非障礙物兩類(lèi)。

2　基于A*算法的路徑規(guī)劃

A*算法是應(yīng)用極為廣泛的啟發(fā)式搜索算法（Heuristic Search Algorithm），相對(duì)于其他盲目搜索算法如廣度優(yōu)先和深度優(yōu)先等，A*算法主要依靠啟發(fā)信息構(gòu)造啟發(fā)函數(shù)，在規(guī)劃搜索路徑時(shí)對(duì)訪問(wèn)節(jié)點(diǎn)進(jìn)行代價(jià)評(píng)價(jià)，以滿(mǎn)足某些指標(biāo)要求，例如時(shí)間最短、空間最小等，從而形成代價(jià)最優(yōu)的節(jié)點(diǎn)訪問(wèn)路徑。它的基本思想是:把從起始點(diǎn)到節(jié)點(diǎn)的代價(jià)與從節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià)結(jié)合起來(lái)對(duì)節(jié)點(diǎn)進(jìn)行評(píng)價(jià):f（n）=g（n）+h（n），在這個(gè)式子當(dāng)中，h（n）是啟發(fā)函數(shù)，是從n到目標(biāo)節(jié)點(diǎn)最佳路徑估價(jià)，f（n）是從初始點(diǎn)經(jīng)由節(jié)點(diǎn)n到終點(diǎn)的評(píng)價(jià)函數(shù)，g（n）是從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)。［13-14］

借鑒A*算法的基本思想，無(wú)人駕駛車(chē)進(jìn)行路徑規(guī)劃時(shí)，首先進(jìn)行一次路徑規(guī)劃（也叫宏觀路徑規(guī)劃），規(guī)劃出一條從起始點(diǎn)到目標(biāo)點(diǎn)的路徑，然后沿著此條路徑移動(dòng)，當(dāng)無(wú)人駕駛車(chē)傳感器探測(cè)到的環(huán)境信息與系統(tǒng)已知的環(huán)境信息不一致的時(shí)候，機(jī)器人重新規(guī)劃從當(dāng)前位置到目標(biāo)點(diǎn)的路徑，如此反復(fù)，直至到達(dá)目標(biāo)點(diǎn)。A*算法的尋路步驟如下:

簡(jiǎn)易地圖（如圖7所示），其中綠色方塊的是起點(diǎn)（用A表示），中間藍(lán)色的是障礙物，紅色的方塊（用B表示）是目的地。用一個(gè)二維數(shù)組來(lái)表示地圖，將地圖劃分成一個(gè)個(gè)的小方塊。尋路步驟如下:

1）從起點(diǎn)A開(kāi)始，把它作為待處理的方格存入一個(gè)開(kāi)啟列表（開(kāi)啟列表就是一個(gè)等待檢查方格的列表），尋找起點(diǎn)A周?chē)梢缘竭_(dá)的方格，將它們放入開(kāi)啟列表，并設(shè)置它們的父方格為A。

2）從開(kāi)啟列表中刪除起點(diǎn)A，并將起點(diǎn)A加入關(guān)閉列表（關(guān)閉列表中存放的都是不需要再次檢查的方格），從開(kāi)啟列表中找出相對(duì)最靠譜的方塊，通過(guò)公式F=G+H來(lái)計(jì)算。G表示從起點(diǎn)A移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費(fèi)（可沿斜方向移動(dòng)），H表示從指定的方格移動(dòng)到終點(diǎn)B的預(yù)計(jì)耗費(fèi)，從開(kāi)啟列表中選擇F值最低的方格C。

3）把它從開(kāi)啟列表中刪除，并放到關(guān)閉列表中，檢查它所有相鄰并且可以到達(dá)（障礙物和關(guān)閉列表的方格都不考慮）的方格。如果這些方格還不在開(kāi)啟列表里的話(huà)，將它們加入開(kāi)啟列表，計(jì)算這些方格的G，H和F值各是多少，并設(shè)置它們的父方格C如圖8。

4）如果某個(gè)相鄰方格D已經(jīng)在開(kāi)啟列表里了，檢查如果用新的路徑（就是經(jīng)過(guò)C的路徑）到達(dá)它的話(huà)，G值是否會(huì)更低一些。如果新的G值更低，那就把它的“父方格”改為目前選中的方格C，然后重新計(jì)算它的F值和G值（H值不需要重新計(jì)算，因?yàn)閷?duì)于每個(gè)方塊，H值是不變的）。如果新的G值比較高，就說(shuō)明經(jīng)過(guò)C再到達(dá)D不是一個(gè)明智的選擇，因?yàn)樗枰h(yuǎn)的路，這時(shí)什么也不做。就這樣，從開(kāi)啟列表找出F值最小的，將它從開(kāi)啟列表中移掉，添加到關(guān)閉列表。再繼續(xù)找出它周?chē)梢缘竭_(dá)的方塊，如此循環(huán)下去。

5）當(dāng)我們發(fā)現(xiàn)開(kāi)始列表里出現(xiàn)了目標(biāo)終點(diǎn)方塊的時(shí)候，說(shuō)明路徑已經(jīng)被找到。

3　實(shí)驗(yàn)與分析

3.1實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)是在北京聯(lián)合大學(xué)無(wú)人駕駛智能車(chē)仿真平臺(tái)上進(jìn)行的，如圖9所示，硬件使用平臺(tái)為北汽C70智能車(chē)，軟件為MATLAB R2013b，操作系統(tǒng)Windows 7。

3.2實(shí)驗(yàn)結(jié)果

1）選擇所用的柵格地圖（如圖10）。

2）設(shè)置地圖障礙物位置（如圖11）。

3）A*算法的尋路實(shí)現(xiàn)（如圖12）。

3.3實(shí)驗(yàn)分析

本實(shí)驗(yàn)將高精度地圖以柵格數(shù)據(jù)結(jié)構(gòu)表示，通過(guò)在柵格地圖模型上設(shè)立障礙物，利用A*算法，為機(jī)器人尋找一條恰當(dāng)?shù)膹钠鹗键c(diǎn)到目標(biāo)點(diǎn)的運(yùn)動(dòng)路徑，且可以使機(jī)器人在運(yùn)動(dòng)過(guò)程中安全、無(wú)碰撞地繞過(guò)所有的障礙物。與其他方式相比，雖然用柵格法規(guī)劃地理空間，具有描述規(guī)范、形式簡(jiǎn)單、一致性好、容易實(shí)現(xiàn)、在計(jì)算機(jī)中存儲(chǔ)方便等優(yōu)點(diǎn)，但是利用柵格數(shù)據(jù)模型表示地圖，對(duì)精度有很強(qiáng)的依賴(lài)性，且在復(fù)雜環(huán)境下，搜索空間變大，算法的效率可能降低。

4　結(jié)束語(yǔ)

在分析了智能汽車(chē)宏觀路徑導(dǎo)航和局部軌跡決策所需的道路網(wǎng)絡(luò)信息之后，本文提出了基于高精度地圖的道路網(wǎng)絡(luò)綜合信息表達(dá)方式，將高精度地圖利用柵格數(shù)據(jù)結(jié)構(gòu)表示，結(jié)合A*算法實(shí)現(xiàn)了從環(huán)境初始點(diǎn)尋找最優(yōu)路徑，繞過(guò)障礙物到達(dá)終點(diǎn)。論文所提方法目前還是仿真驗(yàn)證，環(huán)境假設(shè)是理想的靜態(tài)條件，作為一個(gè)在真實(shí)城市半結(jié)構(gòu)化道路上無(wú)人駕駛車(chē)輛的完整路徑規(guī)劃系統(tǒng)，如何進(jìn)行更高效的動(dòng)態(tài)建圖和地圖定位也是目前工作中正研究的重點(diǎn)

［參考文獻(xiàn)］

［1］ 喬維高，徐學(xué)進(jìn).無(wú)人駕駛汽車(chē)的發(fā)展現(xiàn)狀及方向［J］.上海汽車(chē)，2007，40（1）:40-43.

［2］ 馮學(xué)強(qiáng)，張良旭，劉志宗.無(wú)人駕駛汽車(chē)的發(fā)展綜述［J］.山東工業(yè)技術(shù)，2015，51（1）:1-1.

［3］ 徐友春，王榮本.世界智能車(chē)輛近況綜述［J］.汽車(chē)工程，2001，23（5）:289-295.

［4］ 張銀玲，牛小梅.蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的仿真研究［J］.計(jì)算機(jī)仿真，2011，28（6）:231-234.

［5］ 李擎，徐銀，梅張德政，等.基于粒子群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃策略［J］.北京科技大學(xué)學(xué)報(bào)，2010，32（3）:397 -402.

［6］ 石鐵峰.改進(jìn)遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用［J］.計(jì)算機(jī)仿真，2011，28（4）:193-195，303.

［7］ 方鵬.GPS/INS組合導(dǎo)航與定位系統(tǒng)研究［D］.上海:同濟(jì)大學(xué)，2008:1-11.

［8］ 潘吳，胡飛，楊立國(guó).GPS車(chē)載導(dǎo)航系統(tǒng)的地圖匹配算法研究［J］.中國(guó)水運(yùn)，2007，7（11）:174-176.

［9］ 王衛(wèi)華.未知環(huán)境中移動(dòng)機(jī)器人創(chuàng)建地圖的研究［D］.上海:上海交通大學(xué)，2000.

［10］ 姜巖，王琦，龔建偉，等.無(wú)人駕駛車(chē)輛局部路徑規(guī)劃的時(shí)間一致性與魯棒性研究［J］.自動(dòng)化學(xué)報(bào)，2015，41（3）:518-527.

［11］ 羅飛，楊澤超，伯魯江.大地坐標(biāo)換帶計(jì)算在定向井軌跡設(shè)計(jì)中的應(yīng)用［J］.內(nèi)蒙古石油化工，2007，95（6）:1-3.

［12］ 劉飛，周琳琳，益建芳.GPS大地坐標(biāo)向地方坐標(biāo)轉(zhuǎn)換的實(shí)用方法研究［J］.華東師范大學(xué)學(xué)報(bào)，2005，75（1）:1-2.

［13］ 陸州.移動(dòng)機(jī)器人路徑規(guī)劃與路徑跟蹤研究［D］.廣州:華南理工大學(xué)，2012:19-22.

［14］ Pamosoaji A K，Hong K.A path-planning algorithm using vector potential functions in triangular regions［J］.IEEE Trans Syst Man CybernSyst，2013，43（4）:832-842.

［15］ Jaillet L，Porta J M.Path planning under kinematic constraints by rapidly exploring manifolds［J］.IEEE Trans Robot，2013，29（1）:105-117.

［16］ 黃健生.移動(dòng)機(jī)器人的路徑規(guī)劃研究［D］.杭州:浙江大學(xué)，2008:3-8.

（責(zé)任編輯 李亞青）

The Achievement of Path Planning Based on A*Algorithm

GUAN Quan-zhen，BAO Hong，SHI Zhi-jian
（Beijing Key Laboratory of Information Service Engineering，Beijing Union University，Beijing 100101，China）

Abstract:This study uses high-precision map to restore traffic information，combining with A*algorithm to make the driverless car travel according to the planned path without GPS.The high-precision map is presented in the form of raster model.A*algorithm can find a proper path from the starting point to end point for mobile robots in the environment which is presented in the form of raster and full of barriers.Through simulation experiments，it turns out that this method has the advantage of simplification，consistency and easy implementation on computer.

Key words:Path planning；Autonomous navigation；High-precision map；A*algorithm；Raster data model

［中圖分類(lèi)號(hào)］U 491.2

［文獻(xiàn)標(biāo)志碼］A

［文章編號(hào)］1005-0310（2016）02-0031-09

DOI：10.16255/j.cnki.ldxbz.2016.02.006

［收稿日期］2016-03-07

［基金項(xiàng)目］國(guó)家自然科學(xué)基金重大研究計(jì)劃項(xiàng)目（91420202）。

［作者簡(jiǎn)介］關(guān)泉珍（1990-），女，河南省許昌市人，北京聯(lián)合大學(xué)北京市信息服務(wù)工程重點(diǎn)實(shí)驗(yàn)室碩士，主要研究方向?yàn)槁窂揭?guī)劃。

［通訊作者］鮑泓（1958-），男，北京市人，博士，北京聯(lián)合大學(xué)副校長(zhǎng)、教授，博士生導(dǎo)師，主要研究方向?yàn)閳D像處理、智能控制。E-mail:baohong@buu.edu.cn