宋栓軍， 呂 森

(1.西安工程大學(xué) 機(jī)電工程學(xué)院， 陜西 西安 710048；2.西安工程大學(xué) 西安市現(xiàn)代智能紡織裝備重點(diǎn)實(shí)驗(yàn)室， 陜西 西安 710048)

隨著電商、快遞等行業(yè)的高速發(fā)展，企業(yè)對(duì)大規(guī)模的自動(dòng)引導(dǎo)小車(automated guided vehicle，AGV)的需求擴(kuò)大，多AGV系統(tǒng)常出現(xiàn)沖突問題[1]。AGV系統(tǒng)中的沖突問題主要表現(xiàn)為超過一輛AGV所占用時(shí)間和空間發(fā)生重疊[2]。

為了解決AGV系統(tǒng)中的突出問題，部分學(xué)者對(duì)靜態(tài)算法進(jìn)行了改進(jìn),引入動(dòng)態(tài)機(jī)制和沖突解決策略以滿足作業(yè)需求[3]。王琛[4]和梁承姬等[5-6]先規(guī)劃出最短路徑,根據(jù)時(shí)間窗預(yù)測(cè)沖突,對(duì)路徑進(jìn)行調(diào)整，最終實(shí)現(xiàn)無沖突路徑規(guī)劃。姜辰凱等[7]根據(jù)時(shí)間窗預(yù)測(cè)沖突，對(duì)優(yōu)先級(jí)較低的AGV重新進(jìn)行路徑規(guī)劃。Hu Y J等[8]將A*算法與時(shí)間窗原理相結(jié)合，按時(shí)間順序規(guī)劃每輛AGV的路徑，該方法雖然能有效地解決沖突，但并未考慮是否對(duì)AGV系統(tǒng)的整體效率產(chǎn)生影響。另一部分學(xué)者采用具備多步前瞻性的主動(dòng)沖突解決算法。Zhong M S等[9]建立了混合整數(shù)規(guī)劃模型，使AGVs的延遲時(shí)間最小。Liu C B等[10]采用單向有向圖方法和AGV路徑規(guī)劃的A*算法，有效地解決了AGVs的沖突問題。Yuan Z H等[11]先規(guī)劃AGV全局路徑，然后提出了動(dòng)態(tài)快速探索隨機(jī)樹算法，降低了路徑?jīng)_突的發(fā)生率。Zhao Y L等[12]利用共享資源點(diǎn)的動(dòng)態(tài)預(yù)留來改變AGV的運(yùn)動(dòng)狀態(tài)，避免碰撞和死鎖。曹小華等[13]提出基于沖突預(yù)測(cè)的多AGV避碰決策優(yōu)化方法，求解某一時(shí)刻碰撞小車的多AGV避碰決策組合優(yōu)化問題，建立主動(dòng)沖突解決模型，尋求對(duì)于系統(tǒng)而言的最優(yōu)，然而大多以時(shí)間最短或距離最短為目標(biāo)。但在現(xiàn)實(shí)中，小車能耗的浪費(fèi)導(dǎo)致AGV小車充電次數(shù)的增加，繼而影響小車的效率。能耗作為影響小車搬運(yùn)效率的一項(xiàng)重要因素，對(duì)于整個(gè)AGV系統(tǒng)長(zhǎng)期的搬運(yùn)效率而言更為重要。張中偉等[14]建立了以運(yùn)輸距離和能耗為優(yōu)化目標(biāo)的節(jié)能單 AGV 路徑規(guī)劃模型。張浩杰等[15]通過構(gòu)建機(jī)器人動(dòng)力學(xué)模型及其在運(yùn)動(dòng)過程中的能耗模型,實(shí)現(xiàn)對(duì)路徑的能耗計(jì)算。劉貴杰等[16]針對(duì)傳統(tǒng)路徑優(yōu)化算法中“距離最短能耗非最低”的問題，規(guī)劃出一條能耗最優(yōu)的路徑。以上文獻(xiàn)均以能耗為目標(biāo)或考慮能耗規(guī)劃出一條所需能耗最低的單機(jī)器人移動(dòng)路徑，但在多AGV系統(tǒng)中，小車完成任務(wù)所必須的能耗(最優(yōu)路徑下的能耗)雖然占極大部分，然而多AGV系統(tǒng)在沖突解決過程中的能耗是提高AGV搬運(yùn)效率的關(guān)鍵。

