有軌制導(dǎo)車堆垛的動(dòng)態(tài)穩(wěn)定性研究

尹 昊,董益民,馮 卓,和紅杰,陳 帆+

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院,四川 成都 611756;2.西南交通大學(xué) 計(jì)算機(jī)與人工智能學(xué)院,四川 成都 611756)

1 問題的提出

隨著機(jī)器人、自動(dòng)控制、人工智能和大數(shù)據(jù)等技術(shù)的發(fā)展,智慧物流已成為我國(guó)物流業(yè)供給側(cè)結(jié)構(gòu)性改革的重要發(fā)展方向[1]。智能倉(cāng)儲(chǔ)是智慧物流的重要組成部分,其設(shè)備自動(dòng)化,是企業(yè)降本增效、提高利潤(rùn)的有效手段[2-3]。基于有軌制導(dǎo)車(Rail Guided Vehicle,RGV)[4]調(diào)度的智能立體庫(kù),是智能倉(cāng)儲(chǔ)設(shè)備自動(dòng)化的重要體現(xiàn),其結(jié)構(gòu)如圖1a所示。圖中除立體倉(cāng)庫(kù)外,還包括軌道、RGV、托盤、機(jī)器人等設(shè)備,以及基于視覺導(dǎo)引的機(jī)器人自動(dòng)拆垛/碼垛系統(tǒng)[5-6],以實(shí)現(xiàn)基于訂單的貨物自動(dòng)調(diào)度與出庫(kù)。RGV和托盤是智能倉(cāng)儲(chǔ)自動(dòng)調(diào)度的基本運(yùn)輸單元,裝載貨物的托盤被固定在RGV上,實(shí)現(xiàn)貨物的臨時(shí)短距離搬運(yùn)。因此,貨物裝載效率、RGV運(yùn)動(dòng)速度等直接影響著智能倉(cāng)儲(chǔ)的工作效率。

圖1 基于RGV調(diào)度的智能立庫(kù)

貨物裝載效率與以RGV上托盤為容器的三維裝箱問題[7]的求解息息相關(guān)。本文將該類三維裝箱問題稱為RGV裝箱問題(RGV Bin Packing Problem,RGV-BPP),將裝箱后形成的箱子整體稱為RGV堆垛。RGV-BPP從切割與布局角度,研究如何將一組長(zhǎng)方體箱子(貨物)碼放至RGV上固定尺寸的托盤,使得RGV堆垛所占托盤空間最大,在其他場(chǎng)景中也被稱作托盤裝載問題[8]。RGV運(yùn)動(dòng)速度受限于RGV堆垛承受加速度的能力,由于RGV在有限長(zhǎng)度軌道上的快速度帶來的大加速度,易導(dǎo)致堆垛倒塌,如圖1b所示。由圖1b可知,盡管RGV完成了該次沒有倒塌貨物的搬運(yùn),但掉落貨物無疑阻塞其他RGV的運(yùn)行,甚至導(dǎo)致自動(dòng)系統(tǒng)癱瘓,嚴(yán)重影響倉(cāng)儲(chǔ)自動(dòng)調(diào)度的效率。顯然,準(zhǔn)確計(jì)算不使RGV堆垛中任何箱子倒塌的最大加速度值,對(duì)提高智能倉(cāng)儲(chǔ)自動(dòng)調(diào)度效率,降低物流阻塞風(fēng)險(xiǎn)具有積極的現(xiàn)實(shí)意義。

在裝箱問題研究領(lǐng)域中,堆垛承受水平方向慣性(加速度)的能力被稱作堆垛的動(dòng)態(tài)穩(wěn)定性[9]。與靜態(tài)穩(wěn)定性僅考慮箱子底部支撐情況[10-11]不同,現(xiàn)有裝箱問題的動(dòng)態(tài)穩(wěn)定性評(píng)估的設(shè)計(jì)角度分為箱子支撐、工具模擬、力學(xué)平衡3種。

