多機(jī)器人存取系統(tǒng)動(dòng)態(tài)調(diào)度方法

　　摘要：針對(duì)多機(jī)器人存取系統(tǒng)實(shí)時(shí)性要求高，動(dòng)態(tài)事件發(fā)生時(shí)易偏離調(diào)度計(jì)劃的難題，提出一種動(dòng)態(tài)調(diào)度方法解決此問題。對(duì)系統(tǒng)內(nèi)發(fā)生的動(dòng)態(tài)事件進(jìn)行分析，確定不同動(dòng)態(tài)事件造成的后果和對(duì)調(diào)度的影響。建立以完成時(shí)間最小為目標(biāo)的動(dòng)態(tài)調(diào)度模型。提出動(dòng)態(tài)調(diào)度方法實(shí)現(xiàn)系統(tǒng)內(nèi)的實(shí)時(shí)訂單到達(dá)情況下的預(yù)調(diào)度和動(dòng)態(tài)事件發(fā)生后的重調(diào)度。根據(jù)動(dòng)態(tài)事件的不同影響，確立動(dòng)態(tài)事件發(fā)生時(shí)的重調(diào)度規(guī)則。通過實(shí)例證實(shí)，相比現(xiàn)有調(diào)度方法所提出的動(dòng)態(tài)調(diào)度方法能夠及時(shí)響應(yīng)緊急訂單到達(dá)和機(jī)器人故障等動(dòng)態(tài)事件的發(fā)生，獲得完成時(shí)間更小且路徑長(zhǎng)度更短的調(diào)度方案。選擇在故障時(shí)間后對(duì)受影響機(jī)器人重調(diào)度對(duì)重調(diào)度結(jié)果的影響更小。

　　關(guān)鍵詞：多機(jī)器人存取系統(tǒng);動(dòng)態(tài)調(diào)度;實(shí)時(shí)調(diào)度;重調(diào)度規(guī)則

　　0引言

　　多機(jī)器人存取系統(tǒng)(roboticmobilefulfillmentsystem，RMFS)能夠利用貨架存儲(chǔ)商品，通過自尋址機(jī)器人車(autonomousvehicle，AV)搬運(yùn)貨架至工作站，工作人員無需進(jìn)入儲(chǔ)區(qū)，在工作站內(nèi)進(jìn)行各種操作即可，完成操作后再將貨架搬運(yùn)回儲(chǔ)區(qū)。相比傳統(tǒng)揀貨系統(tǒng)，RMFS具有更高的揀貨效率、更好的系統(tǒng)可擴(kuò)展性和柔性[1]。自2008年Kivasystems公司將其用于亞馬遜的倉(cāng)儲(chǔ)作業(yè)以來[2]，MFS系統(tǒng)被廣泛用于各大電商企業(yè)。

　　機(jī)器人論文范例： 人工智能、物聯(lián)網(wǎng)、機(jī)器人技術(shù)對(duì)安全和責(zé)任框架的影響

　　中間的存儲(chǔ)區(qū)域擺放貨架，兩邊為工作站，承擔(dān)揀貨或補(bǔ)貨任務(wù)。為了避免MFS系統(tǒng)內(nèi)的AV相向沖突和死鎖，大部分系統(tǒng)內(nèi)的道路都是和圖類似的單向道。空載按照道路方向運(yùn)行，并可以在貨架下穿行，負(fù)載只能按照道路方向運(yùn)行。很多學(xué)者都針對(duì)MFS系統(tǒng)內(nèi)的調(diào)度和優(yōu)化問題展開研究，包括訂單指派問題、任務(wù)分配問題、路徑規(guī)劃問題7]、無沖突調(diào)度問題[89]、儲(chǔ)位優(yōu)化問題10等，或是多種問題的結(jié)合問題1113。

