結(jié)合負(fù)載均衡與A＊算法的多AGV路徑規(guī)劃

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

華南理工大學(xué) 機(jī)械與汽車工程學(xué)院，廣州510000

1 引言

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

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

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

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

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

2 基于圖搜索的A＊算法

2.1 傳統(tǒng)A＊算法

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

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

令x 表示某個(gè)節(jié)點(diǎn)，f*(x)為x 的最優(yōu)評價(jià)函數(shù)；目的是使得f*(x)最小。g*(x)是從初始節(jié)點(diǎn)到x 節(jié)點(diǎn)的最小代價(jià)，h*(x)是從x 到目標(biāo)節(jié)點(diǎn)的所有路徑中的最小代價(jià)。

因?yàn)閒*(x)無法預(yù)知，一般使用實(shí)際加估計(jì)的方式做近似如式（2）：

在式（2）中，f(x)是近似處理后當(dāng)前節(jié)點(diǎn)x 的評價(jià)函數(shù)；g(x)是起點(diǎn)到當(dāng)前節(jié)點(diǎn)x 節(jié)點(diǎn)的實(shí)際路徑代價(jià)，h(x)是從當(dāng)前節(jié)點(diǎn)x 到目標(biāo)節(jié)點(diǎn)的估計(jì)路徑代價(jià)。

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

當(dāng)使用兩點(diǎn)之間的距離作為代價(jià)時(shí)，便需要衡量點(diǎn)之間距離的算法。衡量點(diǎn)之間距離最常用的是閔可夫斯基距離。當(dāng)有兩點(diǎn)P 和Q，坐標(biāo)如式（3）和式（4）時(shí)：

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

當(dāng)p=2時(shí)，稱距離L為歐幾里德距離（Euclidean distance），當(dāng)p=1時(shí)稱距離L為曼哈頓距離（Manhattan distance）。

2.2 基于A＊算法且考慮局部區(qū)域擁塞程度的路徑規(guī)劃算法

本節(jié)的目標(biāo)是在已知的環(huán)境情況下，為待規(guī)劃路徑的AGV規(guī)劃一條從AGV原始位置到目標(biāo)位置的路徑，以提高AGV 系統(tǒng)的效率。在目標(biāo)的指導(dǎo)下，考慮了一種AGV 的局部擁塞下的判別方式，并在考慮局部擁塞程度的基礎(chǔ)上，設(shè)計(jì)了基于A*的路徑規(guī)劃方法對AGV進(jìn)行路徑規(guī)劃。

2.2.1 擁塞對AGV路網(wǎng)運(yùn)行的影響

研究表明，在路由選擇策略確定的情況下，當(dāng)單位時(shí)間內(nèi)產(chǎn)生的交通負(fù)載量超過該確定值時(shí)，網(wǎng)絡(luò)交通流快速陷入擁塞狀態(tài)[2]。局部擁塞最大的原因是交通流分布存在不均衡，某些路段已經(jīng)達(dá)到瓶頸狀態(tài)，而有些路段處于非飽和或車流稀少的狀態(tài)[13]。因此避免單位節(jié)點(diǎn)出現(xiàn)過大負(fù)載是解決擁塞的關(guān)鍵。

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

圖1 宏觀基本圖

在MFD 中，橫軸為路網(wǎng)中某區(qū)域一段時(shí)間內(nèi)累計(jì)車輛數(shù)，即在某區(qū)域中存在的車輛數(shù)；縱軸為旅行車輛完成率，即車輛流出率，表達(dá)的是在區(qū)域邊界上每秒流出的車輛數(shù)。根據(jù)局部區(qū)域路網(wǎng)中存在的車輛數(shù)，交通流可歸為四類：自由流、穩(wěn)定流、不穩(wěn)定流、擁堵流量。

MFD 的圖形如圖1，其形狀與拋物線類似，從其圖形可以分析累計(jì)車輛數(shù)（橫軸xi(k)）與車輛完成率（縱軸g(xi(k))）之間的約束關(guān)系，當(dāng)xi(k)=0 時(shí)，g(xi(k))=0；當(dāng)xi(k)路逐漸增加，g(xi(k))也同步增加，并逐漸達(dá)到最大值，該最大值點(diǎn)是穩(wěn)定流向不穩(wěn)定流轉(zhuǎn)變的臨界點(diǎn)。該臨界點(diǎn)過后，隨著xi(k)不斷增大直致超過不穩(wěn)定流狀態(tài)下的最大值，交通流由不穩(wěn)定流狀態(tài)轉(zhuǎn)變?yōu)閾矶聽顟B(tài)。當(dāng)xi(k)增大至某一特定值xmax(k)，道路進(jìn)入完全擁堵狀態(tài)，此時(shí)g(xi(k))=0，無車輛流出。