(1)箱子支撐 該角度的研究主要考慮箱子在各方向的支撐情況。早在1985年,CARPENTER等[12]就提出了兩個(gè)動(dòng)態(tài)穩(wěn)定性準(zhǔn)則:①每個(gè)非底層箱子至少被兩個(gè)箱子支撐;②穿過堆垛接縫的長(zhǎng)度不能超過堆垛長(zhǎng)或?qū)挼哪骋话俜直?。他們認(rèn)為箱子間的“聯(lián)鎖”能夠保障堆垛的穩(wěn)定。隨后,BISCHOFF[13]將準(zhǔn)則①進(jìn)一步弱化,只要求每個(gè)非底單層最外圍的箱子被至少兩個(gè)箱子支撐。BISCHOFF等[14]提出非底層箱子的平均支撐箱數(shù)和至少3個(gè)側(cè)面未與其他物體接觸的箱子百分比兩個(gè)動(dòng)態(tài)穩(wěn)定性指標(biāo),首次引入橫向支撐概念,并將動(dòng)態(tài)穩(wěn)定性進(jìn)行量化。JUNQUEIRA等[15]以由每個(gè)箱子左側(cè)和前側(cè)被其他物體橫向支撐的面積分?jǐn)?shù)定義的支撐系數(shù)β和γ判別是否動(dòng)態(tài)穩(wěn)定,該方法也被最新研究關(guān)注并優(yōu)化[16-17]。以上研究將箱子支撐情況作為裝箱算法的約束條件,使算法計(jì)算出滿足動(dòng)態(tài)穩(wěn)定的解,但是,他們并未驗(yàn)證所提出動(dòng)態(tài)穩(wěn)定性約束的準(zhǔn)確性。甚至有學(xué)者認(rèn)為[9,18],箱子的支撐無法保證其動(dòng)態(tài)穩(wěn)定(即使是在完全橫向支撐的情況下)。

(2)工具模擬 該角度的研究使用物理工具模擬箱子的運(yùn)動(dòng)狀態(tài),分析堆垛倒塌的條件。RAMOS等[18]通過StableCargo工具模擬得到落箱數(shù)(the Number of Fallen Boxes,NFB)和破損邊界曲線內(nèi)箱數(shù)(the Number of Boxes within the Damage Boundary Curve fragility test,NB_DBC)兩個(gè)動(dòng)態(tài)穩(wěn)定性指標(biāo),再使用多元線性回歸對(duì)指標(biāo)建模,并在后續(xù)研究[19]中驗(yàn)證了StableCargo運(yùn)算的精確性。NFB指標(biāo)也在BRACHT等[20]的研究中得到應(yīng)用,但同時(shí)該文獻(xiàn)指出,如果需要精確的結(jié)果,物理工具可能會(huì)導(dǎo)致較高的計(jì)算成本。并且,NFB和NB_DBC指標(biāo)是針對(duì)集裝箱裝載問題提出的,它們?cè)谝运闹懿槐徽趽醯耐斜P為容器的裝箱場(chǎng)景中的適用性未知。

(3)力學(xué)平衡 該角度的研究主要分析箱子的受力情況,提出力學(xué)平衡公式,找出箱子穩(wěn)定的條件。QUEIROZ等[21]在其前期靜態(tài)穩(wěn)定性研究[22]的基礎(chǔ)上,考慮加速度、向心力、阻力,提出一種二維裝箱問題的水平靜態(tài)平衡判斷方法。OLIVEIRA等[23]后續(xù)將QUEIROZ等[21]在動(dòng)態(tài)穩(wěn)定性方面的工作擴(kuò)展至三維,提出一種考慮箱子運(yùn)動(dòng)向心力的平衡檢測(cè)方法,該方法可有效檢測(cè)堆垛中單箱的動(dòng)態(tài)穩(wěn)定,但仍存在不足:①未考慮“單箱穩(wěn)定但箱子所在整體不穩(wěn)定”的情況,該問題在QUEIROZ等[21]的研究中被“尋找垂直連通箱子集”的方法解決,但OLIVEIRA等[23]并未沿用;②對(duì)箱子側(cè)面支持力考慮不充分,OLIVEIRA等[23]默認(rèn)箱子所受側(cè)面支持合力作用于與質(zhì)心等高的箱子側(cè)表面,但實(shí)際作用位置會(huì)隨箱子的接觸高度變化,并且,他們未考慮因向心力(加速度)導(dǎo)致的側(cè)面支持力變化。

以上動(dòng)態(tài)穩(wěn)定性研究中,部分方法[12-15]沒有考慮堆垛承受加速度的能力,另一部分方法[18,21,23]將加速度作為輸入來判斷堆垛是否滿足動(dòng)態(tài)穩(wěn)定,尚未見到直接以堆垛承受加速度的能力定量評(píng)估動(dòng)態(tài)穩(wěn)定性的方法。而在智能倉(cāng)儲(chǔ)自動(dòng)調(diào)度場(chǎng)景中,RGV的運(yùn)動(dòng)加速度關(guān)乎貨物出庫(kù)效率與安全,是十分重要的。因此,本文針對(duì)已有動(dòng)態(tài)穩(wěn)定性評(píng)估方法的不足,面向智能倉(cāng)儲(chǔ)自動(dòng)調(diào)度場(chǎng)景,從RGV堆垛中箱子位置和剛體受力的角度,提出一種RGV堆垛的可承載加速度(即不使任何箱子倒塌的最大加速度值)計(jì)算方法,以定量評(píng)估堆垛的動(dòng)態(tài)穩(wěn)定性,并限制RGV的運(yùn)動(dòng)加速度。本文的主要研究工作如下:

(1)設(shè)計(jì)了一種基于堆的箱子歸類方法,將堆垛中形成穩(wěn)定整體的多個(gè)箱子劃分為堆,以堆為單位進(jìn)行堆垛的動(dòng)穩(wěn)定性態(tài)分析,解決單箱穩(wěn)定但箱子所在整體不穩(wěn)定的問題;

(2)分析并指出了堆垛以特定加速度運(yùn)動(dòng)時(shí),堆垛中各堆之間的一種通過剛體樹傳遞的橫向作用力——阻倒力,考慮因剛體接觸高度或加速度改變帶來的側(cè)面支持力變化,進(jìn)而給出更精確的可承載加速度計(jì)算方法;

(3)通過計(jì)算堆垛的可承載加速度與對(duì)應(yīng)Unity仿真堆垛的動(dòng)態(tài)穩(wěn)定性之間的皮爾遜相關(guān)系數(shù),并與現(xiàn)有動(dòng)態(tài)穩(wěn)定性評(píng)估方法對(duì)比,證明了本文可承載加速度的有效性。

2 問題的描述

圖2 貨物運(yùn)輸基本單元示意圖

設(shè)碼放在托盤上的RGV堆垛S為n個(gè)長(zhǎng)方體箱子b1,b2,...,bn的有序集合,其中bi表示第i個(gè)箱子的信息,包括箱子的坐標(biāo)(箱子左—前—底角相對(duì)于托盤左—前角的位置)、尺寸、質(zhì)量、質(zhì)心坐標(biāo)等。結(jié)合智能立庫(kù)中箱子與托盤的主流材質(zhì)、箱子碼放方式和RGV運(yùn)動(dòng)方式,基本運(yùn)輸單元和堆垛S應(yīng)具有以下特點(diǎn):①RGV加速度始終平行于托盤的邊;②箱子正交碼放于托盤;③箱子碼放不重疊,且不超出托盤邊界;④每個(gè)箱子底部被100%支撐;⑤箱子不會(huì)因受壓力而形變,可視為剛體;⑥箱子與托盤和其他箱子之間的摩擦因數(shù)足夠大,加速時(shí)不會(huì)相對(duì)于托盤水平滑動(dòng)。

堆垛S碼放在托盤上的示意圖如圖3所示,其中白色長(zhǎng)方體表示S中的箱子。當(dāng)RGV向x軸負(fù)方向運(yùn)動(dòng)的加速度足夠大時(shí),S會(huì)向x軸正方向倒塌。也就是說,S是否倒塌與RGV的加速度大小直接相關(guān),理論上存在一個(gè)不使S中任何箱子倒塌的最大加速度值(可承載加速度)。

圖3 堆垛碼放示意圖

(1)

(2)

其中:|·|表示向量的模;td(·)表示當(dāng)前加速度下箱子是否倒塌,若是,則為1,否則為0。

RGV堆垛的可承載加速度可用于限制RGV的運(yùn)動(dòng)加速度,防止RGV堆垛在運(yùn)動(dòng)時(shí)倒塌,還可作為動(dòng)態(tài)穩(wěn)定性評(píng)估指標(biāo),約束RGV-BPP的求解,提高方案堆垛的動(dòng)態(tài)穩(wěn)定性。下一章介紹可承載加速度算法。

3 可承載加速度算法

對(duì)任意給定的堆垛S,其Tac與S中所有箱子的受力相關(guān),而S的箱子數(shù)量可能較多,且受力復(fù)雜,以箱子為單位的分析十分困難。為降低分析難度,對(duì)S中的箱子進(jìn)行歸類,將歸類形成的箱子整體(堆)視為剛體。為便于計(jì)算S的Tac,以樹結(jié)構(gòu)記錄S中的剛體,生成S對(duì)應(yīng)的剛體樹集。最后,分析剛體樹集中樹的根節(jié)點(diǎn)剛體的阻倒力,通過阻倒力計(jì)算S的Tac。本章先給出可承載加速度算法的整體框架,再分別介紹各個(gè)子算法的具體過程,子算法包括箱子歸類、剛體樹生成和可承載加速度計(jì)算。

3.1 算法框架

可承載加速度算法框圖如圖4所示,虛線框表示子算法,實(shí)線框表示子算法的步驟,箭頭表示數(shù)據(jù)傳遞。

圖4 可承載加速度算法框圖

可承載加速度算法包括箱子歸類、剛體樹生成和可承載加速度計(jì)算3個(gè)子算法。

(1)箱子歸類 輸入堆垛S,首先將S中箱子歸類成堆,得堆集,再將中的堆視為剛體,輸出剛體集。箱子歸類的具體過程在3.2節(jié)介紹。

