馬 靜，王佳斌，張 雪

(西安工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710021)

A*算法在無人車路徑規(guī)劃中的應(yīng)用

馬 靜，王佳斌，張 雪

(西安工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710021)

近年來，無人車路徑規(guī)劃已經(jīng)成為智能機(jī)器人研究的基礎(chǔ)和核心方向之一，其為多學(xué)科技術(shù)研究提供了更加廣闊的平臺。針對路徑規(guī)劃算法進(jìn)行研究，在理論模擬的基礎(chǔ)上，結(jié)合車體的有向性實現(xiàn)智能車的路徑規(guī)劃策略。路徑規(guī)劃是無人車智能化的重要標(biāo)志，也作為實現(xiàn)無人車自主導(dǎo)航的基礎(chǔ)。以自主設(shè)計搭建的無人小車為實驗平臺，針對路徑規(guī)劃算法進(jìn)行研究，在對Dijkstra算法等常用的路徑規(guī)劃算法進(jìn)行優(yōu)缺點分析后，選擇了A*算法并實現(xiàn)了該算法。在理論模擬的基礎(chǔ)上，對環(huán)境進(jìn)行柵格化處理，并通過車體上的電子羅盤獲取實時方向，結(jié)合A*算法進(jìn)行車輛調(diào)轉(zhuǎn)策略設(shè)置，最終實現(xiàn)了無人車路徑規(guī)劃策略。

無人車；路徑規(guī)劃；柵格地圖；Dijkstra算法；A*算法；電子羅盤

0 引 言

無人車作為研究的熱點問題之一，其研究方向主要包含傳感器信息采集與融合技術(shù)、地圖創(chuàng)建技術(shù)、圖像識別和圖像處理技術(shù)、導(dǎo)航及定位技術(shù)、路徑規(guī)劃技術(shù)以及車體控制技術(shù)等[1]。路徑規(guī)劃旨在實現(xiàn)無人車從起始狀態(tài)到目標(biāo)狀態(tài)的一條最優(yōu)或者近似最優(yōu)的無碰撞路徑。由于所處環(huán)境信息的不同，路徑規(guī)劃方案有兩種：一種是基于已知的、靜態(tài)的全局無人車路徑規(guī)劃方案；另一種是基于未知的、動態(tài)的局部無人車路徑規(guī)劃方案。

文中的無人車是以自制的、基于ARM Cortex-M3內(nèi)核[2]的STM32系列處理器，并通過電子羅盤等傳感器進(jìn)行導(dǎo)向的“西工1號”作為實驗研究平臺。其主要是通過對已知環(huán)境狀況進(jìn)行柵格處理后，通過A*算法進(jìn)行路徑引導(dǎo)，并結(jié)合電子羅盤捕獲的車體實時方向，最終實現(xiàn)已知靜態(tài)環(huán)境下無人車的全局最短無碰撞路徑規(guī)劃[3]。

1 柵格法創(chuàng)建環(huán)境地圖

環(huán)境地圖的創(chuàng)建是無人車運轉(zhuǎn)的基本條件，在機(jī)器人學(xué)中地圖的表示信息創(chuàng)建方法有四種：拓?fù)涞貓D[4]、特征地圖[5]、直接表征法及柵格地圖[6]。其中柵格法是通過將環(huán)境信息劃分成一系列柵格，通過給柵格一個可能值來表示該柵格被占用的概率。在環(huán)境地圖構(gòu)建中，首先給所處環(huán)境建立二維坐標(biāo)系，并對起始點、目標(biāo)點、障礙物所在柵格設(shè)定不同標(biāo)志，進(jìn)而構(gòu)造出一張環(huán)境狀態(tài)柵格圖。經(jīng)過無人車平臺測試，能夠體現(xiàn)A*算法的執(zhí)行效果。

2 尋徑算法分類

針對尋徑問題總結(jié)出的算法有很多種。在圖論中，其主旨是解決從起點A到目標(biāo)點B的一條通路問題。但在網(wǎng)絡(luò)游戲中，尋徑問題就變得更加復(fù)雜，考慮的因素更多，如游戲地圖中，相關(guān)障礙物是否能夠通過，以及目標(biāo)點所在瓷磚能否通過等。針對不同環(huán)境的尋徑問題，通常將地圖尋徑算法分為兩大類，分別為盲目式搜索和啟發(fā)式搜索。

