基于A*算法的AGV路徑規劃的研究

謝輝輝，胡 江，班玉榮

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

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

0 引言

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

1 概述

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

2 A＊算法原理

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

評估函數：

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

其中：

--節點n是搜索圖中當前被擴展的節點

--f（n）是從初始狀態經由節點n到達目標節點的所有路徑中最小路徑大家f*（n）的估計值

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

--h（n）是從節點n到達目標節點的最優路徑代價h*（n）的估計代價啟發函數

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

A*算法實現的步驟：

1）建立一個OPEN表和CLOSE表，OPEN表中放入剛生成的節點,CLOSE表中放入已經擴展或將要擴展的節點

2）將起點放入OPEN表中；

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

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

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

3 A＊算法的實例

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

圖1 路徑圖

如圖1所示，點1到點10以及點14為AGV的加載點，點11到13是AGV的卸載點，點A到點J是分岔路點。在AGV活動區域內建立笛卡爾坐標系，把AGV每一個可能停留點設置為節點表明它的坐標，所有的節點記錄為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的起始點或者終點。選取每一個節點到終點的直線距離作為h*（n）函數，即

在數據庫中建立表格，把每個節點相鄰節點記錄到表中，同時在另一張表中記錄他們的坐標位置，從起點開始計算每一個相鄰節點到目標節點的距離，即h*（n），選取其中最小值作為下一個節點，然后再次計算距離，再次排序，直到到達終點。例如選取節點1到節點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有關的點，發現存在目標節點14，搜索完畢

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

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

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

4 結論

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

[1]鐘建琳.制造環境中AGV運輸子系統的路徑規劃[J].機械設計與制造,2010（2）：237-239.

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