結合負載均衡與A＊算法的多AGV路徑規劃

袁 洋，葉 峰，賴乙宗，趙雨亭

華南理工大學 機械與汽車工程學院，廣州510000

1 引言

隨著物流倉儲業、自動化制造業的快速發展。AGV 在倉儲物料搬運系統中發揮著越來越重要的作用[1]。龐大且復雜是目前的大規模AGV 道路網絡的顯著特征，由此引發的AGV 交通擁堵問題表露得愈發明顯。研究表明，路網的路徑選擇過程會影響其傳輸能力。因此，可以通過優化動態路由選擇算法，使其趨于高效穩定，以促進路網整體吞吐量及降低交通擁堵程度[2]。

路徑規劃方法主要有三類：圖形搜索法、人工智能法和勢場規劃法。人工智能法進行路徑規劃的方法主要是Q-learning 算法，Q-learning 算法在隨機動態環境的路徑規劃中有較好的應用，但其算法的收斂速度較慢、空間復雜度較大[3]。勢場規劃法進行路徑規劃具有較好的精度[4]，但需要引入人工勢場的概念，進行復雜的勢能計算增大了算法實現難度。圖形搜索算法是目前比較成熟的路徑規劃算法，其算法原理易于實現，在機器人路徑規劃領域得以廣泛應用[3]。本文主要針對基于圖形搜索法的并且在機器人路徑規劃領域中廣泛應用的A*算法進行改進，提供一種能有效均衡區域負載的多AGV路徑規劃算法。

圖形搜索法第一步構造圖結構，在此基礎上采取圖搜索方法實現路徑規劃。圖搜索法包括廣度優先遍歷、深度優先遍歷、啟發式算法、最短路徑搜索算法等。圖論中的最短路徑問題與AGV 路徑規劃問題相關，其中包括單源最短路徑問題、點對點的最短路徑問題、多源多匯點最短路徑問題、全源最短路徑問題[5]。最短路徑問題解法可用于求解單AGV路徑規劃中只求最短運行路徑的情況。如需另行考慮AGV 之間的沖突、死鎖現象，則是多AGV路徑規劃中出現的情景。Dijkstra算法是目前圖搜索算法里單源最短路徑算法中最經典的一種，A*算法則屬于啟發式搜索算法，廣泛應用于移動機器人的路徑預先規劃[6]。D*算法是基于這些圖搜索算法的眾多改進算法之一。張偉等[7]分析了AGV 調度系統中的Dijkstra 算法應用，解決了倉儲配送任務中的AGV 與任務匹配問題。張紫輝等[8]對未知環境下的路徑規劃問題進行研究。在機器人碰到未知障礙物的情況下，采用A*機器人路徑規劃算法，結合二次路徑規劃策略重新規劃路徑，進一步拓寬原算法的應用范圍。Dijkstra 算法、A*算法都是常用且性能較突出的全局路徑規劃算法[9]。

擁堵問題對AGV 整體運行效率有重大影響，是多AGV路徑規劃中需要重點研究的問題。路徑規劃問題是機器人導航應用中最基本、最重要的問題[10]。路網的宏觀基本圖是道路網絡的固有屬性，反映了路網的總交通量和路網運行水平的關系[11]。宏觀基本圖是研究大規模路網車流量與車輛的主要工具，路網中車輛數量超過允許的極限值時，路網局部區域會陷入擁堵狀態，車輛運行效率會受到影響，因此均衡路網中的負載至關重要。

本文針對多AGV在規則路網的路徑規劃問題展開研究，研究多AGV 在運行時單個AGV 的路徑規劃問題。提出一種考慮局部擁塞程度的基于A*的AGV 路徑規劃算法，將路網負載引入到A*算法的評價函數中，避免多AGV 路徑規劃時產生局部車流量過大的情況，最后使用仿真實驗說明了算法的有效性。

2 基于圖搜索的A＊算法

2.1 傳統A＊算法

