基于改進(jìn)A*算法的一種智能車路徑規(guī)劃方法

荊學(xué)東， 陳亞楠

(上海應(yīng)用技術(shù)大學(xué)機(jī)械工程學(xué)院， 上海 201418)

隨著時(shí)代的發(fā)展，AGV(automated guided vehicle)智能車技術(shù)已經(jīng)得到深入的發(fā)展，廣泛用于服務(wù)方面的移動助行、輔助搬運(yùn)等方面，具有十分廣泛的應(yīng)用領(lǐng)域[1-2]。同時(shí)，自動路徑規(guī)劃對于智能車自主移動和路線優(yōu)化具有重要意義，根據(jù)環(huán)境地理信息數(shù)據(jù)，智能車需要自主尋找出一條從初始點(diǎn)到最終目標(biāo)點(diǎn)的安全最短路徑已成為主要趨勢[3-5]。導(dǎo)航技術(shù)發(fā)展至今已有多種方法被應(yīng)用，例如模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法、人工勢場法、遺傳算法[6]、粒子群優(yōu)化算法、蟻群算法道路規(guī)劃方法、圖搜索法[7]。A*算法因?yàn)槠涮囟ǖ乃惴ńY(jié)構(gòu)具有較強(qiáng)的全局搜索能力和較高的搜索效率，因而更有可能搜索到全局最優(yōu)解，是目前移動機(jī)器人路徑規(guī)劃中應(yīng)用較多的一種方法[8-9]。文獻(xiàn)[10]提出一種結(jié)合跳點(diǎn)搜索算法的改進(jìn)A*算法來提高A*算法內(nèi)存占用大，計(jì)算時(shí)間久的問題；為提高算法局部搜索性問題，文獻(xiàn)[11]提出一種結(jié)合天牛須搜索算法的改進(jìn)算法；文獻(xiàn)[12]在傳統(tǒng)A*算法中引入轉(zhuǎn)彎因素，改進(jìn)了路徑的平滑性。

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

1 A*算法的改進(jìn)及實(shí)現(xiàn)辦法

改進(jìn)A*算法的基本流程如圖1所示。

圖1 改進(jìn)A*算法流程圖Fig.1 Improved A* algorithm flow chart

具體實(shí)施步驟如下。

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

步驟2柵格地圖中以起始點(diǎn)為當(dāng)前點(diǎn)，將所有與P相鄰的可行區(qū)域加入可open列表中，表示可行路徑區(qū)域。

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

圖2 路徑點(diǎn)選擇示例Fig.2 Example of path point selection

步驟4若Pi是目標(biāo)點(diǎn)，結(jié)束；若Pi不是目標(biāo)點(diǎn)，繼續(xù)進(jìn)行步驟3。

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

計(jì)算每個(gè)可行區(qū)域的路徑增量模型為：F=H+G，其中F表示路徑增量總量；G表示起始點(diǎn)到當(dāng)前點(diǎn)的移動量；H表示當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的移動估計(jì)量，移動估計(jì)量采用曼哈頓距離法，即不考慮障礙物只計(jì)算當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的水平和豎直距離之和。

1.1 環(huán)境模型的建立

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

圖3 實(shí)驗(yàn)室真實(shí)環(huán)境全景圖Fig.3 Panoramic view of the laboratory

1.2 區(qū)域劃分

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

圖4 簡化環(huán)境圖區(qū)域劃分Fig.4 Division of the environmental map areas

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

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

(1)

有向關(guān)聯(lián)矩陣B(G)表示的是各個(gè)區(qū)域之間的關(guān)聯(lián)性，1表示正向關(guān)聯(lián)，-1表示反向關(guān)聯(lián)，0表示沒有關(guān)聯(lián)。

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

(2)

給每個(gè)邊賦予一個(gè)權(quán)值，邊表示路徑，邊上的權(quán)值表示路徑的長度。

結(jié)合關(guān)聯(lián)矩陣與鄰接矩陣，可以對器人路徑規(guī)劃進(jìn)行指導(dǎo)，關(guān)聯(lián)矩陣得到出發(fā)點(diǎn)與終點(diǎn)之間的路徑選擇，結(jié)合鄰接矩陣權(quán)值得到路徑的初步篩選。

1.3 路徑的可行性因素

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

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

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

運(yùn)用向量的基本法則，得到

(3)

顯然，對u的正負(fù)進(jìn)行判斷就可以判斷出線段AB是否與線段CD交叉。當(dāng)u>0時(shí)，線段AB與線段CD沒有交點(diǎn)，無干涉；當(dāng)u≤0時(shí)，線段AB與線段CD有交點(diǎn)，干涉直接將該點(diǎn)剔除，并加入close。

2 仿真

采用Labview對改進(jìn)A*算法進(jìn)行驗(yàn)證，并與A*算法進(jìn)行對比，如圖7所示為算法中路徑規(guī)劃程序。

具體操作如圖7所示，首先初始導(dǎo)入環(huán)境地圖信息，設(shè)置起始點(diǎn)以及終點(diǎn)位置，改進(jìn)算法進(jìn)行規(guī)劃并輸出路徑信息。在35×35柵格環(huán)境中對A*算法進(jìn)行驗(yàn)證，黑色柵格表示障礙物，白色柵格表示可行區(qū)域，藍(lán)色表示可達(dá)路徑。驗(yàn)證結(jié)果如圖8所示。

如圖8所示改進(jìn)的A*算法可以有效地找到最優(yōu)路徑，并且路徑光順拐點(diǎn)少。拐點(diǎn)數(shù)以及路徑長度對比如表1所示。

表1 算法拐點(diǎn)數(shù)與路徑長度對比

為驗(yàn)證方法在復(fù)雜環(huán)境下的可行性，在原有地圖下以及起始點(diǎn)目標(biāo)點(diǎn)不變前提下，對環(huán)境地圖進(jìn)行復(fù)雜化改變，路徑規(guī)劃結(jié)果如圖9所示。

圖9所示在復(fù)雜環(huán)境下，改進(jìn)的A*算法相對于A*算法而言同樣可以有效地找到最優(yōu)路。拐點(diǎn)數(shù)以及路徑長度如表2所示。

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

圖7 Labview路徑規(guī)劃程序Fig.7 Path planning program of Labview

圖8 起始點(diǎn)(0,0)到目標(biāo)點(diǎn)(35,13)的路徑規(guī)劃圖Fig.8 The path diagram from (0,0) to (35,13)

圖9 復(fù)雜環(huán)境下的起始點(diǎn)(0,0)到目標(biāo)點(diǎn)(35,13)的路徑規(guī)劃Fig.9 The path diagram from (0,0) to (35,13) of complex environment

表2 復(fù)雜環(huán)境下算法拐點(diǎn)數(shù)與路徑長度對比

3 結(jié)論

根據(jù)智能車路徑規(guī)劃問題，提出一種改進(jìn)A*算法，得出以下結(jié)論。

(1)在傳統(tǒng)A*算法上做出改進(jìn)，應(yīng)用圖論理論對路徑進(jìn)行規(guī)劃，提前對路徑選擇進(jìn)行優(yōu)化，提高了軌跡規(guī)劃效率。

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

(3)通過Labview仿真驗(yàn)證了改進(jìn)算法的有效性?？梢栽趶?fù)雜的環(huán)境中得到的路徑較短且平滑的軌跡規(guī)劃策略。