倉儲物流機(jī)器人批量揀選路徑規(guī)劃仿真

陳 文

(福建船政交通職業(yè)學(xué)院，福建 福州 350007)

1 研究背景

經(jīng)濟(jì)的發(fā)展，帶動人們的生活水平不斷提高，電子商務(wù)的發(fā)展突飛猛進(jìn)。物流領(lǐng)域的工作環(huán)境多變、工作量、復(fù)雜性有所提高，傳統(tǒng)的工作模式并不能滿足物流發(fā)展的需要。這種情況下，將移動機(jī)器人引入到物流的倉儲空間中，可以有效代替人工搬運(yùn)的問題，提高工作效率，減輕勞動強(qiáng)度，降低維修成本，并且對倉儲空間的布局有規(guī)劃作用。機(jī)器人的有效應(yīng)用解決了物流企業(yè)不少問題，并且緩解了工作者高強(qiáng)度的工作壓力。但實(shí)際操作中，大量的工作僅僅依靠一個或兩個機(jī)器人并不能完全實(shí)現(xiàn)，因此機(jī)器人集群的作用就體現(xiàn)出來了，機(jī)器人集群的設(shè)計(jì)能夠解決更加復(fù)雜的問題，完成更加復(fù)雜的工作。倉儲物流機(jī)器人系統(tǒng)的研究比較廣泛，包括機(jī)器人導(dǎo)航與定位、系統(tǒng)地圖的構(gòu)建，機(jī)器人任務(wù)的調(diào)度、路徑的揀選與規(guī)劃。本文主要針對倉儲物流機(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ī)器人集群在倉儲空間的定位有很多方式，二維碼、GPS、藍(lán)牙等。機(jī)器人集群與中心控制系統(tǒng)之間的通信可以通過無線網(wǎng)絡(luò)來實(shí)現(xiàn)。而對于機(jī)器人路徑規(guī)劃需要注意的問題有：首先，當(dāng)訂單到達(dá)之后，按照什么標(biāo)準(zhǔn)來調(diào)度機(jī)器人；其次，如何有效揀選及避免機(jī)器人在倉儲環(huán)境中路徑規(guī)劃問題及碰撞問題；最后，在固定的空間中，既定任務(wù)數(shù)量，如何最優(yōu)化的配置機(jī)器人數(shù)量及路線。

2 倉儲空間結(jié)構(gòu)與物流任務(wù)分析

設(shè)計(jì)前期建立一個自動化的物流倉儲空間的模型，設(shè)計(jì)的過程中需要考慮的問題有貨物擺放的位置、進(jìn)貨口、出貨口倉儲內(nèi)部空間道路的情況，每一個倉儲區(qū)域分別由縱向與橫向街道圍起來的區(qū)域，每個區(qū)域有2排擺放貨物的位置。在整個倉儲空間中，如果出現(xiàn)機(jī)器人集群共同工作的情況，需要解決碰撞沖突的問題。逐漸簡化機(jī)器人運(yùn)行規(guī)則，提高機(jī)器人安全運(yùn)行標(biāo)準(zhǔn)，設(shè)定貨物運(yùn)輸方向和道路方向。倉儲物流空間模型的建立，需要根據(jù)物流任務(wù)提出要求，從倉儲空間的某一個貨物架的位置M1到出貨口或入貨口位置M2，待到完成任務(wù)后，返回某一個貨架位置M3，等待下一次任務(wù)，具體流程如圖1所示。

圖1 任務(wù)流程建立

物流任務(wù)的建立可以分為三個步驟：第一個和第三個步驟可以通過任務(wù)的分配調(diào)度來進(jìn)行優(yōu)化，減少浪費(fèi)的時間；第二個步驟需要采用路徑規(guī)劃的方法對路徑進(jìn)行優(yōu)化，具體流程如圖2所示。

圖2 物流任務(wù)的流程圖

3 批量揀選路徑規(guī)劃算法

3.1 批量揀選路徑規(guī)劃數(shù)學(xué)模型

在任務(wù)流程建立的基礎(chǔ)上，忽略精確路徑的規(guī)劃，可以將批量揀選路徑的規(guī)劃問題分為兩種：第一，機(jī)器人起點(diǎn)在出口，這種問題是TSP問題；第二，機(jī)器人的起點(diǎn)不在出口，在其他位置，可以將這種情況看做是起點(diǎn)終點(diǎn)固定的ST-TSP問題。TSP問題可以通過式(1)來進(jìn)行描述，求一條最優(yōu)的路徑L={n1，n2，n3......，nk}

