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

一、倉庫搬運機器人與無人倉系統

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

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

亞馬遜無人倉

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

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

倉庫示意圖

二、倉庫智能規劃和仿真系統需求加大

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

（1）每個庫位的狀態，即是否有貨物存儲，存儲的貨物類型及數量等；

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

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

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

市面上某些WMS系統可能會提供一些機器人調度算法，但是這些算法通常基于一些經驗的規則來調度機器人，較為初級。此外，機器人廠商也會提供路徑規劃算法，但是其算法通常是為單個機器人規劃最短的存取貨路徑，而不會全局考慮各個機器人的狀態，當多個機器人共同作業時，便往往會在倉庫內形成擁堵。

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

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

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

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

三、倉庫搬運機器人優化調度與仿真前沿

1. 機器人路徑規劃算法

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

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

規劃機器人路徑時，我們容易想到一些求最短路的算法，如Floyd算法、Dijkstra算法等等，這些算法都是求最優解的，但是規劃時并不需要最優，只需要快速求出一個優質的、滿足要求的路徑規劃結果來滿足系統的動態性。所以在規劃中一般采用A*算法，A*算法是廣度優先搜索和Dijkstra算法的結合，是一種啟發式算法，它節省了時間的同時犧牲了一點解的質量，即解并不一定為最優解。

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

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

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

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

2. 機器人調度仿真系統

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

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

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