改進(jìn)A*算法在路徑規(guī)劃中的應(yīng)用

王保劍，胡大裟，蔣玉明

1.四川大學(xué) 計(jì)算機(jī)學(xué)院，成都610065

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

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

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

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

1 問題描述

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

（1）分揀臺(tái)：用于存放待分揀的貨物，AGV執(zhí)行任務(wù)的起點(diǎn)，位于倉庫模型的最左側(cè)。

（2）道路：位于分揀臺(tái)和貨架之間，用于AGV搬運(yùn)貨物。

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

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

圖1 智能倉庫模型圖

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

（1）結(jié)合智能倉庫的實(shí)際應(yīng)用情況AGV的運(yùn)動(dòng)方向只考慮上下左右，可橫向或縱向跨越柵格[16]。

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

（3）AGV運(yùn)行過程中速度不變，不考慮起始點(diǎn)出發(fā)時(shí)加速，到達(dá)目的地減速的過程。

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

（5）單個(gè)AGV只能搬運(yùn)單個(gè)貨物，一個(gè)貨物也只能被一個(gè)AGV搬運(yùn)。

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

2 A*算法

2.1 算法描述

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

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

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

2.2 算法流程

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

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

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

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

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

圖3 多個(gè)AGV搶占節(jié)點(diǎn)示意圖

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

3 結(jié)合節(jié)點(diǎn)負(fù)載的改進(jìn)A*算法

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

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 環(huán)境模型

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

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

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

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

4.2 算法對(duì)比

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

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

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

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

圖5 完成單個(gè)任務(wù)的平均時(shí)間

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

圖6 AGV移動(dòng)總里程

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

表1 節(jié)點(diǎn)平均負(fù)載和標(biāo)準(zhǔn)差表

5 結(jié)束語

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