綜上所述，目前解決多AGV系統(tǒng)中可能存在的沖突問題，多采用以時(shí)間最小、路程最短為目標(biāo)，然而得到的沖突解決策略組合并未考慮小車載質(zhì)量不同時(shí)對(duì)策略的影響，可能存在負(fù)載大的小車行走路程較長(zhǎng)、負(fù)載小的小車行走距離反而較短的情況，從而導(dǎo)致部分小車耗電過快、能耗不平衡；因此課題組構(gòu)建了受負(fù)載和時(shí)間所控制的能耗計(jì)算模型，并以總能耗最低為目標(biāo)，建立多AGV系統(tǒng)路徑的沖突消解模型。

1 多AGV系統(tǒng)路徑?jīng)_突判定

課題組研究的倉庫環(huán)境路況為雙向雙車道，假設(shè)某一時(shí)間段內(nèi)所有AGV都在運(yùn)行，且均靠右行駛。倉庫環(huán)境如圖1(a)所示，其中黑色方框?yàn)樨浖埽咨娇驗(yàn)锳GV可行走的路徑。課題組將其簡(jiǎn)化成如圖1(b)所示環(huán)境拓?fù)涞貓DG=(V,A)，其中節(jié)點(diǎn)集合V={1,2,…,M}，節(jié)點(diǎn)坐標(biāo)矩陣記為(x,y)M×2。邊集合A={(i,j);i,j∈V,i≠j}。拓?fù)涞貓D雖然能有效表示出各AGV所經(jīng)過的路徑，但無法直觀地表示出AGV行走的時(shí)間與位置情況，因此在二維拓?fù)鋱D中引入時(shí)間維，如圖1(c)所示。

圖1 環(huán)境地圖Figure 1 Environment map

第k輛小車執(zhí)行任務(wù)的路徑為Rk(Sk，Lk)；自身質(zhì)量與載質(zhì)量之和為mk；其中Sk(x，y)與Lk(x，y)分別為第k輛小車路徑起始點(diǎn)與終止點(diǎn)，其中1≤k≤n。小車以速度V勻速行駛。小車與通過路口均可看作質(zhì)點(diǎn)，由此計(jì)算出路徑Rk(Sk，Lk)下的通過各節(jié)點(diǎn)時(shí)間為：T=[T1，T2，…，Tm]。

(1)

則認(rèn)為第k輛小車與第k+1輛小車的路線同一時(shí)間在節(jié)點(diǎn)M存在干涉。

課題組的研究是在雙向雙車道且靠右行駛的路況上進(jìn)行的，經(jīng)式(1)判定存在干涉的節(jié)點(diǎn)，如小車數(shù)量小于3時(shí)，有可能不發(fā)生沖突。圖2所示的3種情況為干涉節(jié)點(diǎn)不發(fā)生沖突的情況，除此3種情況之外，其他干涉的情況均認(rèn)定為沖突。

圖2 路口不沖突示意圖Figure 2 Schematic diagram of no conflicts at intersections

時(shí)間窗T下的沖突集合為C={C1,C2,…,Cq}，1≤q≤M,Cq儲(chǔ)存了節(jié)點(diǎn)q的沖突屬性，主要包括沖突時(shí)間及沖突小車編號(hào)k。

2 考慮能耗的沖突解決策略優(yōu)化

為應(yīng)對(duì)可能產(chǎn)生的沖突，課題組提出等待與繞道2種沖突解決措施，并提出預(yù)測(cè)各種解決措施下能耗的計(jì)算模型，構(gòu)建了以系統(tǒng)能耗最低為目標(biāo)的AGV沖突消解模型，最終優(yōu)選出系統(tǒng)能耗最低的沖突解決策略。

2.1 能耗計(jì)算模型

為降低能耗分析難度，課題組從運(yùn)動(dòng)角度對(duì)AGV消耗的能耗進(jìn)行分析。AGV的能耗主要包括待機(jī)能耗和運(yùn)動(dòng)能耗2種。其中待機(jī)能耗相對(duì)固定，貫穿于整個(gè)運(yùn)動(dòng)過程，主要包括小車上控制系統(tǒng)、監(jiān)測(cè)系統(tǒng)以及散熱系統(tǒng)的總能耗，具體表現(xiàn)為其額定功率之和P。AGV運(yùn)動(dòng)過程中存在著空氣阻力、車輪與地面的摩擦阻力，由于速度較低，所以空氣阻力忽略不計(jì)。小車運(yùn)動(dòng)狀態(tài)下，驅(qū)動(dòng)電機(jī)提供的力僅維持克服摩擦力做功。那么克服摩擦力做的功為：

