張其嬌，丁 一，秦 濤

1.上海海事大學(xué)物流科學(xué)與工程研究院，上海201306

2.上海海勃物流軟件有限公司，上海200080

集裝箱碼頭作為海陸物流的重要交通樞紐，在全球貿(mào)易中發(fā)揮著十分重要的作用。近年來，隨著集裝箱進出口吞吐量的增加、碼頭設(shè)備和技術(shù)不斷革新升級，傳統(tǒng)集裝箱碼頭已向集裝箱自動化碼頭發(fā)展。自動導(dǎo)引車（automated guided vehicle，AGV）作為水平運輸設(shè)備，由于其自動化程度高、靈活性強、安全性好的特點，為自動化碼頭水平運輸?shù)闹匾O(shè)備之一。

AGV 主要運用在柔性制造系統(tǒng)和自動化碼頭中，一個良好的AGV調(diào)度和路徑規(guī)劃策略能提高系統(tǒng)整體的作業(yè)效率。對于AGV 路徑規(guī)劃問題，很多國內(nèi)外學(xué)者投身于相關(guān)研究中，如沖突規(guī)避、最短路徑以及協(xié)同作業(yè)等。孫毛毛等[1]和王曉軍等[2]分別采用預(yù)先-實時規(guī)劃和離線-在線兩階段方法對倉儲系統(tǒng)中的AGV 實行路徑搜索和沖突規(guī)避。與倉儲中心不同，碼頭作業(yè)需要考慮到岸橋裝卸作業(yè)環(huán)節(jié)和集裝箱任務(wù)的時效性，且需要對突發(fā)事件進行靈活應(yīng)變。Zhong等[3]、Murakami等[4]、楊雅潔等[5]針對自動化碼頭的AGV 路徑規(guī)劃使用混合整數(shù)線性規(guī)劃建立數(shù)學(xué)模型，以實現(xiàn)AGV 的無沖突路徑規(guī)劃。然而在以上研究中，由于AGV 只能在固定時間段行駛在固定路段，因此對于多小車問題來說降低了路徑利用率，從而影響作業(yè)效率。

在路徑規(guī)劃問題中，作為尋路的經(jīng)典算法，A*算法是很多改進尋路算法的基礎(chǔ)。張新艷等[6]、楊周等[7]、Jia等[8]提出了一種基于時間窗的改進A*算法以實現(xiàn)動態(tài)的AGV無碰撞路徑規(guī)劃。宋宇等[9]將A*算法與粒子群算法相結(jié)合，在縮短路徑的同時降低了機器人的平均轉(zhuǎn)折角度數(shù)。牟德君等[10]將A*算法中的距離代價函數(shù)改為時間代價，并引入轉(zhuǎn)向和擁堵代價以減少AGV 轉(zhuǎn)向次數(shù)，躲避擁堵路段。然而這些離線算法并不適用于實時性要求比較高的場合。從Korf[11]的開創(chuàng)性研究開始，實時啟發(fā)式搜索已經(jīng)被研究用于單智能體探路問題中[12-14]。在A*算法基礎(chǔ)上，Sigurdson 等[15]在此基礎(chǔ)上提出了一種用于多智能體尋路的實時啟發(fā)式搜索算法，并與FAR[16]進行對比，表明該算法完成率更高且完成時間更短。Li等[17]首先使用多值決策圖進行沖突分類，再使用兩層搜索來為多智能體尋找滿足無沖突約束的路徑。Koenig 等[18]通過更新A*搜索之間的啟發(fā)式算法來加速具有相同目標(biāo)節(jié)點的重復(fù)A*搜索，結(jié)果表明自適應(yīng)實時搜索A*以更小的代價跟蹤軌跡，但其并未考慮到多智能體之間的相互影響。

