經(jīng)濟(jì)的發(fā)展,帶動(dòng)人們的生活水平不斷提高,電子商務(wù)的發(fā)展突飛猛進(jìn)。物流領(lǐng)域的工作環(huán)境多變、工作量、復(fù)雜性有所提高,傳統(tǒng)的工作模式并不能滿足物流發(fā)展的需要。這種情況下,將移動(dòng)機(jī)器人引入到物流的倉(cāng)儲(chǔ)空間中,可以有效代替人工搬運(yùn)的問題,提高工作效率,減輕勞動(dòng)強(qiáng)度,降低維修成本,并且對(duì)倉(cāng)儲(chǔ)空間的布局有規(guī)劃作用。機(jī)器人的有效應(yīng)用解決了物流企業(yè)不少問題,并且緩解了工作者高強(qiáng)度的工作壓力。但實(shí)際操作中,大量的工作僅僅依靠一個(gè)或兩個(gè)機(jī)器人并不能完全實(shí)現(xiàn),因此機(jī)器人集群的作用就體現(xiàn)出來(lái)了,機(jī)器人集群的設(shè)計(jì)能夠解決更加復(fù)雜的問題,完成更加復(fù)雜的工作。倉(cāng)儲(chǔ)物流機(jī)器人系統(tǒng)的研究比較廣泛,包括機(jī)器人導(dǎo)航與定位、系統(tǒng)地圖的構(gòu)建,機(jī)器人任務(wù)的調(diào)度、路徑的揀選與規(guī)劃。本文主要針對(duì)倉(cāng)儲(chǔ)物流機(jī)器人的路徑揀選問題進(jìn)行了研究與實(shí)驗(yàn)。機(jī)器人路徑揀選的研究的前提是系統(tǒng)給出特定的指令和要求,從環(huán)境中獲取信息和機(jī)器人本身的狀態(tài),在此基礎(chǔ)上,通過特定的方法實(shí)現(xiàn)從目標(biāo)起點(diǎn)到目標(biāo)終點(diǎn)最佳路徑的規(guī)劃和選擇。
機(jī)器人集群在倉(cāng)儲(chǔ)空間的定位有很多方式,二維碼、GPS、藍(lán)牙等。機(jī)器人集群與中心控制系統(tǒng)之間的通信可以通過無(wú)線網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)。而對(duì)于機(jī)器人路徑規(guī)劃需要注意的問題有:首先,當(dāng)訂單到達(dá)之后,按照什么標(biāo)準(zhǔn)來(lái)調(diào)度機(jī)器人;其次,如何有效揀選及避免機(jī)器人在倉(cāng)儲(chǔ)環(huán)境中路徑規(guī)劃問題及碰撞問題;最后,在固定的空間中,既定任務(wù)數(shù)量,如何最優(yōu)化的配置機(jī)器人數(shù)量及路線。
設(shè)計(jì)前期建立一個(gè)自動(dòng)化的物流倉(cāng)儲(chǔ)空間的模型,設(shè)計(jì)的過程中需要考慮的問題有貨物擺放的位置、進(jìn)貨口、出貨口倉(cāng)儲(chǔ)內(nèi)部空間道路的情況,每一個(gè)倉(cāng)儲(chǔ)區(qū)域分別由縱向與橫向街道圍起來(lái)的區(qū)域,每個(gè)區(qū)域有2排擺放貨物的位置。在整個(gè)倉(cāng)儲(chǔ)空間中,如果出現(xiàn)機(jī)器人集群共同工作的情況,需要解決碰撞沖突的問題。逐漸簡(jiǎn)化機(jī)器人運(yùn)行規(guī)則,提高機(jī)器人安全運(yùn)行標(biāo)準(zhǔn),設(shè)定貨物運(yùn)輸方向和道路方向。倉(cāng)儲(chǔ)物流空間模型的建立,需要根據(jù)物流任務(wù)提出要求,從倉(cāng)儲(chǔ)空間的某一個(gè)貨物架的位置M1到出貨口或入貨口位置M2,待到完成任務(wù)后,返回某一個(gè)貨架位置M3,等待下一次任務(wù),具體流程如圖1所示。
物流任務(wù)的建立可以分為三個(gè)步驟:第一個(gè)和第三個(gè)步驟可以通過任務(wù)的分配調(diào)度來(lái)進(jìn)行優(yōu)化,減少浪費(fèi)的時(shí)間;第二個(gè)步驟需要采用路徑規(guī)劃的方法對(duì)路徑進(jìn)行優(yōu)化,具體流程如圖2所示。
在任務(wù)流程建立的基礎(chǔ)上,忽略精確路徑的規(guī)劃,可以將批量揀選路徑的規(guī)劃問題分為兩種:第一,機(jī)器人起點(diǎn)在出口,這種問題是TSP問題;第二,機(jī)器人的起點(diǎn)不在出口,在其他位置,可以將這種情況看做是起點(diǎn)終點(diǎn)固定的ST-TSP問題。TSP問題可以通過式(1)來(lái)進(jìn)行描述,求一條最優(yōu)的路徑L={n1,n2,n3......,nk}
minW(pα)=∑t=1k?1d(nαi,nαi+1)+d(nai,nak) (1)minW(pα)=∑t=1k-1d(nαi,nαi+1)+d(nai,nak)(1)
其中Pα是一組K個(gè)路徑點(diǎn)的排列,Pα是對(duì)路徑的一個(gè)置換,d(nαi,nαt+1)是兩點(diǎn)之間曼哈頓的距離。而對(duì)于TS-TSP來(lái)講,傳統(tǒng)的TSP問題的解決方式并不適合,需要對(duì)算法進(jìn)行改變。將H作為機(jī)器人的起點(diǎn),D為機(jī)器人的終點(diǎn),具體計(jì)算最優(yōu)路徑的方式為式(2):L={H,n1,n2,n3......nk,D}
minW(pα)=∑t=1k?1d(nαi,nαi+1)+d(H,na1)+d(D,nαk) (2)minW(pα)=∑t=1k-1d(nαi,nαi+1)+d(Η,na1)+d(D,nαk)(2)
公式中的Pα為去除H、D中間的K個(gè)路徑點(diǎn)次尋的重新排列,d(H,nα1)為H到一個(gè)分揀區(qū)域的距離,d(D,nαk)為D到另外分揀點(diǎn)的距離。TSP與TS-TSP的算法模型是不同的,但是兩種模型之間也有一定的聯(lián)系,TSP各節(jié)點(diǎn)之間是相通的,而TS-TSP是需要除去起點(diǎn)和終點(diǎn),中間的節(jié)點(diǎn)是相通的,并且兩種模式都要求歷遍所有的節(jié)點(diǎn),兩者都可以利用遺傳算法來(lái)計(jì)算。TSP利用遺傳算法計(jì)算時(shí),需要將路徑中所有的路徑點(diǎn)作為種群的個(gè)體,TS-TSP則是將中間節(jié)點(diǎn)作為種群個(gè)體。
A*算法是在靜態(tài)路網(wǎng)中求最短路徑值。而機(jī)器人揀選路徑則完全可以依靠A*算法。在A*算法路徑的規(guī)劃中,物流機(jī)器人的規(guī)劃問題可以表示為數(shù)學(xué)中的一個(gè)集合{space,rob,S,E,H}.其中space是整個(gè)倉(cāng)儲(chǔ)空間,也就是移動(dòng)機(jī)器人工作的空間,其中也可以包括多個(gè)或單個(gè)障礙物,ROB表示移動(dòng)機(jī)器人,S表示起始點(diǎn),T表示終點(diǎn),H代表A*算法中的函數(shù)。
本文利用柵格法來(lái)進(jìn)行地圖建模,柵格法就是利用AGV的工作環(huán)境進(jìn)行單元分割,分割出大小相等的格子,柵格法可以將環(huán)境信息、順序信息表達(dá)在網(wǎng)格中。分割出的大小相等的網(wǎng)格不會(huì)發(fā)生變化,并且機(jī)器人整個(gè)運(yùn)動(dòng)的過程不會(huì)發(fā)生改變。將機(jī)器人的環(huán)境信息進(jìn)行離散化,機(jī)器人整個(gè)工作的軌跡可以劃分為單個(gè)的運(yùn)動(dòng),然后將其組合起來(lái)。每一個(gè)離散運(yùn)動(dòng)都會(huì)保存在分割的格子上,利用柵格法規(guī)劃和計(jì)算最短路徑,并且要有效規(guī)避障礙物。
A*算法是最有效的直接搜索的方法,并且操作原理比較簡(jiǎn)單,對(duì)兩個(gè)集合進(jìn)行定義,一個(gè)是OPEN表,另一個(gè)CLOSE表,以下簡(jiǎn)稱O表和C表。O表保存準(zhǔn)備考察的節(jié)點(diǎn),C表保存已經(jīng)考察過的節(jié)點(diǎn)。A*算法開始,O表中包含一個(gè)起點(diǎn)元素,C表僅包含一個(gè)障礙物的節(jié)點(diǎn)。A*算法的流程是從O表中選取一個(gè)節(jié)點(diǎn)N(k),并檢驗(yàn)是否為目標(biāo)節(jié)點(diǎn)。如果K為目標(biāo)節(jié)點(diǎn),則路徑規(guī)劃結(jié)束,并且做出結(jié)論。如果K不是目標(biāo)節(jié)點(diǎn),節(jié)點(diǎn)K則會(huì)被保存到C表中,并從O表中刪除。并通過擴(kuò)展節(jié)點(diǎn)的方法考察K節(jié)點(diǎn)周圍的8個(gè)節(jié)點(diǎn),判斷是否為目標(biāo)節(jié)點(diǎn),此種方法,以此類推,具體的操作流程如下。
1)設(shè)置物流機(jī)器人運(yùn)動(dòng)的起點(diǎn)S與目標(biāo)點(diǎn)E,并且做好障礙物的分布工作;
2)做好A*算法的O表和C表,將兩個(gè)表的值進(jìn)行初始化,保證為(null);
3)將S與E賦值給O表,并將障礙節(jié)點(diǎn)賦值給C表;
4)使用評(píng)價(jià)函數(shù)F(k)進(jìn)行評(píng)估當(dāng)前節(jié)點(diǎn),如果K值為目標(biāo)點(diǎn),則路徑規(guī)劃結(jié)束,如果K值不是目標(biāo)點(diǎn),刪除該K值,進(jìn)行下一步;
5)對(duì)K節(jié)點(diǎn)周圍的8個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展,將8個(gè)節(jié)點(diǎn)中值最小的作為路徑規(guī)劃的下一個(gè)點(diǎn);
6)對(duì)O表進(jìn)行查看,是否為空,如果為空,則說明起點(diǎn)到目標(biāo)節(jié)點(diǎn)的所有數(shù)值都考察過,得出路徑規(guī)劃數(shù)據(jù),若不是空,則重復(fù)A*算法,再次進(jìn)行規(guī)劃。
在對(duì)倉(cāng)儲(chǔ)空間結(jié)構(gòu)設(shè)計(jì)時(shí),一般路徑規(guī)劃方法采用模糊算法,人工勢(shì)場(chǎng),神經(jīng)網(wǎng)絡(luò),A*算法等方法。其中比較常用的則是A*算法, A*比較簡(jiǎn)單通用,并且能夠保證用最快的速度尋找最優(yōu)的路徑。一般情況下,倉(cāng)儲(chǔ)空間的道路設(shè)計(jì)為單向行駛,A*算法會(huì)受到該種規(guī)則的約束,因此在特殊規(guī)則下,必須對(duì)A*算法進(jìn)行改正。A*算法的基本流程是從起點(diǎn)開始計(jì)算,根據(jù)實(shí)際計(jì)算情況來(lái)擴(kuò)展節(jié)點(diǎn),直到完成揀選工作,計(jì)算出目標(biāo)點(diǎn)。因此,對(duì)于評(píng)價(jià)函數(shù)的選擇非常重要,如式(3)
f(k)=g(k)+h(k) (3)
其中f(k)代表從起始狀態(tài)經(jīng)過節(jié)點(diǎn)K到目標(biāo)狀態(tài)的預(yù)估代價(jià)。g(k)代表在整個(gè)狀態(tài)空間中,從起始狀態(tài)到狀態(tài)K的實(shí)際代價(jià)。h(k)代表狀態(tài)空間中從狀態(tài)K到目標(biāo)節(jié)點(diǎn)最佳路徑的預(yù)估代價(jià)。倉(cāng)儲(chǔ)空間環(huán)境中所有通行的道路均為單行道路,在整個(gè)線路節(jié)點(diǎn)擴(kuò)展中,方向和順序是固定的。
如圖3所示:沿著縱向道路H1從節(jié)點(diǎn)M1開始擴(kuò)展,依次為M2、M3、M4、M5、M6、M7。其中M2 M3 M5 M6是順序擴(kuò)展的固定流程,主要在于M4和M6的節(jié)點(diǎn)是否會(huì)向P1和P3轉(zhuǎn)動(dòng),因此為了簡(jiǎn)化算法,可以將以網(wǎng)格為單位的擴(kuò)展,轉(zhuǎn)化成以道路為單位的節(jié)點(diǎn)擴(kuò)展路徑。
如圖4所示:沿縱向道路H1從節(jié)點(diǎn)M1開始擴(kuò)展,依次是M1、M2、M3。橫向道路是P1、P2、P3,以道路為節(jié)點(diǎn)的擴(kuò)展方式,減少擴(kuò)展次數(shù),提高工作效率,節(jié)省時(shí)間。道路在倉(cāng)儲(chǔ)空間中,不一定是路徑的起點(diǎn)或終點(diǎn),一般貨架的存放空間才是起點(diǎn)或終點(diǎn),這就是特殊情況,需要加入特殊的擴(kuò)展方法,特殊擴(kuò)展分為三種形式。當(dāng)節(jié)點(diǎn)是貨架的起點(diǎn),可擴(kuò)展的節(jié)點(diǎn)有相鄰道路的位置,如圖5所示,黃色格子為貨架M1,灰色格子是可以擴(kuò)展的后續(xù)節(jié)點(diǎn),節(jié)點(diǎn)P即為H1,節(jié)點(diǎn)Q代表橫向道路P2,當(dāng)節(jié)點(diǎn)為道路時(shí),則可擴(kuò)展所有道路交叉節(jié)點(diǎn)的所有道路。
無(wú)論是道路節(jié)點(diǎn)或是貨架為節(jié)點(diǎn),f(k)評(píng)價(jià)函數(shù)都需要根據(jù)實(shí)際情況作出調(diào)整,除了基本的曼哈頓路徑,還需要根據(jù)道路的方向與實(shí)際情況作出相應(yīng)的轉(zhuǎn)變。
假設(shè)可以對(duì)每一個(gè)時(shí)刻的機(jī)器人的具體位置進(jìn)行監(jiān)控,就可以避免在路徑規(guī)劃過程中可能會(huì)發(fā)生的沖突。因此在算法中可以加入一個(gè)地圖,可以記錄每一個(gè)時(shí)刻機(jī)器人運(yùn)動(dòng)的軌跡,并將機(jī)器人運(yùn)動(dòng)軌跡記錄下來(lái),形成一個(gè)三維地圖,地圖中包括運(yùn)行方向、運(yùn)行時(shí)間,地圖可以作為線路揀選的參考。在基于A*算法的基礎(chǔ)上,加入時(shí)間軌跡,可以將路徑代價(jià)替換為時(shí)間代價(jià)。同時(shí)需要充分考慮到運(yùn)動(dòng)過程中涉及到的碰撞問題,將碰撞問題加入到時(shí)間代價(jià)中。因此在路徑規(guī)劃和揀選中,需要考慮延時(shí)問題,避免規(guī)劃出的路徑產(chǎn)生沖突問題。
倉(cāng)儲(chǔ)道路具有一定的特殊性,其方向?yàn)閱蜗颉R?guī)劃的先后順序并不能保證運(yùn)行的有限順序。后規(guī)劃的路徑A插入到先規(guī)劃的任務(wù)B的前方,那么B只能選擇等待,這樣的問題出現(xiàn)就會(huì)導(dǎo)致實(shí)際規(guī)劃情況與原計(jì)劃不符。遇到這種情況,任務(wù)仍需要按照原規(guī)劃的路徑來(lái)完成。可能在時(shí)間上不能與原計(jì)劃保持一致。但如果繼續(xù)根據(jù)已經(jīng)發(fā)生偏差的路徑來(lái)完成任務(wù),即使任務(wù)能夠完成,誤差則會(huì)積累的更多。因此一旦是按照非規(guī)劃的路徑來(lái)完成任務(wù),則需要及時(shí)修改地圖,保證地圖與實(shí)際情況相符合。
倉(cāng)儲(chǔ)機(jī)器人在運(yùn)動(dòng)的過程中,發(fā)生碰撞的問題是不可避免的。如何有效地解決碰撞的問題,也是路徑揀選過程中需要注意的情況。避免可能發(fā)生的碰撞,需要設(shè)立獨(dú)占點(diǎn)。在特定的時(shí)刻,特定的位置,只能由一個(gè)機(jī)器人來(lái)完成工作。同一時(shí)刻進(jìn)入的工作機(jī)器人必須選擇等待。在實(shí)際工作的系統(tǒng)中,機(jī)器人都會(huì)通過傳感器來(lái)完成定位與導(dǎo)航的工作,在檢測(cè)到機(jī)器人之間的距離小于警戒值,要作出剎車指令,防止出現(xiàn)碰撞情況,影響工作效率,提高工作成本。
通過有效的仿真實(shí)驗(yàn)可以驗(yàn)證選擇的路徑揀選算法是否有效,進(jìn)一步研究機(jī)器人數(shù)量、路徑、效率三種之間的關(guān)系。
必須保證仿真實(shí)驗(yàn)的真實(shí)性與客觀性,避免受到任務(wù)本身性質(zhì)的影響。采用隨機(jī)的算法來(lái)布置任務(wù),貨架與機(jī)器人的位置與數(shù)量都是隨機(jī)產(chǎn)生。任務(wù)的編號(hào)與入貨口、出貨口符合要求,隨機(jī)分布。設(shè)置任務(wù)數(shù)量2000,隨機(jī)調(diào)取20組任務(wù),機(jī)器人數(shù)量分別設(shè)定為10、20、30、40、50、60、70、80、90、100共10種情況。每種情況通過2種算法揀選合適路徑完成20組任務(wù),一共進(jìn)行200次實(shí)驗(yàn)。
在進(jìn)行200次的實(shí)驗(yàn)中,任務(wù)順利完成,驗(yàn)證了倉(cāng)儲(chǔ)物流機(jī)器人路徑規(guī)劃的可行性與有效性。表1顯示,利用方差分析機(jī)器人數(shù)量、路徑規(guī)劃算法對(duì)物流任務(wù)的影響,其中包括里程、時(shí)間及碰撞沖突。機(jī)器人數(shù)量的配置對(duì)運(yùn)行的里程、時(shí)間及碰撞發(fā)生次數(shù)都有明顯的影響。而兩種路徑揀選算法在里程和時(shí)間上沒有明顯的差別,但在碰撞沖突方面的差別比較明顯。
表1 仿真實(shí)驗(yàn)結(jié)果 導(dǎo)出到EXCEL
P |
工作總里程 | 工作時(shí)間 | 碰撞沖突次數(shù) |
機(jī)器人數(shù)量 |
<10-5 | <10-5 | <10-5 |
路徑規(guī)劃算法 |
0.9748 | 0.9211 | 0.0015 |
根據(jù)計(jì)算圖6總結(jié)了不同數(shù)量配置的機(jī)器人集群在兩種路徑規(guī)劃算法下的2000個(gè)任務(wù)所運(yùn)行總里程的10個(gè)實(shí)驗(yàn)平均值。通過呈現(xiàn)的數(shù)據(jù)可以看出,隨著機(jī)器人數(shù)量的不斷增加,機(jī)器人工作總里程也逐漸降低,而增加的機(jī)器人為系統(tǒng)提供了更靈活的工作方式,在工作中可以選擇貨架與目標(biāo)地、機(jī)器人距離比較接近的完成任務(wù)。
通過圖6、圖7的分析可以很直觀的看出,兩種規(guī)劃方法的約束下,A*的算法的各項(xiàng)數(shù)值比較接近,加入時(shí)序路徑規(guī)劃算法,會(huì)降低工作中碰撞的次數(shù)。但如果是倉(cāng)儲(chǔ)空間中,單行道路的設(shè)定,時(shí)序算法并不能完全避免碰撞問題的出現(xiàn)。
本文針對(duì)倉(cāng)儲(chǔ)物流機(jī)器人在倉(cāng)儲(chǔ)空間的路徑規(guī)劃問題進(jìn)行分析和研究,根據(jù)A*算法,建立一個(gè)靈活的倉(cāng)儲(chǔ)空間,根據(jù)任務(wù)建立的特點(diǎn),建立合適的任務(wù)流程和算法模型,根據(jù)A*的基本算法,有針對(duì)性地進(jìn)行修改算法,建立特殊規(guī)則的A*算法和時(shí)序的A*算法。這種方法能夠解決批量路徑揀選的問題,為機(jī)器人更好的工作,提供高效的技術(shù)支持。
權(quán)所有©:上海陽(yáng)合儲(chǔ)運(yùn)
專業(yè)承接上海倉(cāng)庫(kù)租賃、上海倉(cāng)儲(chǔ)配送物流、上海電商倉(cāng)儲(chǔ)企業(yè)服務(wù)與微笑同在"的先進(jìn)理念不斷發(fā)展壯大。