在數學中，圖定義為一個二元組(V,E)，其中V 稱為頂點集，E 為邊集。E 中的每一個元素，即每個邊，使用一對頂點表示，如果一個邊連接了頂點a 和頂點b，則可以用a-b 表示這個邊。在圖中，路徑是由邊連接的一系列頂點。圖的表示方法主要有鄰接矩陣、鄰接表數組兩種方式。鄰接矩陣適用于稠密圖，鄰接表適用于稀疏圖。

A*算法是一種在圖中的啟發式搜索算法，引入了最優啟發式函數，可以在搜索過程中避免盲目性[12]，其表達式如式（1）：

令x 表示某個節點，f*(x)為x 的最優評價函數；目的是使得f*(x)最小。g*(x)是從初始節點到x 節點的最小代價，h*(x)是從x 到目標節點的所有路徑中的最小代價。

因為f*(x)無法預知，一般使用實際加估計的方式做近似如式（2）：

在式（2）中，f(x)是近似處理后當前節點x 的評價函數；g(x)是起點到當前節點x 節點的實際路徑代價，h(x)是從當前節點x 到目標節點的估計路徑代價。

當使用f(x)代替f*(x)時，實際為使用g(x)代替g*(x)，使用h(x)代替h*(x)，需要滿足的條件為h(x)＜h*(x)，即A*算法的啟發函數值要始終小于等于實際最小路徑代價。

當使用兩點之間的距離作為代價時，便需要衡量點之間距離的算法。衡量點之間距離最常用的是閔可夫斯基距離。當有兩點P 和Q，坐標如式（3）和式（4）時：

P 和Q 之間的閔可夫斯基距離L 可以由式（5）表示：

當p=2時，稱距離L為歐幾里德距離（Euclidean distance），當p=1時稱距離L為曼哈頓距離（Manhattan distance）。

2.2 基于A＊算法且考慮局部區域擁塞程度的路徑規劃算法

本節的目標是在已知的環境情況下，為待規劃路徑的AGV規劃一條從AGV原始位置到目標位置的路徑，以提高AGV 系統的效率。在目標的指導下，考慮了一種AGV 的局部擁塞下的判別方式，并在考慮局部擁塞程度的基礎上，設計了基于A*的路徑規劃方法對AGV進行路徑規劃。

2.2.1 擁塞對AGV路網運行的影響

研究表明，在路由選擇策略確定的情況下，當單位時間內產生的交通負載量超過該確定值時，網絡交通流快速陷入擁塞狀態[2]。局部擁塞最大的原因是交通流分布存在不均衡，某些路段已經達到瓶頸狀態，而有些路段處于非飽和或車流稀少的狀態[13]。因此避免單位節點出現過大負載是解決擁塞的關鍵。

在研究路網的宏觀問題中，宏觀基本圖[14]（Macroscopic Fundamental Diagram，MFD）是一個非常重要的工具，它用于描述路網交通流宏觀變量間的關系模型[15]。體現一定區域內車輛流出量（車輛完成率）和車輛的累積數量的關系，如圖1所示[16]。

圖1 宏觀基本圖

在MFD 中，橫軸為路網中某區域一段時間內累計車輛數，即在某區域中存在的車輛數；縱軸為旅行車輛完成率，即車輛流出率，表達的是在區域邊界上每秒流出的車輛數。根據局部區域路網中存在的車輛數，交通流可歸為四類：自由流、穩定流、不穩定流、擁堵流量。

MFD 的圖形如圖1，其形狀與拋物線類似，從其圖形可以分析累計車輛數（橫軸xi(k)）與車輛完成率（縱軸g(xi(k))）之間的約束關系，當xi(k)=0 時，g(xi(k))=0；當xi(k)路逐漸增加，g(xi(k))也同步增加，并逐漸達到最大值，該最大值點是穩定流向不穩定流轉變的臨界點。該臨界點過后，隨著xi(k)不斷增大直致超過不穩定流狀態下的最大值，交通流由不穩定流狀態轉變為擁堵狀態。當xi(k)增大至某一特定值xmax(k)，道路進入完全擁堵狀態，此時g(xi(k))=0，無車輛流出。

