基于沖突預(yù)測的多自動導(dǎo)引小車避碰決策優(yōu)化

曹小華，朱 孟

(武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063)

0 引言

在“中國制造2025”大背景下，我國的工業(yè)水平不斷發(fā)展，智能制造進程不斷推進，柔性裝配流水線和自動化立體倉庫全面進入高速發(fā)展階段。由于在成本、效率、靈活性、可靠性等指標(biāo)上具有優(yōu)勢，自動導(dǎo)引小車(Automated Guided Vehicle，AGV)在工業(yè)中的作用日益突出。

然而，AGV在工業(yè)上的應(yīng)用也面臨著一些問題，其中一個關(guān)鍵問題就是多AGV的路徑?jīng)_突[1-2]。路徑?jīng)_突指同一時段多臺AGV的行駛路線出現(xiàn)交叉或重疊，主要分為路口沖突、追趕沖突和相向沖突[3]。路徑?jīng)_突一旦處理不當(dāng)，就會出現(xiàn)AGV碰撞或死鎖問題，嚴(yán)重影響多AGV系統(tǒng)的工作效率。近年來，多AGV系統(tǒng)的路徑?jīng)_突已經(jīng)成為AGV研究的重點[4]。面對多AGV系統(tǒng)可能出現(xiàn)的路徑?jīng)_突情況，一般做法是應(yīng)用數(shù)學(xué)規(guī)劃方法為AGV在地圖中提前規(guī)劃好無沖突路徑[4-7]，這種路徑規(guī)劃方法是非實時的靜態(tài)路徑規(guī)劃，AGV在行駛過程中并不總能在規(guī)劃的時間到達指定位置，而且隨著AGV數(shù)量的增加，多臺AGV之間的運行路線必將出現(xiàn)交叉和重疊。為了避免AGV路徑?jīng)_突，前人根據(jù)路網(wǎng)的實時狀態(tài)動態(tài)調(diào)整AGV的路徑[8-14]，然而動態(tài)路徑規(guī)劃不但增加了運算量，而且當(dāng)多臺AGV聚集在某一區(qū)域執(zhí)行任務(wù)時，部分AGV必須繞開這片區(qū)域來避免路徑?jīng)_突，從而增加AGV的額外運行時間，除此之外，在高密集型多AGV系統(tǒng)中可能會出現(xiàn)無法搜索到無沖突路徑的情況。

針對上述現(xiàn)狀，為了減少路徑規(guī)劃的計算量，本文采用非實時的靜態(tài)路徑規(guī)劃算法，并通過沖突預(yù)測和避碰決策加以改進，AGV的最優(yōu)路徑在任務(wù)發(fā)布時就規(guī)劃完畢且不再更改，面對路徑?jīng)_突時將會采用停車或繞道的避碰策略來解除路徑?jīng)_突。本文運用圖論知識構(gòu)建多AGV系統(tǒng)的工作地圖，并基于頂點屬性預(yù)測路徑?jīng)_突。考慮到執(zhí)行避碰決策對系統(tǒng)全局狀態(tài)的影響，采用粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法優(yōu)化避碰決策，并對PSO算法進行改進來改善優(yōu)化效果。最后在VS2012平臺上搭建上位機系統(tǒng)進行實驗驗證，結(jié)果表明改進的PSO算法具有較優(yōu)的性能。

1 路徑?jīng)_突分析與預(yù)測

在路徑?jīng)_突問題上，相比于傳統(tǒng)的重規(guī)劃無沖突路徑，文本所提方法注重已知路徑下的避碰決策優(yōu)化，即在路徑?jīng)_突時不進行二次路徑規(guī)劃。在多路徑類型的工作環(huán)境下，本文提出結(jié)合頂點屬性和AGV位姿信息的沖突預(yù)測方法，通過預(yù)測多AGV系統(tǒng)未來的路徑?jīng)_突狀態(tài)來實現(xiàn)避碰決策的全局優(yōu)化。

