基于Ant-agent的自動化碼頭AGV控制算法

蘭培真，陳錦文，曹士連

(1.集美大學海上交通安全研究所，福建廈門361021；2.交通安全應急信息技術國家工程實驗室，福建廈門361021)

0 引 言

自動化碼頭AGV 運輸系統(tǒng)高效穩(wěn)定地運行及合理地調度對于提高自動化碼頭的作業(yè)效率有著非常重要的意義.持續(xù)增長的港口吞吐量需要更多的自動導引車(簡稱AGV)分擔集裝箱水平運輸任務.由于土地資源限制，AGV系統(tǒng)的運輸路網(wǎng)難以進一步擴大，使得AGV 路徑?jīng)_突和道路死鎖問題日益凸顯.

對于解決自動化碼頭AGV 路徑?jīng)_突和道路死鎖的研究集中在靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃兩方面.文獻[1-4]利用約束條件對AGV 行駛進行限制，求得目標函數(shù)的最優(yōu)解規(guī)劃其行駛路徑，然而該方法無法有效解決路徑?jīng)_突和突發(fā)狀況，在長時間的運輸作業(yè)下效率較低；文獻[5-6]利用區(qū)域控制策略可避免AGV 間的路徑?jīng)_突，但針對緊急情況無法實現(xiàn)安全的動態(tài)路徑規(guī)劃；文獻[7-8]使用時間窗算法實現(xiàn)了AGV 的動態(tài)路徑規(guī)劃，但運輸任務量較大時，無法有效解決路徑?jīng)_突問題，AGV 停車等待時間較長.因此，一種實時避免AGV路徑?jīng)_突和解除道路死鎖的方法對提高自動化碼頭集裝箱的水平運輸效率至關重要.

文獻[9-10]利用蟻群算法實現(xiàn)了對單一機器人的動態(tài)路徑規(guī)劃，但此方法針對自動化碼頭的多AGV 控制，難以實現(xiàn)全局最優(yōu).本文根據(jù)自動化碼頭AGV 運輸系統(tǒng)作業(yè)的特點，仿照蟻群覓食行為，提出一種基于Ant-agent 的AGV 控制算法，實現(xiàn)多AGV 的實時運動控制，解決路徑?jīng)_突和道路死鎖問題，提高集裝箱的水平運輸效率.

1 AGV路徑選擇

1.1 AGV運輸系統(tǒng)

自動化碼頭內集裝箱的水平運輸由中控系統(tǒng)向AGV 運輸系統(tǒng)(簡稱系統(tǒng))內的所有AGV 發(fā)送指令完成，本質上為集中式結構的多agent 系統(tǒng)(Multi-agent System，MAS)[11].由于不同種類的系統(tǒng)控制AGV 的方式均不同，故對算法及模型研究的系統(tǒng)提出以下假設：

(1)系統(tǒng)為集中式結構的MAS，一切指令由中控系統(tǒng)發(fā)送至各AGV.

(2)系統(tǒng)內各AGV之間無任何信息通訊.

(3)系統(tǒng)的運輸路網(wǎng)由路段和節(jié)點構成.

(4)各路段不允許兩臺及以上AGV并列行駛.

(5)各節(jié)點不允許兩臺及以上AGV同時經(jīng)過.

(6)不考慮環(huán)境、天氣等外部不可控因素對系統(tǒng)的影響.

1.2 Ant-agent與擁擠度

蟻群算法仿照蟻群覓食，讓螞蟻通過釋放信息素來搜索路徑，若將AGV 視為Ant-agent，讓AGV 具備螞蟻的各項特性，則中控系統(tǒng)可根據(jù)信息素濃度實時判斷路網(wǎng)狀況，結合各輛AGV 當前位置和目標位置向其發(fā)送指令進行集裝箱運輸.本文將蟻群算法融入MAS，提出了一種基于Antagent 的AGV 控制算法，實現(xiàn)對AGV 運輸行駛的實時控制.

AGV 運輸系統(tǒng)需同時控制多輛AGV 在運輸路網(wǎng)上行駛，若與傳統(tǒng)蟻群算法相同，信息素為正反饋機制，AGV 將產(chǎn)生路徑?jīng)_突和碰撞.同時，由于各路段交叉點間的距離較長，同一時刻同一路段上的不同位置能夠感知到的信息素濃度均不同，若將路段作為信息素載體，無法準確表示此路段對各AGV 的排斥程度.故對Ant-agent(AGV)提出如下限定：