(1)

其中Pα是一組K個路徑點(diǎn)的排列，Pα是對路徑的一個置換，d(nαi,nαt+1)是兩點(diǎn)之間曼哈頓的距離。而對于TS-TSP來講，傳統(tǒng)的TSP問題的解決方式并不適合，需要對算法進(jìn)行改變。將H作為機(jī)器人的起點(diǎn)，D為機(jī)器人的終點(diǎn)，具體計(jì)算最優(yōu)路徑的方式為式(2)：L={H，n1，n2，n3......nk，D}

(2)

公式中的Pα為去除H、D中間的K個路徑點(diǎn)次尋的重新排列，d(H,nα1)為H到一個分揀區(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)，兩者都可以利用遺傳算法來計(jì)算。TSP利用遺傳算法計(jì)算時，需要將路徑中所有的路徑點(diǎn)作為種群的個體，TS-TSP則是將中間節(jié)點(diǎn)作為種群個體。

3.2 對A*算法改進(jìn)的具體步驟

A*算法是在靜態(tài)路網(wǎng)中求最短路徑值。而機(jī)器人揀選路徑則完全可以依靠A*算法。在A*算法路徑的規(guī)劃中，物流機(jī)器人的規(guī)劃問題可以表示為數(shù)學(xué)中的一個集合{space，rob，S,E,H}.其中space是整個倉儲空間，也就是移動機(jī)器人工作的空間，其中也可以包括多個或單個障礙物，ROB表示移動機(jī)器人，S表示起始點(diǎn)，T表示終點(diǎn)，H代表A*算法中的函數(shù)。

1.環(huán)境建模。本文利用柵格法來進(jìn)行地圖建模，柵格法就是利用AGV的工作環(huán)境進(jìn)行單元分割，分割出大小相等的格子，柵格法可以將環(huán)境信息、順序信息表達(dá)在網(wǎng)格中。分割出的大小相等的網(wǎng)格不會發(fā)生變化，并且機(jī)器人整個運(yùn)動的過程不會發(fā)生改變。將機(jī)器人的環(huán)境信息進(jìn)行離散化，機(jī)器人整個工作的軌跡可以劃分為單個的運(yùn)動，然后將其組合起來。每一個離散運(yùn)動都會保存在分割的格子上，利用柵格法規(guī)劃和計(jì)算最短路徑，并且要有效規(guī)避障礙物。

2.A*算法的具體流程。A*算法是最有效的直接搜索的方法，并且操作原理比較簡單，對兩個集合進(jìn)行定義，一個是OPEN表，另一個CLOSE表，以下簡稱O表和C表。O表保存準(zhǔn)備考察的節(jié)點(diǎn)，C表保存已經(jīng)考察過的節(jié)點(diǎn)。A*算法開始，O表中包含一個起點(diǎn)元素，C表僅包含一個障礙物的節(jié)點(diǎn)。A*算法的流程是從O表中選取一個節(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則會被保存到C表中，并從O表中刪除。并通過擴(kuò)展節(jié)點(diǎn)的方法考察K節(jié)點(diǎn)周圍的8個節(jié)點(diǎn)，判斷是否為目標(biāo)節(jié)點(diǎn)，此種方法，以此類推，具體的操作流程如下。

1)設(shè)置物流機(jī)器人運(yùn)動的起點(diǎn)S與目標(biāo)點(diǎn)E，并且做好障礙物的分布工作；

2)做好A*算法的O表和C表，將兩個表的值進(jìn)行初始化，保證為(null)；

3)將S與E賦值給O表，并將障礙節(jié)點(diǎn)賦值給C表；

4)使用評價函數(shù)F(k)進(jìn)行評估當(dāng)前節(jié)點(diǎn)，如果K值為目標(biāo)點(diǎn)，則路徑規(guī)劃結(jié)束，如果K值不是目標(biāo)點(diǎn)，刪除該K值，進(jìn)行下一步；

5)對K節(jié)點(diǎn)周圍的8個節(jié)點(diǎn)進(jìn)行擴(kuò)展，將8個節(jié)點(diǎn)中值最小的作為路徑規(guī)劃的下一個點(diǎn)；

6)對O表進(jìn)行查看，是否為空，如果為空，則說明起點(diǎn)到目標(biāo)節(jié)點(diǎn)的所有數(shù)值都考察過，得出路徑規(guī)劃數(shù)據(jù)，若不是空，則重復(fù)A*算法，再次進(jìn)行規(guī)劃。

