基于A*算法的AGV路徑規(guī)劃的研究

謝輝輝，胡 江，班玉榮

XIE Hui-hui，HU Jiang，BAN Yu-rong

（北京機械工業(yè)自動化研究所，北京 100120）

0 引言

隨著生產(chǎn)技術(shù)和生產(chǎn)管理水平的進(jìn)步，柔性好，自動化程度高和智能化水平高的AGVS（Automated Guided Vehicles System，自動導(dǎo)向車）越來越多的應(yīng)用于生產(chǎn)中間的過程物流輸送。而對于AGVS而言，選擇正確而有效的路徑，可以提高運輸效率，從而降低運輸成本。本文將著重論述AGV運輸系統(tǒng)的路徑規(guī)劃。

1 概述

將AGV運行涉及的區(qū)域用笛卡爾坐標(biāo)系表示，將AGV小車可能停留的點和分叉路口的點作為節(jié)點保存，那么AGV小車從一點到達(dá)另一點的路徑規(guī)劃就可以轉(zhuǎn)換為圖論搜索法。該方法現(xiàn)在運用比較多的有Dijkstra算法、Floyd算法和A*算法等，其中A*算法因搜索過程效率較高而被較多使用。下面具體介紹一下A*算法的原理。

2 A＊算法原理

A*算法是一種啟發(fā)式搜索算法。之所以叫啟發(fā)式算法，是因為該算法會在搜索過程中獲得問題自身的一些特性信息來指導(dǎo)搜索，這些特性信息主要作用是對節(jié)點的重要性進(jìn)行評估，通過這個評估來實現(xiàn)對狀態(tài)空間的可能位置進(jìn)行排序，得出最小代價的位置，在狀態(tài)空間中對每一個節(jié)點進(jìn)行評估，得到最優(yōu)的節(jié)點，再從這個節(jié)點出發(fā)進(jìn)行下一節(jié)點的搜索，直到尋找到目標(biāo)節(jié)點。

評估函數(shù)：

f（n）=g（n）+h（n）----f*（n）=g*（n）+h*（n）

其中：

--節(jié)點n是搜索圖中當(dāng)前被擴展的節(jié)點

--f（n）是從初始狀態(tài)經(jīng)由節(jié)點n到達(dá)目標(biāo)節(jié)點的所有路徑中最小路徑大家f*（n）的估計值

--g（n）是從初始節(jié)點到節(jié)點n的最小代價g*（n）

--h（n）是從節(jié)點n到達(dá)目標(biāo)節(jié)點的最優(yōu)路徑代價h*（n）的估計代價啟發(fā)函數(shù)

并且有如下限制：h（n）＜h*（n）

A*算法實現(xiàn)的步驟：

1）建立一個OPEN表和CLOSE表，OPEN表中放入剛生成的節(jié)點,CLOSE表中放入已經(jīng)擴展或?qū)⒁獢U展的節(jié)點

2）將起點放入OPEN表中；

3）在圖中搜索與起點相通的節(jié)點，判斷其中是否含有終點，如果有，則結(jié)束搜索，若沒有，則將與之相通的所有節(jié)點放入OPEN表中，將起點放入CLOSE表中

4）將OPEN表中的點按照估價函數(shù)f（n）的值排序，選出最小值的節(jié)點，將其作為下一個擴展結(jié)點，將該最小節(jié)點放入CLOSE表中，重復(fù)步驟4），直至OPEN表中出現(xiàn)終點

這樣，CLOSE表中所存儲的點就是A*算法得出的路徑。

3 A＊算法的實例

本文針對如下簡單路徑采用A*算法進(jìn)行了模擬，將AGV活動區(qū)域形成“地圖”，并將AGV可能起始的點、到達(dá)的點與路口分叉點作為節(jié)點記錄到“地圖”中，在AGV接受任務(wù)時，只需輸入起始目的節(jié)點，該系統(tǒng)就會算出路徑。

圖1 路徑圖

