文｜北京科技大學(xué)機械工程學(xué)院 孫陽君、趙寧

在電子商務(wù)繁榮發(fā)展的今天，利用多機器人存取系統(tǒng)可以節(jié)約人力成本、提高揀選效率、提高存儲密度、降低碳排放，因此許多電商企業(yè)選擇布局多機器人存取系統(tǒng)，通過“機器換人”，實現(xiàn)“貨到人”揀選。隨著多機器人存取系統(tǒng)在企業(yè)內(nèi)的應(yīng)用發(fā)展，多機器人存取系統(tǒng)也成為近年來的熱點研究問題。本文重點介紹了多機器人存取系統(tǒng)中的熱點研究方向，總結(jié)了現(xiàn)有的解決方案，最后對未來研究進行了展望。

最早的移動機器人在1953年被美國basrrte公司開發(fā)成功，它能夠沿著布置在空中的導(dǎo)線完成任務(wù)，但不能自主隨意移動。自20世紀(jì)初，自尋址技術(shù)的出現(xiàn)對傳統(tǒng)的移動機器人實現(xiàn)了技術(shù)革命。自尋址技術(shù)可以不預(yù)先鋪設(shè)軌道，以非接觸的方式實現(xiàn)車輛的智能尋址和定位，大幅增加了移動機器人的智能程度和應(yīng)用范圍。隨著自尋址技術(shù)的發(fā)展，移動機器人可廣泛用于車間、碼頭、倉庫等系統(tǒng)中，系統(tǒng)內(nèi)的機器人數(shù)量也從幾臺擴展到上百臺。

2008 年，Kiva systems公司首次將上百輛互相協(xié)作的移動機器人同時用于亞馬遜的倉儲作業(yè)中[1]，即最早的多機器人存取系統(tǒng)。2012年，亞馬遜收購Kiva公司將多機器人存取系統(tǒng)部署在北美的各大配送中心內(nèi)。國內(nèi)也緊隨其后，菜鳥、京東、極智嘉和快倉等公司已經(jīng)成功應(yīng)用多機器人存取系統(tǒng)完成相關(guān)業(yè)務(wù)。

近年來，多機器人存取系統(tǒng)的銷量也在不斷增長?！?019年世界機器人報告》[2]顯示，僅2018年就賣出了超過十萬的多機器人系統(tǒng)，其中大多數(shù)都被用于電子商務(wù)倉庫中，為電商公司提供存取服務(wù)。2020年，COVID-19疫情進一步推動了多機器人存取系統(tǒng)的市場，《2020年世界機器人報告》[3]顯示，電商倉庫內(nèi)的移動機器人交易額增長了110％，達到19億美元。按預(yù)測，未來的交易額增長可能達到每年40％甚至更高。

種種跡象都表明，多機器人存取系統(tǒng)已經(jīng)成為應(yīng)用熱點，對多機器人存取系統(tǒng)的研究也日益增多。本文首先介紹了多機器人存取系統(tǒng)，描述了多個熱點研究方向和解決方案，最后對現(xiàn)有研究進行了總結(jié)和展望。

一、系統(tǒng)簡介

多機器人存取系統(tǒng)利用貨架存儲商品，通過移動機器人搬運貨架，工作人員只需要在工作站等待，不用進入存儲區(qū)域，工作完畢后移動機器人再將貨架搬運回存儲區(qū)域。這樣一來，就大大減少了工作人員的勞動強度，減少人員行走距離。如圖1所示，移動機器人依靠掃描地面的二維碼定位，根據(jù)指令向任意方向行駛。按照任務(wù)要求，執(zhí)行搬運、升降貨架、等待等操作。

圖1 多機器人存取系統(tǒng)

圖2 多機器人存取系統(tǒng)工作流程

