王保劍，胡大裟，蔣玉明

1.四川大學 計算機學院，成都610065

2.四川省大數(shù)據(jù)分析與融合應用技術工程實驗室，成都610065

隨著中國制造2025的不斷推進，對我國工業(yè)制造的智能自動化提出了更高的要求。智能自動化倉庫系統(tǒng)作為現(xiàn)代工業(yè)制造的基礎，因此成為智能系統(tǒng)研究的熱點領域之一。其中基于自動導引車（Automated Guided Vehicle，AGV）的智能自動化倉庫系統(tǒng)是智能倉庫系統(tǒng)的重要分支。在由多臺自動導引車組成的自動導引車系統(tǒng)（Automated Guided Vehicle System，AGVS）的運行過程中，需要解決任務調(diào)度、路徑規(guī)劃和避碰等一系列問題[1-3]，其中AGVS的路徑規(guī)劃是研究的熱點、難點。

目前主要路徑規(guī)劃算法有Dijkstra算法[4]、A*算法[5-6]等，智能路徑規(guī)劃算法有蟻群算法[7]、遺傳算法[8]、Q-learning算法[9]等。其中A*算法是啟發(fā)式搜索算法[10]，其算法本身具有簡潔高效，能夠快速找到最優(yōu)解的優(yōu)點，因此被廣泛應用于AGVS路徑規(guī)劃。A*算法有很多局限性，文獻[11]提出一種結合跳點搜索算法的改進A*算法，能夠有效減少列表中無用節(jié)點數(shù)量，減少計算量，提高算法效率，解決A*算法在規(guī)模較大的AGVS中對多個AGV進行路徑規(guī)劃的應用場景中系統(tǒng)開銷大，路徑規(guī)劃速度慢的問題。文獻[12]在當前節(jié)點的啟發(fā)函數(shù)中加入父節(jié)點的啟發(fā)函數(shù)，使啟發(fā)函數(shù)在代價函數(shù)中的占比保持在一個合理范圍，提高算法的實時性。文獻[10]采用新的數(shù)據(jù)結構將A*算法中的搜索操作并行化，同時實現(xiàn)算法的快速插入操作，提升算法的效率。文獻[13]在傳統(tǒng)A*算法的啟發(fā)函數(shù)中引入網(wǎng)路負載，能夠有效均衡各網(wǎng)絡負載，改善出口區(qū)域負載過高的情況。但是采用模型較為簡單，只考慮特殊情形下局部網(wǎng)絡負載過高的情況，與實際應用場景差別較大，改進算法并不能廣泛適用于AGVS的路徑規(guī)劃。

AGV尋路過程中避開高負載節(jié)點是解決局部擁塞的關鍵。因此本文在傳統(tǒng)A*算法的啟發(fā)函數(shù)中，引入節(jié)點負載，從算法層面上解決了多AGV系統(tǒng)采用傳統(tǒng)A*算法進行路徑規(guī)劃時容易造成局部節(jié)點負載過高的問題，從而避免AGV系統(tǒng)陷入局部擁塞，提高系統(tǒng)效率。最后通過模擬仿真實驗，證實了改進算法的可行性。

1 問題描述

本文改進A*算法是應用在基于柵格地圖[14]的智能倉庫，智能倉庫模型如圖1所示。倉庫模型主要有以下部分：

（1）分揀臺：用于存放待分揀的貨物，AGV執(zhí)行任務的起點，位于倉庫模型的最左側。

（2）道路：位于分揀臺和貨架之間，用于AGV搬運貨物。

（3）貨架：集中在倉庫模型的中間靠右側，用于存放已經(jīng)分揀好的貨物。

（4）AGV：用于貨物搬運的工具，能夠根據(jù)相應的算法，把貨物從起點運送到目標節(jié)點位置。

圖1 智能倉庫模型圖

以模型構建的現(xiàn)實性和易處理性為原則，不失一般性[15]，提出如下假設：

（1）結合智能倉庫的實際應用情況AGV的運動方向只考慮上下左右，可橫向或縱向跨越柵格[16]。

（2）不考慮AGV的裝載和卸載時間，即AGV的裝載和卸載時間均為0。

（3）AGV運行過程中速度不變，不考慮起始點出發(fā)時加速，到達目的地減速的過程。