3.2 箱子歸類

由剛體平面運(yùn)動(dòng)的質(zhì)心動(dòng)量矩定理

(3)

實(shí)際觀察發(fā)現(xiàn),堆垛中同時(shí)倒塌的多個(gè)箱子大多在z軸相互接觸,重力使得它們緊密連接成為一個(gè)整體——稱為堆。堆在倒塌時(shí)可視為一個(gè)剛體,以堆為單位對(duì)堆垛的可承載進(jìn)行分析,可極大地降低分析難度。為找出堆垛中的所有堆,設(shè)計(jì)一種基于堆的箱子歸類(Heap Based Classification,HBC)方法。

HBC方法為:對(duì)任意堆垛S,初始化堆集=?,查找S中最容易倒塌的箱子整體(堆),記為箱子集合H,=∪{H}。令新堆垛S′=SH,再查找S′的最容易倒塌的堆,重復(fù)以上步驟,直至新堆垛中沒有箱子,最終可得堆垛S的堆集,完成歸類。其中,堆垛S的堆H的查找步驟如下:

步驟1初始化候選堆集*=?。找出S中頂部和x軸正方向側(cè)面均不與其他箱子接觸的箱子,稱其為自由箱,得自由箱集F。

步驟2對(duì)F中每個(gè)自由箱bfree,執(zhí)行步驟2.1～步驟2.4。

步驟2.1令已搜索箱集P={bfree},未搜索箱集Q=S{bfree}。令初始候選堆H*=P,*=*∪H*。

步驟2.2搜索Q中與P中箱子底部有接觸、x坐標(biāo)最大、z坐標(biāo)最小(優(yōu)先級(jí)由高至低)的箱子bbttm,令P=P∪{bbttm},Q=Q{bbttm}。

步驟2.3搜索Q中與P中箱子頂部或x軸正方向側(cè)面接觸的所有箱子Babv,令P=P∪Babv,Q=QBabv。重復(fù)該步驟,直至P和Q不再變化。

步驟2.4令H*=P,*=*∪H*,若Q中仍存在與P中箱子底部有接觸的箱子,則返回步驟2.2。

步驟3刪除*中一起倒塌的可能性較小的候選堆,該類候選堆具有如下特點(diǎn):H*的所有非最底箱子中,存在箱子底部在y軸被H*中其他箱子支撐的長(zhǎng)度小于該箱自身在y軸長(zhǎng)度的70%。

步驟4找出*中(l/h)g最小的候選堆最后令輸出H。其中,l表示在x軸上,H*的質(zhì)心與其底部的x軸正方向邊界之間的距離,h表示H*質(zhì)心與H*底部之間的距離,g表示重力加速度大小。(l/h)g是指將H*視為獨(dú)立剛體時(shí)不使其倒塌的最大加速度值,該式可反映H*倒塌的難易程度,其原理在3.4節(jié)說明。

堆垛S最容易倒塌的堆H的查找(部分)過程示意圖如圖5所示。

圖5 S的H的查找過程示意圖

箱子歸類偽代碼如算法1所示,其中SearchHeap函數(shù)用于查找堆垛S的堆H。

算法1箱子歸類。

輸入:S={b1,b2,...,bn} //堆垛;

1:function HBC(S)

3: while S≠? do

4: H←SearchHeap(S) //獲取H(步驟1～4)

6: S←SH //將H中箱子從S移除

7: end while

9: end function

3.3 剛體樹生成

對(duì)任意堆垛S,其剛體集中存在頂部和x軸正方向側(cè)面均不與其他剛體接觸的剛體,稱其為自由剛體。自由剛體是堆垛S中最容易倒塌的部分,由于它們的倒塌不被其他剛體阻止,它們?cè)谀骋患铀俣认率欠竦顾苯臃从扯讯饽芊癯惺茉摷铀俣取?/p>

自由剛體(記為Rfree)的倒塌,除受自身屬性影響外,還可能受另外兩類剛體影響:

(1)Rfree的底部接觸剛體Rb;

(2)Rfree的x軸負(fù)方向側(cè)面接觸剛體Rx。

其中,Rb對(duì)Rfree的倒塌產(chǎn)生影響的前提是Rb自身出現(xiàn)倒塌趨勢(shì),使得Rb對(duì)Rfree的支持力集中在Rfree底部靠x軸負(fù)方向的區(qū)域,導(dǎo)致Rfree產(chǎn)生順時(shí)針方向的力矩,如圖6所示。但是,根據(jù)HBC算法的特點(diǎn),位于某一剛體下方的剛體,一般高度較低,難以倒塌。因此,可忽略Rb對(duì)Rfree的倒塌產(chǎn)生的影響。

圖6 Rb對(duì)Rfree倒塌的影響