(1)信息素具有負反饋機制，對同伴產(chǎn)生排斥效應.

(2)每個Ant-agent 均攜帶相同濃度λ的信息素進入運輸路網(wǎng)，在運輸過程中，信息素不釋放，濃度不改變.

(3)距離越遠感知到的信息素濃度越低.

(4)利用路徑交叉點感知信息素，信息素濃度之和為該點的擁擠度.

為實現(xiàn)對AGV 的實時控制，采用擁擠度實時全局更新策略，各節(jié)點的擁擠度根據(jù)每一時刻運輸路網(wǎng)內所有AGV的位置進行更新.

式中：n為t時刻運輸路網(wǎng)內AGV 的數(shù)量；為t時刻第k輛AGV與點(i,j)間的直線距離.

1.3 AGV的狀態(tài)轉移規(guī)則

由于存在停車以避免路徑?jīng)_突的情況，AGV的狀態(tài)分為停車等待和選擇下一路徑點兩類.設AGV在節(jié)點(i,j)處的下一路徑點的集合為(I′,J′)，

節(jié)點(i′,j′)處的擁擠度越高，選擇此節(jié)點為下一路徑點發(fā)生路徑?jīng)_突和碰撞的可能性越大，引入擁擠度閾值q來規(guī)避AGV 間的碰撞.當τ(i′,j′)=0時，表明節(jié)點(i′,j′)周圍無AGV 作業(yè)，選擇此節(jié)點為下一路徑點不存在碰撞危險；當τ(i′,j′)=λ時，表明節(jié)點(i′,j′)感知到的信息素濃度之和為λ，等價于此節(jié)點處有1 輛AGV，若選擇此節(jié)點為下一路徑點，極易發(fā)生碰撞.因此，本文將擁擠度閾值的范圍設定為(0,λ).設allowedk為N(k)AGV的下一路徑點集合，表示第k輛AGV.若τ(i′,j′)(t)＜q，則 以(i′,j′)為下一路徑點發(fā)生碰撞的可能性較小，不影響運輸系統(tǒng)的正常運行，(i′,j′)∈allowedk；若τ(i′,j′)(t)≥q，則以(i′,j′)為下一路徑點發(fā)生碰撞的可能性較大，會影響系統(tǒng)的正常運行，(i′,j′)?allowedk.若allowedk=?，則N(k)AGV停車等待；若allowedk≠?，則N(k)AGV選擇下一路徑點.

AGV路徑點的選擇與待選節(jié)點的吸引程度和啟發(fā)函數(shù)有關.以擁擠度閾值q與時刻t節(jié)點(i′,j′)處信息素濃度τ(i′,j′)(t)的差值來表示節(jié)點(i′,j′)對AGV的吸引值，即

傳統(tǒng)蟻群算法將當前節(jié)點與下一節(jié)點間的能見度作為啟發(fā)函數(shù)[1-2]，但存在控制對象難以快速接近目標的缺點.建立兩類啟發(fā)函數(shù)和，分別表示AGV當前所在節(jié)點(i,j)與下一節(jié)點(i′,j′)間的能見度和下一節(jié)點(i′,j′)與目標點(ex,ey)間的能見度，即

式 中：為節(jié)點(i,j)與節(jié)點(i′,j′)的直線距離；為節(jié)點(i′,j′)與目標點(ex,ey)的直線距離.

的狀態(tài)轉移概率為

式中：為t時刻從節(jié)點(i,j)轉移至節(jié)點(i′,j′)的概率；α,β,γ分別為節(jié)點吸引函數(shù)，兩類啟發(fā)函數(shù)和的重要程度系數(shù).根據(jù)式(6)確定下一路徑點(i′0,j0′).

2 沖突檢測及解決機制

擁擠度閾值q可規(guī)避如圖1(a)所示的節(jié)點沖突.

令

式中：為到達節(jié)點(i′,j′)的時刻；dsafe為AGV間的安全距離；v為AGV的行駛速度.