　　但這些研究多是針對(duì)靜態(tài)MFS系統(tǒng)，而電商企業(yè)中的訂單是實(shí)時(shí)到達(dá)并要求立即響應(yīng)的，對(duì)系統(tǒng)的實(shí)時(shí)性要求高。 針對(duì)實(shí)時(shí)RMFS系統(tǒng)，大部分研究都集中于任務(wù)分配、路徑規(guī)劃和無沖突調(diào)度等問題。Ma等(2017)[14]將AV路徑規(guī)劃問題建模為以最小任務(wù)完成時(shí)間為目標(biāo)的多代理路徑尋找問題，開發(fā)了令牌傳遞算法和帶有任務(wù)交換的令牌傳遞算法，實(shí)驗(yàn)驗(yàn)證了算法規(guī)劃任務(wù)的能力能否用于實(shí)時(shí)調(diào)度系統(tǒng)中。Yoshitake等(2019)[15]以揀貨人員空閑時(shí)間為目標(biāo)，建立一種實(shí)時(shí)整體調(diào)度方法，AV同時(shí)搬運(yùn)RMFS系統(tǒng)中的貨架和工作站中的揀貨架。

　　Lee(2019)[16]在RMFS系統(tǒng)中驗(yàn)證了動(dòng)態(tài)無沖突調(diào)度策略，采用改進(jìn)A*算法根據(jù)對(duì)實(shí)時(shí)數(shù)據(jù)進(jìn)行處理得到的當(dāng)前狀態(tài)規(guī)劃路徑，利用離開、繞路和啟動(dòng)前等待三種方式避開間的持續(xù)沖突、對(duì)頭沖突和交叉口沖突。Keung等(2020)[17]在Lee研究的基礎(chǔ)上，對(duì)多層多深度倉(cāng)庫(kù)布局中的六種沖突進(jìn)行處理，實(shí)現(xiàn)實(shí)時(shí)調(diào)度。Guney和Raptis(2020)[18]開發(fā)了一個(gè)基于優(yōu)先級(jí)的車輛運(yùn)動(dòng)協(xié)調(diào)算法解決單向網(wǎng)絡(luò)MFS中的沖突問題，在實(shí)時(shí)調(diào)度中獲得了魯棒性更強(qiáng)的調(diào)度結(jié)果。這些研究的多采用啟發(fā)式規(guī)則和智能算法實(shí)現(xiàn)任務(wù)分配，利用動(dòng)態(tài)路徑規(guī)劃算法規(guī)劃AV的路徑，通過啟發(fā)式規(guī)則規(guī)避動(dòng)態(tài)運(yùn)行時(shí)AV間的沖突，調(diào)度結(jié)果表現(xiàn)很好。

　　系統(tǒng)布局也不再局限于單向道，能夠較好的在實(shí)時(shí)環(huán)境中解決之間的沖突問題。但在實(shí)際運(yùn)行時(shí)，除了實(shí)時(shí)到達(dá)的訂單外，MFS系統(tǒng)內(nèi)常會(huì)出現(xiàn)很多動(dòng)態(tài)不確定事件，導(dǎo)致AV調(diào)度計(jì)劃與實(shí)際運(yùn)行難以完全符合，甚至偏差過大導(dǎo)致系統(tǒng)停擺。因此，對(duì)MFS系統(tǒng)內(nèi)的動(dòng)態(tài)事件分析并及時(shí)處理就成為研究的關(guān)鍵。這些動(dòng)態(tài)事件包括緊急訂單到達(dá)、AV故障、路塊不可用等。