W=μmgL/α。

(2)

式中：μ為滑動(dòng)摩擦因數(shù)，m為小車與運(yùn)載的貨物質(zhì)量之和，g為重力加速度，L為小車行走的距離，α為行走驅(qū)動(dòng)功率因數(shù)。

小車完成任務(wù)過程中的能耗

E=(μmgL/α)+(L/V)×P,

(3)

在此基礎(chǔ)上提出2種沖突消解措施下的能耗計(jì)算方法。

1) 等待措施。若第k輛小車到達(dá)沖突節(jié)點(diǎn)M時(shí)有n″輛小車等待通過，第k輛小車等待時(shí)間

(4)

f(x,y)=|x-xl|+|y-yl|。

(5)

局部路徑評(píng)價(jià)方法是用局部路徑替換原路徑中對(duì)應(yīng)的片段，然后進(jìn)行評(píng)價(jià)，評(píng)價(jià)函數(shù)如式(3)所示。其中L為該局部路徑替換路徑片段后的總長(zhǎng)，以評(píng)價(jià)的函數(shù)值對(duì)局部路徑集進(jìn)行排序，在選擇局部路徑時(shí)，先選取評(píng)價(jià)函數(shù)值最小的局部路徑替換原路徑部分片段。小車?yán)@道策略下的新路徑比原路徑多消耗的能耗

(6)

式中ΔL為繞道策略下新路徑比原路徑多出的長(zhǎng)度。

2.2 沖突消解模型

s.t.

(7)

(8)

m0≤mk≤m0+Q;

(9)

(10)

(11)

優(yōu)化目標(biāo)為第k輛小車完成任務(wù)過程中所有等待與繞道策略下所需的能耗最低，具體計(jì)算如式(7)所示。約束條件式(8)表示小車完成運(yùn)送任務(wù)后所剩的電量不低于最低安全電量，約束條件式(9) 表示AGV負(fù)載不能超過其最大載質(zhì)量。

3 算例分析

為驗(yàn)證課題組提出方法的有效性，采用MATLAB 2018a版進(jìn)行編程實(shí)現(xiàn)。建立80 m×60 m的倉庫拓?fù)涞貓D如圖3所示，地圖中路口節(jié)點(diǎn)個(gè)數(shù)M為60，節(jié)點(diǎn)36～53、節(jié)點(diǎn)18～35和節(jié)點(diǎn)57～58的距離為20 m，其余各節(jié)點(diǎn)間距離均為10 m。

圖3 環(huán)境拓?fù)涞貓DFigure 3 Environmental topological map

設(shè)置小車參數(shù)如表1所示。在參數(shù)相同的情況下以4輛小車進(jìn)行仿真實(shí)驗(yàn)，將本研究沖突解決方式與基于貪心算法的沖突解決方式進(jìn)行對(duì)比。基于貪心算法的沖突解決方式在當(dāng)前看來是最好的沖突解決策略，該方式只注重于當(dāng)前的決策對(duì)系統(tǒng)的影響，不考慮后續(xù)是否可能會(huì)產(chǎn)生更多的沖突。

表1 AGV參數(shù)Table 1 AGV parameters

給定小車載質(zhì)量與路徑如表2所示，各小車路徑的時(shí)空?qǐng)D如圖4所示。得出結(jié)果如表3～4所示，2種沖突解決方式下的路徑時(shí)空?qǐng)D如圖5所示。

表2 AGV起始路徑Table 2 Starting path of AGV

表3 沖突節(jié)點(diǎn)以及沖突AGV的解決措施Table 3 Conflict nodes and resolution measures of conflict AGV

圖4 各AGV路徑時(shí)空?qǐng)DFigure 4 Time and space diagram of AGV