（4）不考慮包裹到達投遞區(qū)之后的出庫過程。

（5）單個AGV只能搬運單個貨物，一個貨物也只能被一個AGV搬運。

（6）為了最大程度上避免沖突和死鎖，本文采用文獻[17]的避碰策略，任務優(yōu)先級高的AGV先行，優(yōu)先級低的AGV則等待。

2 A*算法

2.1 算法描述

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

其中，AGV路徑是由各個節(jié)點組成，可通過節(jié)點集合{d1,d2,…,dn,…,dm}表示，d1表示起始節(jié)點，dn表示為當前節(jié)點，dm表示目標節(jié)點。f*(n)為代價函數(shù)，g*(n)是起始節(jié)點到當前節(jié)點的最短距離，如果g*(n)=0，代價函數(shù)所表示的算法是最佳優(yōu)先搜索算法（BFS）。h*(n)是當前節(jié)點到目標節(jié)點的最短距離，如果h*(n)=0，代價函數(shù)所表示的算法是Dijkstra算法。目前是無法通過該節(jié)點預知該節(jié)點與目標節(jié)點的最短距離，因此使用h(n)代替h*(n)，因此替換過后的代價函數(shù)表達式如式（2）：

h(n)選取原則為h(n)的值不大于h*(n)，通常使用歐式距離計算公式、曼哈頓距離計算公式和切比雪夫距離計算公式，其對應表達式分別是式（3）～（5）：

2.2 算法流程

A*算法流程的核心就是維護Open和Closed兩個集合。其中Closed集合中存放的是已拓展節(jié)點，Open集合中存放待拓展節(jié)點。節(jié)點代價函數(shù)值表示該節(jié)點的優(yōu)先級，選取Open集合中代價最?。▋?yōu)先級最高）的節(jié)點進行拓展，將已經(jīng)拓展的節(jié)點存放在Closed集合中。如果目標節(jié)點出現(xiàn)在Open集合中，則依次返回父節(jié)點，最終規(guī)劃出一條路徑。其算法的路徑規(guī)劃過程如圖2。

其中橙色節(jié)點D1為路徑的起點，Dm為目標節(jié)點，黑色節(jié)點為障礙物，AGV無法通過障礙物節(jié)點，綠色節(jié)點為待拓展節(jié)點，白色為可通過節(jié)點。最終生成一條藍色節(jié)點的路徑。

2.3 傳統(tǒng)A*算法不足之處

圖2 A*算法尋路過程示意圖

在采用傳統(tǒng)A*算法的多AGV系統(tǒng)中，代價函數(shù)只考慮起始節(jié)點到當前節(jié)點的最短路徑和當前節(jié)點到目標節(jié)點的最短路徑估計。在很多應用場景中，AGV起點相對集中在一個區(qū)域，目標節(jié)點相對集中在另一個區(qū)域。若是采用傳統(tǒng)A*算法，只考慮距離作為單一評價方式的啟發(fā)函數(shù)，執(zhí)行不同任務的AGV所行走的路徑大致相同，這會導致一部分節(jié)點繁忙，一部分節(jié)點空閑。繁忙節(jié)點負載較大，周圍常常有多個AGV需要競爭、搶占該節(jié)點，因此該節(jié)點周圍會出現(xiàn)等待或滯留的AGV，容易導致該區(qū)域出現(xiàn)局部擁塞甚至是死鎖。同樣系統(tǒng)中的很多空閑節(jié)點就會造成資源的浪費，系統(tǒng)效率低下。多AGV搶占節(jié)點如圖3所示。

圖3 多個AGV搶占節(jié)點示意圖

圖中，箭頭表示AGV移動的軌跡，灰色節(jié)點表示有多個AGV搶占的節(jié)點。然而在傳統(tǒng)A*算法的啟發(fā)函數(shù)中，沒有引入節(jié)點負載，因此無法在尋路過程中避開這些高負載節(jié)點，避免局部擁塞的發(fā)生。

3 結合節(jié)點負載的改進A*算法

本文提出一種結合節(jié)點負載的改進A*算法，在傳統(tǒng)A*算法的啟發(fā)函數(shù)中引入節(jié)點負載，并且提出動態(tài)節(jié)點負載計算公式，能夠動態(tài)更新節(jié)點負載，有效提高算法的實時性。改進算法的表達式如式（6）：

