A*算法的改進(jìn)及其在AGV路徑規(guī)劃中的應(yīng)用

衛(wèi) 珊，王 凌，王斌銳，任海軍，楊永帥，劉緒樂，丁灃城

（1.中國計(jì)量大學(xué)機(jī)電工程學(xué)院，浙江 杭州 310018；2.杭州新松機(jī)器人自動化有限公司，浙江 杭州 311200）

A*算法的改進(jìn)及其在AGV路徑規(guī)劃中的應(yīng)用

衛(wèi) 珊1，王 凌1，王斌銳1，任海軍2，楊永帥2，劉緒樂2，丁灃城2

（1.中國計(jì)量大學(xué)機(jī)電工程學(xué)院，浙江 杭州 310018；2.杭州新松機(jī)器人自動化有限公司，浙江 杭州 311200）

A*算法是一種啟發(fā)式搜索算法，被廣泛應(yīng)用于路徑規(guī)劃中。其中，啟發(fā)函數(shù)的設(shè)計(jì)尤其重要。針對物流工廠中自主移動機(jī)器人AGV運(yùn)行路徑的特點(diǎn)，提出一種A*算法中啟發(fā)函數(shù)的設(shè)計(jì)方法，以提高路徑搜索效率。首先，進(jìn)行環(huán)境地圖建模，使用拓?fù)浣７ǎ瑢GV運(yùn)行地圖轉(zhuǎn)化為圖論中的有向圖，并以鄰接表的形式存儲有向圖中節(jié)點(diǎn)信息和邊信息；然后，研究不同啟發(fā)函數(shù)的選擇對A*算法執(zhí)行效率的影響；最后，對A*算法進(jìn)行改進(jìn)，結(jié)合實(shí)際工廠中AGV路徑特點(diǎn)，研究加權(quán)曼哈頓距離中權(quán)值的選擇對算法執(zhí)行效率的影響，并選取經(jīng)驗(yàn)值進(jìn)行試驗(yàn)。試驗(yàn)結(jié)果表明，與采用曼哈頓距離作為啟發(fā)函數(shù)的A*算法相比，采用改進(jìn)的A*算法平均路徑規(guī)劃效率提高了11.6%。改進(jìn)A*算法在AGV路徑規(guī)劃中可以有效提高路徑搜索的效率，作為一種適用于工廠環(huán)境的AGV的路徑規(guī)劃算法，對A*算法啟發(fā)函數(shù)的設(shè)計(jì)有一定的參考價(jià)值。

AGV；路徑規(guī)劃；最短路徑算法；A*算法；啟發(fā)函數(shù)；曼哈頓距離

0 引言

自主移動機(jī)器人（automated guided vehicle，AGV），作為主要的物流設(shè)備，其柔性好、自動化程度高，被廣泛應(yīng)用于數(shù)字化工廠、倉儲搬運(yùn)系統(tǒng)、柔性制造系統(tǒng)。AGV選擇合理的運(yùn)行路徑進(jìn)行作業(yè)，對于提高企業(yè)的整體生產(chǎn)效率、降低產(chǎn)品的生產(chǎn)成本具有重要意義。

本文著重論述AGV最短路徑規(guī)劃方法。

常用的最短路徑規(guī)劃方法有：Dijkstra算法［1］、A*算法［2］、基于分割的多層算法［3］，此外還有蟻群算法［4］、遺傳算法［5］、粒子群算法等［6-7］。A*算法以其能夠求得接近最優(yōu)解的解、求解速度快及效率高等優(yōu)點(diǎn)而被廣泛使用。

本文提出了一種改進(jìn)的A*算法，并研究了其在AGV最短路徑規(guī)劃中的應(yīng)用。