在本文研究的港口、物流倉儲等環(huán)境下的多AGV系統(tǒng)中，AGV沿固定車道行駛，將車道的交叉點和卸貨點作為圖的頂點，車道作為連接兩相鄰頂點的邊。AGV行駛的車道分為單向單車道、雙向單車道、雙向雙車道3類。因為單向單車道和雙向雙車道可以看作為雙向單車道的一種特殊情況，所以在處理路徑?jīng)_突情況時只需要制定AGV在雙向單車道上的行駛規(guī)則和避碰規(guī)則，即可解決多AGV系統(tǒng)中的路徑?jīng)_突。

針對上述情況，本文提出一種基于圖論的沖突預(yù)測方法，預(yù)測過程包括基于頂點屬性快速搜索階段、結(jié)合AGV位姿預(yù)測沖突階段兩個階段。首先，基于圖論的基本原理將某一時刻向某個頂點行駛的總AGV數(shù)量作為頂點的一個屬性。顯然，若某一時刻朝向某頂點的AGV數(shù)量大于等于2，則在該頂點處可能發(fā)生沖突，根據(jù)這一特點可以快速搜索到可能發(fā)生沖突的頂點，避免預(yù)測過程中的重復(fù)計算。然后，根據(jù)各個AGV的位姿信息進一步確定可能發(fā)生沖突的AGV。

(1)基于頂點屬性的快速搜索階段

建立二維數(shù)組M[A][B]表示頂點與AGV的關(guān)系。其中A為AGV的總數(shù)量，B為地圖中頂點的總數(shù)量，M[i][j]=k表示當(dāng)前時刻下j號頂點是i號AGV的第k個目標(biāo)頂點。在沖突頂點的搜索過程中需要遍歷數(shù)組M，將當(dāng)前時刻具有相同目標(biāo)頂點的AGV存儲到一個一維數(shù)組中，表示可能存在沖突的頂點集合。搜索算法的偽代碼如下：

算法1路徑?jīng)_突頂點搜索算法偽代碼。

1 /* 采用頂點屬性法搜索沖突頂點*/

2 建立頂點屬性矩陣M[A][B]

3 建立頂點沖突數(shù)組Conflict[B]

3 for b=0, b

4 Conflict[b]=0;

5 for a=0, a

6 If M[a][b]=1 then

7 Conflict[b]++;

8 End

9 If Conflict[b]>1 then

10 b號節(jié)點可能發(fā)生沖突

11 End

(2)結(jié)合AGV位姿的預(yù)測沖突階段

通過搜索算法快速得出可能發(fā)生路徑?jīng)_突的頂點后，需要接收AGV內(nèi)置傳感器的數(shù)據(jù)，根據(jù)AGV的實際位姿預(yù)測路徑?jīng)_突區(qū)域的中心頂點。

如圖1所示，當(dāng)前時刻AGV1和AGV2均以中心頂點作為目標(biāo)，兩AGV的行駛路線存在交叉，為了預(yù)測AGV是否會發(fā)生碰撞，需要結(jié)合AGV位姿信息進行分析。

首先記錄一臺AGV從進入到離開一個頂點所需的時間，記為t0，根據(jù)該時間估算AGV的安全距離D，D=Vmaxt0+K。對于可能發(fā)生路徑?jīng)_突的AGV，采用安全距離法判斷是否會發(fā)生碰撞。首先調(diào)用通過頂點屬性法初步確定的路徑?jīng)_突的頂點和以其為目標(biāo)頂點的AGV，然后計算各個AGV與頂點之間的距離S1，S2，…，Sk。對于任意兩臺AGV頂點的距離Si和Sj，若|Si-Sj| ≤D，則預(yù)測i號AGV和j號AGV會在該頂點處發(fā)生碰撞；若|Si-Sj|>D，則判定不發(fā)生碰撞。

預(yù)測出發(fā)生碰撞的AGV和頂點后，一般采取停車或繞道讓行的方式解決沖突。

2 避碰決策的優(yōu)化方法

2.1 多AGV系統(tǒng)的全局優(yōu)化目標(biāo)

在多AGV系統(tǒng)中，AGV在避碰過程中的通行次序?qū)⒂绊懳磥頃r刻的系統(tǒng)路徑?jīng)_突狀態(tài)，因此如何規(guī)劃多AGV的避碰決策非常重要。在第2章路徑?jīng)_突預(yù)測方法的基礎(chǔ)上，提出一種基于沖突預(yù)測的多AGV系統(tǒng)避碰決策優(yōu)化方法。