圖7 Rx示意圖

圖8 剛體樹示意圖

步驟1搜索中所有的自由剛體,分別生成根節(jié)點(diǎn),加入剛體樹集。初始化葉子節(jié)點(diǎn)集=。

步驟2遍歷,若有不位于其他剛體下方的剛體R,與中節(jié)點(diǎn)L剛體的x軸負(fù)方向側(cè)面接觸,則以R生成節(jié)點(diǎn),并將該節(jié)點(diǎn)作為L(zhǎng)的子節(jié)點(diǎn)。

步驟3將更新為中的所有葉子節(jié)點(diǎn)。若變化,則返回步驟2,否則輸出。

另外,為便于后續(xù)可承載加速度的計(jì)算,剛體樹中節(jié)點(diǎn)除記錄剛體本身外,還需記錄與剛體相關(guān)的一系列參數(shù),如表1所示為節(jié)點(diǎn)具體的屬性定義。其中,R、h、l、m、core在節(jié)點(diǎn)生成時(shí)確定,parent、z、p在將節(jié)點(diǎn)作為其他節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)確定,children在添加子節(jié)點(diǎn)時(shí)確定。這些參數(shù)在3.4節(jié)可承載加速度計(jì)算中介紹。

表1 節(jié)點(diǎn)屬性定義

剛體樹生成偽代碼如算法2所示。

算法2剛體樹生成。

4: while true do

6: if R不位于其他剛體下方

7: and R與L剛體的x軸負(fù)方向側(cè)面接觸 do

8: 以R生成節(jié)點(diǎn),并將該節(jié)點(diǎn)作為L(zhǎng)的子節(jié)點(diǎn)

9: end if

10: end foreach

13: break

14: end if

15: end while

17:end function

3.4 可承載加速度計(jì)算

堆垛S的Tac為不使S中任何箱子倒塌的最大加速度值,即不使S的剛體樹集中任何樹的根節(jié)點(diǎn)剛體(自由剛體)倒塌的最大加速度值。自由剛體的倒塌會(huì)受樹中其他剛體的影響,本文將這種影響抽象為剛體之間的阻倒力的傳遞。阻倒力表示阻止剛體倒塌需要的力的大小,阻倒力越大,剛體倒塌趨勢(shì)越大。本節(jié)首先分析倒塌不受其他剛體影響的剛體(稱為獨(dú)立剛體)的阻倒力,隨后分析剛體樹中阻倒力的傳遞方式,最后給出基于阻倒力的可承載加速度計(jì)算方法。

3.4.1 獨(dú)立剛體的阻倒力

圖9 托盤上放置獨(dú)立剛體場(chǎng)景

ma=f;

(4)

JCε=fh-Nl。

(5)

N=mg。

(6)

聯(lián)立式(4)～式(6)可得:

JCε=mah-mgl。

(7)

ma=f+φ;

(8)

JCε=fh-Nl-φd。

(9)

由于R持續(xù)處于臨界倒塌狀態(tài),角加速度ε=0。聯(lián)立式(6)、式(8)和式(9)可得,

(10)

當(dāng)a<(l/h)g時(shí),加速度不足以使R倒塌,阻倒力φ=0。因此,獨(dú)立剛體R的阻倒力φ的計(jì)算式為:

(11)

由式(11)可知,φ可視為隨a和d變化的變量,即φ=φ(a,d)。不使獨(dú)立剛體R倒塌的最大加速度值,就等于使它的阻倒力φ=0的a的最大值,即(l/h)g。

3.4.2 剛體樹中阻倒力的傳遞

圖10 托盤上放置兩個(gè)相鄰剛體場(chǎng)景

m2a=f2-ψ1+φ2;

(12)

f2h2-m2gl2+ψ1e1-φ2d2=0。

(13)

(14)

等號(hào)右側(cè)可由加號(hào)分為兩個(gè)子式:①將R2視為獨(dú)立剛體時(shí)的阻倒力;②R1傳遞給R2的阻倒力。在計(jì)算②時(shí),還需另添加一權(quán)重p1,取值范圍為(0,1],命名為阻倒力傳遞系數(shù)。添加該權(quán)重的原因是:R1的x軸正方向側(cè)面除了與R2接觸外,還可能與其他剛體接觸,導(dǎo)致R1僅將部分阻倒力傳遞至R2,另外部分傳遞至其他剛體。本文以接觸面積的比例表示阻倒力傳遞系數(shù),即

(15)

其中:c12表示R1與R2的接觸面積,∑c1表示R1在x軸正方向側(cè)面的總接觸面積。

又因?yàn)樽璧沽Ψ秦?fù),且隨加速度的增大而增大,可得φ2的計(jì)算式,

(16)

其中α為下式的解,

(17)