磁導(dǎo)航AGV的運(yùn)行路徑具有正南正北、正東正西方向規(guī)則布局、沒有斜向路段的特點(diǎn)。文獻(xiàn)［8］和文獻(xiàn)［9］對A*算法的論述中，沒有具體討論啟發(fā)函數(shù)的選取對算法效率的影響，只是簡單介紹A*算法中可以選取的常用啟發(fā)函數(shù)。本文根據(jù)具體的地圖特點(diǎn)，研究不同啟發(fā)函數(shù)對A*算法執(zhí)行效率的影響，進(jìn)而提出一種啟發(fā)函數(shù)的設(shè)計(jì)方法，實(shí)現(xiàn)A*算法的改進(jìn)。將改進(jìn)算法與Dijkstra算法進(jìn)行比較，驗(yàn)證了改進(jìn)A*算法的優(yōu)點(diǎn)和可行性。

1 AGV運(yùn)行環(huán)境建模

在數(shù)字化工廠中，磁導(dǎo)航式AGV通常沿著鋪設(shè)在地面上的磁條從起始點(diǎn)運(yùn)行到目標(biāo)點(diǎn)，完成物料的運(yùn)輸。本文所采用的AGV運(yùn)行地圖是新松機(jī)器人自動化有限公司的數(shù)字化生產(chǎn)線地圖，地圖中共有73個(gè)節(jié)點(diǎn)，代表AGV在運(yùn)行過程中經(jīng)過的和可能停靠的工位點(diǎn)。兩個(gè)節(jié)點(diǎn)之間共形成80條有向路段。

地圖的表示方法主要有：拓?fù)涞貓D表示法、柵格地圖表示法和集合地圖表示法等［10］。

本文采用拓?fù)涞貓D表示法，將AGV運(yùn)行的地圖抽象為圖論中的圖，生成一個(gè)具有V個(gè)頂點(diǎn)和E條邊的有向圖。

最短路徑就是有向圖中的頂點(diǎn)序列，將AGV通過每段路的距離作為每條邊的權(quán)重。本文中的圖屬于稀疏圖，故以鄰接表的形式存儲節(jié)點(diǎn)、邊和邊的權(quán)重信息，降低算法復(fù)雜度。

2 算法簡介

2.1 Dijkstra算法

Dijkstra算法是用于在有向圖或無向圖中的節(jié)點(diǎn)之間找到最短路徑的算法［11-12］。常見的方法是將單個(gè)節(jié)點(diǎn)固定為源節(jié)點(diǎn)，并找到從源節(jié)點(diǎn)到圖中所有其他節(jié)點(diǎn)的最短路徑，形成最短路徑樹。

算法思想：開始節(jié)點(diǎn)被稱為源節(jié)點(diǎn)，某個(gè)節(jié)點(diǎn)的距離是指從初始節(jié)點(diǎn)到該節(jié)點(diǎn)的距離。Dijkstra算法將分配一些初始距離值，并逐步更新節(jié)點(diǎn)的距離值。

2.2 A*算法

A*算法是廣泛用于尋路和圖遍歷的計(jì)算機(jī)算法。由于其具有較好的性能和準(zhǔn)確性，經(jīng)常被使用在最短路徑求解中，是一種啟發(fā)式搜索算法。其成本估計(jì)函數(shù)為：

式中：f（n）為從起始節(jié)點(diǎn)經(jīng)由當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的估計(jì)成本；g（n）為初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際成本；h（n）為從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)n的最佳路徑的估計(jì)成本。

算法思想：A*算法典型的實(shí)現(xiàn)方法是使用優(yōu)先級隊(duì)列來重復(fù)執(zhí)行選擇要擴(kuò)展的最小估計(jì)成本節(jié)點(diǎn)。此優(yōu)先級隊(duì)列稱為開集，在算法的每個(gè)步驟中，從開集中移除具有最低f（n）值的節(jié)點(diǎn)，其相鄰節(jié)點(diǎn)的f（n）和g（n）值被相應(yīng)地更新，并且這些相鄰節(jié)點(diǎn)被添加到隊(duì)列中。算法繼續(xù)進(jìn)行，直到目標(biāo)節(jié)點(diǎn)具有比隊(duì)列中的任何節(jié)點(diǎn)更低的值（或者直到隊(duì)列為空）。該目標(biāo)節(jié)點(diǎn)的值就是最短路徑的長度。

