亞馬遜無人倉和KIVA搬運自動機器人的出現(xiàn)掀起了倉庫AGV調(diào)度研究及應用的熱潮。先進的搬運機器人智能調(diào)度算法是無人倉系統(tǒng)高效落地應用的關鍵，市場需求極大。本文作者基于多年的專業(yè)研究提供了倉庫搬運機器人調(diào)度優(yōu)化與仿真的相關建議以供行業(yè)參考。

一、倉庫搬運機器人與無人倉系統(tǒng)

在現(xiàn)代自動化倉庫中，各種類型和功能的機器人已逐漸開始普及應用，例如自動導引運輸車（Automated Guided Vehicle，簡稱AGV）、碼垛機器人、揀選機器人、包裝機器人等。AGV是指配備電磁、光學或計算機視覺等自動導航裝置，能夠按一定的路線或者規(guī)則行駛，且具有安全保護以及各種移載功能的運輸車，屬于輪式移動機器人（Wheeled Mobile Robot，簡稱WMR）的范疇，AGV可通過充電獲得其動力來源，通?？赏ㄟ^電腦來控制其行駛路線及其他行為。

亞馬遜成功研發(fā)和應用KIVA機器人系統(tǒng)掀起了倉庫AGV調(diào)度研究及應用的熱潮。而國內(nèi)多家電商企業(yè)和科技公司在無人倉和AGV調(diào)度方面也取得了令人矚目的成果，京東物流全國規(guī)模最大的自動機器人倉群已投入使用，不同層級的無人倉數(shù)量已超過50個；菜鳥已經(jīng)上線了第三代無人倉，實現(xiàn)了從商品存儲到直接發(fā)貨的全流程自動化，還有昆船智能、極智嘉、快倉科技、新松機器人、海柔創(chuàng)新等。

亞馬遜無人倉

雖然如上文所說，國內(nèi)多家企業(yè)自稱已成功研發(fā)并應用了先進的無人倉系統(tǒng)，并且大大提升了存揀貨效率，但企業(yè)外部的人員，包括關注無人倉技術發(fā)展的筆者，卻無法從相關報道或者學術文獻中獲得真實的測試數(shù)據(jù)和結果，從而無法驗證其無人倉系統(tǒng)的高效性，無法對比其與傳統(tǒng)倉庫的效率。這讓人不禁懷疑，機器人在實際運作時究竟能否像宣傳視頻中一樣流暢地作業(yè)呢？而且根據(jù)某些業(yè)內(nèi)人士透露的信息，目前傳統(tǒng)倉庫仍占絕大多數(shù)，無人倉實際上并沒有被廣泛地應用起來。

為什么如此先進的無人倉沒有被廣泛地應用？主要有兩個原因，一是無人倉硬件成本過高，機器人本身的造價非常高；二是搬運機器人調(diào)度算法不成熟，當無人倉中搬運機器人的密度增加到一定程度，高效地調(diào)度搬運機器人的難度也隨之增加，對算法的要求就更高。因此，要想使無人倉真正地普及開來，除了不斷降低硬件成本之外，研發(fā)先進的搬運機器人智能調(diào)度算法極為關鍵，這也是筆者多年的研究領域之一。

倉庫示意圖

二、倉庫智能規(guī)劃和仿真系統(tǒng)需求加大

倉庫搬運機器人的調(diào)度主要包含兩個部分，即將存揀貨任務分配給機器人和為機器人規(guī)劃行駛路徑。調(diào)度搬運機器人的一個必要條件是需要有強大的倉庫管理系統(tǒng)（Warehouse Management System，簡稱WMS）支撐，通過WMS我們可以實時地（通常是秒級或更快）獲取倉庫的狀態(tài)，主要包括：

（1）每個庫位的狀態(tài)，即是否有貨物存儲，存儲的貨物類型及數(shù)量等；

（2）存取貨任務信息，即哪些存取貨任務正在等待，哪些正在被執(zhí)行等；

（3）搬運機器人的狀態(tài)，即搬運機器人的剩余電量，所處的位置，正在執(zhí)行哪個任務，當前規(guī)劃的行駛路徑，任務列表中有哪些任務等；

（4）充電樁被占用的情況等。

市面上某些WMS系統(tǒng)可能會提供一些機器人調(diào)度算法，但是這些算法通?；谝恍┙?jīng)驗的規(guī)則來調(diào)度機器人，較為初級。此外，機器人廠商也會提供路徑規(guī)劃算法，但是其算法通常是為單個機器人規(guī)劃最短的存取貨路徑，而不會全局考慮各個機器人的狀態(tài)，當多個機器人共同作業(yè)時，便往往會在倉庫內(nèi)形成擁堵。

