考慮沖突規避的自動化碼頭多AGV路徑規劃

張其嬌，丁 一，秦 濤

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

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

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

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

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

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

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

1 問題描述

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

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

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

（1）參數

n：地圖中的節點；

n′：節點的后繼節點；

c：節點之間的距離；

t：時間單位；

A：一組AGV集合；

d：AGV之間的直線距離。

（2）變量

ε：啟發式的權重系數，ε≥1；

vision：AGV之間的安全距離；

lookahead：算法每次執行的搜索深度，大于等于1的整數。

將AGV在運輸路徑中不可行駛的區域視為靜態障礙，在運輸節點碰到的其他AGV 視為動態障礙。一個AGV 每次僅完成一個任務，作業中途不可返回。當d

（1）

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

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

2 多AGV路徑的沖突規避

2.1 加權實時A*算法（WRTA*）

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

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

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

（1）評估函數

對于所有的相鄰節點，計算評估函數如式（5）所示：

（2）啟發式規則

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

（3）行為選擇

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

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

2.2 動態沖突規避

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

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

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

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

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

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

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

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

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

在以上兩個解中，a1路徑均不變，Solution1為a2繞行的結果，Solution2 為a2在節點（2，5）處等待1 個時間步長。可以看出，此時a1與a2在各個時間步均不存在沖突，兩個解均為合理路徑。由于Solution1的總路徑長度為13，Solution2的總路徑長度為11，故選擇當前階段總路徑最短的Solution2為優先解（若同時出現兩個或兩個以上相同長度的解，隨機選擇一個作為最優解）。之后將得出的解路徑記作a12，與第三個小車a3共享路徑信息，重復以上步驟進行沖突判斷與規避。

3 算例分析

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

3.1 算例描述

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

表1 AGV任務表Table 1 AGV task list

圖7 AGV路網柵格圖Fig.7 Grid map of AGV road network

3.2 實時搜索

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

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

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

由表2 可知，a2共執行8 次搜索、a1和a3均執行9次搜索、a4共執行10次搜索后到達目標節點。其中，在執行第一次和第二次搜索時會有沖突產生，每執行一次搜索后進行動態沖突規避，重新規劃路徑，其余搜索均為無沖突。

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

標識各AGV 路徑中出現的共同節點，如圖8（c）所示，根據表2 驗證路徑的合理性，如標注①處a1與a3分別在t=3 和t=8 經過節點（2，6）。標注②處a1與a3分別在t=4 和t=7 經過節點（2，7）。

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

3.3 普通搜索

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

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

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

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

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

3.4 結果分析

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

表4 結果分析Table 4 Result analysis

表5 不同AGV規模下的結果分析Table 5 Analysis of results under different AGV scales

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

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

4 結論

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

本文是在AGV調度以及任務分配順序已知的前提下進行的路徑規劃，在日后研究中可以結合任務調度在避障過程中引入任務優先級規則或其他優先級規則進行系統性優化。