謝輝輝，胡 江，班玉榮

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

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

0 引言

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

1 概述

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

2 A＊算法原理

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

評估函數(shù)：

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

其中：

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

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

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

--h（n）是從節(jié)點n到達目標節(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表中，重復步驟4），直至OPEN表中出現(xiàn)終點

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

3 A＊算法的實例

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

圖1 路徑圖

如圖1所示，點1到點10以及點14為AGV的加載點，點11到13是AGV的卸載點，點A到點J是分岔路點。在AGV活動區(qū)域內(nèi)建立笛卡爾坐標系，把AGV每一個可能停留點設(shè)置為節(jié)點表明它的坐標，所有的節(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é)點記錄到表中，同時在另一張表中記錄他們的坐標位置，從起點開始計算每一個相鄰節(jié)點到目標節(jié)點的距離，即h*（n），選取其中最小值作為下一個節(jié)點，然后再次計算距離，再次排序，直到到達終點。例如選取節(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)存在目標節(jié)點14，搜索完畢

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

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

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

4 結(jié)論

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

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

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