多機器人存取系統動態調度方法

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

　　關鍵詞：多機器人存取系統;動態調度;實時調度;重調度規則

　　0引言

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

　　機器人論文范例： 人工智能、物聯網、機器人技術對安全和責任框架的影響

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

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

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

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

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

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

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

　　1問題描述

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

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

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

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

　　2動態調度方法

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

　　3應用實例

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

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

　　4結束語

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

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

　　參考文獻：

　　[1]XUXiangin,MAZhongqiang.RoboticMobileFulfillmentSystems:StateofthertandProspects[J].ActaAutomaticaSinica,2020.(inChinese)[徐翔斌，馬中強.基于移動機器人的揀貨系統研究進展.自動化學報,2020.

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

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

　　作者：孫陽君，趙寧

轉載請注明來自發表學術論文網：http://www.zpfmc.com/jjlw/28918.html