當(dāng)R2存在R11,R12,...,R1k等多個(gè)子節(jié)點(diǎn)剛體時(shí)(如圖11),不難推斷,φ2的計(jì)算式為:

(18)

圖11 R2存在多個(gè)子節(jié)點(diǎn)剛體示意圖

其中α為下式的解,

(19)

由式(18)可知,在剛體接觸面的最高位置已知的前提下,R2的阻倒力φ2可視為隨a和d2變化的變量,即φ2=φ2(a,d2)。若需進(jìn)一步將R2的阻倒力傳遞至它的父節(jié)點(diǎn)剛體R3,可再通過式(18)將φ2(a,d2)作為R3的阻倒力φ3的子式進(jìn)行計(jì)算。

3.4.3 可承載加速度計(jì)算

堆垛S的Tac,等于不使S的剛體樹集中任何樹的根節(jié)點(diǎn)剛體倒塌的最大加速度值,等于使中所有樹的根節(jié)點(diǎn)剛體阻倒力為0的最大加速度值。

由樹的結(jié)構(gòu)和阻倒力的傳遞方式可知,剛體樹中的阻倒力是從葉子節(jié)點(diǎn)剛體開始,逐步往上層剛體傳遞,直至根節(jié)點(diǎn)剛體。因此,根節(jié)點(diǎn)剛體的阻倒力的計(jì)算涉及剛體樹中的所有剛體。本文使用深度優(yōu)先搜索算法實(shí)現(xiàn)根節(jié)點(diǎn)剛體阻倒力的計(jì)算。

可承載加速度計(jì)算偽代碼如算法3所示,其中GetPhi為阻倒力計(jì)算函數(shù)。樹中節(jié)點(diǎn)屬性的定義見表1。

算法3可承載加速度計(jì)算。

輸出:Tac//可承載加速度。

2: TAC←?

4: TAC←TAC∪{使GetPhi(T.root,a,0)=0的a的最大值}

//根節(jié)點(diǎn)剛體的d不影響計(jì)算結(jié)果,默認(rèn)為0

5: end foreach

6: return TAC中的最小值Tac

7:end function

8:function GetPhi (node,a,d) //阻倒力計(jì)算函數(shù)

9: (h,l,m,p,core)←node.(h,l,m,p,core)

10: if node沒有子節(jié)點(diǎn) do

11: return max(0,(m/(h+d))(ah-gl))

12: end if

13: φ←(m/(h+d))(ah-gl)

14: foreach child∈node.children do

15: e1←child.z-core.z

16: d1←child.z-child.core.z

17: φ←φ+(h+e1)/(h+d)GetPhi(child,a,d1)

18: end foreach

19: return max(0,φ·p)

20:end function

4 實(shí)驗(yàn)測(cè)試

為驗(yàn)證本文提出的可承載加速度的有效性,將本文和文獻(xiàn)[14-15]、文獻(xiàn)[23]提出的動(dòng)態(tài)穩(wěn)定性評(píng)估方法對(duì)比。其中,文獻(xiàn)[14]提出的非底層箱子的平均支撐箱數(shù)記為M1;文獻(xiàn)[15]中所有箱子在x軸正方向側(cè)面的平均支撐系數(shù)記為M2;文獻(xiàn)[23]中使所有箱子保持平衡的x軸負(fù)方向最大加速度值記為M3;本文提出的可承載加速度記為Tac。對(duì)比分析RGV堆垛的M1、M2、M3、Tac與RGV堆垛的真實(shí)動(dòng)態(tài)穩(wěn)定性之間的相關(guān)性,相關(guān)性越強(qiáng),則表明對(duì)應(yīng)方法在智能倉(cāng)儲(chǔ)自動(dòng)調(diào)度場(chǎng)景中的性能越好。為提高測(cè)試效率,利用Unity仿真環(huán)境測(cè)試得到不使RGV堆垛倒塌的最大加速度值,記為Sim,表示RGV堆垛的真實(shí)動(dòng)態(tài)穩(wěn)定性。本文可承載加速度算法由C#語(yǔ)言實(shí)現(xiàn),使用的Unity版本為2017.4,內(nèi)置PhysX物理引擎,實(shí)驗(yàn)計(jì)算機(jī)的CPU為Intel(R) Core(TM) i5-7300HQ CPU @ 2.50 GHz。

4.1 RGV堆垛的動(dòng)態(tài)穩(wěn)定性仿真