在運(yùn)行此算法之后，目標(biāo)節(jié)點(diǎn)將指向其前導(dǎo)節(jié)點(diǎn)。依此類推，直到某個(gè)節(jié)點(diǎn)的前導(dǎo)是開始節(jié)點(diǎn)，就可以得到最短路徑序列。

A*算法采用了一個(gè)啟發(fā)函數(shù)h（n），使算法利用啟發(fā)信息朝著某個(gè)確定的方向搜索，所以其訪問的節(jié)點(diǎn)比Dijkstra算法少得多，能快速地導(dǎo)向目標(biāo)結(jié)點(diǎn)，訪問到目標(biāo)節(jié)點(diǎn)后算法停止。對于起始點(diǎn)和目標(biāo)點(diǎn)都確定的情況，A*能利用啟發(fā)函數(shù)快速找到目標(biāo)點(diǎn)。

2.3 A*算法代價(jià)估計(jì)函數(shù)

本文選擇A*算法作為最短路徑規(guī)劃的基礎(chǔ)算法，其代價(jià)估計(jì)函數(shù) f（n）=g（n）+h（n）是影響算法運(yùn)行效率的重要因素。

當(dāng)從初始點(diǎn)向目標(biāo)點(diǎn)搜索時(shí)，算法權(quán)衡g（n）、h（n）這兩個(gè)值，每次循環(huán)時(shí)，檢查最小節(jié)點(diǎn)。搜索最短路徑的關(guān)鍵在于啟發(fā)函數(shù)h（n）的選取。h（n）越接近實(shí)際值，搜索效率越高。

理論上，如果 h（n）是 0，則只有 g（n）起作用，此時(shí)A*演變?yōu)镈ijkstra算法。

如果h（n）小于實(shí)際代價(jià)，則算法保證能找到一條最短路徑。隨著h（n）的減小，A*擴(kuò)展的節(jié)點(diǎn)越來越多，算法運(yùn)行得越慢。

如果h（n）正好與實(shí)際代價(jià)相等，那么算法只訪問最佳路徑上的節(jié)點(diǎn)而不擴(kuò)展其余節(jié)點(diǎn)，算法將運(yùn)行得很快。

如果h（n）比實(shí)際代價(jià)大，則算法不一定能找到最短路徑，但會運(yùn)行得更快。如果h（n）比g（n）大很多，則只有h（n）起作用，A*就變成廣度優(yōu)先算法（breadth first search，BFS）。

為了快速地得到最短路徑，關(guān)鍵在于h（n）的選擇。

啟發(fā)函數(shù)h（n）代表當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的代價(jià)估計(jì)，經(jīng)典A*算法通常采用歐幾里得度量（歐氏距離）、Octile距離和曼哈頓距離來表示代價(jià)估計(jì)［13-14］。歐氏距離是常用的一個(gè)空間里兩點(diǎn)間的距離定義，代表兩個(gè)點(diǎn)之間的實(shí)際距離。歐氏距離的估計(jì)代價(jià)值計(jì)算公式如下：

式中：（nx，ny）為算法中訪問的當(dāng)前節(jié)點(diǎn)坐標(biāo)；（goalx，goaly）為目標(biāo)節(jié)點(diǎn)坐標(biāo)。

另一種用來表示代價(jià)估計(jì)的距離是曼哈頓距離，表示兩個(gè)點(diǎn)在標(biāo)準(zhǔn)坐標(biāo)系上的絕對軸距離的和。用曼哈頓距離表示估計(jì)代價(jià)時(shí)：