其中，n表示尋路過程中拓展的第n個節(jié)點，f(n)是代價函數(shù)表示待拓展節(jié)點的優(yōu)先級，f(n)值越大，節(jié)點優(yōu)先級就越低，f(n)值越小，節(jié)點優(yōu)先級就越高。g(n)是起始節(jié)點到當前節(jié)點的最短距離，l(n)是結合節(jié)點負載的節(jié)點啟發(fā)函數(shù)，μ是一個常數(shù)，對節(jié)點負載進行縮放，使算法有更好的表現(xiàn)，如果μ=0，該算法就變成傳統(tǒng)的A*算法，h(n)是傳統(tǒng)A*算法的啟發(fā)函數(shù)，常用曼哈頓距離或者歐式距離計算公式。k n是此時第n個節(jié)點的負載值，存儲在一個(M×N)的二維矩陣中，通過維護二維矩陣，動態(tài)更新節(jié)點負載值，負載值最低是0，其計算公式如式（7）、（8）：

其中，x表示節(jié)點負載迭代次數(shù)，k x表示第x次迭代過后的節(jié)點負載值，T x表示第x次迭代的時刻，迭代從T0時刻開始，并且T0…T x時間間隔相等，?是一個系數(shù)，G x表示T x-1～T x這段時間內(nèi)所有通過該節(jié)點的AGV所花費的總時間，其計算公式如式（8）。g表示T x-1～T x這段時間內(nèi)通過該節(jié)點的AGV數(shù)量，t i表示第i個AGV通過該節(jié)點花費的時間。D是節(jié)點冷卻常數(shù)，如果T x-1～T x這段時間沒有AGV或者有較少的AGV通過該節(jié)點，該節(jié)點負載就會相應減少，系統(tǒng)每隔T x-T x-1更新一次二維矩陣，并且節(jié)點負載值恒大于等于0。

本文提出的改進A*算法，在啟發(fā)函數(shù)中引入節(jié)點負載作為評價函數(shù)，從而節(jié)點負載影響AGV尋路過程中節(jié)點的選擇。如果節(jié)點負載較高，其相應的代價函數(shù)f(n)就會較大，對應的優(yōu)先級就會較小，因此AGV在尋路過程中就會優(yōu)先考慮負載較低的節(jié)點，從而均衡各個節(jié)點的負載，達到避免局部擁塞的發(fā)生，提升系統(tǒng)效率的目的。

中國—東盟博覽會永久落戶南寧，不僅為南寧吸引了大量的外部投資，也為南寧的旅游業(yè)帶來了充足的客源。因此，中國—東盟博覽會在推動南寧經(jīng)濟的同時，也使南寧旅游業(yè)整體質量的提高。東博會和旅游業(yè)的良性互動，使得兩者融合發(fā)展，促進南寧城市競爭力。在中國—東盟博覽會的影響下，南寧的旅游業(yè)不斷向好向快發(fā)展；而南寧旅游業(yè)的完善也在一定程度上保證了東博會舉辦的質量。兩者的互動迎來社會和諧發(fā)展共贏的局面。

4 仿真實驗

4.1 環(huán)境模型

實驗采用柵格地圖對智能倉庫模型進行建模，將本文提出的改進A*算法與基于交通規(guī)則下的A*算法[19]做對比，證明改進算法能夠有效均衡各節(jié)點負載，提高系統(tǒng)效率。仿真模擬規(guī)則如下：

（1）生成20×20的柵格地圖，每個格子長1 m，小車的速度1 m/s。其中灰色方格表示分揀臺，為每個AGV分配貨物，黑色格子表示貨架，AGV執(zhí)行相應的任務將分揀臺上的貨物運輸?shù)街付ㄘ浖?，黑色小圓點表示正在執(zhí)行任務的AGV，白色格子表示AGV可以通行的區(qū)域。柵格地圖如圖1。

（2）對應地圖生成和維護兩個二維矩陣和一個系統(tǒng)時鐘記錄時刻T x，從T0時刻開始，并且T0…T x間隔相等。第一個矩陣用于存放公式（8）計算出T x-1～T x時間段內(nèi)所有通過該節(jié)點的AGV所花費的總時間。再通過公式（7）計算生成對應的節(jié)點負載值并存放在第二個二維矩陣。每隔?T(T x-T x-1)更新一次二維矩陣，時間間隔?T設為8 s。其中，節(jié)點負載最大值為40。