對于一個沖突時刻ti，對發(fā)生路徑?jīng)_突的AGV做出避碰規(guī)劃γi。對于每臺AGV-Ak，用Lk表示其等待時長。對于目標(biāo)規(guī)劃γ={γ1,γ2,γ3,…,γi}，K號AGV產(chǎn)生的總等待時長記為Lk(γ)∈[0,∞)。由此得出，同時執(zhí)行任務(wù)的m輛AGV的總等待時長

(1)

設(shè)定每臺AGV在執(zhí)行一次任務(wù)所需的時間為

nk0+nk1+nk2=nk。

(2)

式中：Tk為k號AGV經(jīng)過的總時間；v為AGV的平均速度；eij為頂點ij的距離(i,j

Lk(γ)=nk1·t1+nk2·t2為路徑?jīng)_突造成堵塞的總等待時間，其中t1為AGV在路口等待的時間，t2包括頂點轉(zhuǎn)彎時間、最小安全距離移動時間和等待時間。除去因避碰決策造成的額外時間t1t2，一臺AGV執(zhí)行任務(wù)所必要的時間為

(3)

由式(3)可得m輛AGV執(zhí)行任務(wù)所需的必要時間總和為

(4)

定義系統(tǒng)堵塞率J為m輛AGV總等待時間與任務(wù)執(zhí)行總耗時的比值，即

(5)

則多AGV路徑?jīng)_突的避碰決策優(yōu)化目標(biāo)為min(J)。

2.2 多AGV避碰決策優(yōu)化算法

在多AGV系統(tǒng)運行過程中，每一次的避碰決策都會對系統(tǒng)運行產(chǎn)生影響，而多AGV的避碰決策的組合優(yōu)化是一個NP難問題，難以采用傳統(tǒng)數(shù)學(xué)規(guī)劃方法進行求解，因此結(jié)合第2章的沖突預(yù)測方法，采用PSO算法優(yōu)化AGV系統(tǒng)避碰決策。

PSO算法是受自然界鳥群覓食行為的啟發(fā)而總結(jié)出的群體智能優(yōu)化算法[15-17]，本文通過調(diào)整PSO算法模型，將其應(yīng)用在避碰決策的優(yōu)化中。實驗發(fā)現(xiàn)，該算法存在提前收斂、全局搜索能力弱的問題，為解決這一問題，本文對PSO算法進行了改進。

在D維解空間中設(shè)置m個粒子，粒子群表示為G={p1,p2,p3,…,pi,…,pm},i=1,2,3,…,m。每個粒子有速度V和位置X兩個屬性，速度V用于更新解的變換，可表示為V={v1,v2,v3,…,vi,…,vD},vi=-1,0,1；位置X即對應(yīng)的避碰決策方案，決策方案的數(shù)量為D，表示一個決策周期T內(nèi)的避碰決策集合，表示為X={x1,x2,x3,…,xi,…,xD},xi=0,1。由于避碰決策是離散型變量，用0和1表示兩種不同的避碰決策，0表示在避碰過程中小編號的AGV讓行，1表示在避碰過程中大編號的AGV讓行。每個粒子在決策空間中單獨地搜尋最優(yōu)解，并將其記為當(dāng)前個體最優(yōu)解Pbest，最優(yōu)的個體極值記為整個粒子群的當(dāng)前全局最優(yōu)解Gbest，粒子群中的所有粒子根據(jù)當(dāng)前個體最優(yōu)解和全局最優(yōu)解來調(diào)整自己的速度和位置。

PSO算法步驟主要分為：①初始化粒子群；②計算粒子適應(yīng)值；③尋找個體最優(yōu)解；④尋找全局最優(yōu)解；⑤修改粒子的速度和位置。

PSO算法的核心是粒子速度V與位置X的更新，粒子速度V根據(jù)個體最優(yōu)解Pbest和群體最優(yōu)解Gbest來更新調(diào)整。粒子的個體最優(yōu)解通過計算適應(yīng)度函數(shù)來確定，適應(yīng)度f=1-J，J采用式(5)計算，將計算出的適應(yīng)度與粒子的當(dāng)前個體最優(yōu)解比較，較大適應(yīng)度的成為新的個體最優(yōu)解,擁有最大適應(yīng)度的個體最優(yōu)解作為群體最優(yōu)解Gbest。