由MFD 可以看出，擁堵會嚴(yán)重影響路網(wǎng)內(nèi)車輛的運(yùn)行效率。

2.2.2 單向多入多出路網(wǎng)模型和雙向多入多出路網(wǎng)模型

仿真是交通效率和安全性能評價(jià)的重要手段[17]。單向和雙向的多入多出路網(wǎng)模型可用于對不同路徑規(guī)劃算法下路網(wǎng)負(fù)載情況進(jìn)行仿真研究。n×n 路網(wǎng)模型包含了n×n 個(gè)子區(qū)域。單向多入多出路網(wǎng)模型和雙向多入多出路網(wǎng)模型的區(qū)別在于車輛駛?cè)敕较虿煌?，前者車輛從一側(cè)的n 個(gè)子區(qū)域中之一駛?cè)?，后者車輛從隨機(jī)一側(cè)的n 個(gè)子區(qū)域中之一駛?cè)?，兩者車輛都是從另一側(cè)n 個(gè)子區(qū)域中之一駛出。

圖2是單向多入多出路網(wǎng)示意圖。該13×13路網(wǎng)示意圖中，圓代表子區(qū)域，連通的子區(qū)域通過在兩圓心之間連線表示，AGV在路網(wǎng)外部的運(yùn)行方向采用箭頭標(biāo)識。

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

圖2 13×13單向多入多出路網(wǎng)示意圖

圖3 13×13雙向多入多出路網(wǎng)示意圖

單向多入多出路網(wǎng)模型中，AGV執(zhí)行任務(wù)時(shí)，從一側(cè)（北側(cè)）13個(gè)中選擇一個(gè)作為入口駛?cè)耄瑥牧硪粋?cè)（南側(cè)）13個(gè)中選擇一個(gè)作為出口駛出。

雙向多入多出路網(wǎng)模型中，AGV執(zhí)行任務(wù)時(shí)，從隨機(jī)一側(cè)（南側(cè)或北側(cè)）隨機(jī)一個(gè)口駛?cè)?，從對面出口中的隨機(jī)一個(gè)口駛出。

在區(qū)域路網(wǎng)負(fù)載的研究中，通常按照如下的三個(gè)步驟展開：

（1）AGV 執(zhí)行任務(wù)時(shí)的出入口位置采用隨機(jī)生成的方法，生成多種組合方式。

（2）結(jié)合出入口位置進(jìn)行路徑規(guī)劃。

（3）統(tǒng)計(jì)路網(wǎng)子區(qū)域內(nèi)經(jīng)過該區(qū)域的規(guī)劃路徑條數(shù)作為該子區(qū)域負(fù)載，然后統(tǒng)計(jì)所有子區(qū)域負(fù)載作為路網(wǎng)負(fù)載，觀察路網(wǎng)負(fù)載規(guī)律。

2.2.3 A＊路徑規(guī)劃算法下路網(wǎng)負(fù)載情況

如圖4為經(jīng)典的A*算法流程圖，其核心思想為通過維護(hù)兩個(gè)節(jié)點(diǎn)元素集合開集OpenSet和閉集CloseSet以及對于有關(guān)節(jié)點(diǎn)的松弛操作得到最終結(jié)果。

圖4 A*算法流程圖

測試中，A*算法采用距離作為評價(jià)函數(shù)，對多個(gè)AGV分別進(jìn)行路徑規(guī)劃。g(x)表示從起點(diǎn)到當(dāng)前x 節(jié)點(diǎn)的實(shí)際距離，h(x)表示從當(dāng)前x 節(jié)點(diǎn)到終點(diǎn)的歐幾里德距離。

測試中區(qū)域的負(fù)載統(tǒng)計(jì)包含了4 000個(gè)任務(wù)的路徑規(guī)劃結(jié)果。在單向多入多出路網(wǎng)模型中所有任務(wù)的起始位置在第一行隨機(jī)選取，目標(biāo)位置在最后一行隨機(jī)選取。圖5和圖6分別是在5×5和13×13的單向多入多出路網(wǎng)模型下仿真實(shí)驗(yàn)得出的路網(wǎng)負(fù)載情況。

圖5 5×5單向多入多出路網(wǎng)負(fù)載

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