（3）AGV系統(tǒng)生成150個任務，使用不同數(shù)量的AGV分別使用基于交通規(guī)則下的A*算法，改進算法完成任務，對應的AGV數(shù)量依次是5、10、15、20、25、30。記錄系統(tǒng)完成所有任務所需要的時間，AGV行走的總路程和不同時間段節(jié)點負載值。

4.2 算法對比

仿真系統(tǒng)分別采用基于交通規(guī)則的A*算法（簡稱算法1）和本文的改進A*算法（簡稱算法2）進行對比實驗，分別記錄AGV系統(tǒng)完成所有任務的總時間，單個任務完成的平均時間，AGV行走的總里程和節(jié)點負載，從不同維度對算法1和算法2進行對比。

圖4所示的是在分別采用算法1和算法2的AGV系統(tǒng)中，完成150個任務所需要的時間。藍色實線表示算法1，橙色虛線表示算法2。從圖中不難發(fā)現(xiàn)，隨著系統(tǒng)中AGV數(shù)量的增加，系統(tǒng)所花費的時間會相應減少。當系統(tǒng)中AGV數(shù)量超過15個時候，兩種算法都趨于緩和，但算法2優(yōu)于算法1，總的系統(tǒng)消耗時間比算法1減少了16.18%。

圖4 AGV系統(tǒng)完成任務總時間

圖5 所示的是擁有不同AGV數(shù)量的AGV系統(tǒng)完成單個任務所需要花費的平均時間。隨著系統(tǒng)中AGV數(shù)量的增加，完成單個任務的平均時間增加。當系統(tǒng)中有較多AGV時，多個AGV搶占節(jié)點的概率增加，根據(jù)公式（7）、（8），被搶占節(jié)點負載增加，從而被搶占節(jié)點所在區(qū)域中會出現(xiàn)多個AGV等待下一節(jié)點釋放或一直未能搶占到下一節(jié)點而滯留父節(jié)點的現(xiàn)象，使得該區(qū)域節(jié)點負載增加，導致局部擁塞，甚至死鎖，大大降低系統(tǒng)效率。算法2在尋路過程時能夠有效避開高負載節(jié)點，對比算法1能夠減少14.24%的時間開銷。

圖5 完成單個任務的平均時間

圖6 所表示的是在AGV系統(tǒng)中，完成所有任務AGV行走的總里程。在采用算法1進行路徑規(guī)劃的AGV系統(tǒng)中，隨著系統(tǒng)中AGV數(shù)量的增加，AGV行走的總里程變化較小，維持在一個特定值附近。然而在采用算法2的AGV系統(tǒng)中，AGV行走總里程隨著系統(tǒng)中AGV數(shù)量的增加而相應增加，在算法1的基礎上增加了4.67%。這是因為改進算法在算法1的代價函數(shù)中引入節(jié)點負載，AGV在尋路過程中會避開高負載節(jié)點，沒有選擇最短路徑，犧牲了路徑長度，減少時間開銷，提高了系統(tǒng)效率。

圖6 AGV移動總里程

表1對比了算法1和算法2的節(jié)點負載情況，系統(tǒng)中AGV數(shù)量為30，時間是系統(tǒng)開始運行后80 s。算法2雖然平均負載值相對算法1增加了5.45%，但標準差減少了－29.93%，說明改進算法能夠有效避開熱點節(jié)和利用低負載節(jié)點，均衡各節(jié)點負載。

表1 節(jié)點平均負載和標準差表

5 結束語

本文提出一種結合節(jié)點負載的改進A*算法，在啟發(fā)函數(shù)中引入節(jié)點負載，對比基于交通規(guī)則下A*算法，雖然增加了系統(tǒng)中AGV行走的總路程和節(jié)點平均負載，卻換了更少的時間開銷，以及提高了單個任務的執(zhí)行效率。通過仿真實驗能表明改進A*算法能夠有效避開高負載節(jié)點，均衡各節(jié)點負載，避免局部擁塞，提高系統(tǒng)運行效率。