基于交通約束及多元啟發函數的改進A*算法*

張金越，侯至丞，張 弓，王衛軍，楊文林

( 廣州中國科學院先進技術研究所機器人與智能裝備中心,廣州 511458)

0 引言

路徑規劃是指移動機器人基于某些特定的準則，在環境中存在障礙物的前提下，自主規劃一條從起始位置到目標位置的安全、無碰撞的最短路徑。隨著自主移動機器人的快速發展，路徑規劃成為了一個熱門的研究問題。

現階段，國內外眾多學者已取得了大量關于路徑規劃的研究成果：馬浩浩等[1]對傳統遺傳算法中的種群初始化、交叉算子以及變異算子進行改進，設計了機器人路徑規劃算法，有效提高了算法的效率；吳東林等[2]基于人工勢場法設計了采摘機器人的動態路徑規劃系統，具有很好地避障和路徑規劃的能力；陸皖麟等[3]在A*算法的基礎上添加閾值減少了搜索柵格的數量，并結合了Floyd算法去除了多余節點，使得規劃的路徑短且光滑；劉彩霞[4]提出了一種基于模糊推理的PSO路徑規劃算法，解決了移動機器人路徑規劃質量不佳的問題；Jabbarpour M R等[5]針對現有路徑規劃算法無法降低UGV能耗的問題，將能耗預測模型與蟻群算法相結合，在減少計算時間和迭代次數的同時，規劃出低功耗的無碰撞最短路徑；Zhang H等[6]為防止RRT算法對配置空間的過度搜索，引入了回歸機制，提高了規劃的成功率和效率。在上述的路徑規劃算法中，遺傳算法、蟻群算法以及粒子群算法能否規劃出最優路徑取決于各參數的選取；基于引力與斥力的原理的人工勢場法容易陷入受力平衡而出現目標不可達的情況[7]；RRT算法存在搜索效率較低、用時較長的缺陷[8]；而A*算法在編程方式簡單的前提下能夠有效地搜索到最優解。

對于多AGV的避碰問題，常見的避碰算法包括區域控制方法、時間窗法、交通約束法等[9]。其中，區域控制法容易在物品的傳遞環節浪費大量時間，降低工作效率；而時間窗法是利用AGV的行進速度預測其經過每一節點的時間，若AGV的速度發生變化，則會降低預測結果的可信度；交通約束法根據日常生活中的交通規則，通過優先級的高低進行減速避讓，有效地實現AGV間的避碰。

綜上所述，對于單一AGV，A*算法在路徑規劃的研究工作中一定程度提高了最優路徑的搜索效率，但所規劃的路徑往往拐角數過多[10]，而AGV每次轉彎都需要經歷加減速的過程，大量的拐角會增加AGV完成路徑行走的時間、能耗；而存在多AGV時，交通約束法能夠有效地解決AGV間的避碰問題，并且降低系統規劃路徑時的計算量。

因此，本文將研究采用一種基于交通約束及多元啟發函數的A*算法，對傳統的A*算法進行優化，引入交通約束，并在原有的啟發函數的基礎上，添加拐角數的評判指標，構成多元啟發函數，在保證規劃出最短路徑的前提下，實現拐角數最優。

1 環境建模

環境建模即根據工作環境特點建立的抽象化地圖，是AGV進行路徑規劃的先決條件。現階段常用的環境建模方法包括：柵格法、拓撲法、幾何信息法等[11]。

柵格法是將AGV的工作環境劃分為多個大小一致的柵格，采用二值信息表示自由空間和障礙物區域。拓撲法[12]是將環境劃分為多個具有一定拓撲特征的子空間，根據子空間的連通性構建拓撲網絡并進行搜索路徑的方法。幾何信息法利用環境信息提取出幾何特征，再使用這些幾何信息進行環境建模。

圖1 貨架布局示意圖

由于本文所依托的項目主要執行貨架上貨物的搬運任務，貨架的布局具體如圖1所示，其中，黑色區域為貨架，白色區域為自由空間。

出于建模方便、編程易于實現等因素的考慮，本文采用柵格法進行環境建模。按照AGV實際的工作環境，建立一個12×10大小的柵格地圖，并根據通行狀態將該地圖劃分為可通行的白色自由區域以及不可通行的黑色障礙物區域。同時為了更好地描述柵格位置，本文采用坐標的形式對柵格進行編號，定義地圖左下角的坐標為(1,1)，橫坐標從左到右、縱坐標從下到上逐個遞增，相鄰柵格坐標值相差1。

2 A*算法設計

2.1 交通約束法