對多個(gè)AGV 分別在5×5 和17×17 單向多入多出路網(wǎng)模型中進(jìn)行路徑規(guī)劃測試，其結(jié)果分別如圖7 和圖8所示。由圖可得，傳統(tǒng)A*算法在單向多入多出路網(wǎng)模型下進(jìn)行規(guī)劃路徑時(shí)，會在接近出口區(qū)域時(shí)在左右方向上移動，從而更靠近出口，進(jìn)而會導(dǎo)致靠近出口處區(qū)域的負(fù)載較大。

圖6 13×13單向多入多出路網(wǎng)負(fù)載

圖7 5×5路網(wǎng)下兩個(gè)路徑規(guī)劃實(shí)例

圖8 17×17路網(wǎng)下兩個(gè)路徑規(guī)劃實(shí)例

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

3 考慮負(fù)載均衡下AGV路徑規(guī)劃方法及路網(wǎng)負(fù)載

考慮負(fù)載均衡下的AGV路徑規(guī)劃方法實(shí)質(zhì)是在傳統(tǒng)的A*算法基礎(chǔ)上，將負(fù)載因素考慮到實(shí)際路徑代價(jià)中，即對新的代價(jià)函數(shù)g(x)進(jìn)行改進(jìn)，引入負(fù)載因素，可由式（6）表示：

其中，l(x)表示從初始節(jié)點(diǎn)到節(jié)點(diǎn)x 的實(shí)際距離，load(x)表節(jié)點(diǎn)x 的負(fù)載。α 是將負(fù)載轉(zhuǎn)換為負(fù)載代價(jià)的轉(zhuǎn)換系數(shù)，后續(xù)實(shí)驗(yàn)中，測試不同的α 值，以求得最優(yōu)α 值。當(dāng)α=0 時(shí)即為不考慮負(fù)載均衡的情況。

仿真實(shí)驗(yàn)原理如下：保持4 000個(gè)AGV任務(wù)的起點(diǎn)和終點(diǎn)不變，對比考察考慮負(fù)載均衡情況下不同的負(fù)載系數(shù)的路網(wǎng)負(fù)載情況，當(dāng)負(fù)載系數(shù)為0時(shí)是傳統(tǒng)的A*算法，即為不考慮負(fù)載均衡。

在實(shí)現(xiàn)步驟上，首先對第一臺AGV 使用考慮負(fù)載均衡改進(jìn)的A*算法的路徑規(guī)劃方法進(jìn)行路徑規(guī)劃，然后根據(jù)本次路徑規(guī)劃的結(jié)果對路網(wǎng)中的負(fù)載數(shù)據(jù)進(jìn)行更新，在此更新后的路網(wǎng)負(fù)載基礎(chǔ)上，對后續(xù)AGV依次使用相同方法進(jìn)行路徑規(guī)劃并且更新路網(wǎng)負(fù)載，直至所有的AGV完成路徑規(guī)劃，并對路網(wǎng)更新為止。

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

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

圖9 α=0 下10×10單向多入多出路網(wǎng)區(qū)域負(fù)載

圖10 α=1 下10×10單向多入多出路網(wǎng)區(qū)域負(fù)載

圖11 α=0 下20×20雙向多入多出路網(wǎng)區(qū)域負(fù)載

圖12 α=10 下20×20雙向多入多出路網(wǎng)區(qū)域負(fù)載

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

由于負(fù)載均衡的引入，有效地均衡了區(qū)域負(fù)載，但是可能會導(dǎo)致某些AGV在路徑規(guī)劃的時(shí)候避開最短路徑從而導(dǎo)致路網(wǎng)整體的負(fù)載增加。為研究負(fù)載均衡的引入給路網(wǎng)整體負(fù)載帶來的影響，針對單向多入多出和雙向多入多出路網(wǎng)模型做了多次實(shí)驗(yàn)。得出路網(wǎng)負(fù)載標(biāo)準(zhǔn)差和路網(wǎng)區(qū)域平均負(fù)載在引入負(fù)載均衡前后的變化程度如表1～表4所示。

表1 單向多入多出路網(wǎng)下模型區(qū)域負(fù)載標(biāo)準(zhǔn)差

表2 單向多入多出路網(wǎng)下模型區(qū)域平均負(fù)載

表3 雙向多入多出路網(wǎng)下模型區(qū)域負(fù)載標(biāo)準(zhǔn)差

表4 雙向多入多出路網(wǎng)下模型區(qū)域平均負(fù)載

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

4 結(jié)語

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