A*算法的改進及其在AGV路徑規劃中的應用

衛 珊，王 凌，王斌銳，任海軍，楊永帥，劉緒樂，丁灃城

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

A*算法的改進及其在AGV路徑規劃中的應用

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

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

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

AGV；路徑規劃；最短路徑算法；A*算法；啟發函數；曼哈頓距離

0 引言

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

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

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

本文提出了一種改進的A*算法，并研究了其在AGV最短路徑規劃中的應用。

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

1 AGV運行環境建模

在數字化工廠中，磁導航式AGV通常沿著鋪設在地面上的磁條從起始點運行到目標點，完成物料的運輸。本文所采用的AGV運行地圖是新松機器人自動化有限公司的數字化生產線地圖，地圖中共有73個節點，代表AGV在運行過程中經過的和可能?？康墓の稽c。兩個節點之間共形成80條有向路段。

地圖的表示方法主要有：拓撲地圖表示法、柵格地圖表示法和集合地圖表示法等［10］。

本文采用拓撲地圖表示法，將AGV運行的地圖抽象為圖論中的圖，生成一個具有V個頂點和E條邊的有向圖。

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

2 算法簡介

2.1 Dijkstra算法

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

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

2.2 A*算法

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

式中：f（n）為從起始節點經由當前節點n到目標節點的估計成本；g（n）為初始節點到當前節點n的實際成本；h（n）為從當前節點到目標節點n的最佳路徑的估計成本。

算法思想：A*算法典型的實現方法是使用優先級隊列來重復執行選擇要擴展的最小估計成本節點。此優先級隊列稱為開集，在算法的每個步驟中，從開集中移除具有最低f（n）值的節點，其相鄰節點的f（n）和g（n）值被相應地更新，并且這些相鄰節點被添加到隊列中。算法繼續進行，直到目標節點具有比隊列中的任何節點更低的值（或者直到隊列為空）。該目標節點的值就是最短路徑的長度。

在運行此算法之后，目標節點將指向其前導節點。依此類推，直到某個節點的前導是開始節點，就可以得到最短路徑序列。

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

2.3 A*算法代價估計函數

本文選擇A*算法作為最短路徑規劃的基礎算法，其代價估計函數 f（n）=g（n）+h（n）是影響算法運行效率的重要因素。

當從初始點向目標點搜索時，算法權衡g（n）、h（n）這兩個值，每次循環時，檢查最小節點。搜索最短路徑的關鍵在于啟發函數h（n）的選取。h（n）越接近實際值，搜索效率越高。

理論上，如果 h（n）是 0，則只有 g（n）起作用，此時A*演變為Dijkstra算法。

如果h（n）小于實際代價，則算法保證能找到一條最短路徑。隨著h（n）的減小，A*擴展的節點越來越多，算法運行得越慢。

如果h（n）正好與實際代價相等，那么算法只訪問最佳路徑上的節點而不擴展其余節點，算法將運行得很快。

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

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

啟發函數h（n）代表當前節點到目標節點的代價估計，經典A*算法通常采用歐幾里得度量（歐氏距離）、Octile距離和曼哈頓距離來表示代價估計［13-14］。歐氏距離是常用的一個空間里兩點間的距離定義，代表兩個點之間的實際距離。歐氏距離的估計代價值計算公式如下：

式中：（nx，ny）為算法中訪問的當前節點坐標；（goalx，goaly）為目標節點坐標。

另一種用來表示代價估計的距離是曼哈頓距離，表示兩個點在標準坐標系上的絕對軸距離的和。用曼哈頓距離表示估計代價時：

在AGV運行地圖中選擇五組不同起始點的路徑，分別采用Dijkstra算法、基于歐式距離的A*算法和基于曼哈頓距離的A*算法進行路徑規劃，對各個算法搜到最短路徑所遍歷的節點數進行統計。各算法遍歷的節點數比較如圖1所示。

圖1 各算法遍歷節點數比較圖Fig.1 Comparison of the number of nodes traversed by each algorithm

由圖1可以看出，采用曼哈頓距離的A*算法進行路徑規劃時，遍歷的節點數更接近最短路徑上的節點數，即算法效率最高。

3 算法改進

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

本文提出一種啟發函數設計方法對A*算法進行改進，采用加權啟發函數，如式（4）所示。

在地圖中選取不同的起始點，研究W1和W2的不同取值對算法運行效率的影響。根據經驗，W1的取值范圍為1～6，每組起始點總共36次試驗。對三組不同的起始點進行路徑規劃，結果如圖3所示。

圖2 W1和W2不同取值算法遍歷節點數比較圖Fig.2 Comparison of the traversal node numbers under different W1and W2

A*算法在搜索以上最短路徑時，y方向與實際路徑相差較多，即｜ny-goaly｜＜Ly；x 方向與實際相同，即｜nx-goalx｜=Lx。由圖2可以看出，W2越大，遍歷的節點數越接近最短路徑上的節點數；W1越大，算法遍歷的節點數越多。所以對于方向實際路徑復雜的路徑，設計啟發函數時，W1取1，W2取適當大的值，可以提高算法效率。

改進后的A*算法步驟如下。

①將起點加到OPEN表中，CLOSE表為空。

②判斷OPEN表是否為空，若為空，則算法結束；否則進入下一步。

③將OPEN表中f（n）最小的節點添加到CLOSE表中，并判斷該節點是否為目標節點。若為目標節點，算法結束；否則，進入下一步。

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

⑤重復步驟②～步驟④，直到目標點在CLOSE表中，或OPEN表為空，算法結束。

4 算法測試與試驗

4.1 算法測試

本文取W1=1、W2=5，進行試驗驗證，采用改進后的代價估計函數如式（5）所示。

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

結合AGV運行地圖可知，此算法是可行的，故進行多次試驗，證明算法的優勢。

4.2 試驗結果

在AGV運行地圖上給定起點和終點，分別采用基于不同啟發函數的A*算法進行路徑規劃，多次試驗并記錄最短路徑上的節點數以及遍歷的節點數。每種算法都能得到相同的最短路徑，所以通過比較得到最短路徑過程中遍歷的節點數，分析算法的優勢。試驗結果比較如圖3所示。

圖3 試驗結果比較圖Fig.3 Comparison of the test results

5 結束語

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

［1］ ZHANG J D，FENG 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］ 李偉光，蘇霞.基于改進A*算法的AGV路徑規劃［J］.現代制造工程，2015（10）：33-36.

［3］張波良，張瑞昌，關佶紅.道路網上最短路徑算法綜述［J］.計算機應用與軟件，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］曹有輝，王良曦.基于改進粒子群優化算法的 AGV全局路徑規劃［J］.計算機工程與應用，2009，45（27）：224-227.

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

［9］鐘建琳，ANDRZEJM.制造環境中AGV運輸子系統的路徑規劃［J］.機械設計與制造，2010（2）：237-239.

［10］朱大奇，顏明重.移動機器人路徑規劃技術綜述［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］趙玉娟，劉擎超.基于混合多距離度量的多分類器加權集成研究［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

國家自然科學基金資助項目（51575530）

衛珊（1992—），女，在讀碩士研究生，主要研究領域為AGV路徑規劃、多目標調度算法。E-mail：842863961@qq.com。王凌（通信作者），男，博士，副教授，主要研究領域為機器人技術與應用、故障預測及維修保障優先等。E-mail：wanglingleo@163.com。