A*算法在無人車路徑規劃中的應用

馬 靜，王佳斌，張 雪

(西安工業大學 計算機科學與工程學院，陜西 西安 710021)

A*算法在無人車路徑規劃中的應用

馬 靜，王佳斌，張 雪

(西安工業大學 計算機科學與工程學院，陜西 西安 710021)

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

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

0 引 言

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

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

1 柵格法創建環境地圖

環境地圖的創建是無人車運轉的基本條件，在機器人學中地圖的表示信息創建方法有四種：拓撲地圖[4]、特征地圖[5]、直接表征法及柵格地圖[6]。其中柵格法是通過將環境信息劃分成一系列柵格，通過給柵格一個可能值來表示該柵格被占用的概率。在環境地圖構建中，首先給所處環境建立二維坐標系，并對起始點、目標點、障礙物所在柵格設定不同標志，進而構造出一張環境狀態柵格圖。經過無人車平臺測試，能夠體現A*算法的執行效果。

2 尋徑算法分類

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

2.1 盲目式搜索

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

2.2 啟發式搜索

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

3 基于柵格的路徑規劃算法

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

3.1 基于柵格構圖下的Dijkstra算法的最短路徑規劃

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

圖1 帶權有向圖G

3.1.1Dijkstra算法基本思想

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

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

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

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

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

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

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

3.1.2 算法實現

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

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

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

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

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

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

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

3.2 基于柵格構圖下的A*算法最短路徑規劃

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

圖2 無人車環境建模

3.2.1A*算法

圖3 A*柵格

3.2.2A*算法實施策略

A*算法評價函數為：

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

其中，F'(n)為起始節點經由節點n到目標節點的評估函數；G'(n)為起始節點到當前節點n的最優路徑值，其為已經確定的值；H'(n)作為A*算法評價函數的核心，其為當前節點n到目標節點的啟發值，即預估開銷。

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

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

創建兩個表OPEN和CLOSED，其中OPEN表保存所有已經生成而未考察的節點，CLOSED表保存已訪問過的節點。

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

2.重復執行以下步驟：

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

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

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

①如果其為障礙物或者已經移入CLOSED表中，則忽略掉此節點。

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

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

④將目標節點加入OPEN表中，即表示路徑已經找到，否則查找失敗，且OPEN為空，即無路徑。

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

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

4 電子羅盤

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

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

4.1 設定下一步行走方向標志和車頭實時方向標志

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

123804765

圖4 柵格地圖方向

4.2 兩個標志結合實現路徑規劃

設定標志位dir，令dir=dir_sg-dir_lp，并設定無人車最小調轉量為45°，最終通過dir值確定無人車調轉方向和角度。無人車具體調轉策略如下：

(1)當1≤dir≤4,無人車右轉，轉角為 dir*45°；

(2)當4≤dir≤7,無人車左轉，轉角為(8-dir)*45°；

(3)當-4≤dir≤(-1),無人車左轉，轉角為|dir|*45°；

(4)當-7≤dir<(-4)，無人車右轉，轉角為(8-|dir|)*45°。

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

5 結束語

在無人車路徑規劃項目中，利用柵格法構建地圖，A*算法來搜索從起點到終點的最優行駛路徑，同時利用電子羅盤作為無人車行駛的導向，通過實驗和仿真無人車能夠尋找一條從起始狀態到目標狀態的無碰撞路徑。柵格法劃歸地圖并結合A*算法實現路徑規劃，是靜態環境下無人車自主尋徑的研究，對后續在動態環境下無人車自主尋徑的研究打下了基礎，也是該項目進一步研究的方向。

[1] 李江抒.多移動機器人路徑規劃算法與導航系統研究[D].長春：吉林大學,2004.

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

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

[4] 王 娜.移動機器人拓撲地圖創建研究[D].濟南：山東大學,2009.

[5] 熊 蓉.室內未知環境線段特征地圖構建[D].杭州：浙江大學,2009.

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

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

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

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

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

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

[12] 譚浩強，陳 明.實用數據結構基礎[M].北京:清華大學出版社，2002.

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

[14] 顧 青,豆風鉛,馬 飛.基于改進A*算法的電動車能耗最優路徑規劃[J].農業機械學報，2015，46(12):316-322.

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

[16] 王勇軍,李 智,李 翔.三軸電子羅盤的設計與誤差校正[J].傳感器與微系統，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

國家大學生創新創業項目(201410702037)；西安工業大學跨學科研究基金(CXY1340-6)

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

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