基于改進A*算法的一種智能車路徑規劃方法

荊學東， 陳亞楠

(上海應用技術大學機械工程學院， 上海 201418)

隨著時代的發展，AGV(automated guided vehicle)智能車技術已經得到深入的發展，廣泛用于服務方面的移動助行、輔助搬運等方面，具有十分廣泛的應用領域[1-2]。同時，自動路徑規劃對于智能車自主移動和路線優化具有重要意義，根據環境地理信息數據，智能車需要自主尋找出一條從初始點到最終目標點的安全最短路徑已成為主要趨勢[3-5]。導航技術發展至今已有多種方法被應用，例如模擬退火算法、神經網絡算法、人工勢場法、遺傳算法[6]、粒子群優化算法、蟻群算法道路規劃方法、圖搜索法[7]。A*算法因為其特定的算法結構具有較強的全局搜索能力和較高的搜索效率，因而更有可能搜索到全局最優解，是目前移動機器人路徑規劃中應用較多的一種方法[8-9]。文獻[10]提出一種結合跳點搜索算法的改進A*算法來提高A*算法內存占用大，計算時間久的問題；為提高算法局部搜索性問題，文獻[11]提出一種結合天牛須搜索算法的改進算法；文獻[12]在傳統A*算法中引入轉彎因素，改進了路徑的平滑性。

基于以上問題，提出一種改進算法，在傳統A*算法基礎上結合圖論[13]對初始路徑方向進行選擇，剔除無效路徑，提高算法的計算效率；同時利用幾何方法去除路徑中多余的拐點，在改善規劃路徑的平滑性的同時考慮路徑的最短特性。最后通過Labview仿真實驗對改進算法的可行性和有效性進行驗證。

1 A*算法的改進及實現辦法

改進A*算法的基本流程如圖1所示。

圖1 改進A*算法流程圖Fig.1 Improved A* algorithm flow chart

具體實施步驟如下。

步驟1區域劃分，利用圖論原理將地圖區域劃分，并建立相關路徑的有向圖，得到可行區域之間關聯矩陣和鄰接矩陣。

步驟2柵格地圖中以起始點為當前點，將所有與P相鄰的可行區域加入可open列表中，表示可行路徑區域。

步驟3在open列表中極端每一塊與A相鄰的區域Pi的路徑增量值，選擇路徑增量最小區域作為下一個路徑點，如圖2所示。同時將A放入close列表中，表示不可行路徑區域。

圖2 路徑點選擇示例Fig.2 Example of path point selection

步驟4若Pi是目標點，結束；若Pi不是目標點，繼續進行步驟3。

步驟5判斷P、Pi連線是否穿過障礙物，若是，則剔除Pi，將改點加入close，重復步驟3選擇新的Pi，否則重復步驟4。

計算每個可行區域的路徑增量模型為：F=H+G，其中F表示路徑增量總量；G表示起始點到當前點的移動量；H表示當前點到目標點的移動估計量，移動估計量采用曼哈頓距離法，即不考慮障礙物只計算當前點到目標點的水平和豎直距離之和。

1.1 環境模型的建立

使用的實際環境為實驗室環境，如圖3所示,無儀器地面為可行路徑，中間的桌椅以及儀器視為障礙物。

圖3 實驗室真實環境全景圖Fig.3 Panoramic view of the laboratory

1.2 區域劃分

將利用Labview對實際地圖進行簡化，并利用圖論原理將簡化環境地圖劃分為13個可行區域：Start、A1、A2、A3、B1、B2、C1、C2、D1、D2、E1、E2、End，如圖4所示，采用有向圖理論，通過有向線段將其連接成一個有向圖，如圖5所示。那么基于有向圖理論從Start 到End 的路徑問題可以轉化圖5所示一個簡單有向圖G，字母表示該范圍的矩形可行區域，邊e表示區域之間的關系即有公共邊界。

圖4 簡化環境圖區域劃分Fig.4 Division of the environmental map areas

圖5 路徑有向圖GFig.5 The path directed graph G