　　部分學(xué)者對(duì)MFS系統(tǒng)內(nèi)的動(dòng)態(tài)事件加以研究，例如Gong等(2020)[19]建立了多機(jī)器人存取系統(tǒng)的高維馬爾可夫模型，考慮到加急訂單的實(shí)時(shí)到達(dá)，實(shí)驗(yàn)了機(jī)器人速度、機(jī)器人數(shù)量和揀選站數(shù)量對(duì)系統(tǒng)吞吐量的影響。但是由于MFS系統(tǒng)對(duì)實(shí)時(shí)性要求高，動(dòng)態(tài)事件發(fā)生時(shí)系統(tǒng)情況復(fù)雜，加劇了系統(tǒng)內(nèi)的沖突。因此現(xiàn)有的研究對(duì)動(dòng)態(tài)事件的考慮不足，很少考慮到AV故障、路塊不可用等事件以及對(duì)這類事件的處理。在其他類似的調(diào)度系統(tǒng)中，針對(duì)這類動(dòng)態(tài)事件的處理方式可以被分為完全反應(yīng)式調(diào)度、預(yù)反應(yīng)式調(diào)度、預(yù)反應(yīng)式魯棒調(diào)度和主動(dòng)魯棒調(diào)度[2。其中，預(yù)反應(yīng)式調(diào)度是最常用的調(diào)度方法。

　　預(yù)反應(yīng)式調(diào)度方法是首先生成一個(gè)預(yù)調(diào)度方案，發(fā)生動(dòng)態(tài)事件時(shí)再觸發(fā)重調(diào)度�，F(xiàn)已經(jīng)被用于作業(yè)車間[2、混合流水車間[2、車輛路徑問題[2等動(dòng)態(tài)調(diào)度問題中，且取得了良好表現(xiàn)，保證動(dòng)態(tài)事件發(fā)生后能夠及時(shí)調(diào)整調(diào)度計(jì)劃，得到新的調(diào)度方案。預(yù)反應(yīng)式調(diào)度方法分為預(yù)調(diào)度和重調(diào)度兩個(gè)部分。預(yù)調(diào)度的方式和靜態(tài)調(diào)度類似，重調(diào)度方式包括右移重調(diào)度、部分重調(diào)度和完全重調(diào)度等25]。在MFS實(shí)際應(yīng)用時(shí)，也多是通過類似的方法確保調(diào)度計(jì)劃順利進(jìn)行，即先確定調(diào)度計(jì)劃，在運(yùn)行中根據(jù)實(shí)際情況動(dòng)態(tài)調(diào)整。

　　但是由于動(dòng)態(tài)事件造成的后果復(fù)雜，受影響的和路塊又會(huì)發(fā)生連鎖反應(yīng)，造成連環(huán)沖突和死鎖。工業(yè)界應(yīng)用時(shí)只能用簡(jiǎn)單的啟發(fā)式規(guī)則處理動(dòng)態(tài)事件發(fā)生后的重調(diào)度問題，其所用規(guī)則的有效性待驗(yàn)證。如AV故障后，其他受影響的只有在即將進(jìn)入故障路塊時(shí)才能確定當(dāng)前路塊被占用，再進(jìn)行重調(diào)度選擇其他路線，由于重調(diào)度反應(yīng)時(shí)間長(zhǎng)，可能會(huì)造成死鎖現(xiàn)象。本文針對(duì)實(shí)時(shí)MFS系統(tǒng)建立了多機(jī)器人存取系統(tǒng)動(dòng)態(tài)調(diào)度方法，提出動(dòng)態(tài)調(diào)度算法進(jìn)行實(shí)時(shí)到達(dá)訂單的任務(wù)分配、路徑選擇和無沖突調(diào)度以生成預(yù)調(diào)度方案，再根據(jù)系統(tǒng)內(nèi)出現(xiàn)的各類動(dòng)態(tài)事件，通過分析動(dòng)態(tài)事件的后果，確定不同事件的處理方式，確立重調(diào)度規(guī)則，最后通過實(shí)例驗(yàn)證動(dòng)態(tài)調(diào)度方法的有效性。

　　1問題描述

　　MFS的調(diào)度首先需要根據(jù)系統(tǒng)實(shí)時(shí)輸入的訂單，將一段時(shí)間的訂單到達(dá)后統(tǒng)一拆分成任務(wù)。即訂單是實(shí)時(shí)到達(dá)的，但待分配的任務(wù)是周期性到達(dá)的。之后，為每個(gè)可接取任務(wù)的確定當(dāng)前情況下要執(zhí)行的任務(wù)，完成任務(wù)分配。

　　再為接取任務(wù)的確定途徑的各個(gè)路塊，完成路徑規(guī)劃。最后，為確定各路塊的進(jìn)入時(shí)間和離開時(shí)間，保證多輛AV間運(yùn)行時(shí)互不干擾，完成無沖突調(diào)度。調(diào)度的目的是先確定到達(dá)的任務(wù)，哪些接取哪些任務(wù)，如何完成這些任務(wù)，保證完成任務(wù)時(shí)不產(chǎn)生碰撞和死鎖現(xiàn)象。

　　當(dāng)出現(xiàn)動(dòng)態(tài)事件時(shí)，需要根據(jù)調(diào)度計(jì)劃和當(dāng)前的動(dòng)態(tài)事件，進(jìn)行重調(diào)度，以保證任務(wù)順利完成，繼而完成所有訂單。在調(diào)度中，路徑規(guī)劃部分的路徑和接取的任務(wù)相關(guān)。AV接取任務(wù)后，分三個(gè)階段完成任務(wù)：從當(dāng)前路塊到貨架所在路塊;從貨架路塊到工作站;從工作站返回儲(chǔ)區(qū)。

　　完成任務(wù)需要對(duì)這三個(gè)階段的路徑進(jìn)行規(guī)劃。由于任務(wù)的貨架所在路塊和工作站不會(huì)變動(dòng)，即無論哪個(gè)接取任務(wù)都需要經(jīng)過這兩段路徑，那么這兩段路徑規(guī)劃可以提前規(guī)劃，即在任務(wù)到達(dá)后分配前規(guī)劃。為了增加計(jì)劃的柔性，在這兩個(gè)階段的路徑規(guī)劃時(shí)不只規(guī)劃單條路徑，而是規(guī)劃出路徑集。在后續(xù)調(diào)度中，對(duì)任務(wù)的第二階段和第三階段的路徑只在路徑集內(nèi)進(jìn)行路徑選擇。通過提前規(guī)劃路徑集，減少不必要的路徑規(guī)劃時(shí)間，以增加調(diào)度的效率。此外，還能在系統(tǒng)中單個(gè)或幾個(gè)路塊無法通行時(shí)，為提供備選路徑。調(diào)度中的路徑規(guī)劃只包括在接取任務(wù)之后從當(dāng)前路塊到貨架所在路塊這一段的路徑。大大減少了實(shí)時(shí)調(diào)度中所需的時(shí)間。

　　2動(dòng)態(tài)調(diào)度方法

　　動(dòng)態(tài)調(diào)度方法包括預(yù)調(diào)度和重調(diào)度兩部分。預(yù)調(diào)度不考慮動(dòng)態(tài)事件，主要包括任務(wù)分配、路徑規(guī)劃和無沖突調(diào)度三部分;只有在動(dòng)態(tài)事件如故障發(fā)生時(shí)才進(jìn)行重調(diào)度，重調(diào)度時(shí)需要分析故障情況，選取合適的重調(diào)度規(guī)則，最后得到新的調(diào)度方案。動(dòng)態(tài)調(diào)度方法流程如圖所示。初始輸入包括初始任務(wù)數(shù)據(jù)、AV數(shù)據(jù)，實(shí)時(shí)輸入包括新到達(dá)任務(wù)數(shù)據(jù)、離開工作站時(shí)間、任務(wù)完成時(shí)間、產(chǎn)生異常時(shí)間和異常情況。實(shí)時(shí)輸出的是當(dāng)前時(shí)間調(diào)度方案。如果有緊急訂單到達(dá)，緊急訂單到達(dá)后立刻確定緊急任務(wù)的各項(xiàng)信息�？紤]到調(diào)度方案的穩(wěn)定性，在調(diào)度中將緊急任務(wù)的優(yōu)先級(jí)提高，在新一輪任務(wù)分配時(shí)和其他任務(wù)一起調(diào)度。

　　3應(yīng)用實(shí)例

　　實(shí)驗(yàn)在IntelCorei75557、3.10GHzCPU、4.00GRAM、64位Windows10操作系統(tǒng)和Matlab2016a編程環(huán)境下編譯運(yùn)行。運(yùn)行參數(shù)包括：st=0.5，turn=2.5，across=0.5，lr=3。每次禁忌搜索參數(shù)包括：種群數(shù)量，代數(shù)50。Merschformann等人設(shè)計(jì)了圖所示的系統(tǒng)布局，通過單行道的方式避免系統(tǒng)內(nèi)的相向沖突，但也造成了不必要的繞路。本文的數(shù)學(xué)模型可以用于任何道路方向，能夠處理間的相向沖突，因此在存儲(chǔ)區(qū)內(nèi)道路可以任意通行。對(duì)圖的布局修改后，本文RMFS系統(tǒng)布局和道路方向如圖所示，箭頭表示道路方向，為工作站。

　　布局圖中間的存儲(chǔ)區(qū)域全部為雙向道，空載可以無障礙的穿行，負(fù)載在過道中運(yùn)行。為了避免在工作站內(nèi)的死鎖，左右兩側(cè)工作站道路仍為單向道。輛AV同時(shí)在系統(tǒng)內(nèi)運(yùn)行，隨機(jī)給定初始位置，將一定時(shí)間內(nèi)的訂單拆分成任務(wù)，按照一定時(shí)間間隔作為任務(wù)輸入系統(tǒng)。任務(wù)分波到達(dá)，隨機(jī)生成貨架點(diǎn)和工作站，一共包括50個(gè)任務(wù)數(shù)據(jù)。

　　4結(jié)束語

　　針對(duì)多機(jī)器人存取系統(tǒng)中存在的訂單實(shí)時(shí)到達(dá)、緊急訂單到達(dá)、AV故障等問題，建立一種動(dòng)態(tài)調(diào)度方法。首先分析系統(tǒng)內(nèi)的不同動(dòng)態(tài)事件并確定其對(duì)調(diào)度的影響，提出以最小完成時(shí)間為目標(biāo)的多機(jī)器人存取系統(tǒng)動(dòng)態(tài)調(diào)度模型。建立實(shí)時(shí)系統(tǒng)的動(dòng)態(tài)調(diào)度方法，利用動(dòng)態(tài)調(diào)度算法實(shí)現(xiàn)系統(tǒng)內(nèi)的預(yù)調(diào)度和重調(diào)度。通過禁忌搜索、改進(jìn)A*算法和無沖突調(diào)度方法解決任務(wù)分配、路徑規(guī)劃和無沖突調(diào)度問題。根據(jù)動(dòng)態(tài)事件的不同影響，確立重調(diào)度規(guī)則。實(shí)例證明動(dòng)態(tài)調(diào)度方法能夠解決訂單實(shí)時(shí)到達(dá)即任務(wù)分波次到達(dá)的情況下的AV調(diào)度問題，保證系統(tǒng)內(nèi)的AV順利完成所有任務(wù)，且多輛AV運(yùn)行時(shí)無沖突死鎖現(xiàn)象。

　　相比傳統(tǒng)方法，動(dòng)態(tài)調(diào)度方法獲得的調(diào)度方案完成時(shí)間更小，調(diào)度時(shí)間更短，緊急訂單到達(dá)時(shí)能夠確保緊急訂單優(yōu)先完成。當(dāng)出現(xiàn)AV故障時(shí)，能夠順利完成重調(diào)度并保證當(dāng)前任務(wù)受到的影響最小。對(duì)比不同故障時(shí)間重調(diào)度的觸發(fā)時(shí)機(jī)，相比傳統(tǒng)方法中在故障路塊前重調(diào)度，在故障時(shí)間后重調(diào)度任務(wù)的當(dāng)前階段完成時(shí)間更小，重調(diào)度路徑長(zhǎng)度更短，甚至能夠獲得比重調(diào)度前完成時(shí)間更短的調(diào)度方案。通過對(duì)比證實(shí)如果故障時(shí)有受影響，對(duì)調(diào)度的影響最大。本文目前的研究還集中于緊急訂單到達(dá)和AV故障兩種動(dòng)態(tài)事件中，缺少對(duì)人員相關(guān)的動(dòng)態(tài)事件的預(yù)測(cè)和重調(diào)度規(guī)則的研究，下一步將結(jié)合數(shù)字孿生技術(shù)針對(duì)人員暫停工作、人員突然進(jìn)入系統(tǒng)內(nèi)等事件進(jìn)行預(yù)測(cè)并研究相關(guān)重調(diào)度規(guī)則。

　　參考文獻(xiàn)：

　　[1]XUXiangin,MAZhongqiang.RoboticMobileFulfillmentSystems:StateofthertandProspects[J].ActaAutomaticaSinica,2020.(inChinese)[徐翔斌，馬中強(qiáng).基于移動(dòng)機(jī)器人的揀貨系統(tǒng)研究進(jìn)展.自動(dòng)化學(xué)報(bào),2020.

　　[2]WURMANPR,D’ANDREAR,MOUNTZM.Coordinatinghundredsofcooperative,autonomousvehiclesinwarehouse[J].AIMagazine,2008,29(1):919.

　　ERSCHFORMANNM,LAMBALLAIST,KOSTERMBM,etal.Decisionrulesforroboticmobilefulfillmentsystems[J].OperationsResearchPerspectives,2019,6:115.

　　作者：孫陽君，趙寧

轉(zhuǎn)載請(qǐng)注明來自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///jjlw/28918.html