由MFD 可以看出，擁堵會嚴重影響路網內車輛的運行效率。

2.2.2 單向多入多出路網模型和雙向多入多出路網模型

仿真是交通效率和安全性能評價的重要手段[17]。單向和雙向的多入多出路網模型可用于對不同路徑規劃算法下路網負載情況進行仿真研究。n×n 路網模型包含了n×n 個子區域。單向多入多出路網模型和雙向多入多出路網模型的區別在于車輛駛入方向不同，前者車輛從一側的n 個子區域中之一駛入，后者車輛從隨機一側的n 個子區域中之一駛入，兩者車輛都是從另一側n 個子區域中之一駛出。

圖2是單向多入多出路網示意圖。該13×13路網示意圖中，圓代表子區域，連通的子區域通過在兩圓心之間連線表示，AGV在路網外部的運行方向采用箭頭標識。

圖3 為一個13×13 的雙向多入多出路網示意圖。示意圖中圓、連線和箭頭的涵義同單向多入多出路網示意圖。

圖2 13×13單向多入多出路網示意圖

圖3 13×13雙向多入多出路網示意圖

單向多入多出路網模型中，AGV執行任務時，從一側（北側）13個中選擇一個作為入口駛入，從另一側（南側）13個中選擇一個作為出口駛出。

雙向多入多出路網模型中，AGV執行任務時，從隨機一側（南側或北側）隨機一個口駛入，從對面出口中的隨機一個口駛出。

在區域路網負載的研究中，通常按照如下的三個步驟展開：

（1）AGV 執行任務時的出入口位置采用隨機生成的方法，生成多種組合方式。

（2）結合出入口位置進行路徑規劃。

（3）統計路網子區域內經過該區域的規劃路徑條數作為該子區域負載，然后統計所有子區域負載作為路網負載，觀察路網負載規律。

2.2.3 A＊路徑規劃算法下路網負載情況

如圖4為經典的A*算法流程圖，其核心思想為通過維護兩個節點元素集合開集OpenSet和閉集CloseSet以及對于有關節點的松弛操作得到最終結果。

圖4 A*算法流程圖

測試中，A*算法采用距離作為評價函數，對多個AGV分別進行路徑規劃。g(x)表示從起點到當前x 節點的實際距離，h(x)表示從當前x 節點到終點的歐幾里德距離。

測試中區域的負載統計包含了4 000個任務的路徑規劃結果。在單向多入多出路網模型中所有任務的起始位置在第一行隨機選取，目標位置在最后一行隨機選取。圖5和圖6分別是在5×5和13×13的單向多入多出路網模型下仿真實驗得出的路網負載情況。

圖5 5×5單向多入多出路網負載

由圖5、圖6可知，負載過高的區域集中在中部位置的出口行附近，而在入口行附近，負載比較均衡而且負載較低。

對多個AGV 分別在5×5 和17×17 單向多入多出路網模型中進行路徑規劃測試，其結果分別如圖7 和圖8所示。由圖可得，傳統A*算法在單向多入多出路網模型下進行規劃路徑時，會在接近出口區域時在左右方向上移動，從而更靠近出口，進而會導致靠近出口處區域的負載較大。

圖6 13×13單向多入多出路網負載

圖7 5×5路網下兩個路徑規劃實例

圖8 17×17路網下兩個路徑規劃實例

綜上，在使用傳統的A*算法即未考慮負載均衡情況下，會出現負載過高區域集中在靠近出口處的情況，并且負載在靠近出口的行呈現類似鐘形曲線分布，出口行左右方向上靠近中部的區域負載也會顯著高于其他區域。負載高的區域發生擁堵的幾率更大，從而會造成AGV系統運行效率低下，進而影響整體AGV系統運行。

3 考慮負載均衡下AGV路徑規劃方法及路網負載

考慮負載均衡下的AGV路徑規劃方法實質是在傳統的A*算法基礎上，將負載因素考慮到實際路徑代價中，即對新的代價函數g(x)進行改進，引入負載因素，可由式（6）表示：

