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

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

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

　　0引言

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

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

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

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

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

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

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

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

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

　　1問題描述

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

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

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

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

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

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

　　3應用實例

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

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

　　4結(jié)束語

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

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

　　參考文獻：

　　[1]XUXiangin,MAZhongqiang.RoboticMobileFulfillmentSystems:StateofthertandProspects[J].ActaAutomaticaSinica,2020.(inChinese)[徐翔斌，馬中強.基于移動機器人的揀貨系統(tǒng)研究進展.自動化學報,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)載請注明來自發(fā)表學術(shù)論文網(wǎng)：http:///jjlw/28918.html