2.1 盲目式搜索

盲目搜索作為一種傳統(tǒng)的搜索算法，其主要采用的辦法有深度優(yōu)先搜索(Depth First Search)[7]、廣度優(yōu)先搜索(Breadth-First Search)[8]以及等價搜索。當(dāng)針對這種問題進(jìn)行搜索時，往往是采用某種固定的搜索方式進(jìn)行搜索，不利用需解決問題的相關(guān)信息。因此其不利于進(jìn)行一些較為復(fù)雜的尋徑問題，因為這樣會占用大量的計算空間和時間。

2.2 啟發(fā)式搜索

啟發(fā)式搜索[9](Heuristic Algorithm)就是在所構(gòu)建的環(huán)境地圖中，以起點A的相鄰位置作為評估點，針對每個評估點的值進(jìn)行比較，得到一個最佳的位置B，進(jìn)而再以B的相鄰位置作為下一部分評估點，直到最終找到目標(biāo)點。通過這樣的辦法可以省去大量無用的路徑搜索，從而提高效率。在啟發(fā)式搜索中，對位置的評估是至關(guān)重要的，即選擇的算法不同，其評估策略有所不同。常用的啟發(fā)式算法有最好優(yōu)先搜索法、局部擇優(yōu)搜索法等等，其中A*算法就是一種最好的優(yōu)先算法。

3 基于柵格的路徑規(guī)劃算法

在無人車路徑規(guī)劃問題上，首先應(yīng)解決對環(huán)境的建模問題，其次應(yīng)解決的是尋找合適的算法實現(xiàn)路徑規(guī)劃策略。其中常有的路徑規(guī)劃算法有Dijkstra算法、A*算法、遺傳算法[10]、蟻群算法[11]等。

3.1 基于柵格構(gòu)圖下的Dijkstra算法的最短路徑規(guī)劃

Dijkstra算法[12]使用了廣度優(yōu)先搜索解決非負(fù)權(quán)有向圖的單元路徑規(guī)劃問題，它是典型的單元最短路徑算法，用于計算一個節(jié)點到其他節(jié)點的最短路徑，是很有代表性的最短路徑算法。主要特點是以起始點為中心，向外層進(jìn)行層層擴(kuò)展，直到終點為止。如圖1所示，在帶權(quán)有向圖G中從出發(fā)點即源點V0到目標(biāo)點V5尋找一條最優(yōu)路徑。

圖1 帶權(quán)有向圖G

3.1.1Dijkstra算法基本思想

按路徑長度遞增次序產(chǎn)生最短路徑算法，把V分成兩組：

(1)S：已求出最短路徑的頂點集合。

(2)V-S=T：尚未確定最短路徑的頂點集合。

將T中頂點按最短路徑遞增的次序加入到S中，并確保(1)從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度。

(3)每個頂點對應(yīng)一個距離值。

S中頂點：從V0到此頂點的最短路徑長度。

T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度。

3.1.2 算法實現(xiàn)

(1)初始時令S={V0},T={其余頂點}，T中頂點對應(yīng)的距離值：

若存在，d(V0,Vi)為弧上的權(quán)值；

若不存在，d(V0,Vi)為∝。

(2)從T中選取一個其距離值為最小的頂點W且不在S中，加入S。

(3)對S中頂點的距離值進(jìn)行修改：若加進(jìn)W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值。

重復(fù)上述步驟(2)、(3)，直到S中包含所有頂點，即W=Vi為止。

Dijkstra算法的成功率很高，它總能找到兩點間的最短路徑，但算法的時間復(fù)雜度為O(n2)，效率比較低，并且空間占用率較大，在路徑規(guī)劃中會受到地圖大小以及節(jié)點個數(shù)的影響，因此搜索的速度較慢。

3.2 基于柵格構(gòu)圖下的A*算法最短路徑規(guī)劃