由表3可得各AGV在沖突節(jié)點(diǎn)采取的措施，對(duì)應(yīng)的路徑如圖5所示。由圖5可以得出基于能耗的沖突解決方式下僅僅有2輛車在路徑?jīng)_突時(shí)等待，而基于貪心算法的沖突解決方式下有3輛小車在路徑?jīng)_突時(shí)等待。表4所示為在表3的措施下每輛AGV完成任務(wù)的時(shí)間、距離以及能耗，可以觀察到課題組提出的沖突解決方式與基于貪心算法的沖突解決方式的總距離相同，但總能耗與總時(shí)間相對(duì)較低。由表3知2種沖突解決方式下所選的沖突解決措施均為等待,根據(jù)式(3)可知載質(zhì)量只對(duì)運(yùn)動(dòng)能耗產(chǎn)生影響，而等待過程中運(yùn)動(dòng)能耗為0，所以基于貪心算法的沖突解決方式隨機(jī)選擇小車通過沖突節(jié)點(diǎn)的順序，由此而導(dǎo)致多發(fā)生了一次沖突。此外表3驗(yàn)證了本研究?jī)?yōu)化目標(biāo)中的能耗計(jì)算方式能兼顧負(fù)載與路徑長(zhǎng)度，得到的沖突解決策略下各AGV的能耗較為均衡。

表4 2種沖突解決方式下的各數(shù)據(jù)對(duì)比Table 4 Data comparison under two conflict resolution methods

圖5 2種沖突解決方式下路徑時(shí)空?qǐng)DFigure 5 Path time-space diagram under two conflict resolution methods

為進(jìn)一步對(duì)驗(yàn)證本研究提出的方法，用20臺(tái)AGV與30臺(tái)AGV各進(jìn)行30次試驗(yàn)。每次隨機(jī)生成起始點(diǎn)與終止點(diǎn)，在負(fù)載與電量相同情況下，用遺傳算法進(jìn)行規(guī)劃。20臺(tái)AGV時(shí)，2種策略下的總能耗對(duì)比如圖6所示。完成任務(wù)總時(shí)間、距離以及總能耗如表5所示。由表5可知2種沖突解決方式下每次試驗(yàn)的總路程均為2 000 m，基于能耗的沖突解決方式的能耗均低于基于貪心算法的能耗，本研究解決沖突的繞道措施較為靈活，進(jìn)行繞道時(shí)，選擇的局部路徑在長(zhǎng)度上可能與原路徑相同，基于能耗的沖突解決方式能兼顧整個(gè)系統(tǒng)運(yùn)行過程，因此相較于基于貪心算法的解決方式所消耗的能耗更低。

圖6 20臺(tái)AGV時(shí)2種沖突解決方式下的總能耗對(duì)比Figure 6 Total energy consumption comparison of 20 AGVs under two conflict resolution methods

表5 20臺(tái)AGV時(shí)2種沖突解決方式下的數(shù)據(jù)對(duì)比

30臺(tái)AGV時(shí)，2種策略下的總能耗對(duì)比如圖7所示，完成任務(wù)總時(shí)間、距離以及總能耗如表6所示。由表6可得到2種沖突解決方式下每次試驗(yàn)的總路程均為3 000 m，基于能耗的沖突解決方式的能耗均低于基于貪心算法的能耗。且由表5和表6得出隨著AGV數(shù)量的增多，基于能耗的沖突解決方式與基于貪心算法的沖突解決方式所需的總能耗之差在增大。

表6 30臺(tái)AGV 2種沖突解決方式下的數(shù)據(jù)對(duì)比Table 6 Data comparison of 30 AGVs undertwo conflict resolution methods

圖7 30臺(tái)AGV時(shí)2種沖突解決方式下進(jìn)行試驗(yàn)的總能耗對(duì)比Figure 7 Total energy consumption comparison of test under two conflict resolution methods with 30 AGVs

4 結(jié)語

針對(duì)多AGV系統(tǒng)中可能存在的路徑?jīng)_突問題，課題組構(gòu)建的能耗計(jì)算模型受負(fù)載和時(shí)間所控制，并以能耗最低作為沖突消解模型的評(píng)判標(biāo)準(zhǔn)，能綜合考慮時(shí)間與負(fù)載對(duì)沖突解決策略的影響，相比于傳統(tǒng)以時(shí)間為目標(biāo)更符合現(xiàn)實(shí)中AGV運(yùn)行情況。課題組提出的方法在沖突解決方式中采用繞道策略，較為靈活簡(jiǎn)單，能有效找尋出合理的局部路徑，經(jīng)仿真證明課題組提出方法在隨著AGV數(shù)量增加而導(dǎo)致的路況復(fù)雜的情況下，依舊能有效得到合理的沖突解決策略組合。在未來工作中可以引入任務(wù)優(yōu)先級(jí)，在綜合考慮任務(wù)優(yōu)先級(jí)與小車電量情況下進(jìn)行規(guī)劃，獲取均衡的沖突解決策略組合。