3.3 特殊規(guī)則下A*算法的路徑規(guī)劃

在對倉儲空間結(jié)構(gòu)設(shè)計(jì)時，一般路徑規(guī)劃方法采用模糊算法，人工勢場，神經(jīng)網(wǎng)絡(luò)，A*算法等方法。其中比較常用的則是A*算法， A*比較簡單通用，并且能夠保證用最快的速度尋找最優(yōu)的路徑。一般情況下，倉儲空間的道路設(shè)計(jì)為單向行駛，A*算法會受到該種規(guī)則的約束，因此在特殊規(guī)則下，必須對A*算法進(jìn)行改正。A*算法的基本流程是從起點(diǎn)開始計(jì)算，根據(jù)實(shí)際計(jì)算情況來擴(kuò)展節(jié)點(diǎn)，直到完成揀選工作，計(jì)算出目標(biāo)點(diǎn)。因此，對于評價函數(shù)的選擇非常重要，如式(3)

f(k)=g(k)+h(k)

(3)

其中f(k)代表從起始狀態(tài)經(jīng)過節(jié)點(diǎn)K到目標(biāo)狀態(tài)的預(yù)估代價。g(k)代表在整個狀態(tài)空間中，從起始狀態(tài)到狀態(tài)K的實(shí)際代價。h(k)代表狀態(tài)空間中從狀態(tài)K到目標(biāo)節(jié)點(diǎn)最佳路徑的預(yù)估代價。倉儲空間環(huán)境中所有通行的道路均為單行道路，在整個線路節(jié)點(diǎn)擴(kuò)展中，方向和順序是固定的。

圖3 節(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)是否會向P1和P3轉(zhuǎn)動，因此為了簡化算法，可以將以網(wǎng)格為單位的擴(kuò)展，轉(zhuǎn)化成以道路為單位的節(jié)點(diǎn)擴(kuò)展路徑。

圖4 沿道路擴(kuò)展節(jié)點(diǎn)

如圖4所示：沿縱向道路H1從節(jié)點(diǎn)M1開始擴(kuò)展，依次是M1、M2、M3。橫向道路是P1、P2、P3，以道路為節(jié)點(diǎn)的擴(kuò)展方式，減少擴(kuò)展次數(shù)，提高工作效率，節(jié)省時間。道路在倉儲空間中，不一定是路徑的起點(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)為道路時，則可擴(kuò)展所有道路交叉節(jié)點(diǎn)的所有道路。

圖5 貨物架子空間為節(jié)點(diǎn)

無論是道路節(jié)點(diǎn)或是貨架為節(jié)點(diǎn)，f(k)評價函數(shù)都需要根據(jù)實(shí)際情況作出調(diào)整，除了基本的曼哈頓路徑，還需要根據(jù)道路的方向與實(shí)際情況作出相應(yīng)的轉(zhuǎn)變。

3.4 A*算法中加入時序的路徑規(guī)劃

假設(shè)可以對每一個時刻的機(jī)器人的具體位置進(jìn)行監(jiān)控，就可以避免在路徑規(guī)劃過程中可能會發(fā)生的沖突。因此在算法中可以加入一個地圖，可以記錄每一個時刻機(jī)器人運(yùn)動的軌跡，并將機(jī)器人運(yùn)動軌跡記錄下來，形成一個三維地圖，地圖中包括運(yùn)行方向、運(yùn)行時間，地圖可以作為線路揀選的參考。在基于A*算法的基礎(chǔ)上，加入時間軌跡，可以將路徑代價替換為時間代價。同時需要充分考慮到運(yùn)動過程中涉及到的碰撞問題，將碰撞問題加入到時間代價中。因此在路徑規(guī)劃和揀選中，需要考慮延時問題，避免規(guī)劃出的路徑產(chǎn)生沖突問題。

倉儲道路具有一定的特殊性，其方向?yàn)閱蜗颉Ｒ?guī)劃的先后順序并不能保證運(yùn)行的有限順序。后規(guī)劃的路徑A插入到先規(guī)劃的任務(wù)B的前方，那么B只能選擇等待，這樣的問題出現(xiàn)就會導(dǎo)致實(shí)際規(guī)劃情況與原計(jì)劃不符。遇到這種情況，任務(wù)仍需要按照原規(guī)劃的路徑來完成?？赡茉跁r間上不能與原計(jì)劃保持一致。但如果繼續(xù)根據(jù)已經(jīng)發(fā)生偏差的路徑來完成任務(wù)，即使任務(wù)能夠完成，誤差則會積累的更多。因此一旦是按照非規(guī)劃的路徑來完成任務(wù)，則需要及時修改地圖，保證地圖與實(shí)際情況相符合。

