多機(jī)器人存取系統(tǒng)研究現(xiàn)狀

文 / 孫陽君 趙 寧

北京科技大學(xué)機(jī)械工程學(xué)院

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

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

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

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

一、系統(tǒng)簡介

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

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

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

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

二、研究方向

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

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

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

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

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

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

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

圖4 幾種新型布局模式

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

2.訂單指派問題

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

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

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

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

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

圖5 機(jī)器人的不同路徑

5.沖突消解問題

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

圖6 機(jī)器人間的沖突情況

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

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

7.充電策略問題

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

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

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

三、總結(jié)和展望

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

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

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

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

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

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

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