交通約束即對AGV的行進過程添加交通規則的約束，使得AGV在某一通道上只能沿特定方向行進。

AGV在正常行進的過程中，常見的會遇態勢包括對遇、交叉等，具體如圖2所示。

(a)AGV對遇 (b)AGV交叉圖2 常見的AGV會遇態勢

上述的兩種情況，都會對AGV的正常行進產生影響：當兩AGV在同一通道對遇時，由于各自下一步指令均為前進，故陷入了死鎖的現象；在兩AGV出現交叉的局面時，因兩者下一節點相同、會出現碰撞的情況，因此也停留在原地不動。

在引入交通約束法后，同一通道上的AGV只能沿著一個方向行進，此時AGV交叉會遇的現象將不復存在；而對于交叉的情況，AGV會根據自身所賦予的優先級大小進行下一步動作：停車避讓或者繼續前行。

相比于時間窗法，本文所采用的交通約束法的優勢在于不用預測每臺AGV到達每個節點的時間，無需考慮AGV在工作時受到其他因素干擾而發生速度變化的問題[13]，同時減少了會遇的類型，有效避免了AGV在通道內的碰撞問題，減少了在工作環境中的碰撞幾率，具有更強穩定性。

2.2 傳統A*算法

A*算法是一種典型的啟發式搜索算法，傳統的A*算法主要從垂直和水平方向進行搜索：從起始點開始，沿著垂直和水平方向進行搜索點的擴展，通過啟發函數f(n)估計擴展點的代價值，同時將擴展點存入open列表中，再將open列表中選取代價值最小的節點作為下一次搜索的起點,并將該點從open列表中移除，重復上述步驟直至找到目標點。

由上述的A*算法的工作原理可知，其成功與否主要取決于啟發函數f(n)，啟發函數的表達式[14]為：

f(n)=g(n)+h(n)

(1)

式中，g(n)為起始點到當前點n的實際代價，h(n)為當前點n到目標點的估計代價，本文采用曼哈頓距離進行兩點間的代價預估：

D=|xn-xg|+|yn-yg|

(2)

式中，xnyn分別為當前點n的橫坐標和縱坐標，xgyg分別為目標點g的橫坐標和縱坐標。

當前進方向為障礙物或為地圖的邊緣時，此時該方向的代價為無窮大。

由于傳統A*算法所采用的啟發函數主要進行距離的評判，因此當出現多個代價相同的節點時，算法將隨機選擇一個節點作為下一次搜索的起點，這導致了所規劃的路徑雖長度最短，但拐角數并非最優的問題。

2.3 基于多元啟發函數的A*算法

針對上述的問題，本文在原有A*算法的基礎上，添加了拐角數的評判指標，構成多元啟發函數。當算法中出現多個代價相同的候選節點時，觸發拐角數評判機制，對行進至候選節點的路徑上的拐角數進行比較。改進后的啟發函數表達式如下：

f(n)=g(n)+h(n)+a×N

(3)

(4)

(5)

在改進后的啟發函數表達式中，a為拐角數評判機制的觸發函數，N為拐角數，m表示在原始啟發函數中除n點外的最小代價點。

當存在兩個及以上的最小代價點(即g(n)+h(n)=g(m)+h(m))時，式(5)中b=1，根據式(4)可得a=1，此時觸發了啟發函數中的拐角數評判機制，滿足代價最小的點進行式(3)的比較，最終選擇f值最小的點作為算法路徑選擇的下一個節點；當僅存在一個最小代價點時，b≠1，此時a=0，拐角數評判機制未能觸發，故該點默認為算法路徑選擇的下一個節點。

拐角數的統計步驟具體如下：獲取當前節點A的坐標(A1,A2)，節點A的父節點B的坐標(B1,B2)，以及節點B的父節點C的坐標(C1,C2)，當A1-B1≠B1-C1且A2-B2≠B2-C2，則說明路徑出現了拐角，此時節點A的拐角數=節點B的拐角數+1。

改進后的A*算法具體步驟如下[14]：

(1)設置一個open列表和close列表，并將起始節點放入open列表中；

(2)遍歷搜索open列表中存在的節點，根據啟發函數確定代價f(n)大小，將f(n)值最小的節點n作為算法路徑選擇的下一節點，將該節點從open列表中刪除并添加到close列表；若存在多個f(n)值最小的節點，則觸發拐角數評判機制，選擇拐角數最少的點作為下一個節點；

(3)判斷節點n是否為目標節點，若為目標節點，則結束算法；否則，則進行下一步；