若同時滿足式(9)和式(10)，即在t時刻，和(a,b為AGV 編號)分別從(i,j)和(i″,j″)同時駛向(i′,j′)且到達節(jié)點(i′,j′)的時間間隔小于行駛安全距離所需時間，則中央控制系統(tǒng)判定兩輛AGV產(chǎn)生節(jié)點沖突，如圖1(b)所示.

若同時滿足式(10)～式(12)，或式(13)～式(15)，或式(16)～式(18)，則中央控制系統(tǒng)判定存在路徑擁堵，分別如圖1(c)，圖1(d)和圖1(e)所示.

圖1 路徑?jīng)_突示意圖Fig.1 Diagram of path conflict

針對節(jié)點沖突，利用沖突節(jié)點對兩輛AGV 的綜合吸引值進行比較，以確定此沖突節(jié)點為哪輛AGV的下一路徑點.沖突節(jié)點(i′,j′)對的綜合吸引函數(shù)為

式 中：為節(jié)點(i′,j′)對的吸引值；為當前位置與節(jié)點(i′,j′)間的能見度；為 節(jié)點(i′,j′)與目標節(jié)點間的能見度.

設定如圖2所示的映射f：A→B.

圖2 映射示意圖Fig.2 Diagram of mapping

通過式(20)～式(22)依次確定α、β、γ的最大值μ、中間值ξ、最小值φ，根據(jù)式(23)～式(25)確定第一優(yōu)先級函數(shù)P1，第二優(yōu)先級函數(shù)P2，第三優(yōu)先級函數(shù)P3.

首先比較的第一優(yōu)先級函數(shù)P1k.若P1a ＜P1b，則沖突節(jié)點(i′,j′)為的下一路徑點；若P1a ＞P1b，則沖突節(jié)點(i′,j′)為的下一路徑點；若P1a=P1b，則逐級依次比較P2a與P2b、P3a與P3b.若P2a=P2b且P3a=P3b，則中控系統(tǒng)隨機決定哪輛AGV 選擇(i′,j′)為下一路徑點；另一輛AGV在其allowed中選擇其余節(jié)點，若allowed中無其他節(jié)點，則停車等待.

針對路徑擁堵，中控系統(tǒng)將兩AGV 之間的距離控制在安全距離dsafe后停車.

3 算法設計

根據(jù)自動化碼頭AGV 運輸系統(tǒng)的運營模式，結合狀態(tài)轉移規(guī)則和沖突解決機制，提出基于Ant-agent 的自動化碼頭AGV 控制算法(簡稱Antagent算法)，流程如圖3所示.

圖3 Ant-agent 算法流程圖Fig.3 Flow chart of Ant-agent algorithm

4 算法驗證及性能分析

4.1 算法性能評價及仿真環(huán)境

參數(shù)q，α，β，γ直接影響AGV 的路徑選擇、局部死鎖的解除和集裝箱的水平運輸效率，因此利用表1中3項指標衡量算法的性能.

表1 算法性能及對應指標Table1 Algorithm performance and corresponding indicators

蟻群算法中，當信息素和啟發(fā)式函數(shù)的重要程度均位于區(qū)間[1,5]時，算法的性能較優(yōu)[13-14].結合擁擠度閾值q的范圍，將初始試驗參數(shù)設置為

共有4 個參數(shù)，每個參數(shù)包含9 個水平.為以較少的試驗次數(shù)獲取精確的最優(yōu)參數(shù)組合，分兩個階段，采用均勻設計法進行試驗，以全局最優(yōu)為選擇依據(jù)，確定運輸效率最高時的參數(shù)組合最優(yōu)，每個參數(shù)組合取10 次試驗的平均值為最終結果，具體試驗方案如圖4所示.

在Netlogo 6.1.0中，參照某自動化碼頭的布局和實際數(shù)據(jù)構建如圖5所示仿真環(huán)境，包含3個雙小車岸橋(STS)裝卸點，24 個自動化軌道吊(ARMG)裝卸點和18 臺AGV.AGV 由ARMG 行駛至STS 的上行速度為5.8 m ?s-1，由STS 行駛至ARMG的下行速度為3.5 m ?s-1，安全距離為10 m.

圖4 兩階段均勻設計試驗流程圖Fig.4 Flow chart of two-stage uniform design experiment