在電子商務(wù)的訂單揀選中，系統(tǒng)的目的就是盡可能提升揀貨效率，更快更好地完成客戶的訂單。如圖2所示，系統(tǒng)的工作流程可以概況為：根據(jù)客戶下達的訂單，指派工作站完成訂單，按照訂單上的商品確定機器人需要執(zhí)行的任務(wù)，通過機器人搬運貨架至工作站完成揀選，再搬運貨架回儲區(qū)。在系統(tǒng)運行中，如果訂單需求的貨物量超過了安全庫存，還需要進行補貨操作。如果機器人的電量不足，需要充電，確定充電策略。除了工作流程中的策略和優(yōu)化方法外，還需要確定貨架和商品存放在哪些位置，并進行儲位優(yōu)化。此外，系統(tǒng)的布局模式、機器人的數(shù)量、揀貨站的數(shù)量、貨架的位置等都會對系統(tǒng)效率造成影響。因此，還需要對系統(tǒng)整體布局中的工作站位置、貨架位置、充電站位置等進行優(yōu)化。

二、研究方向

按照圖2系統(tǒng)的工作流程，可以對系統(tǒng)本身和系統(tǒng)內(nèi)的各個環(huán)節(jié)進行研究，主要包括以下研究方向：布局優(yōu)化、訂單指派、任務(wù)分配、路徑規(guī)劃、沖突消解、儲位優(yōu)化、充電策略、實時調(diào)度等。這些研究方向涉及到系統(tǒng)運行前的整體布局和系統(tǒng)運行中的各個流程。

1.布局優(yōu)化問題

圖3 多機器人存取系統(tǒng)俯視圖

一個普通的多機器人存取系統(tǒng)的俯視圖見圖3。布局優(yōu)化就是對系統(tǒng)內(nèi)的機器人、貨架、工作站等的位置、數(shù)量、比例等進行設(shè)計，確定最合適的布局，以提高揀貨效率，增加系統(tǒng)吞吐量，更快完成訂單。

對于系統(tǒng)的布局研究，包括以下幾種情況：

（1）工作站所處的位置和數(shù)量。圖3中工作站是在貨架的一側(cè)，但在布局中，可以兩側(cè)都擺放貨架，也可以四周都有工作站[4]。不同數(shù)量的工作站會對揀選效率有影響。

（2）貨架布局方式。a.貨架長寬比，貨架區(qū)域的設(shè)置影響車輛運行的路徑，可以通過建立排隊網(wǎng)模型計算不同長寬比對揀貨效率的影響[5]。b.布局模式。圖3展示的是傳統(tǒng)的布局模式，還有很多新型布局模式可以考慮，特殊的布局模式可以增加揀貨的效率或系統(tǒng)的存儲密度。例如圖4展示的V型布局[4]、魚骨型布局[6]、多深布局[7]等。

圖4 幾種新型布局模式

（3）倉庫內(nèi)道路布局。道路布局有很多需要考慮的地方。如a)道路方向。圖3展示的道路都有具體的方向，即單向道。通過單向道避免發(fā)生相向沖突和死鎖。除單向道外，道路也可以采用雙向道布局方式，機器人可以沿任意方向運行，能夠減少機器人的繞路，加快運行效率?？紤]到雙向道內(nèi)的相向沖突較為嚴(yán)重，也可以將兩者結(jié)合布局，部分區(qū)域采用單向道，部分區(qū)域采用雙向道[8]。b）車道數(shù)量，圖3中，只有在工作站和存儲區(qū)域的道路是雙行道，存儲區(qū)域都是單行道，即只能容納一輛車通過。雙行道可以更大程度上避免機器人的沖突，但浪費了存儲面積。c）是否有交叉口。交叉口同樣降低了存儲密度，但機器人移動時可選擇的路徑比無交叉口時更多，能夠避免機器人間的擁堵。單向單行道和雙向單行道、有交叉口和無交叉口的對比可以參考Lienert等[9]的研究。

2.訂單指派問題

訂單是多機器人存取系統(tǒng)的輸入，完成訂單是系統(tǒng)運行的首要目的。單張訂單每件商品按順序揀選的完成方式會大大降低系統(tǒng)效率，不同訂單有同一件商品時，完全可以一同揀選，即使沒有一樣的商品，兩張訂單需要揀選的商品也可能位于同一個貨架上。因此，就需要對訂單進行整合和指派，確立訂單內(nèi)商品在哪些貨架上，哪些訂單可以在同一個工作站內(nèi)揀選[10-11]。優(yōu)化訂單的順序還能減少機器人的數(shù)量，降低系統(tǒng)運行成本[12]。為了提高系統(tǒng)效率，訂單內(nèi)的貨物甚至可以被拆分到不同的工作站完成[13]。