在AGV運(yùn)行地圖中選擇五組不同起始點(diǎn)的路徑，分別采用Dijkstra算法、基于歐式距離的A*算法和基于曼哈頓距離的A*算法進(jìn)行路徑規(guī)劃，對各個(gè)算法搜到最短路徑所遍歷的節(jié)點(diǎn)數(shù)進(jìn)行統(tǒng)計(jì)。各算法遍歷的節(jié)點(diǎn)數(shù)比較如圖1所示。

圖1 各算法遍歷節(jié)點(diǎn)數(shù)比較圖Fig.1 Comparison of the number of nodes traversed by each algorithm

由圖1可以看出，采用曼哈頓距離的A*算法進(jìn)行路徑規(guī)劃時(shí)，遍歷的節(jié)點(diǎn)數(shù)更接近最短路徑上的節(jié)點(diǎn)數(shù)，即算法效率最高。

3 算法改進(jìn)

工廠環(huán)境中磁導(dǎo)航AGV的運(yùn)行路徑具有正南正北、正東正西方向規(guī)則布局、沒有斜向路段的特點(diǎn)，當(dāng)采用曼哈頓距離作為啟發(fā)信息時(shí)，該距離更接近實(shí)際距離，所以算法效率更高。但對于實(shí)際AGV運(yùn)行路線，如本文地圖中從起點(diǎn)38號節(jié)點(diǎn)到終點(diǎn)1號節(jié)點(diǎn)，用（Lx，Ly）表示當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)實(shí)際路徑長度。由于圖是閉合圖，當(dāng)A*算法運(yùn)行時(shí)，曼哈頓距離中會出現(xiàn)｜nx-goalx｜＜Lx或｜ny-goaly｜＜Ly的情況，所以 A*算法遍歷的節(jié)點(diǎn)算法的數(shù)較多，運(yùn)行速度較慢。

本文提出一種啟發(fā)函數(shù)設(shè)計(jì)方法對A*算法進(jìn)行改進(jìn)，采用加權(quán)啟發(fā)函數(shù)，如式（4）所示。

在地圖中選取不同的起始點(diǎn)，研究W1和W2的不同取值對算法運(yùn)行效率的影響。根據(jù)經(jīng)驗(yàn)，W1的取值范圍為1～6，每組起始點(diǎn)總共36次試驗(yàn)。對三組不同的起始點(diǎn)進(jìn)行路徑規(guī)劃，結(jié)果如圖3所示。

圖2 W1和W2不同取值算法遍歷節(jié)點(diǎn)數(shù)比較圖Fig.2 Comparison of the traversal node numbers under different W1and W2

A*算法在搜索以上最短路徑時(shí)，y方向與實(shí)際路徑相差較多，即｜ny-goaly｜＜Ly；x 方向與實(shí)際相同，即｜nx-goalx｜=Lx。由圖2可以看出，W2越大，遍歷的節(jié)點(diǎn)數(shù)越接近最短路徑上的節(jié)點(diǎn)數(shù)；W1越大，算法遍歷的節(jié)點(diǎn)數(shù)越多。所以對于方向?qū)嶋H路徑復(fù)雜的路徑，設(shè)計(jì)啟發(fā)函數(shù)時(shí)，W1取1，W2取適當(dāng)大的值，可以提高算法效率。

改進(jìn)后的A*算法步驟如下。

①將起點(diǎn)加到OPEN表中，CLOSE表為空。

②判斷OPEN表是否為空，若為空，則算法結(jié)束；否則進(jìn)入下一步。

③將OPEN表中f（n）最小的節(jié)點(diǎn)添加到CLOSE表中，并判斷該節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)。若為目標(biāo)節(jié)點(diǎn)，算法結(jié)束；否則，進(jìn)入下一步。

④找到節(jié)點(diǎn)n的所有相鄰節(jié)點(diǎn)x。若x既不在OPEN表中，又不在CLOSE表中，則計(jì)算f（x）并加入OPEN表中；若x在OPEN表中，但是f（x）比OPEN表中估計(jì)值小，則更新OPEN表中的估計(jì)值，并按從小到大排序；若x在CLOSE表中，則忽略該點(diǎn)。

