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

謝輝輝，胡 江，班玉榮

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

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

0 引言

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

1 概述

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

2 A＊算法原理

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

評(píng)估函數(shù)：

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

其中：

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

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

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

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

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

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

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

2）將起點(diǎn)放入OPEN表中；

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

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

這樣，CLOSE表中所存儲(chǔ)的點(diǎn)就是A*算法得出的路徑。

3 A＊算法的實(shí)例

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

圖1 路徑圖

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

點(diǎn)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）為交叉點(diǎn)；點(diǎn)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的起始點(diǎn)或者終點(diǎn)。選取每一個(gè)節(jié)點(diǎn)到終點(diǎn)的直線(xiàn)距離作為h*（n）函數(shù)，即

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

1）選擇1的兩個(gè)分叉點(diǎn)A和I,距離L（A）=41.23,L（I）=50.99,選A點(diǎn)，將點(diǎn)I計(jì)入CLOSE表；

2）選擇A的三個(gè)點(diǎn)I,E,B,L（E）=40,L（B）=31.62,比較三點(diǎn)距離后，比較候選點(diǎn)I,E,B選擇B點(diǎn)，將點(diǎn)E計(jì)入CLOSE表；

3）選擇B的三個(gè)點(diǎn)A,F,C,L（F）=30,L（C）=22.36,比較候選點(diǎn)I,E,A,F,C選擇C點(diǎn)，將F計(jì)入CLOSE表；

4）選擇C的三個(gè)點(diǎn)B，G,D,L（G）=20,L（D）=10,比較候選點(diǎn)I,E,A,C,B,G,D選擇D點(diǎn)，將G點(diǎn)計(jì)入CLOSE表

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

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

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

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

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

4 結(jié)論

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

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

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