圖5 AGV 運輸路網(wǎng)圖Fig.5 Diagram of AGV transportation road network

4.2 驗證結果與對比分析

采用如圖4所示的方法找出不同運輸任務量下算法的最優(yōu)參數(shù)組合，實現(xiàn)算法在不同運輸任務量下的自適應調整，結果如圖6所示.

圖6 參數(shù)自適應變化曲線圖Fig.6 Curve of parameter adaptive change

當運輸任務量小于12 000 TEU 時，α在[5.4,5.5] 內波動，β在[0.5,0.6] 內波動，γ在[3.9,4.4] 內波動，q在[0.26λ,0.31λ] 內波動；當運輸任務量大于等于12 000 TEU時，α=5.4，β=0.6，γ=4.4，q=0.26λ.由圖6可以看出，隨著運輸任務量的增大，下一節(jié)點與目標節(jié)點間能見度的重要程度系數(shù)γ顯著增加，擁擠度閾值q略有減小，同時算法參數(shù)的自適應調整趨于穩(wěn)定.

將有兩類啟發(fā)函數(shù)F2和F3的Ant-agent 算法(Ant-agent algorithm with two types of heuristic function，Ant-agent-2hf)與只有當前節(jié)點與待選節(jié)點間啟發(fā)函數(shù)F2的Ant-agent 算法(Ant-agent-hf)，文獻[8]提出的基于時間窗改進Dijskra的動態(tài)路徑規(guī)劃算法(TW-Dijskra)在不同運輸任務量下進行性能對比，結果如圖7～圖9所示.

圖7 避碰性能對比Fig.7 Comparison of collision avoidance performance

圖8 解鎖性能對比Fig.8 Comparison of unlock performance

圖9 運輸效率對比Fig.9 Comparison of transportation efficiency

各運輸任務量下，Ant-agent-2hf較TW-Dijskra，避碰性能、解鎖性能和運輸效率平均提升11.18%、22.69%、8.16%.由圖7～圖9可以看出，由于TW-Dijskra 無法實時的規(guī)避路徑?jīng)_突，缺少有效的AGV死鎖解除方法，隨著運輸任務量的增加，當各節(jié)點的最優(yōu)時間窗均被占用時，其避碰性能和解鎖性能會顯著下降，導致運輸效率降低.

Ant-agent-2hf和Ant-agent-hf在實現(xiàn)動態(tài)路徑搜索的基礎上，均可利用擁擠度閾值和沖突解決機制，實時避免AGV 間的路徑?jīng)_突，結合AGV 的位置變化實時更新各節(jié)點處的擁擠度，并利用狀態(tài)轉移規(guī)則解除AGV 的局部死鎖.但由于Antagent-2hf添加了啟發(fā)函數(shù)F3，AGV可更加快速地接近目標點，在相同運輸任務量下可減少AGV 路徑?jīng)_突和停車次數(shù)，避碰性能較Ant-agent-hf 平均提升6.42%.Ant-agent-2hf與Ant-agent-hf均利用狀態(tài)轉移規(guī)則解除AGV 的局部死鎖，但更少的路徑?jīng)_突和停車次數(shù)降低了AGV 局部死鎖程度，因而Ant-agent-2hf 解鎖性能更優(yōu)，較Ant-agent-hf 平均提升1.06%.避碰性能和解鎖性能的優(yōu)勢使Antagent-2hf 具有更高的運輸效率，較Ant-agent-hf 平均提升了5.02%.結合圖9可以看出，Ant-agent-2hf在較大的運輸任務量下，運輸效率優(yōu)勢更明顯.

5 結 論

針對自動化碼頭存在的AGV 路徑?jīng)_突和道路死鎖問題，提出基于Ant-agent 的AGV 控制算法.與傳統(tǒng)的動態(tài)路徑規(guī)劃方法相比，Ant-agent算法可根據(jù)路網(wǎng)內AGV 位置實時更新各節(jié)點的擁擠度，利用狀態(tài)轉移規(guī)則和沖突解決機制，有效地解決AGV的路徑?jīng)_突和道路死鎖問題，提高AGV的運輸效率.隨著船舶大型化趨勢的日益明顯，Ant-agent算法在較大的運輸任務量下具有更好的應用意義.