當今企業(yè)運營的倉庫面積通常很大，可達幾萬平方米，存儲位高達幾萬個，甚至是立體的存儲位，日均入庫和出庫量高達幾十萬次，裝卸月臺達幾十個，搬運機器人的數(shù)量可超過百臺，而倉庫的運營是一個動態(tài)的過程，即入庫和出庫操作隨著時間的推移連續(xù)不斷地進行，因此庫內(nèi)搬運機器人調(diào)度的實時性要求非常高。不難想象，倉庫雖然大，但是其中不可能專門騰出空間只為了方便機器人通行，那么在機器人任務量越來越大之后，規(guī)劃的效果會越來越差，如果不優(yōu)化，甚至會出現(xiàn)死鎖的情況。對此，WMS系統(tǒng)優(yōu)化的方法有兩種：

一是可以把任務分配和規(guī)劃路徑結合起來，考慮到機器人的當前位置和任務的緊急性、需要花費的時間等等來決定任務分配給哪一個機器人，這樣把全局因素都加入算法中進行計算，規(guī)劃的效果會有很大地提升，但這個方法暫未有比較好的成果。

二是提升調(diào)度算法的性能，提升調(diào)度算法的性能可以在不增加硬件投入的情況下提升倉庫的運營效率，從而創(chuàng)造收益。這個方法的研究比較深入，算法效果也比較好，所以目前企業(yè)的WMS系統(tǒng)主流優(yōu)化方向都是提升調(diào)度算法的性能。

從筆者了解的情況來看，目前很多企業(yè)已經(jīng)建成智能倉庫，并且部署有完善的WMS系統(tǒng)，但是仍然沒有把高效率全局調(diào)度多個機器人的智能算法應用于倉庫，上文說到調(diào)度算法的優(yōu)化研究比較深入，算法效果也已經(jīng)比較好，但是為什么沒有應用到實際呢？這是因為仿真系統(tǒng)的缺失，當一個算法應用到實際的時候，需要具體適配和驗證算法的性能，而由于實體機器人的成本太高經(jīng)不起試錯，所以仿真系統(tǒng)是必不可少的。也就是說，機器人調(diào)度算法的研究者首先要構建相應的倉庫仿真系統(tǒng)，使用相關企業(yè)的歷史數(shù)據(jù)來進行仿真模擬，并且比較使用優(yōu)化算法前后的倉庫效率，測算出優(yōu)化算法對倉庫運營效率的提升程度，最終幫助企業(yè)測算出使用優(yōu)化算法帶來的效益，從而使企業(yè)更放心地在其WMS系統(tǒng)中集成智能優(yōu)化算法來指導實際操作。此外，倉庫仿真系統(tǒng)有助于算法研究人員研發(fā)和測試不同類型的算法，也便于算法研究人員調(diào)試算法?？梢钥吹?，如果有一個好的倉庫仿真系統(tǒng)，無論是研究還是實際應用，都會便利許多。

三、倉庫搬運機器人優(yōu)化調(diào)度與仿真前沿

1. 機器人路徑規(guī)劃算法

倉庫內(nèi)機器人的調(diào)度也稱為多Agent路徑規(guī)劃（Multi-Agent Path Finding, 簡稱為MAPF），即給定一個圖，一些數(shù)量的智能體，每一個都有多個任務，每個任務有指定的起點和終點，目標是為每個智能體規(guī)劃能完成任務而不會碰撞的路徑，從而最小化總成本。從問題屬性來看，MAPF屬于較為復雜的組合優(yōu)化問題，該問題的狀態(tài)空間隨著問題中智能體的增加而呈指數(shù)增長，已被證明為NP-Hard問題。MAPF在物流、軍事、安防、無人駕駛、車聯(lián)網(wǎng)、無人港口等眾多領域有著大量的應用場景。

總的來說，MAPF的研究可以分為理論與實踐兩大方面。先談理論方面，首先需要先假設時間和地圖都是離散化的，這是算法成立的前提條件，其次定義智能體在每一個行動點有兩種動作，一種是移動到相鄰的位置，一種是在當前位置等待，而且完成動作的耗時是固定的，同時給出智能體碰撞的兩種類型：一種叫點沖突，即在任意時刻內(nèi)，有兩個智能體在同一時間達到同一位置；另一種叫邊沖突，即兩個智能體在同一時間交換彼此的位置。

規(guī)劃機器人路徑時，我們?nèi)菀紫氲揭恍┣笞疃搪返乃惴ǎ鏔loyd算法、Dijkstra算法等等，這些算法都是求最優(yōu)解的，但是規(guī)劃時并不需要最優(yōu)，只需要快速求出一個優(yōu)質(zhì)的、滿足要求的路徑規(guī)劃結果來滿足系統(tǒng)的動態(tài)性。所以在規(guī)劃中一般采用A*算法，A*算法是廣度優(yōu)先搜索和Dijkstra算法的結合，是一種啟發(fā)式算法，它節(jié)省了時間的同時犧牲了一點解的質(zhì)量，即解并不一定為最優(yōu)解。