通過柵格法對無人車所處環(huán)境進(jìn)行建模，如圖2所示，并設(shè)定無人車的起點S和目標(biāo)點G。在起點S和終點G之間通過算法選擇一條最優(yōu)或者近似最優(yōu)的無碰撞路徑。A*算法作為一種典型的啟發(fā)式算法，在人工智能尋徑問題中具有很廣泛的應(yīng)用，其將整個環(huán)境構(gòu)造成柵格狀，通過設(shè)定起點S、目標(biāo)點G和障礙物B(灰色)，并通過相應(yīng)的評價函數(shù)來進(jìn)行最優(yōu)路徑分析，最終查找出最優(yōu)路徑。查找出最優(yōu)路徑后，通過與電子羅盤的結(jié)合，實現(xiàn)從仿真到實際的最短路徑規(guī)劃[13]。

圖2 無人車環(huán)境建模

3.2.1A*算法

圖3 A*柵格

3.2.2A*算法實施策略

A*算法評價函數(shù)為：

F'(n)=G'(n)+H'(n)

其中，F(xiàn)'(n)為起始節(jié)點經(jīng)由節(jié)點n到目標(biāo)節(jié)點的評估函數(shù)；G'(n)為起始節(jié)點到當(dāng)前節(jié)點n的最優(yōu)路徑值，其為已經(jīng)確定的值；H'(n)作為A*算法評價函數(shù)的核心，其為當(dāng)前節(jié)點n到目標(biāo)節(jié)點的啟發(fā)值，即預(yù)估開銷。

預(yù)估方法通常有兩種：第一種為Manhattan預(yù)估方法[14]，即計算通過水平和垂直方向的平移到達(dá)目的所經(jīng)過的方格數(shù)值的移動開銷；第二種為Euclidean預(yù)估方法[15]，即計算當(dāng)前節(jié)點n到目標(biāo)節(jié)點的距離的移動開銷。在此，文中采用第一種評估方法。

對于A*算法的搜索過程如下：

創(chuàng)建兩個表OPEN和CLOSED，其中OPEN表保存所有已經(jīng)生成而未考察的節(jié)點，CLOSED表保存已訪問過的節(jié)點。

1.將S點放入OPEN表中，并且將CLOSED表置為空。

2.重復(fù)執(zhí)行以下步驟：

(1)遍歷OPEN，查找F'(n)min并將其作為預(yù)處理節(jié)點。

(2)將步驟(1)得到的節(jié)點移入CLOSED表中。

(3)對于當(dāng)前節(jié)點的8個相鄰節(jié)點的每一個節(jié)點作如下處理：

①如果其為障礙物或者已經(jīng)移入CLOSED表中，則忽略掉此節(jié)點。

②如果其不在OPEN表中，則將其移入OPEN表，并將當(dāng)前節(jié)點設(shè)置為其父節(jié)點，并記錄F'(n)值。

③如果其已經(jīng)在OPEN表中，通過G'(n)對OPEN表中節(jié)點再進(jìn)行判斷，如果有更小值，則將其父節(jié)點設(shè)置為當(dāng)前節(jié)點，并重新計算F'(n)和G'(n)。

④將目標(biāo)節(jié)點加入OPEN表中，即表示路徑已經(jīng)找到，否則查找失敗，且OPEN為空，即無路徑。

(4)保存路徑，路徑即為從目標(biāo)節(jié)點開始，沿著父節(jié)點移動至起始節(jié)點所組成。

A*算法作為一種典型的啟發(fā)式搜索算法，在人工智能尋徑問題有著廣泛的應(yīng)用。其不必遍歷所有節(jié)點，搜尋速度快，但由于評估進(jìn)行移動開銷預(yù)測，所以可能存在找不到最優(yōu)路徑的問題，有待于同其他尋徑算法的對比論證和后期的改進(jìn)。

4 電子羅盤

電子羅盤[16]能實時提供移動物體的航向和姿態(tài)，是一種重要的導(dǎo)航工具，也是路徑規(guī)劃技術(shù)研究中不可缺少的導(dǎo)向傳感器。MAG3110是高精度的數(shù)字地磁傳感器，方向定位準(zhǔn)確，校準(zhǔn)數(shù)據(jù)掉電保存。該羅盤分為3個軸，能定位準(zhǔn)確的獨立羅盤航向信息。在文中所提到的無人車路徑規(guī)劃中，主要用到X軸和Y軸，在水平面上為無人車的車頭方向進(jìn)行定位。