由上可以看出，雖然目前已有眾多學(xué)者在多AGV路徑規(guī)劃方面提出各種研究，但多數(shù)只考慮到靜態(tài)環(huán)境下的無沖突路徑，忽略了時間和空間特性，而現(xiàn)有針對動態(tài)環(huán)境提出的實時避碰方法忽略了多AGV之間存在的協(xié)作性，無法對突發(fā)事件進行靈活應(yīng)變。且在以往研究中，對AGV 的集中式控制導(dǎo)致計算量巨大易造成控制中心崩潰，分布式控制由于AGV 之間通信困難而容易形成死鎖。因此，本文結(jié)合兩種控制方式的優(yōu)點，針對環(huán)境多變的碼頭水平運輸作業(yè)，采用混合式控制方式，如圖1 所示。將AGV 在行駛過程中與其他AGV 可能產(chǎn)生的同向、相向或交叉沖突視為動態(tài)沖突，讓每個AGV 單獨運行加權(quán)實時A*算法規(guī)劃路徑，將實時搜索的路徑信息上傳給控制中心，由控制中心實現(xiàn)路徑信息共享，根據(jù)共享信息各AGV 使用二叉樹原理進行無沖突規(guī)劃以實現(xiàn)動態(tài)沖突的規(guī)避。最后將該方法與普通A*算法進行比較，表明在同時滿足路徑長度較優(yōu)的情況下，本文的方法在多AGV 作業(yè)的沖突規(guī)避和計算時間方面表現(xiàn)的效果更優(yōu)。

圖1 混合式控制方式Fig.1 Hybrid control mode

1 問題描述

采用傳統(tǒng)的垂直碼頭布局，以進口箱作業(yè)為例，水平運輸工具為AGV。AGV以恒定的運輸速度經(jīng)過水平運輸區(qū)域，隨后到達任務(wù)指定堆場。以某自動化集裝箱碼頭為例，其平面布局如圖2所示，左側(cè)為岸橋作業(yè)區(qū)，右側(cè)為堆場作業(yè)區(qū)，中間為AGV 水平運輸作業(yè)區(qū)。其中，水平運輸作業(yè)區(qū)中間部分為AGV緩沖區(qū)，陰影區(qū)域為空閑AGV 停車區(qū)，該陰影區(qū)域?qū)τ谡谶M行水平運輸作業(yè)的AGV是不可通行的，將其視為AGV的靜態(tài)障礙。由于運輸任務(wù)的不同，AGV 從岸橋作業(yè)區(qū)到堆場作業(yè)區(qū)的運輸路徑也會不同，由此可能產(chǎn)生沖突。特別是在岸橋作業(yè)區(qū)，由于碼頭布局的特殊性，水平運輸任務(wù)的起始點均在同一側(cè)，當(dāng)多個運輸任務(wù)同時開始時，在該側(cè)最容易產(chǎn)生沖突。本文的研究目標(biāo)是在其水平運輸路線中為多AGV 規(guī)劃出一條無沖突、無擁堵且運輸時間最短的行駛路徑。

圖2 自動化集裝箱碼頭布局Fig.2 Layout of automated container terminal

在自動化碼頭作業(yè)環(huán)境中，每個AGV 需要從岸橋移動到任務(wù)指定的堆場以完成運輸任務(wù)。假設(shè)AGV速度恒定且每個AGV每次只運輸一個40英尺集裝箱，對涉及到的相關(guān)參數(shù)變量及其意義說明如下：

（1）參數(shù)

n：地圖中的節(jié)點；

n′：節(jié)點的后繼節(jié)點；

c：節(jié)點之間的距離；

t：時間單位；

A：一組AGV集合；

d：AGV之間的直線距離。

（2）變量

ε：啟發(fā)式的權(quán)重系數(shù)，ε≥1；

vision：AGV之間的安全距離；

lookahead：算法每次執(zhí)行的搜索深度，大于等于1的整數(shù)。

將AGV在運輸路徑中不可行駛的區(qū)域視為靜態(tài)障礙，在運輸節(jié)點碰到的其他AGV 視為動態(tài)障礙。一個AGV 每次僅完成一個任務(wù)，作業(yè)中途不可返回。當(dāng)d