圖2所示為粒子適應(yīng)度值的計算過程。由于當(dāng)前路徑?jīng)_突的避碰決策會影響AGV系統(tǒng)的運行狀態(tài)，要獲得合理的適應(yīng)度值，就要考慮AGV后續(xù)的路徑?jīng)_突。設(shè)置決策周期為T，即每一次路徑?jīng)_突都會考慮避碰決策對未來T時段內(nèi)AGV系統(tǒng)狀態(tài)的影響。采用第1章的路徑?jīng)_突預(yù)測方法預(yù)測未來的路徑?jīng)_突并執(zhí)行決策集X對應(yīng)的避碰決策，直到對T時間內(nèi)的所有路徑?jīng)_突做出避碰決策后，再估算系統(tǒng)等待時間并返回粒子的適應(yīng)度值。

對于本文研究的多AGV避碰決策優(yōu)化問題，由于解空間是離散的，需要對粒子運動速度V的更新方式進行改進。引入速度離散函數(shù)H(K)，將計算出的連續(xù)速度轉(zhuǎn)為離散速度，使粒子能在離散解空間中移動。

K=ωVi(t)+c1r1(Pbest-Xi(t))+

c2r2(Gbest-Xi(t))；

(6)

Vi(t+1)=H(K)。

(7)

式中K為計算速度；H(K)為速度離散函數(shù)。K可分解為D個維度方向的分速度，即

K={k1,k2,k3,…,ki,…,kD}。

(8)

(9)

式中：ki為第i維方向上的計算速度；h(ki)為第i維方向速度的離散函數(shù)；KN為速度的下界；KP為速度的上界。

通過比較計算出的連續(xù)速度值K與設(shè)定的速度上下界限定值KN，KP，確定AGV在解空間各個維度方向上的速度。

位置X更新公式為

Xi(t+1)=Xi(t)+Vi(t+1)。

(10)

通過不斷迭代，調(diào)整粒子速度V和位置X，使個體位置不斷接近群體最優(yōu)解Gbest。

為了能夠優(yōu)化粒子在解空間的移動速度和方向，引入速度接納概率Pv。Pv表示接受通過計算得到的速度K的概率，Pv越大，該維上的速度更新概率越大，反之粒子速度更新概率越小。每一維上的Pv可用下式調(diào)節(jié)：

(11)

通過式(11)可以調(diào)節(jié)粒子在每一維上的速度變化概率，使高維度決策位的速度調(diào)節(jié)概率降低，即時間上靠后的決策不易被改變，從而限制粒子在解空間的運動方向，使粒子按照決策的時間順序逐步移動到最優(yōu)解附近的解空間，以找尋到更優(yōu)解。

為了提高粒子的全局搜索能力，避免優(yōu)化算法早熟，本文融合遺傳算法的變異思想引入粒子變異操作，讓粒子有一定概率跳出局部最優(yōu)位置而收斂到更優(yōu)位置。為了使算法最終能夠收斂，設(shè)置變異概率隨迭代次數(shù)的增加不斷降低，通過調(diào)整變異概率的大小，使改進PSO算法在合適的迭代次數(shù)后收斂。變異概率為

n=1,2,3,…,D,i=1,2,3,…,gmax。

(12)

式中：n為解空間的維度；i為算法迭代次數(shù)；gmax為最大迭代次數(shù)。

3 實驗結(jié)果及分析

為了驗證本文所提多AGV系統(tǒng)避碰決策優(yōu)化算法的有效性，采用C++編寫了多AGV系統(tǒng)的控制程序和算法，并用Visual studio 2012搭建了Winform上位機控制系統(tǒng)平臺，多AGV通過CAN總線與上位機建立通信。圖3所示為上位機控制系統(tǒng)界面。

實驗參數(shù)如表1所示，多AGV系統(tǒng)工作環(huán)境被重構(gòu)成包括100個頂點的圖，每次實驗投放的AGV數(shù)量為1～40臺，標(biāo)準(zhǔn)數(shù)量為30臺。每臺AGV的平均運行速度設(shè)置為1 m/s，實驗次數(shù)為200次。