3.任務(wù)分配問題

任務(wù)分配是在訂單指派后，將訂單拆分成涉及到具體貨架的任務(wù)，將任務(wù)分配給機器人進行執(zhí)行。系統(tǒng)內(nèi)同時有多個任務(wù)和多輛機器人，一輛機器人在同一時間只能搬運一個貨架，任務(wù)分配情況關(guān)系到機器人未來的行動路線。在任務(wù)分配時，需要綜合考慮機器人和任務(wù)要求的貨架之間的距離，機器人本身的任務(wù)情況，任務(wù)間的關(guān)系等多個因素?，F(xiàn)有的研究中，任務(wù)分配可以是采用一些策略進行分配，如基于作業(yè)速率、近似最優(yōu)和最優(yōu)指派策略等被用于任務(wù)分配[14]。還可以根據(jù)當(dāng)前系統(tǒng)內(nèi)任務(wù)的距離、時間、效率等狀態(tài)，設(shè)計啟發(fā)式規(guī)則完成任務(wù)分配[10]。此外，可以利用智能算法通過迭代優(yōu)化的方式獲得更好的任務(wù)分配結(jié)果，如遺傳算法[15]，模擬退火算法[16]，禁忌搜索[17]等。

4.路徑規(guī)劃問題

圖5 機器人的不同路徑

機器人接取任務(wù)之后，就需要執(zhí)行任務(wù)，按照任務(wù)要求對運行路徑進行規(guī)劃。機器人的運行路徑規(guī)劃是多機器人存取系統(tǒng)的核心。好的路徑規(guī)劃方案能夠大幅度提升系統(tǒng)效率，減少機器人的能耗。如圖5(a)所示，機器人完成任務(wù)需要三段路徑，首先要從當(dāng)前位置到貨架所在位置，再從貨架所在位置到工作站，之后帶著貨架返回儲區(qū)。這期間，機器人由無數(shù)條路徑可以完成任務(wù)，例如圖5(a)是最短路徑，但也可選擇圖5(b)的其他路徑，但最終完成任務(wù)的路徑受到多方面影響。由于倉庫內(nèi)不只一輛機器人，多輛機器人之間會造成沖突問題。最短路徑可能有其他機器人頻繁經(jīng)過，產(chǎn)生嚴(yán)重的沖突問題。因此機器人運行的最短路徑并非就是最好的，還需要綜合考慮其他機器人的情況。常用的路徑生成方法包括動作依賴圖[18]、路線圖生成算法[19]、A*算法[20]、Dijkstra's 算法[17]等以及對這些算法的改進。

5.沖突消解問題

圖6 機器人間的沖突情況

多輛機器人運行時，由于運行路線有交錯，必然會發(fā)生沖突。機器人間的沖突可以被歸為以下幾類：趕超沖突、交叉口沖突、相向沖突，如圖6所示。針對這些沖突，有多種啟發(fā)式規(guī)則可以采用，如設(shè)立優(yōu)先級進行避讓[21]，任務(wù)少的機器人等待[22]，或是采取多種方式比如離開、繞路和啟動前等待以避開不同沖突[20]，利用通道協(xié)議避免一條通道內(nèi)的機器人沖突[23]等。

6.儲位優(yōu)化問題

貨架的存儲位置決定了機器人將其搬運至工作站時行走的距離，貨架離工作站越近，搬運耗費的時間越少，系統(tǒng)的效率越高。但是，如果貨架都在工作站附近，機器人搬運時也聚集在工作站附近，反而會造成工作站附近的擁堵。因此，儲位優(yōu)化也成為研究的熱點問題之一。對貨架存儲位置設(shè)置不同的策略，對實際運行時的影響不同[24]?，F(xiàn)有研究中，采取的策略包括：

（1）固定位置存儲。貨架固定在某一確定位置存儲；

（2）隨機存儲。貨架從工作站離開時，隨機選擇空位存放；

（3）最近存儲。貨架從工作站離開時，選擇離工作站最近的空位存放；

（4）分區(qū)存儲[5]。按照貨架上貨物被揀選的頻率，對儲區(qū)進行分區(qū)，高頻區(qū)靠近工作站，低頻區(qū)遠離工作站，貨架按照區(qū)域存儲，在區(qū)域內(nèi)部也可有“固定位”、“隨機”、“最近”等存儲策略。