通過電子羅盤和A*算法結(jié)合實現(xiàn)路徑規(guī)劃，基于柵格地圖的A*算法確定無人車行駛的路徑，電子羅盤確定無人車實時車頭方向。

4.1 設(shè)定下一步行走方向標(biāo)志和車頭實時方向標(biāo)志

在柵格法構(gòu)建的地圖中，對中心柵格的相鄰8個方向進(jìn)行標(biāo)識，如圖4所示。其中，“0”代表無人車當(dāng)前所處位置，“1”到“8”為無人車下一步可能行進(jìn)的方向的標(biāo)志。通過A*算法得到的路徑來設(shè)定無人車下一步行進(jìn)方向的方向標(biāo)志位dir_sg，即dir_sg的值可能為“1”到“8”的任意值。通過電子羅盤對無人車車頭實時方向進(jìn)行判斷，設(shè)定8個方向標(biāo)志位，用dir_lp表示。如圖4所示，“1”到“8”為dir_lp可能取得的值。

123804765

圖4 柵格地圖方向

4.2 兩個標(biāo)志結(jié)合實現(xiàn)路徑規(guī)劃

設(shè)定標(biāo)志位dir，令dir=dir_sg-dir_lp，并設(shè)定無人車最小調(diào)轉(zhuǎn)量為45°，最終通過dir值確定無人車調(diào)轉(zhuǎn)方向和角度。無人車具體調(diào)轉(zhuǎn)策略如下：

(1)當(dāng)1≤dir≤4,無人車右轉(zhuǎn)，轉(zhuǎn)角為 dir*45°；

(2)當(dāng)4≤dir≤7,無人車左轉(zhuǎn)，轉(zhuǎn)角為(8-dir)*45°；

(3)當(dāng)-4≤dir≤(-1),無人車左轉(zhuǎn)，轉(zhuǎn)角為|dir|*45°；

(4)當(dāng)-7≤dir<(-4)，無人車右轉(zhuǎn)，轉(zhuǎn)角為(8-|dir|)*45°。

例如，當(dāng)前車頭所指方向為“4”，即dir_lp=4，參考圖4。以無人車當(dāng)前所處柵格作為標(biāo)志位為“0”柵格，并且通過A*算法確定下一步無人車要行進(jìn)的柵格的標(biāo)志位為“2”，即dir_sg=2。通過公式dir=dir_sg-dir_lp得dir=(-2),根據(jù)調(diào)轉(zhuǎn)策略(3)可知，無人車左轉(zhuǎn)|-2|*45°=90°，即無人車通過左轉(zhuǎn)90°后車頭可調(diào)整到目標(biāo)方向，到達(dá)目標(biāo)方向后前進(jìn)即可到達(dá)目標(biāo)柵格。

5 結(jié)束語

在無人車路徑規(guī)劃項目中，利用柵格法構(gòu)建地圖，A*算法來搜索從起點到終點的最優(yōu)行駛路徑，同時利用電子羅盤作為無人車行駛的導(dǎo)向，通過實驗和仿真無人車能夠?qū)ふ乙粭l從起始狀態(tài)到目標(biāo)狀態(tài)的無碰撞路徑。柵格法劃歸地圖并結(jié)合A*算法實現(xiàn)路徑規(guī)劃，是靜態(tài)環(huán)境下無人車自主尋徑的研究，對后續(xù)在動態(tài)環(huán)境下無人車自主尋徑的研究打下了基礎(chǔ)，也是該項目進(jìn)一步研究的方向。

[1] 李江抒.多移動機(jī)器人路徑規(guī)劃算法與導(dǎo)航系統(tǒng)研究[D].長春：吉林大學(xué),2004.

[2] 林恒杰.對基于ARM Cortex-M3嵌入式系統(tǒng)的仿真[D].上海：上海交通大學(xué),2008.

[3] 劉淑華，夏 菁，孫學(xué)敏，等.已知環(huán)境下一種高效全覆蓋路徑規(guī)劃算法[J].東北師大學(xué)報:自然科學(xué)版,2012,43(4):39-43.