如圖1所示，點1到點10以及點14為AGV的加載點，點11到13是AGV的卸載點，點A到點J是分岔路點。在AGV活動區(qū)域內(nèi)建立笛卡爾坐標(biāo)系，把AGV每一個可能停留點設(shè)置為節(jié)點表明它的坐標(biāo)，所有的節(jié)點記錄為AGV的活動地圖。

點A（10,0）B（20,0）C（30,0）D（40,0）E（10,10）,F（20,10）,G（30,10）,H（40,10）,I（0,0）,J（50,0）為交叉點；點1（3,0），2（7,0），3（13,0），4（17,0），5（23，0），6（27,0），7（33,0），8（37,0），9（43,0），10（47,0），11（15,10），12（25,10），13（35,10），14（50,10）為AGV的起始點或者終點。選取每一個節(jié)點到終點的直線距離作為h*（n）函數(shù)，即

在數(shù)據(jù)庫中建立表格，把每個節(jié)點相鄰節(jié)點記錄到表中，同時在另一張表中記錄他們的坐標(biāo)位置，從起點開始計算每一個相鄰節(jié)點到目標(biāo)節(jié)點的距離，即h*（n），選取其中最小值作為下一個節(jié)點，然后再次計算距離，再次排序，直到到達(dá)終點。例如選取節(jié)點1到節(jié)點14的路徑，步驟為：

1）選擇1的兩個分叉點A和I,距離L（A）=41.23,L（I）=50.99,選A點，將點I計入CLOSE表；

2）選擇A的三個點I,E,B,L（E）=40,L（B）=31.62,比較三點距離后，比較候選點I,E,B選擇B點，將點E計入CLOSE表；

3）選擇B的三個點A,F,C,L（F）=30,L（C）=22.36,比較候選點I,E,A,F,C選擇C點，將F計入CLOSE表；

4）選擇C的三個點B，G,D,L（G）=20,L（D）=10,比較候選點I,E,A,C,B,G,D選擇D點，將G點計入CLOSE表

5）選擇D的三個點C,J,H,L（J）=10,L（H）=10,比較候選點I,E,A,C,B,G,J,H,從點J，H中任意選擇一點，如H

6）選擇與H有關(guān)的點，發(fā)現(xiàn)存在目標(biāo)節(jié)點14，搜索完畢

最后到達(dá)終點，路徑為：1—A—B—C—D—J—14

圖2是采用A*算法進(jìn)行AGV路徑規(guī)劃的應(yīng)用程序界面，在該應(yīng)用程序中，只需在界面上輸入起始目的結(jié)點，點擊“計算路徑”按鈕，就會輸出AGV從起始點到目的節(jié)點所應(yīng)經(jīng)過的節(jié)點，然后AGV可根據(jù)這些點的坐標(biāo)位置進(jìn)行路徑選擇，從而引導(dǎo)AGV直到目標(biāo)節(jié)點。

圖2 采用A*算法進(jìn)行AGV路徑規(guī)劃的應(yīng)用程序界面

4 結(jié)論

從上例的模擬計算可以看出，可以很容易算單臺AGV起點到終點的最終路徑，并且該h*（n）的選取保證了所選路段為距離最優(yōu)的路段，比較符合對AGV路徑規(guī)劃的要求。但在實際的生產(chǎn)環(huán)境中，會有多臺AGV同時運行，所選路徑會涉及到碰撞、死鎖等問題，需要在路徑規(guī)劃的基礎(chǔ)上增加對這些問題的復(fù)雜運算。這些需要根據(jù)現(xiàn)場的環(huán)境要求對h*（n）和f*（n）做綜合的評估和選取，以此來滿足不同要求的路徑。

[1]鐘建琳.制造環(huán)境中AGV運輸子系統(tǒng)的路徑規(guī)劃[J].機械設(shè)計與制造,2010（2）：237-239.

[2]林堯瑞,馬少平.人工智能導(dǎo)論[M].北京：清華大學(xué)出版社.