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

一、倉(cāng)庫(kù)搬運(yùn)機(jī)器人與無人倉(cāng)系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、倉(cāng)庫(kù)搬運(yùn)機(jī)器人優(yōu)化調(diào)度與仿真前沿

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

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

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

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

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

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

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

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

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

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

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

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

（來源：物流技術(shù)與應(yīng)用）