⑤重復(fù)步驟②～步驟④，直到目標(biāo)點(diǎn)在CLOSE表中，或OPEN表為空，算法結(jié)束。

4 算法測試與試驗(yàn)

4.1 算法測試

本文取W1=1、W2=5，進(jìn)行試驗(yàn)驗(yàn)證，采用改進(jìn)后的代價(jià)估計(jì)函數(shù)如式（5）所示。

作為A*算法中選擇路徑節(jié)點(diǎn)的判斷函數(shù)，在vs2013平臺下按照算法流程編寫算法程序和顯示界面，給定起點(diǎn)12和終點(diǎn)33，路徑搜索結(jié)果為12→7→2→3→4→5→26→27→28→29→31→32→33。

結(jié)合AGV運(yùn)行地圖可知，此算法是可行的，故進(jìn)行多次試驗(yàn)，證明算法的優(yōu)勢。

4.2 試驗(yàn)結(jié)果

在AGV運(yùn)行地圖上給定起點(diǎn)和終點(diǎn)，分別采用基于不同啟發(fā)函數(shù)的A*算法進(jìn)行路徑規(guī)劃，多次試驗(yàn)并記錄最短路徑上的節(jié)點(diǎn)數(shù)以及遍歷的節(jié)點(diǎn)數(shù)。每種算法都能得到相同的最短路徑，所以通過比較得到最短路徑過程中遍歷的節(jié)點(diǎn)數(shù)，分析算法的優(yōu)勢。試驗(yàn)結(jié)果比較如圖3所示。

圖3 試驗(yàn)結(jié)果比較圖Fig.3 Comparison of the test results

5 結(jié)束語

AGV應(yīng)用到數(shù)字化工廠和物流系統(tǒng)中，能提高生產(chǎn)效率，最短路徑規(guī)劃是AGV合理調(diào)度的基礎(chǔ)。磁導(dǎo)航AGV的運(yùn)行路徑具有正南正北、正東正西方向規(guī)則布局、沒有斜向路段的特點(diǎn)。在分析傳統(tǒng)算法的基礎(chǔ)上，重點(diǎn)研究了A*算法中啟發(fā)函數(shù)的選擇，提出了一種啟發(fā)函數(shù)的設(shè)計(jì)方法。該方法更適用于工廠環(huán)境中AGV的路徑規(guī)劃。本文初步定量地分析了啟發(fā)函數(shù)中加權(quán)系數(shù)的選擇問題，對于路徑規(guī)劃優(yōu)化問題中地圖的形狀特點(diǎn)和復(fù)雜性與啟發(fā)函數(shù)的關(guān)系，還有待進(jìn)一步的研究。

［1］ ZHANG J D，F(xiàn)ENG Y J，SHI F F，et al.Vehicle routing in urban areas based on the oil consumption weight dijkstra algorithm［J］.IET Intelligent Transport Systems，2016，10（7）：495-502.

［2］ 李偉光，蘇霞.基于改進(jìn)A*算法的AGV路徑規(guī)劃［J］.現(xiàn)代制造工程，2015（10）：33-36.

［3］張波良，張瑞昌，關(guān)佶紅.道路網(wǎng)上最短路徑算法綜述［J］.計(jì)算機(jī)應(yīng)用與軟件，2014，31（10）：1-9.

［4］ JABBARPOUR M R，ZARRABI H，JUNG J J，et al.A greenantbased method for path planning of unmanned ground vehicles［J］.IEEE Access，2017（5）：1820-1832.

［5］ LEE J，KANG B Y，KIM D W.Fast genetic algorithm for robot path planning［J］.Electronics Letters，2013，49（23）：1449-1451.

［6］ KAPLAN A，KINGRY N，UHING P，et al.Time-optimal path planning with power schedules for a solar-powered ground robot［J］.IEEE Transactions on Automation Science and Engineering，2017，14（2）：1235-1244.