[4] 王 娜.移動機(jī)器人拓?fù)涞貓D創(chuàng)建研究[D].濟(jì)南：山東大學(xué),2009.

[5] 熊 蓉.室內(nèi)未知環(huán)境線段特征地圖構(gòu)建[D].杭州：浙江大學(xué),2009.

[6] 陳曉娥，蘇 理.一種基于環(huán)境柵格地圖的多機(jī)器人路徑規(guī)劃方法[J].機(jī)械科學(xué)與技術(shù)，2009，28(10)：1335-1339.

[7] 劉中華，張穎超.深度優(yōu)先搜索的非遞歸算法[J].科技信息,2010(25)：160-161.

[8] 劉 翔，龔道雄.深度優(yōu)先搜索算法和A*算法在迷宮搜索中的仿真研究[J].制造業(yè)自動化,2011,33(11)：101-104.

[9] 樂美龍，李 貞.基于深度優(yōu)先搜索算法的機(jī)組復(fù)原研究[J].武漢理工大學(xué)學(xué)報，2012，34(9)：63-68.

[10] 孫樹棟，林 茂.基于遺傳算法的多移動機(jī)器人協(xié)調(diào)路徑規(guī)劃[J].自動化學(xué)報，2000,26(5):672-676.

[11] 段海濱,王道波,朱家強(qiáng),等.蟻群算法理論及應(yīng)用研究的進(jìn)展[J].控制與決策，2004,19(12):1321-1326.

[12] 譚浩強(qiáng)，陳 明.實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)[M].北京:清華大學(xué)出版社，2002.

[13] 樊 莉,孫繼銀,王 勇.人工智能中的A*算法應(yīng)用及編程[J].微機(jī)發(fā)展(現(xiàn)更名：計算機(jī)技術(shù)與發(fā)展)，2003，13(5):33-35.

[14] 顧 青,豆風(fēng)鉛,馬 飛.基于改進(jìn)A*算法的電動車能耗最優(yōu)路徑規(guī)劃[J].農(nóng)業(yè)機(jī)械學(xué)報，2015，46(12):316-322.

[15] 王殿君.基于改進(jìn)A*算法的室內(nèi)移動機(jī)器人路徑規(guī)劃[J].清華大學(xué)學(xué)報:自然科學(xué)版，2012,52(8):1085-1089.

[16] 王勇軍,李 智,李 翔.三軸電子羅盤的設(shè)計與誤差校正[J].傳感器與微系統(tǒng)，2010，29(10):110-112.

Application of A* Algorithm in Unmanned Vehicle Path Planning

MA Jing,WANG Jia-bin,ZHANG Xue

(School of Computer Science and Engineering,Xi’an Technological University,Xi’an 710021,China)

In recent years,path planning for unmanned vehicle is the basis and one of the core directions in intelligent robot research,which provides an extensive platform for multidisciplinary technology research.Aiming at the path planning,on the basis of theoretic simulation,the path planning strategy for intelligent vehicles is realized combining the direction of vehicle.Path planning is an important symbol of unmanned vehicle intelligence,also as a basis for autonomous navigation of unmanned vehicles.Taking unmanned vehicle of autonomous design as experiment platform,in view of the path planning algorithm for research,after analyzing the advantage and disadvantage for common path planning algorithms like Dijkstra,the A* algorithm is selected and implemented.On the basis of the theoretical simulation,rasterizing the environment,and through electronic compass in vehicle to get real-time direction,the A* algorithm is combined to carry out the vehicle shift strategy,finally realizing unmanned vehicle path planning strategy.

unmanned vehicle;path planning;grid map;Dijkstra algorithm;A*algorithm;electronic compass

2016-01-29

2016-05-11

時間：2016-10-24

國家大學(xué)生創(chuàng)新創(chuàng)業(yè)項目(201410702037)；西安工業(yè)大學(xué)跨學(xué)科研究基金(CXY1340-6)

馬 靜(1980-)，女，研究生，講師，研究方向為嵌入式系統(tǒng)。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1117.068.html

TP242.6

A

1673-629X(2016)11-0153-04

10.3969/j.issn.1673-629X.2016.11.034