(4)搜索節點n鄰域內所有符合搜索要求的子節點m，計算所有待搜索節點的f(m)值，選擇f(m)值最小的節點m作為算法路徑選擇的下一個節點；

(5)若節點m不在open列表和close列表中，則將其添加到open列表中，并為子節點m添加一個指針指向其父節點n；若節點m在open列表中，則對比之前存儲在open列表中的函數值，保留函數值小的數值；若節點在close列表中，則該節點已在當前最優路徑上，返回上一步繼續對比擴展其他子節點；

(6)循環步驟 (2)～步驟 (6)，但算法尋找到目標節點或open列表為空時，結束算法。

當算法尋到目標節點時，以目標節點為起點，沿著每個方格的父節點移動至起點，即可獲取最優路徑。算法流程圖3所示。

圖3 基于多元啟發函數的A*算法流程

2.4 基于交通約束及多元啟發函數的A*算法

在多AGV系統中，為了使AGV在自主規劃路徑的前提下，減少AGV間的路徑重疊程度，降低AGV間的避碰幾率，提高系統的工作效率，本文將交通約束法與改進后的基于多元啟發函數A*算法相結合，實現AGV的路徑規劃。

多AGV系統的運行流程圖如圖4所示，單臺AGV在獲取地圖信息后，根據地圖上各點的交通約束條件，調用基于多元啟發函數的A*算法進行路徑規劃；當AGV的制定的路徑遇到其他AGV時，根據兩者的優先級進行避讓行為。

圖4 多AGV系統運行流程圖

3 仿真與分析

為了驗證改進后的基于交通約束及多元啟發函數的A*算法的效果，本文在MATLAB軟件上進行算法仿真，其中起始點和目標點的位置是隨機生成的。柵格的大小為12×10，代表AGV路徑規劃區域的大小，黑色的方格代表障礙物的位置。

本文通過實驗對傳統的A*算法(記為算法1)、基于多元啟發函數A*算法(記為算法2)和基于交通約束及多元啟發函數的A*算法(記為算法3)所規劃的路徑進行對比、分析。

實驗1：單臺AGV的路徑規劃。起點為(2，11)，目標點為(9，2)，具體的仿真結果如圖5所示，圖中圓點為起點，方點為目標點。

(a) 算法1 (b) 算法2(c) 算法3

為了更好地驗證改進A*算法的優越性，本文將實驗1中3種算法在路徑長度和拐角數量兩項主要指標進行了比較，如表1所示。

表1 三種算法在實驗1中的結果比較

通過對仿真圖的觀察以及對路徑長度、拐角數量這兩項指標的對比結果的分析可知，算法1雖能夠規劃出長度最短的路徑，但是該路徑拐角數多，路徑復雜程度較高；而算法2和算法3可在規劃出長度最短的路徑的同時，盡可能地減少拐角數，以降低路徑的復雜程度。

由于在實驗1中，無法有效地分辨出算法2和算法3的優劣勢，因此，本文再次進行實驗，對算法2和算法3進行對比分析。

實驗2：多臺AGV的路徑規劃。1號AGV的起點為(9，2)、目標點為(2，11)，2號AGV的起點為(2，11)、目標點為(9，2)，具體的仿真結果如圖6所示，其中圖6a、圖6b分別為算法2和算法3所規劃的路徑，圖中圓點為起點，方點為目標點，1號AGV的路徑為黑色，2號AGV的路徑為灰色。

(a)算法2(b)算法3 圖6 不同算法在實驗2的規劃路線

通過對仿真圖的觀察可知，算法2為兩臺AGV規劃的路徑存在大量相同的節點，此時兩臺AGV在行進的過程會產生對遇的局面，進而出現死鎖現象；而算法3在交通規則的約束下，為兩臺AGV規劃了無相同的節點的路徑，使得兩臺AGV無避碰、高效地達到目標點。

4 結論

在移動機器人得到廣泛應用的時代，路徑規劃是一個重要的研究領域。本文針對多AGV同時運行容易出現碰撞的情況以及傳統A*算法所規劃的路徑存在拐角數多的問題，在傳統A*算法的基礎上引入了交通約束條件，并在原有啟發函數的基礎上，添加了拐角數評判機制，構成多元啟發函數。采用柵格法進行環境建模，并在MATLAB實驗環境下進行兩組的實驗，實驗結果表明，在多AGV的環境下，相比于傳統的A*算法，基于交通約束及多元啟發函數的A*算法所規劃路徑合理，拐角數量優于傳統A*算法，且能有效地降低AGV間地碰撞幾率，降低AGV完成路徑的能耗，增強系統的穩定性，具有一定的應用價值。