文 / 孫陽君 趙 寧

北京科技大學機械工程學院

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

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

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

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

一、系統(tǒng)簡介

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

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

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

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

二、研究方向

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

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

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

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

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

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

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

圖4 幾種新型布局模式

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

2.訂單指派問題

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

3.任務分配問題

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

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

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

圖5 機器人的不同路徑

5.沖突消解問題

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

圖6 機器人間的沖突情況

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

貨架的存儲位置決定了機器人將其搬運至工作站時行走的距離，貨架離工作站越近，搬運耗費的時間越少，系統(tǒng)的效率越高。但是，如果貨架都在工作站附近，機器人搬運時也聚集在工作站附近，反而會造成工作站附近的擁堵。因此，儲位優(yōu)化也成為研究的熱點問題之一。對貨架存儲位置設置不同的策略，對實際運行時的影響不同[24]?，F(xiàn)有研究中，采取的策略包括： （1）固定位置存儲。貨架固定在某一確定位置存儲；（2）隨機存儲。貨架從工作站離開時，隨機選擇空位存放；（3）最近存儲。貨架從工作站離開時，選擇離工作站最近的空位存放；（4）分區(qū)存儲[5]。按照貨架上貨物被揀選的頻率，對儲區(qū)進行分區(qū)，高頻區(qū)靠近工作站，低頻區(qū)遠離工作站，貨架按照區(qū)域存儲，在區(qū)域內部也可有“固定位”、“隨機”、“最近”等存儲策略。

7.充電策略問題

機器人雖然不用像人類一樣需要休息，但機器人的運行需要依靠電能，圖3右下角就是機器人的充電區(qū)。機器人的充電策略涉及到以下兩部分：（1）充電時機，即機器人還有多少電量時需要充電[25]。如果充電時機選擇的過晚，就會出現(xiàn)有機器人因為電量耗盡而停留在儲區(qū)或工作區(qū)內的情況，會直接影響任務的完成和其他機器人的運行。過早的充電雖然可以避免機器人沒電停止，但機器人頻繁的充電影響系統(tǒng)效率，同時也影響電池壽命，而且充電區(qū)的容量也是有限的，頻繁充電可能導致充電區(qū)發(fā)生堵塞。（2）充電模式。機器人可以選擇在充電區(qū)充電，也可以直接換電池?，F(xiàn)有研究的實驗表明，換電池比充電更能提升系統(tǒng)性能[26]。

8.實時調度問題

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

三、總結和展望

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

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

現(xiàn)有的倉庫規(guī)模不斷擴大，機器人數(shù)量逐漸增多，系統(tǒng)運行流程復雜，問題之間聯(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)結合起來，利用虛擬系統(tǒng)模擬物理系統(tǒng)運行。多機器人存取系統(tǒng)內人類活動少，機器人行為可以預測，進而實現(xiàn)對整個系統(tǒng)運行情況的預測。通過對物理系統(tǒng)狀態(tài)的預測，可以提前處理未來可能發(fā)生的問題，從而指導物理系統(tǒng)運行。

3.機器學習

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