圖中任意兩點的路徑問題對應的圖關系為G=(V(G),E(G),φG)，其中：V(G)中的元素表示圖G的頂點，E(G)中的元素表示G的邊,φG是關聯函數，它使E(G)中每一個元素對應于V(G)中的一個無序元素對。其中：用bij表示頂點vi與邊ej關聯的次數(取值為0,1，2)，得到圖G的有向關聯矩陣B(G)：

(1)

有向關聯矩陣B(G)表示的是各個區域之間的關聯性，1表示正向關聯，-1表示反向關聯，0表示沒有關聯。

圖G=(V,E)的頂點集為：V={Start,A1,…,End }，用aij表示G中頂點vi與vj之間的邊數，得到圖G的鄰接矩陣M(G)：

(2)

給每個邊賦予一個權值，邊表示路徑，邊上的權值表示路徑的長度。

結合關聯矩陣與鄰接矩陣，可以對器人路徑規劃進行指導，關聯矩陣得到出發點與終點之間的路徑選擇，結合鄰接矩陣權值得到路徑的初步篩選。

1.3 路徑的可行性因素

采用幾何向量方法檢測相鄰路徑點連線是否與障礙物邊界有干涉來進行路徑可行性的判斷，如圖6所示。

圖6 路徑干涉檢測模型Fig.6 Path interference detection model

判斷同一平面上兩根線段AB、CD是否交叉，其中各個點坐標分別為A(a1,a2)、B(b1,b2)、C(c1,c2)、D(d1,d2)，判斷線段交叉轉換為判斷點A點B是否跨立于線段CD的兩側。

運用向量的基本法則，得到

(3)

顯然，對u的正負進行判斷就可以判斷出線段AB是否與線段CD交叉。當u>0時，線段AB與線段CD沒有交點，無干涉；當u≤0時，線段AB與線段CD有交點，干涉直接將該點剔除，并加入close。

2 仿真

采用Labview對改進A*算法進行驗證，并與A*算法進行對比，如圖7所示為算法中路徑規劃程序。

具體操作如圖7所示，首先初始導入環境地圖信息，設置起始點以及終點位置，改進算法進行規劃并輸出路徑信息。在35×35柵格環境中對A*算法進行驗證，黑色柵格表示障礙物，白色柵格表示可行區域，藍色表示可達路徑。驗證結果如圖8所示。

如圖8所示改進的A*算法可以有效地找到最優路徑，并且路徑光順拐點少。拐點數以及路徑長度對比如表1所示。

表1 算法拐點數與路徑長度對比

為驗證方法在復雜環境下的可行性，在原有地圖下以及起始點目標點不變前提下，對環境地圖進行復雜化改變，路徑規劃結果如圖9所示。

圖9所示在復雜環境下，改進的A*算法相對于A*算法而言同樣可以有效地找到最優路。拐點數以及路徑長度如表2所示。

由表1、表2可以看出，改進A*算法在保證路徑最短前提下均可得到平滑光順的路徑。

圖7 Labview路徑規劃程序Fig.7 Path planning program of Labview

圖8 起始點(0,0)到目標點(35,13)的路徑規劃圖Fig.8 The path diagram from (0,0) to (35,13)

圖9 復雜環境下的起始點(0,0)到目標點(35,13)的路徑規劃Fig.9 The path diagram from (0,0) to (35,13) of complex environment

表2 復雜環境下算法拐點數與路徑長度對比

3 結論

根據智能車路徑規劃問題，提出一種改進A*算法，得出以下結論。

(1)在傳統A*算法上做出改進，應用圖論理論對路徑進行規劃，提前對路徑選擇進行優化，提高了軌跡規劃效率。

(2)在保證最短路徑的前提下，在路徑選擇過程中采用幾何法去除多余拐點，得到了相對平滑光順的路徑。更符合智能車的運動規律。

(3)通過Labview仿真驗證了改進算法的有效性。可以在復雜的環境中得到的路徑較短且平滑的軌跡規劃策略。