［7］曹有輝，王良曦.基于改進(jìn)粒子群優(yōu)化算法的 AGV全局路徑規(guī)劃［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（27）：224-227.

［8］謝輝輝，胡江，班玉榮.基于A*算法的AGV路徑規(guī)劃的研究［J］.制造業(yè)自動化，2011，33（2）：113-114.

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

［10］朱大奇，顏明重.移動機(jī)器人路徑規(guī)劃技術(shù)綜述［J］.控制與決策，2010，25（7）：961-967.

［11］BROUMI S，TALEA M，BAKALI A，et al.Application of Dijkstra algorithm for solving interval valued neutron sophic shortest path problem［C］//Computational Intelligence（SSCI），2016 IEEE Symposium Series，IEEE，2016：1-6.

［12］SUN Q Y，WAN W G，CHEN G L，et al.Path planning algorithm under specific constraints in weighted directed graph［C］//Audio，Language and Image Processing（ICALIP），2016 International Conference，IEEE，2016：635-640.

［13］KUMAR N，VáMOSSY Z，SZABó-RESCH Z M.Heuristic approaches in robot navigation［C］//Intelligent Engineering Systems（INES）， 2016 IEEE 20th Jubilee International Conference，IEEE，2016：219-222.

［14］趙玉娟，劉擎超.基于混合多距離度量的多分類器加權(quán)集成研究［J］.計(jì)算機(jī)工程，2012，38（21）：172-174.

Improvement of A*Algorithm and Its Application in AGV Path Planning

WEI Shan1，WANG Ling1，WANG Binrui1，REN Haijun1，YANG Yongshuai2，LIU Xule2，DING Fengcheng2
（1.College of Mechanical and Electrical Engineering，China Jiliang University，Hangzhou 310018，China；2.Hangzhou SIASUN Robotamp;Automation Co.，Ltd.，Hangzhou 311200，China）

A*algorithm is a heuristic search algorithm widely used in path planning，in which the design of the heuristic function is particularly important.Considering the features of the operation path of automated guided vehicle（AGV）in logistics factories，a design method of heuristic function in A*algorithm is proposed to improve the efficiency of path search.Firstly，the model of environment map is established using the topological modeling method，and the AGV operation map is transformed into the directed graph in graph theory，and the information of the nodes and edges in the directed graph are stored in the form of adjacency tables.Then，the different heuristic functions in A*algorithm are selected to analyze their impacts to the execution efficiency of A*algorithm.Finally，based on the features of AGV path in the actual factories，the influence of the weighting of the weighted Manhattan distance on the efficiency of the algorithm is studied to improve the A*algorithm；and the empirical value is selected for the experiment.The experimental results show that compared with the A*algorithm using the Manhattan distance as the heuristic function，the improved A*algorithm increases the efficiency of the average path planning by 11.6%.The improved A*algorithm can effectively improve the efficiency of path search in AGV path planning and is suitable for the path planning of AGV in factory environment.The improved A*algorithm can effectively improve the efficiency of path search in AGV path planning.It is suitable for the path planning of AGV factory environment and has certain reference value for the design of A*algorithm heuristic function.

Automated guided vehicle（AGV）；Path planning；Shortest path algorithm；A*algorithm；Heuristic function；Manhattan distance

TH-39；TP24

A

10.16086／j.cnki.issn1000-0380.201711013

修改稿收到日期：2017-06-12

國家自然科學(xué)基金資助項(xiàng)目（51575530）

衛(wèi)珊（1992—），女，在讀碩士研究生，主要研究領(lǐng)域?yàn)锳GV路徑規(guī)劃、多目標(biāo)調(diào)度算法。E-mail：842863961@qq.com。王凌（通信作者），男，博士，副教授，主要研究領(lǐng)域?yàn)闄C(jī)器人技術(shù)與應(yīng)用、故障預(yù)測及維修保障優(yōu)先等。E-mail：wanglingleo@163.com。