（1）

（2）兩個AGV 將在同一時間步的直線距離小于安全距離。

不斷重復(fù)上述搜索的過程直至ai到達目標(biāo)節(jié)點搜索終止，從到之間形成一條路徑P(n)即為所尋路徑。

2 多AGV路徑的沖突規(guī)避

2.1 加權(quán)實時A*算法（WRTA*）

實時A*（RTA*）在移動前會執(zhí)行一個固定的計算以確定合理的下一步移動，直到達到目標(biāo)狀態(tài)。令每次執(zhí)行的搜索深度為lookahead，并讓每個AGV運行一個單獨的實時啟發(fā)式搜索，將其他AGV視為障礙物，若即將產(chǎn)生沖突(d

雖然每個實時搜索算法總是朝著估算成本最小的節(jié)點移動，但隨著算法運行，已遍歷節(jié)點的估計距離變得比未遍歷的節(jié)點高。為解決這個問題，在RTA*的基礎(chǔ)上為啟發(fā)式值h添加一個使得算法收斂速度最優(yōu)的權(quán)重系數(shù)ε，從而減少算法在CPU 中的運算時間，加快算法搜索。在該算法中，g表示AGV 與岸橋作業(yè)點的實際距離，h采用的是碼頭實際中的距離計算公式：曼哈頓距離，表示AGV與堆場作業(yè)點的距離。如式（1）所示：

設(shè)h*(n)是ai從節(jié)點n到堆場作業(yè)點的實際距離，h(n)是其下界值，用hε(n)表示ai在節(jié)點n的ε下界值，則有：為保持估計距離的一致性執(zhí)行式公式（3）、（4）操作：

（1）評估函數(shù)

對于所有的相鄰節(jié)點，計算評估函數(shù)如式（5）所示：

（2）啟發(fā)式規(guī)則

根據(jù)式（4）更新hε(n)。當(dāng)同時存在多個最小fε(n′)值時，選擇最小hε(n)的節(jié)點。另外，對于由任何移動指令生成的每個節(jié)點n和每個后繼節(jié)點n′，從n到的估計距離不大于從n到n′的距離加上從n′到的距離。h(n)需滿足以下條件：

（3）行為選擇

根據(jù)指令，ai移動到具有最小fε(n′)值的鄰居節(jié)點n′處。如式（9）所示：

此時，從節(jié)點n到目標(biāo)節(jié)點的路徑P=(n0,n1,n2,…,即為所求路徑。

2.2 動態(tài)沖突規(guī)避

多AGV并行能有效提高路徑利用率并提高作業(yè)效率，但由于各AGV之間無法共享實時位置信息，導(dǎo)致行為缺乏協(xié)調(diào)性，同時進行運輸作業(yè)時很容易發(fā)生沖突。為實現(xiàn)路徑信息共享，引入第三維度：時間t，形成時空三維坐標(biāo)(x,y,t)，表示AGV在時間t時處于位置(x,y)[19]，AGV 將時空位置信息上傳給控制中心，由控制中心檢索各AGV路徑，實現(xiàn)各AGV的實時位置共享。

如圖3所示，AGV在t=0 時從起點出發(fā)，在t=7 時到達終點。與傳統(tǒng)算法只記錄位置的空間二維坐標(biāo)(x,y)相比，時空坐標(biāo)精確記錄下每個AGV 在某一時間點的位置，通過時間檢索出同一時間步各AGV 的位置信息，從而方便檢查有無沖突發(fā)生。

圖3 時空圖Fig.3Space-time map

為解決多AGV 之間的動態(tài)沖突并降低運行時間，對AGV 進行分組規(guī)避，使用二叉樹原理對每個時間步中的節(jié)點進行分支，通過檢索時空坐標(biāo)實現(xiàn)路徑信息共享，判斷分支節(jié)點是否存在沖突，并對沖突節(jié)點的AGV重新規(guī)劃路徑。首先使用2.1 節(jié)中的WRTA*對每個AGV進行單獨地路徑搜索，再檢查一對AGV的路徑是否相互獨立，若獨立，則該組路徑為合理路徑；若在相同時間步長發(fā)生沖突，則對該組AGV 進行重新規(guī)劃。由于WRTA*每次搜索的深度是固定的，且AGV在重新規(guī)劃時有等待和繞行兩種選擇，從而避免了搜索過程中可能陷入無窮分支的死循環(huán)。圖4 為進行動態(tài)沖突規(guī)避的單次實時路徑搜索流程，循環(huán)執(zhí)行該流程直至各AGV到達相應(yīng)的目標(biāo)節(jié)點。

圖4 單次實時搜索流程Fig.4 Process of single real-time search

其中，動態(tài)沖突的判斷如圖5所示。在圖5中，一對AGVa1、a2從各自的起點分別向目標(biāo)點移動，且不可經(jīng)過另一小車的目標(biāo)點。首先執(zhí)行路徑搜索，分別得出其在特定的時間步長內(nèi)可能的移動路徑，之后共享路徑，將這兩條路徑在相應(yīng)的時間步長里合并成一組路徑再進行沖突檢測。

圖5 二叉樹沖突判斷原理Fig.5 Principle of binary tree conflict judgment

a1、a2分別在t=1、2、3時存在可能的沖突點，由圖5（c）可知主要沖突點在t=3 時的節(jié)點（3，3）處。首先在t=0 時在起始節(jié)點對鄰居節(jié)點的合法性進行判斷，即a1和a2需要在節(jié)點（1，4）、（2，5）處舍棄共同的鄰居節(jié)點（2，4）；在t=1 時選擇合法鄰居節(jié)點進行路徑搜索，同理，舍棄（2，3）與（3，4）節(jié)點；此時，a1和a2從在t=2 時有且僅有唯一的共同鄰居節(jié)點（3，3），因此需要重新規(guī)劃路徑，這里只列舉重新規(guī)劃的兩種解情況，如圖6所示。

圖6 重新規(guī)劃的兩種解Fig.6 Two solutions of replanning

在以上兩個解中，a1路徑均不變，Solution1為a2繞行的結(jié)果，Solution2 為a2在節(jié)點（2，5）處等待1 個時間步長?？梢钥闯觯藭ra1與a2在各個時間步均不存在沖突，兩個解均為合理路徑。由于Solution1的總路徑長度為13，Solution2的總路徑長度為11，故選擇當(dāng)前階段總路徑最短的Solution2為優(yōu)先解（若同時出現(xiàn)兩個或兩個以上相同長度的解，隨機選擇一個作為最優(yōu)解）。之后將得出的解路徑記作a12，與第三個小車a3共享路徑信息，重復(fù)以上步驟進行沖突判斷與規(guī)避。

3 算例分析

為有效描述港口水平運輸作業(yè)環(huán)境，參照某自動化碼頭AGV 局部水平運輸作業(yè)環(huán)境，將其轉(zhuǎn)換成大小為20×20 的柵格圖，柵格中心點為坐標(biāo)點，相鄰節(jié)點距離為1。在該柵格圖中，當(dāng)AGV之間的距離至少為對角線長度時可以避免AGV的相向、同向和交叉沖突。因此，兩種算法均使用安全距離參數(shù)進行搜索，以時空坐標(biāo)(x,y,t) 記錄路徑表，在CPU 為Intel Corei5-1135G7 2.40 GHz、內(nèi)存為16 GB 的Windows10 上使用Python3.7 版本進行算法運行。令表示一對AGVai和aj在時間步長為t時產(chǎn)生的動態(tài)沖突，記錄兩種算法的沖突數(shù)量、路徑長度和運行時間，綜合比較兩者的運行效果。

3.1 算例描述

任務(wù)安排如表1所示，AGV需要在相應(yīng)的岸橋作業(yè)點經(jīng)由行駛車道避開緩沖區(qū)到達指定的堆場作業(yè)點。已知生成4個任務(wù)請求，岸橋作業(yè)側(cè)共有7條車道，堆場作業(yè)側(cè)共有6條車道。

表1 AGV任務(wù)表Table 1 AGV task list

圖7 AGV路網(wǎng)柵格圖Fig.7 Grid map of AGV road network

3.2 實時搜索

在搜索到堆場作業(yè)區(qū)的目標(biāo)節(jié)點前一直使用2.1節(jié)中ε=2、lookahead=4 的WRTA*進行實時路徑搜索，即AGV 在岸橋作業(yè)區(qū)的起始節(jié)點移動前計算深度為4 的搜索，同時結(jié)合3.2 節(jié)中的動態(tài)沖突規(guī)避方法對搜索結(jié)果進行沖突檢查和規(guī)避，得到長度為4 的無沖突路徑，并向其方向移動，然后再次執(zhí)行同樣的搜索，直到抵達目標(biāo)節(jié)點。記錄各AGV無沖突路徑如表2和圖8（c）所示。

表2 實時搜索路徑表Table 2 Path table of real-time research

圖8 實時搜索路徑圖Fig.8 Path map of real-time research

由表2 可知，a2共執(zhí)行8 次搜索、a1和a3均執(zhí)行9次搜索、a4共執(zhí)行10次搜索后到達目標(biāo)節(jié)點。其中，在執(zhí)行第一次和第二次搜索時會有沖突產(chǎn)生，每執(zhí)行一次搜索后進行動態(tài)沖突規(guī)避，重新規(guī)劃路徑，其余搜索均為無沖突。

截取沖突路段進行分析，如圖8（a）所示，a2和a3執(zhí)行第一次搜索在t=1 時會產(chǎn)生沖突。此時a2在節(jié)點（1，11），a3在節(jié)點（1，12）處，兩車距離，故需要進行沖突規(guī)避。規(guī)避后a3保持路徑不變，a2繞行，重新規(guī)劃后的實際移動路徑如圖8（b）所示，當(dāng)t=1 時a2在節(jié)點（2，10）、a3在節(jié)點（1，12）處，再進行第二次搜索。如圖8（b）所示，a1和a3在執(zhí)行第二次搜索時在t=5 處會產(chǎn)生沖突，此時a1在節(jié)點（2，8）、a3在節(jié)點（2，9）處，規(guī)避后a3保持路徑不變，a1繞行，此時a1在節(jié)點（3，7）、a3在節(jié)點（2，9）處。全部搜索完成后得到實際無沖突路徑如圖8（c）所示。

標(biāo)識各AGV 路徑中出現(xiàn)的共同節(jié)點，如圖8（c）所示，根據(jù)表2 驗證路徑的合理性，如標(biāo)注①處a1與a3分別在t=3 和t=8 經(jīng)過節(jié)點（2，6）。標(biāo)注②處a1與a3分別在t=4 和t=7 經(jīng)過節(jié)點（2，7）。

同理，各AGV均在不同時間步經(jīng)過③~⑧處節(jié)點。由上分析可知，各AGV在不同時間步經(jīng)過共同節(jié)點，連續(xù)兩個時間步長內(nèi)各AGV之間的距離均滿足d≥vision的無沖突要求，各AGV之間不存在沖突，該路徑合理。

3.3 普通搜索

在執(zhí)行普通A*進行搜索時得到各AGV路徑如圖9所示。對其沖突區(qū)進行分析，AGV 之間共產(chǎn)生9 個沖突：a1與a3在t=5 和t=6 時產(chǎn)生沖突在t=1、t=2、t=3 時產(chǎn)生沖突和；a1與a4在t=7 和t=8 時產(chǎn)生沖突和；a2與a4在t=4和t=5 時產(chǎn)生沖突

圖9 普通A*搜索路徑圖Fig.9 Path map of ordinary A* search

同理，對其使用3.2 節(jié)中沖突規(guī)避的方法進行多AGV并行運算，得出各AGV的無沖突路徑如表3和圖10所示，各AGV在不同時間步經(jīng)過共同節(jié)點①~④。

表3 普通搜索的無沖突路徑表Table 3Conflict free path table of ordinary research

圖10 普通搜索的無沖突路徑圖Fig.10 Conflict free path map of ordinary search

3.4 結(jié)果分析

對3.2 和3.3 節(jié)的結(jié)果進行分析如表4 所示。在算法消耗時間方面：使用實時搜索計算時間共消耗了7.061 6 s，使用普通搜索的計算時間共消耗了7.937 2 s；在沖突數(shù)量方面：在未進行動態(tài)沖突規(guī)避時，WRTA*共產(chǎn)生2 次沖突，普通A*共產(chǎn)生9 次沖突；在路徑長度方面：兩種方法得出的4 條路徑總長度均為110。為進一步驗證算法有效性，設(shè)置不同AGV 規(guī)模下的路徑規(guī)劃算例，得到的結(jié)果如表5所示。

表4 結(jié)果分析Table 4 Result analysis

表5 不同AGV規(guī)模下的結(jié)果分析Table 5 Analysis of results under different AGV scales

由以上結(jié)果可知，沖突數(shù)量和計算時間會隨著AGV數(shù)量的增加而增加，WRTA*在計算時間和產(chǎn)生的沖突數(shù)量方面優(yōu)于普通A*。另外，可以看出無論使用WRTA*還是普通A*，結(jié)合使用2.2節(jié)中的動態(tài)避障方法最終都能得到無沖突路徑。

碼頭作業(yè)是一個實時作業(yè)環(huán)境，與普通A*搜索相比，WRTA*算法由于每次執(zhí)行固定深度的搜索，在作業(yè)中途遇到如環(huán)境變化、設(shè)備故障、目標(biāo)節(jié)點改變等需要終止算法的突發(fā)情況時其損失代價較小。而普通A*由于在執(zhí)行路徑的第一步之前就計算好整個解路徑，一旦碰到突發(fā)情況整個搜索將前功盡棄。特別是在地圖較大的情況下，由于一次計算全局解，普通搜索儲存的路徑表更長，易造成存儲負擔(dān)，降低計算速度。因此，在碼頭作業(yè)環(huán)境中，本文提出的實時搜索方法由于每次執(zhí)行固定深度搜索，且在搜索過程中伴隨沖突規(guī)避，故在多AGV作業(yè)的動態(tài)沖突規(guī)避和計算時間方面表現(xiàn)的效果更優(yōu)。

4 結(jié)論

針對多AGV 路徑規(guī)劃問題，考慮到碼頭作業(yè)的實時環(huán)境和多AGV 之間的行為影響和協(xié)作性，本文在混合控制模式下使用WRTA*搜索算法尋找路徑，采用時空三維坐標(biāo)以實現(xiàn)實時路徑信息共享，同時結(jié)合二叉樹原理進行沖突判斷和規(guī)避，有效避免了多AGV 作業(yè)產(chǎn)生的沖突問題，最后通過算例與普通A*算法相比較。結(jié)果表明，WRTA*算法的消耗時間較小，且由于每個AGV單獨使用加權(quán)實時A*交錯規(guī)劃路徑，產(chǎn)生的沖突數(shù)量遠少于普通A*算法，驗證了實時搜索方法的有效性。

本文是在AGV調(diào)度以及任務(wù)分配順序已知的前提下進行的路徑規(guī)劃，在日后研究中可以結(jié)合任務(wù)調(diào)度在避障過程中引入任務(wù)優(yōu)先級規(guī)則或其他優(yōu)先級規(guī)則進行系統(tǒng)性優(yōu)化。