表1 實驗參數(shù)表

為了優(yōu)化PSO算法的搜索能力，提出優(yōu)化粒子運動方向和速度及變異操作來改進PSO算法。圖4所示的實驗結(jié)果清晰地表明了改進PSO算法與傳統(tǒng)PSO算法在粒子速度更新上的差異。虛線為傳統(tǒng)PSO算法在500次迭代過程中粒子平均速度的變化曲線，可見傳統(tǒng)PSO算法的粒子速度收斂過快，難以充分搜索解空間。實線為改進PSO算法的速度曲線，粒子在整個迭代過程中移動速度較快，收斂速度平緩，具備較好的搜索能力。

在一次實驗中，為30臺AGV隨機分配任務(wù)起始點，并采用Dijkstra算法為各AGV規(guī)劃行駛路徑，在AGV的任務(wù)全部執(zhí)行完畢后，計算堵塞率J，實驗次數(shù)為200次。圖5所示為 PSO算法和改進PSO算法的系統(tǒng)堵塞率擬合趨勢線，可見采用改進粒子群避碰決策優(yōu)化算法后，在同樣的任務(wù)下，堵塞率明顯下降，平均堵塞率從6.41%下降到5.96%，減少了7.1%的堵塞時間。

圖6所示為基于任務(wù)優(yōu)先級避碰方式、基于貪心算法避碰方式和基于沖突預(yù)測的避碰方式(使用改進PSO算法優(yōu)化)的系統(tǒng)堵塞率分布情況。其中對照組基于任務(wù)優(yōu)先級避碰方式是根據(jù)每臺AGV優(yōu)先級確定避碰決策，優(yōu)先級別低的AGV在避碰過程中需要為其他AGV讓行。

基于貪心算法避碰方式在求解過程中采用貪心算法思想，該算法在一次決策中分別計算不同決策對當(dāng)前路網(wǎng)造成的擁堵情況，然后實施對路網(wǎng)狀態(tài)負(fù)面影響最小的決策。相比本文方法，這種啟發(fā)式搜索避碰方法只關(guān)注決策對當(dāng)前系統(tǒng)狀態(tài)的影響，不考慮對系統(tǒng)的后續(xù)影響，因此是短視的。

在200次實驗中，每次實驗都會為AGV隨機生成任務(wù)和運行路徑，并依次采用3種避碰方式對同一初始條件進行決策。結(jié)合表2可見，與傳統(tǒng)的優(yōu)先級避碰方式和基于貪心算法的避碰方式相比，基于沖突預(yù)測的避碰方式的系統(tǒng)堵塞率和等待時長較低。

表2 不同避碰方式下的實驗數(shù)據(jù)

圖7所示為堵塞率下降百分比圖，其以優(yōu)先級避碰方式為對照，可見基于貪心算法避碰相對優(yōu)先級避碰的提升并不很大，而且有可能出現(xiàn)堵塞率負(fù)增長，而采用改進PSO算法的沖突預(yù)測避碰方式能提升20%以上。

圖8所示為隨著同時運行AGV數(shù)量的增加，不同算法的優(yōu)化效果?？梢姡珹GV的數(shù)量越多，采用改進PSO算法沖突預(yù)測避碰方式的優(yōu)化效果越明顯。

4 結(jié)束語

AGV數(shù)量的增加增大了解決多AGV系統(tǒng)路徑?jīng)_突的困難。本文根據(jù)圖論知識和AGV位姿信息預(yù)測沖突點，實現(xiàn)了多AGV系統(tǒng)中路徑?jīng)_突的快速和準(zhǔn)確預(yù)測。為了有效地解決AGV的沖突問題，本文將改進PSO算法應(yīng)用到避碰策略優(yōu)化中，經(jīng)過實驗分析驗證了該算法可以有效緩解路線擁堵狀況，顯著提升多AGV系統(tǒng)的運行效率。未來將研究融合多AGV系統(tǒng)的動態(tài)路徑規(guī)劃算法，以進一步緩解路網(wǎng)的阻塞狀況，提高系統(tǒng)的生產(chǎn)效率。