其中，l(x)表示從初始節點到節點x 的實際距離，load(x)表節點x 的負載。α 是將負載轉換為負載代價的轉換系數，后續實驗中，測試不同的α 值，以求得最優α 值。當α=0 時即為不考慮負載均衡的情況。

仿真實驗原理如下：保持4 000個AGV任務的起點和終點不變，對比考察考慮負載均衡情況下不同的負載系數的路網負載情況，當負載系數為0時是傳統的A*算法，即為不考慮負載均衡。

在實現步驟上，首先對第一臺AGV 使用考慮負載均衡改進的A*算法的路徑規劃方法進行路徑規劃，然后根據本次路徑規劃的結果對路網中的負載數據進行更新，在此更新后的路網負載基礎上，對后續AGV依次使用相同方法進行路徑規劃并且更新路網負載，直至所有的AGV完成路徑規劃，并對路網更新為止。

在單向的多入多出路網模型進行實驗。在式（6）中，令α=0 時即為不考慮負載均衡的情況。在10×10的單向多入多出路網模型中分別設置α 值為0、1 進行實驗，以上兩種路網模型下路網負載情況分別如圖9、圖10所示；在沒有負載均衡的情況下，單向多入多出路網模型中的車輛負載會出現在靠近出口行中部集中的情況，而負載系數α 為1 的情況下，路網中的車輛負載明顯均衡。負載均衡改進的A*算法在單向多入多出路網模型中具有較好的負載均衡效果。

在雙向的多入多出路網模型進行實驗。在20×20的雙向多入多出路網模型中分別設置α 值為0、10 進行了同樣的實驗。兩種路網模型下路網負載情況分別如圖11、圖12 所示。由圖對比可知負載均衡改進的A*算法在雙向多入多出路網模型中具有較好的負載均衡效果。

圖9 α=0 下10×10單向多入多出路網區域負載

圖10 α=1 下10×10單向多入多出路網區域負載

圖11 α=0 下20×20雙向多入多出路網區域負載

圖12 α=10 下20×20雙向多入多出路網區域負載

可以看出，在兩種路網模型下，隨著α 值的增大，路網區域負載逐漸趨于穩定。在α 值增大至某一特定值后，除處于入口行和出口行區域外，處于中間行的區域負載基本相同。由于入口行和出口行僅由隨機生成的任務決定，考慮負載均衡與未考慮負載均衡情況下，近入口行和近出口行的區域路網負載是幾乎沒有變化的。由路網中間的區域負載情況可知，在單向或雙向的路網模型下由負載均衡改進的A*算法均具有較好的負載均衡效果。

由于負載均衡的引入，有效地均衡了區域負載，但是可能會導致某些AGV在路徑規劃的時候避開最短路徑從而導致路網整體的負載增加。為研究負載均衡的引入給路網整體負載帶來的影響，針對單向多入多出和雙向多入多出路網模型做了多次實驗。得出路網負載標準差和路網區域平均負載在引入負載均衡前后的變化程度如表1～表4所示。

表1 單向多入多出路網下模型區域負載標準差

表2 單向多入多出路網下模型區域平均負載

表3 雙向多入多出路網下模型區域負載標準差

表4 雙向多入多出路網下模型區域平均負載

對比表1與表2，在單向多入多出路網模型中，引入負載均衡后區域負載標準差大大減小，而平均負載增加的比例幾乎可以忽略。對比表3 與表4，在雙向的多入多出路網模型中情況一樣。可以看出，在引入負載均衡后，路網平均負載有微量的增加，而路網負載的標準差明顯下降。因此引入負載均衡后能夠保證路網平均負載微量增加的情況有效地均衡路網負載。

4 結語

本文針對大規模AGV路網下區域負載不均衡以及造成的擁塞問題，提出了考慮負載均衡改進的A*算法，實驗證明了所提方法在均衡路網區域負載上的有效性。通過將負載轉化為A*算法中代價函數的一部分，在路網平均負載微量增加的情況下能夠均衡負載，從而有效避免局部擁塞問題，大大提升了AGV的運行。