為測(cè)試得到RGV堆垛的Sim,使用Unity生成托盤和箱子,給與它們碰撞器、摩擦材質(zhì)和剛體屬性,搭建RGV堆垛運(yùn)動(dòng)的虛擬場(chǎng)景。虛擬場(chǎng)景中,托盤、箱子和地板的具體參數(shù)設(shè)置如表2所示(未聲明的參數(shù)為默認(rèn)設(shè)置)。為使仿真測(cè)試更接近現(xiàn)實(shí),設(shè)置箱子的質(zhì)量正比于體積;為使托盤運(yùn)動(dòng)平穩(wěn),設(shè)置其質(zhì)量足夠大(100倍箱子總質(zhì)量)。

表2 Unity虛擬場(chǎng)景中托盤、箱子和地板的具體參數(shù)設(shè)置

對(duì)給定的RGV堆垛,將托盤放置在地板上,再將堆垛放置在托盤上,利用Unity庫(kù)的AddForce()函數(shù)對(duì)托盤施加x軸負(fù)方向的力,力的大小等于(托盤質(zhì)量+箱子總質(zhì)量)×給定加速度值,以此模擬給定加速度下的RGV堆垛運(yùn)動(dòng)。RGV堆垛的Sim的測(cè)試步驟如下:

步驟1選擇一個(gè)合適的加速度大小范圍[alow,ahigh](本文選擇[0,10]);

步驟2若ahigh-alow<0.1,結(jié)束查找,取Sim=alow;

步驟3取amid=(alow+ahigh)/2,使托盤以大小為amid的加速度向x軸負(fù)方向加速;

步驟4若5 s內(nèi)有箱子往x軸正方向的旋轉(zhuǎn)角度大于15°,取ahigh=amid,否則取alow=amid,還原場(chǎng)景,返回步驟2。

4.2 示例測(cè)試

為介紹M1、M2、M3、Tac與Sim的相關(guān)性測(cè)試的具體過程,本節(jié)在小樣本上進(jìn)行示例測(cè)試。由文獻(xiàn)[24]三維裝箱算法,根據(jù)OR-Library中的BR1前4個(gè)算例[14]生成4個(gè)堆垛,在虛擬場(chǎng)景中的顯示如圖12所示,其(箱子種類,箱子個(gè)數(shù),總質(zhì)量)分別為(3,105,269),(3,122,281),(3,112,266)和(3,153,273)。以這4個(gè)堆垛構(gòu)建樣本,測(cè)試M1、M2、M3、Tac與Sim之間的相關(guān)性。

圖12 4個(gè)堆垛在虛擬場(chǎng)景中的顯示

對(duì)任一堆垛S,首先,將S中的箱子歸類,得堆集,歸類結(jié)果可視化如圖13所示,其中以顏色區(qū)分不同的堆,將中各個(gè)堆視為剛體,得剛體集;其次,生成對(duì)應(yīng)的剛體樹集;再次,根據(jù)計(jì)算S的可承載加速度Tac;最后,分別計(jì)算S的M1、M2、M3,并使用4.1節(jié)中的方法測(cè)試得到Sim。

圖13 4個(gè)堆垛的歸類結(jié)果可視化

4個(gè)堆垛的M1、M2、M3、Tac計(jì)算結(jié)果和Sim測(cè)試結(jié)果如表3所示。由表3可知,隨著堆垛的變換,M1和M2的變化趨勢(shì)與Sim有一定差別,M3和Tac均與Sim有著大致相同的變化趨勢(shì)。因此,在該樣本上,M1、M2與Sim的相關(guān)性不明顯,M3、Tac與Sim之間可能存在一定相關(guān)性。

4.3 統(tǒng)計(jì)測(cè)試對(duì)比

為深入分析M1、M2、M3、Tac與Sim之間的相關(guān)性,由文獻(xiàn)[24]三維裝箱算法根據(jù)OR-Library中的BR1～BR10算例[14]生成1 000個(gè)樣本堆垛,并改變堆垛的碼放方向以提高樣本隨機(jī)性,每個(gè)堆垛有4種碼放方向,分別對(duì)應(yīng)堆垛的4個(gè)側(cè)面靠近x軸正方向,因此可得4 000個(gè)樣本。另外,為分析堆垛的異構(gòu)強(qiáng)度(箱子種類數(shù))對(duì)本文可承載加速度算法性能的影響,根據(jù)箱子種類的不同將4 000個(gè)樣本堆垛劃分為10組,每組有400個(gè)堆垛,分別對(duì)應(yīng)算例BR1～BR10,異構(gòu)強(qiáng)度分別為3、5、8、10、12、15、20、30、40、50。計(jì)算10組樣本堆垛的M1、M2、M3和Tac,并測(cè)試Sim。

