張其嬌，丁 一，秦 濤

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

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

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

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

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

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

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

1 問(wèn)題描述

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

圖2 自動(dòng)化集裝箱碼頭布局Fig.2 Layout of automated container terminal

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

（1）參數(shù)

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

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

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

t：時(shí)間單位；

A：一組AGV集合；

d：AGV之間的直線距離。

（2）變量

ε：?jiǎn)l(fā)式的權(quán)重系數(shù)，ε≥1；

vision：AGV之間的安全距離；

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

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

（1）

（2）兩個(gè)AGV 將在同一時(shí)間步的直線距離小于安全距離。

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

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

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

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

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

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

（1）評(píng)估函數(shù)

對(duì)于所有的相鄰節(jié)點(diǎn)，計(jì)算評(píng)估函數(shù)如式（5）所示：

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

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

（3）行為選擇

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

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

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

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

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

圖3 時(shí)空?qǐng)DFig.3Space-time map

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

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

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

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

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

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

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

3 算例分析

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

3.1 算例描述

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

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

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

3.2 實(shí)時(shí)搜索

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

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

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

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

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

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

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

3.3 普通搜索

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

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

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

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

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

3.4 結(jié)果分析

對(duì)3.2 和3.3 節(jié)的結(jié)果進(jìn)行分析如表4 所示。在算法消耗時(shí)間方面：使用實(shí)時(shí)搜索計(jì)算時(shí)間共消耗了7.061 6 s，使用普通搜索的計(jì)算時(shí)間共消耗了7.937 2 s；在沖突數(shù)量方面：在未進(jìn)行動(dòng)態(tài)沖突規(guī)避時(shí)，WRTA*共產(chǎn)生2 次沖突，普通A*共產(chǎn)生9 次沖突；在路徑長(zhǎng)度方面：兩種方法得出的4 條路徑總長(zhǎng)度均為110。為進(jìn)一步驗(yàn)證算法有效性，設(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ù)量和計(jì)算時(shí)間會(huì)隨著AGV數(shù)量的增加而增加，WRTA*在計(jì)算時(shí)間和產(chǎn)生的沖突數(shù)量方面優(yōu)于普通A*。另外，可以看出無(wú)論使用WRTA*還是普通A*，結(jié)合使用2.2節(jié)中的動(dòng)態(tài)避障方法最終都能得到無(wú)沖突路徑。

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

4 結(jié)論

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

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