A*算法流程如下：（1）定義起點和終點，從起點（初始狀態(tài)）開始的距離函數(shù)g(x)，到終點（最終狀態(tài)）的距離函數(shù)h(x)，以及每個點的估價函數(shù)f(x) = g(x) + h(x)。（2）每次取出一個估價函數(shù)f(x)最小的節(jié)點x，然后通過x這個節(jié)點計算與x相鄰的節(jié)點的狀態(tài)。（3）若x的相鄰節(jié)點中有終點則結束算法，否則重復第二步。需要注意的是，這里的h(x)是我們定義的一個估計函數(shù)，在一些條件下是可以靈活定義h(x)來適應要求的，根據(jù)不同的h(x)的定義將得到不同的解。如果單純用A*算法來規(guī)劃單個機器人路徑，規(guī)劃結果無疑是片面的，因此需要整體考慮多個機器人的路徑規(guī)劃，這樣才能讓規(guī)劃結果更優(yōu)。 

基于這樣的需求，人們就發(fā)明了Conflict-Based Search（CBS）算法，CBS算法是當前比較主流且有較好效果的MAPF理論算法。它本質(zhì)上是一個兩層A*算法，上層的節(jié)點存儲智能體和地圖的信息，遇到?jīng)_突后會在節(jié)點的地圖添加限制（添加限制的方法如圖3所示），下層則是再度用A*對兩個沖突的智能體在有限制的地圖上進行路徑規(guī)劃，消除沖突后再重新加入上層隊列中。

在實踐方面，我們必須考慮MAPF的實際延伸問題，即K-Robust MAPF，因為很多情況下智能體是不會嚴格執(zhí)行每一個動作的，也就是說會產(chǎn)生延遲。解決延遲帶來的問題的方法是要求k時間段內(nèi)不讓某個智能體進入某塊矩形區(qū)域，也就是在某個矩形區(qū)域的邊界上設定更加“厚”的限制，逼迫智能體等待或者繞路。在實踐中還有一個關鍵的問題，如果一個智能體完成任務后，會獲得下一個任務，此時如何對智能體進行路徑規(guī)劃呢？某文獻提出了一個解決該問題的思路，即Rolling-Horizon Collision Resolution （RHCR）算法。RHCR算法每隔h個時間點處理一個窗口MAPF問題，也就是每次規(guī)劃給定智能體全部路徑，但是只處理w步內(nèi)的沖突，且w要大于h，否則就會出現(xiàn)碰撞情況，任務分配中心會向智能體分配多個任務。RHCR算法有4個優(yōu)點，即：（1）它適用于任何地圖；（2）不需要時時刻刻重新規(guī)劃，而是可以由用戶決定規(guī)劃的時間間隔h；（3）算法速度提升明顯；（4）解的質(zhì)量能夠得到保證。

上述CBS、RHCR等算法都是側重于解決離散時間離散地圖下的路徑規(guī)劃，考慮如何在連續(xù)時間連續(xù)地圖里進行路徑規(guī)劃也是研究的一個熱門方向，但該方向暫未取得較好的成果。

2. 機器人調(diào)度仿真系統(tǒng)

現(xiàn)有仿真系統(tǒng)的架構一般和真實的情況類似，它連接著企業(yè)的服務器，其智能體運動的效果可以看作是真實的效果。仿真系統(tǒng)包含三個模塊（見圖4），即服務器端、客戶端與可視化界面，其中可視化界面與服務器端是獨立的。

路徑優(yōu)化算法在服務器端通過編寫代碼來實現(xiàn)，具體的通訊流程為：（1）客戶端向服務端發(fā)送第一次請求，創(chuàng)建問題實例，即告知服務器端地圖信息，機器人狀態(tài)（任務、位置、已下發(fā)的路徑），服務器端會返回初規(guī)劃結果；（2）在運行過程中，客戶端每隔一段時間會發(fā)送請求告知機器人當前狀態(tài)（任務、位置等）并發(fā)布新的任務，服務器端會根據(jù)當前狀態(tài)返回規(guī)劃結果。

仿真系統(tǒng)的實現(xiàn)有多種方式。一種方式是采用國外商業(yè)仿真軟件Flexsim或者Anylogic，其優(yōu)點是這些商業(yè)軟件功能強大，可以為非常多的場景建立仿真模型，并且開發(fā)速度快；但是其開放的接口可能有限，不一定能完全滿足機器人調(diào)度算法的需求，一旦出現(xiàn)不滿足需求的情況就會使仿真程序的開發(fā)出現(xiàn)卡殼的現(xiàn)象，因為這些軟件廠商通常不會根據(jù)客戶的實際需求定制化接口。另一種方式是基于某些編程語言（例如Java或者C#）從零開始編寫特定倉庫場景下的仿真程序，其優(yōu)點是可靈活根據(jù)需求設計，自主可控，不會被“卡脖子”；缺點是成本較高，開發(fā)周期長。鑒于當前國際形勢，我國更應該采取第二種方式。