本文采取與RAMOS等[18]相同的相關(guān)性分析方法,即以皮爾遜相關(guān)系數(shù)[25](Pearson’s correlation coefficient,Pearson’s r)表示兩變量之間的相關(guān)性。Pearson’s r∈[-1,1],其絕對(duì)值越大,表明兩變量的線性相關(guān)性越強(qiáng)。另外,計(jì)算p-value以進(jìn)行顯著性分析,其值越小,表明結(jié)果越顯著。在10組樣本(每組400個(gè)堆垛)和總體樣本(共4 000個(gè)堆垛)分別計(jì)算M1、M2、M3、Tac與Sim之間的Pearson’s r和對(duì)應(yīng)的p-value。

相關(guān)性測(cè)試結(jié)果對(duì)比如表4所示(其中“<”符號(hào)表示p-value<2.2e-16)。由表4可知,M1在BR1、BR2、BR4、BR5、BR7～BR10上的p-value<0.05,Pearson’s r∈[0,0.4),在BR3、BR6上的p-value>0.05,在總體樣本上的p-value<0.001,Pearson’s r∈[0,0.4),表明M1在大部分樣本組與Sim在0.05水平上顯著正相關(guān)性,但相關(guān)性弱[25],在小部分樣本組(BR3、BR6)與Sim的相關(guān)性不顯著,在總體樣本與Sim在0.001水平上顯著正相關(guān)性,但相關(guān)性弱[25]。同理可知,M2在所有樣本組與Sim在0.01水平上顯著正相關(guān)性(相關(guān)性弱),在總體樣本與Sim在0.001水平上顯著正相關(guān)性(相關(guān)性弱);M3在弱異構(gòu)樣本組(BR1～BR6)與Sim在0.01水平上顯著正相關(guān)性(相關(guān)性弱),在強(qiáng)異構(gòu)樣本組(BR7～BR10)與Sim的相關(guān)性不顯著,在總體樣本與Sim在0.001水平上顯著正相關(guān)性(相關(guān)性弱)。本文提出的Tac在所有樣本組上的p-value<0.001,Pearson’s r∈[0.8,1],在總體樣本上的p-value<0.001,Pearson’s r∈[0.8,1],表明Tac在所有樣本組和總體樣本均與Sim在0.001水平上顯著正相關(guān)性,且相關(guān)性極強(qiáng)[25]。同時(shí)由表4可知,Tac與Sim之間的Pearson’s r不因堆垛異構(gòu)強(qiáng)度的改變產(chǎn)生明顯變化。

以上測(cè)試結(jié)果表明,本文提出的可承載加速度能夠有效評(píng)估RGV堆垛的動(dòng)態(tài)穩(wěn)定性,在智能倉(cāng)儲(chǔ)自動(dòng)調(diào)度場(chǎng)景中的性能優(yōu)于多數(shù)同類型算法。需要注意的是,Unity仿真堆垛的運(yùn)動(dòng)規(guī)律與真實(shí)堆垛存在差距,筆者發(fā)現(xiàn)當(dāng)Unity中豎直疊放箱子數(shù)較多時(shí),它們會(huì)變得過于不穩(wěn)定,甚至出現(xiàn)仿真堆垛的動(dòng)態(tài)穩(wěn)定性等于0的情況,這使得部分堆垛測(cè)試的Sim偏小,影響Pearson’s r的計(jì)算。

5 結(jié)束語(yǔ)

本文對(duì)RGV堆垛的動(dòng)態(tài)穩(wěn)定性進(jìn)行了研究,提出一種RGV堆垛的可承載加速度(使任何箱子都不倒塌的最大加速度值)計(jì)算方法。算法過程為:①將RGV堆垛中箱子歸類為堆,將堆視為剛體;②根據(jù)剛體間的位置構(gòu)建剛體樹,生成剛體樹集合;③根據(jù)剛體樹集合中樹的根節(jié)點(diǎn)剛體阻倒力計(jì)算RGV堆垛的可承載加速度。為了驗(yàn)證本文提出的可承載加速度的有效性,測(cè)試了RGV堆垛可承載加速度計(jì)算結(jié)果Tac與Unity仿真堆垛的動(dòng)態(tài)穩(wěn)定性Sim之間的皮爾遜相關(guān)系數(shù),結(jié)果表明兩者呈現(xiàn)極強(qiáng)線性相關(guān)性,優(yōu)于現(xiàn)有動(dòng)態(tài)穩(wěn)定性評(píng)估方法。本文提出的可承載加速度可用于約束RGV運(yùn)動(dòng)加速度,以減少倒堆垛倒塌事件的發(fā)生,還能夠定量評(píng)估RGV堆垛的動(dòng)態(tài)穩(wěn)定性,約束RGV-BPP的求解,從而兼顧堆垛的裝載效率和動(dòng)態(tài)穩(wěn)定性。未來的工作將專注于將可承載加速度用于實(shí)際的三維裝箱問題的求解。高效且滿足動(dòng)態(tài)穩(wěn)定需求的裝箱算法,將是后續(xù)研究的重點(diǎn)。