3.5 機(jī)器人碰撞預(yù)防分析

倉儲機(jī)器人在運(yùn)動的過程中，發(fā)生碰撞的問題是不可避免的。如何有效地解決碰撞的問題，也是路徑揀選過程中需要注意的情況。避免可能發(fā)生的碰撞，需要設(shè)立獨(dú)占點(diǎn)。在特定的時刻，特定的位置，只能由一個機(jī)器人來完成工作。同一時刻進(jìn)入的工作機(jī)器人必須選擇等待。在實(shí)際工作的系統(tǒng)中，機(jī)器人都會通過傳感器來完成定位與導(dǎo)航的工作，在檢測到機(jī)器人之間的距離小于警戒值，要作出剎車指令，防止出現(xiàn)碰撞情況，影響工作效率，提高工作成本。

4 仿真實(shí)驗(yàn)驗(yàn)證與分析

通過有效的仿真實(shí)驗(yàn)可以驗(yàn)證選擇的路徑揀選算法是否有效，進(jìn)一步研究機(jī)器人數(shù)量、路徑、效率三種之間的關(guān)系。

4.1 任務(wù)設(shè)定和實(shí)驗(yàn)設(shè)定

必須保證仿真實(shí)驗(yàn)的真實(shí)性與客觀性，避免受到任務(wù)本身性質(zhì)的影響。采用隨機(jī)的算法來布置任務(wù)，貨架與機(jī)器人的位置與數(shù)量都是隨機(jī)產(chǎn)生。任務(wù)的編號與入貨口、出貨口符合要求，隨機(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)。

4.2 實(shí)驗(yàn)結(jié)果分析

在進(jìn)行200次的實(shí)驗(yàn)中，任務(wù)順利完成，驗(yàn)證了倉儲物流機(jī)器人路徑規(guī)劃的可行性與有效性。表1顯示，利用方差分析機(jī)器人數(shù)量、路徑規(guī)劃算法對物流任務(wù)的影響，其中包括里程、時間及碰撞沖突。機(jī)器人數(shù)量的配置對運(yùn)行的里程、時間及碰撞發(fā)生次數(shù)都有明顯的影響。而兩種路徑揀選算法在里程和時間上沒有明顯的差別，但在碰撞沖突方面的差別比較明顯。

表1 仿真實(shí)驗(yàn)結(jié)果

根據(jù)計(jì)算圖6總結(jié)了不同數(shù)量配置的機(jī)器人集群在兩種路徑規(guī)劃算法下的2000個任務(wù)所運(yùn)行總里程的10個實(shí)驗(yàn)平均值。通過呈現(xiàn)的數(shù)據(jù)可以看出，隨著機(jī)器人數(shù)量的不斷增加，機(jī)器人工作總里程也逐漸降低，而增加的機(jī)器人為系統(tǒng)提供了更靈活的工作方式，在工作中可以選擇貨架與目標(biāo)地、機(jī)器人距離比較接近的完成任務(wù)。

圖6 兩種算法路徑規(guī)劃對比分析

圖7 運(yùn)動中機(jī)器人數(shù)量與碰撞次數(shù)分析

通過圖6、圖7的分析可以很直觀的看出，兩種規(guī)劃方法的約束下，A*的算法的各項(xiàng)數(shù)值比較接近，加入時序路徑規(guī)劃算法，會降低工作中碰撞的次數(shù)。但如果是倉儲空間中，單行道路的設(shè)定，時序算法并不能完全避免碰撞問題的出現(xiàn)。

5 結(jié)束語

本文針對倉儲物流機(jī)器人在倉儲空間的路徑規(guī)劃問題進(jìn)行分析和研究，根據(jù)A*算法，建立一個靈活的倉儲空間，根據(jù)任務(wù)建立的特點(diǎn)，建立合適的任務(wù)流程和算法模型，根據(jù)A*的基本算法，有針對性地進(jìn)行修改算法，建立特殊規(guī)則的A*算法和時序的A*算法。這種方法能夠解決批量路徑揀選的問題，為機(jī)器人更好的工作，提供高效的技術(shù)支持。