7.充電策略問題

機器人雖然不用像人類一樣需要休息，但機器人的運行需要依靠電能，圖3右下角就是機器人的充電區(qū)。機器人的充電策略涉及到以下兩部分：

（1）充電時機，即機器人還有多少電量時需要充電[25]。如果充電時機選擇的過晚，就會出現(xiàn)有機器人因為電量耗盡而停留在儲區(qū)或工作區(qū)內(nèi)的情況，會直接影響任務(wù)的完成和其他機器人的運行。過早的充電雖然可以避免機器人沒電停止，但機器人頻繁的充電影響系統(tǒng)效率，同時也影響電池壽命，而且充電區(qū)的容量也是有限的，頻繁充電可能導(dǎo)致充電區(qū)發(fā)生堵塞。

（2）充電模式。機器人可以選擇在充電區(qū)充電，也可以直接換電池?，F(xiàn)有研究的實驗表明，換電池比充電更能提升系統(tǒng)性能[26]。

8.實時調(diào)度問題

實時調(diào)度是在系統(tǒng)實際運行時進行調(diào)度，對調(diào)度的時效性要求較高。因此，多采用一些規(guī)則處理系統(tǒng)運行中遇到的各種問題，如利用分配任務(wù)極為快速的令牌傳遞算法[27]；通過得到的當(dāng)前機器人的狀態(tài)，進行動態(tài)路徑規(guī)劃，避免機器人間的沖突[7,28]；實時調(diào)整機器人的優(yōu)先級以協(xié)調(diào)沖突[29]。還有一些和系統(tǒng)輸入相關(guān)的問題，例如緊急訂單的出現(xiàn)，緊急訂單優(yōu)于其他訂單進行指派，優(yōu)于其他任務(wù)被分配給機器人完成[30]。此外，在實際運行中還會出現(xiàn)機器人故障、貨物跌落等突發(fā)事件。

三、總結(jié)和展望

多機器人存取系統(tǒng)具有更高的揀貨效率、更好的系統(tǒng)可擴展性和柔性，因此成為近年來備受關(guān)注的研究領(lǐng)域之一。本文描述了多機器人存取系統(tǒng)中的布局優(yōu)化、訂單指派、任務(wù)分配、路徑規(guī)劃、沖突消解、儲位優(yōu)化、充電策略、實時調(diào)度等問題。除此之外，還有多個方面有待關(guān)注。

1.協(xié)同優(yōu)化

現(xiàn)有的倉庫規(guī)模不斷擴大，機器人數(shù)量逐漸增多，系統(tǒng)運行流程復(fù)雜，問題之間聯(lián)系緊密，單個機器人的最佳路線、單個問題的最優(yōu)策略在系統(tǒng)全局運行時并非最優(yōu)。因此，需要進行協(xié)同優(yōu)化，找到系統(tǒng)運行時最合適的策略組合，確定同時考慮多輛機器人多個問題的優(yōu)化方法，共同提升系統(tǒng)效率。

2.數(shù)字孿生系統(tǒng)

數(shù)字孿生是近年來的熱點方向，數(shù)字孿生可以將虛擬系統(tǒng)和現(xiàn)實系統(tǒng)結(jié)合起來，利用虛擬系統(tǒng)模擬物理系統(tǒng)運行。多機器人存取系統(tǒng)內(nèi)人類活動少，機器人行為可以預(yù)測，進而實現(xiàn)對整個系統(tǒng)運行情況的預(yù)測。通過對物理系統(tǒng)狀態(tài)的預(yù)測，可以提前處理未來可能發(fā)生的問題，從而指導(dǎo)物理系統(tǒng)運行。

3.機器學(xué)習(xí)

多機器人存取系統(tǒng)本身是一個復(fù)雜系統(tǒng)，系統(tǒng)內(nèi)的問題很多。機器學(xué)習(xí)和人工智能的發(fā)展為系統(tǒng)運行提供了新思路。通過對大量經(jīng)驗數(shù)據(jù)的學(xué)習(xí)，將復(fù)雜問題簡單化，快速做出決策，將是未來研究的新方向。