機器人線上“偷懶”怎麼辦？阿裡研究出了這兩套算法

--------點選螢幕右側或者螢幕底部“+訂閱”，關注我，随時分享機器智能最新行業動态及技術幹貨----------

前言

與傳統工業優化不同，多智能體系統中每個機器人互相替代性很強，流程是非線性的，導緻系統效率很難直接模組化。一般通過調整任務配置設定與移動路徑，優化總任務距離來間接逼近系統效率。但我們在實踐中發現，任務距離與系統效率并不強相關。由于成本的限制，機器人數量往往是有限的，當針對任務距離進行優化時，會導緻部分作業人員過于繁忙，而部分作業人員無事可做的問題。

是以我們結合了菜鳥柔性自動化實驗室在多智能體系統的實踐與反思，于論文《Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers》中提出了基于工作站空閑時間的優化模型，關注如何最大化人的能力，進而推動整個系統達到更高的效率。我們對工作站的工作時間進行了離散化切分，模拟了機器人排隊與等待的情況，并通過一套統一的網絡流模型獲得機器人與工作站的配置設定政策，以及機器人叢集的路徑規劃，提升了系統産能。

論文位址：

https://aaai.org/Papers/AAAI/2020GB/AAAI-KouN.3001.pdf

應用場景

基于多智能體叢集的自動化技術方案的興起和發展，促進了現代物流業的發展和全球化，代表着物流與供應鍊行業未來的一個主要方向。在阿裡巴巴旗下菜鳥網絡以及其合作夥伴的倉儲和分撥中心有着成百上千的機器人在工作，實作包裹高效安全的到達使用者手上。

圖 1 機器人叢集在分撥中心進行包裹分撥

圖 1 是一個機器人分撥中心，幾百個機器人在快速的把大量的包裹根據城市分撥，幫助幹線物流網絡更高效的運輸包裹。機器人分撥中心的核心是三部分：工作站（Station），機器人（Agent）以及道口（Sorting Bin）。機器人會自動行駛到工作站領取包裹，通過自動掃碼，然後再将包裹運輸到對應的目的道地口，此時機器人會将包裹投進道口，進而完成包裹分撥。如何讓這幾百個機器人高效的運轉，使得包裹可以更加快速的到達使用者手中。這裡要值得思考的是，一般性的會認為讓這些機器人總的行駛路線最短就會使得整個分撥中心的效率最高。然而并不是這樣，我們會看輸入和輸出，輸入是所有的包裹，輸出是各個道口中的包裹。受限于大量的包裹以及有限的機器人，僅僅是去優化路線最短并不能最大産出，這樣就會存在部分工作站機器人排隊而另一些工作站缺乏機器人的情況，在輸入部分就已經限制了整個系統的産能。是以我們的目标是最小化所有工作站的空閑時間，來達到最大化系統産能的目的。下面會介紹如何模組化來解決最小化空閑時間的問題。

問題模組化

我們将上圖機器人分撥中心模式進行抽象成如下圖 2 所示，這樣可以友善的引入多智能體路徑規劃的研究，其中核心三要素分别是橙色的工作站，綠色的機器人以及藍色的道口。

圖 2 分撥過程，橙色節點為工作站，綠色節點是機器人，藍色節點為分撥道口（每個道口對應了一個目的地結合）

要完成最小化工作站空閑時間，其核心是解決兩個問題：

1. 每個機器人去哪個工作站接包裹，即任務配置設定(Task Assignment)問題；
2. 接完包裹後每個機器人按照什麼路線運作到目的道地口，每個機器人可以視為一個智能體，即多智能體路徑規劃(Multi-Agent Path Finding, MAPF)問題。

這兩個問題合在一起在學術上定義為 TAPF 問題。解決單次的任務配置設定和路徑規劃問題，我們定義為一個單次的 TAPF 問題。那麼順理成章的對于上述的自動化分撥中心持續作業的場景，可以抽象成 Lifelong TAPF 問題。接下來我們給出 TAPF 的定義。在給定的如下 3 個條件：

• 一個全連接配接的無向圖 G(V,E)；
• N個Station

  

  ；
• M個Agent

  

TAPF 會找到一個配置設定方案，這個配置設定方案表示即為每個 Agent 去哪個 Station，同時會為所有的 Agents 找到沒有沖突的路徑使得可以更快的到達各自的工作站。

當每個 Agent 到達其目的地 Station 點後，Station 将需要T的時間将包裹處理到 Agent 上的時間。是以如果給定一個時間視窗 [0, KT)，那麼我們可以設定每個工作站的操作時間為 K 個工作時間片: [0,T), [T,2T),..., [(K-1)T,KT)，且每個 Station 僅允許 Agent 的到達時間為 kT，其中 k=0,1,...,K-1。基于以上，我們認為當一個 Agent 在 kT 時刻到達其目的地工作站時，則這個工作站在時間段 [kT,(k+1)T) 内将會被占用。

對于 Life-Long TPAF 問題，那就不是僅僅計算一次任務配置設定和多智能體路徑規劃問題。其本質就是不斷的計算并更新每個 Agent 的配置設定方案和路徑，這樣對于上述場景中即是，每個機器人在運作過程中都在調整其目的地工作站和運作的路線，最終達到最小化工作站空閑時間最大化分撥中心産能的目的。

目标函數：基于以上定義，我們可以定義：在一個給定時間段内，最小化總的空閑時間，即為在這段時間内所有工作站的空閑時間之和。

示例說明：在後面的章節中，我們将用如下示例來詳細解釋每一種模型。

圖 3 問題示例

• 兩個 Agent：

  

  于時刻 0 從 A 出發，

  

  于時刻 1 于 C 出發；
• 兩個 Station：

  

  位于 E 點，其位置用

  

  表示，

  

  位于F點，其位置用

  

  表示；

那麼假設給定時間範圍是 [0,6)，工作站的處理時間 T=2，我們可以看到一個最優的 TAPF 的解決方案是給

配置設定工作站

，且其路線為

配置設定到工作站

，且其路線為 ，null 表示 0 時刻不在地圖中。這樣兩個工作站的工作時間段均為 [4,6)，得到的目标函數即總的空閑時間為 8。

ITO-空閑時間優化

圖 4 ITO 模型，邊上标記(cost, capacity)，為簡潔起見(cost=0,capacity=1)的邊沒有标記

為優化空閑時間，如圖 4 所示，我們建立了 ITO（Idle Time Optimization）網絡流模型。每一條邊有兩個屬性 (cost, capacity)，cost 代表了每機關流量經過這條邊需要付出的代價，capacity 代表這條邊能承載多少機關的流量。為簡潔起見，在圖中我們省略(cost=0,capacity=1)的邊。

我們對每一個建立了一個對應的藍色節點，對每個建立一個矩形 Station 子結構。Station 子結構根據時間軸展開成K個離散的時間段，每個時間段 [kT,(k+1)T) 用節點表示，這樣可以友善的考慮每個時間段的工作情況。Agent 與 Station 子結構之間是一個全連通的二分圖，表示每個 Agent 都能被指派到任意一個 Station 并占用一個對應的工作時間段。

圖5 Agent 節點與 Station 子結構的連結

圖 5 解釋了 Agent 節點與 Station 子結構的連結細節。對于每一組

，我們可以估算到達的時間，如果這個時間段是[kT,(k+1)T)，那麼可以在

時間段開始排隊，并填補之後任意一個時間段的空缺，排隊的特性我們通過

與

之間的連結實作。

最後，為使得整個系統的空閑時間最少，我們希望找到一個工作站指派使得工作站時間段盡可能被占用。是以我們以 Agent 節點為流的入口，每個 Agent 配置設定一個機關流量，以工作站時間段為出口，每個工作時間段最多流出一個機關流量。這樣每個時間段隻能被一個 Agent 獨占，每個 Agent 也隻能占用一個時間段。這個網絡流模型的最大流解即是使整個系統空閑時間最少的 Agent-Station 配置設定。當我們得出配置設定方案後，再通過 MAPF 算法求得無沖突的 Agent 路徑，就可以按照該路徑來控制排程整個多智能體叢集。

圖6 示例的 ITO 模型

圖 6 是前文示例對應的 ITO 模型，兩個 Agent 的預測到達時間都是在第 3 個時間段，粗邊是最大流的解，對應比對為

與。

PITO-結合路徑規劃的空閑時間優化

由于 ITO 将 Station 配置設定與路徑規劃分開考慮，其效果高度依賴于基于到達時間預測的精确程度。為了避免這個依賴，我們基于 ITO 設計了 PITO（Path Finding with ITO），它将 ITO 與匿名 MAPF 網絡流模型（Anonymous MAPF flow network, Yu and LaValle 2013）相結合，通過一個統一個網絡流模型，同時計算得出 Station 配置設定與 Agent 路徑。

圖 7 PITO 模型

PITO 的構造過程如圖7所示由兩部分構成。左側 MAPF 網絡用于計算生成路徑資訊，右側 ITO 網絡用于生成 Station 配置設定結果。

對于任何一個地圖中的點

，我們根據時間軸将其擴充到每一時刻 t，t 時刻的 u 用一個紫色節點表示。對于每一個

，我們建立一個緊随其後的綠色輔助節點

。由于

之間隻有一條 capacity 為 1 的邊，任何時刻 t 最多隻會有一個機關的流通過 u，進而避免了多個 Agent 同時到達 u 而相撞。我們在這裡并沒有在網絡結構中設計避免在邊上相撞，而是采用了一個小技巧，如果有兩個 Agent 在一條邊上相撞，則令他們在目前點等待，并交換兩者的 Station 配置設定與後面的路徑。由于 Agent 是匿名的，交換 Station 配置設定與後面的路徑并不會影響空閑時間，進而達到了簡化網絡、加速求解的目的。

ITO 網絡和前一章的構造方式基本相同，我們不再将Agent 與 Station 子結構直接相連，而是采用讓 Agent 通過 MAPF 直接“走到” Station 的方式。每個 Station

有其真實位置

。對于每個工作時間段 [kT,(k+1)T)，我們從輔助節點

連接配接一條邊到對應的工作站時間段

，進而允許Agent在到達

時可以占用其對應工作時間段。最後我們根據 Agent 的起始時間與起始位置，将它們連接配接到對應的節點上。

圖8 示例的 PITO 模型

圖8 是前文示例對應的 PITO 模型，藍色粗邊相連的節點展示了 Agent 的對應路徑以及 Station 的配置設定結果。

Lifelong 優化

這一章我們讨論如何将 ITO 與 PITO 應用到 Lifelong 的優化中。前面我們讨論了如何利用 ITO 與 PITO 求解 One-Shot 問題的 Station 配置設定與路徑規劃，每個 Agent 隻需要去 Station 一次。但在現實場景中我們更關心的是一個動态的過程，Agent 不斷往返工作站與傾倒口。是以在每經過 的一個時間視窗，我們會重新根據場上情況重算為 Agent 配置設定 Station 并規劃路徑。

但為了讓上個時間視窗的結果能夠更好的為下一個時間視窗留出優化空間，Agent 最好能占用更早工作時間段。我們通過增加懲罰節點 P 來達到這個目的。如圖 4 和 8，我們在 ITO 與 PITO 中增加了一個紅色懲罰節點 P，将它們轉化為一個最小費用最大流的問題。P 擁有足夠大的流量并且跟所有的時間段相連但 cost 不為 0，如果一個工作時間段沒有 Agent 能夠占據，就會産生一個從 P 到該時間段的等同于 cost 的懲罰。為了讓 Agent 盡可能占據前面的時間段，我們用一個随時間單調遞減的函數

來表示P到

的cost，比如采用線性遞減或者指數遞減函數。進而當空閑時間相等時，解會傾向于将空閑時間放在後面。

我們将 Lifelong 版的 ITO 與 PITO（帶時間視窗 W 與懲罰節點 P）稱為 ITO-L 與 PITO-L。

實驗分析

基于以上提出的的 ITO-L 和 PITO-L 算法以及我們給出3種對比算法，共 5 種算法架構進行 Life-Long TAPF 的實驗對比。5 種算法架構分别如下：

• 1）H(Inf)-L

  采用 Hungarian 算法将所有 agents 按照總距離最近的方式統一配置設定到工作站，解決 Task Assignment 問題，然後采用改進的 PBS 算法求解 MAPF 問題；随着系統的運作不斷重複實時的計算直至時間視窗結束。

• 2）H(1)-L

  采用Hungarian算法重複計算 [M/N] 次将所有 agents 配置設定到工作站，解決 Task Assignment 問題；然後采用改進的 PBS 算法求解 MAPF 問題，随着系統的運作不斷重複實時的計算直至時間視窗結束。

• 3）H(Q)-L

  采用 Hungarian 算法重複計算 [M/(NQ)] 次将所有 agents 配置設定到工作站，解決 Task Assignment 問題；然後采用改進的 PBS 算法求解 MAPF 問題。可以發現 H(1)-L 和 H(Inf)-L 分别對應 Q=1 和 Q=∞，随着系統的運作不斷重複實時的計算直至時間視窗結束。

• 4）ITO-L

  采用 Primal Dual 算法求解 Min Cost Max Flow 問題，解決 Task Assignment 問題；然後采用改進的 PBS 算法求解 MAPF 問題，随着系統的運作不斷重複實時的計算直至時間視窗結束。

• 5）PITO-L

  采用 Primal Dual 算法求解可直接得到 TAPF 問題的解，同時解決 Task Assignment 和 MAPF 問題，随着系統的運作不斷重複實時的計算直至時間視窗結束。

下面将介紹我們采用的兩個實驗平台。

Agent Simulator

圖9 模拟實驗中兩個分撥中心的地圖

Agent simulator 是指在我們随機生成的分撥中心業務模式的地圖集合上（如圖 9 所示），其中橙色代表工作站，藍色表示道口，Agent 未标明在上述地圖中。采用我們設計的仿真架構來模拟系統的運作，核心參數分别是：

• 工作站處理包裹時間，T = 10;
• 時間視窗範圍為[0,600]，即KT = 600，K = 60;
• 每次重複計算的時間間隔30，即W = 30;
• Q = M/N + 5;

Industrial Simulator

圖10 分撥中心場地的 2D 布局，綠點為 Station，灰點為不可達區域，黑點為道口

我們将 ITO-L 算法和 H(Q)-L 算法應用到上述應用場景的分撥中心的排程系統中；其中 Task Assignment 問題分别用對應的算法解決，實際中的路徑規劃采用 centralized A*算法求解以及解決 deadlock 問題。我們将實際分撥中心的地圖抽象抽象成如圖 10 所示。核心參數分别如下：

• T = 4;
• K = 75;
• Q = 15;

資料結果

Agent Simulator 的實驗結果如下圖 11 與 12 所示：

圖 11 變化 Agent 數量的空閑時間趨勢

圖 12 相對H(Inf)-L算法，各算法對于總産能的提升比例

Industrial Simulator 的實驗結果如圖 13 所示，其中全場分布的綠色方塊表示帶着包裹的機器人，全場分布的藍色表示空載的機器人。

圖 13 Industrial Simulator 運作截圖，以及 ITO-L 與 H(Q)-L 在 Industrial Simulator 的表現

從以上資料結果我們可以看到：

1. 在自測平台上，無論是 ITO-L 還是 PITO-L 表現的要比其他算法好，最小化空閑時間帶來的産能提升超過 10%，且我們知道 10% 的分撥能力的提升對一個持續運作的業務系統來說已經是比較好的表現。
2. 在實際分撥中心的系統仿真中，我們的産能提升也可以達到 11%，表明了我們所設計的算法的擴充性和實用性。

結束語

本文是研究任務配置設定，多智能體路徑規劃以及兩者結合在一起的 TAPF 問題的一次成功嘗試。我們的核心是針對目前物流行業前沿的自動化方案機器人作業模式的研究，分析其核心點 Life-Long TAPF 問題，首次提出了最小化工作站空閑時間的思想，來優化提高系統的效率。并在此基礎上設計了兩種算法架構 ITO-L 和 PITO-L 來求解 Lifelong TAPF 問題，達到最小化工作站空閑時間的目的。在實驗部分，我們分别采用了 Agent Simulator 和 Industrial Simulator 兩種仿真平台來驗證所設計的兩種算法。實驗資料表明在兩個測試平台上我們所提出的算法在系統産能上均可以有 10% 以上的提升，而對于一個長期運作的自動化作業系統來說，10% 的提升已經是一個不錯的表現，可以讓大量的包裹更加高效快速的到達使用者手中，對保證和提高物流時效、加速物流自動化的發展起到了積極的作用。本文主要表達，針對物流自動化機器人作業模式，我們在優化方向上和算法設計上的一些思考和做的事情。後續我們将繼續分析行業問題，設計和改進算法來進一步加速算法應用來提高系統效率。

原文連結：

https://mp.weixin.qq.com/s/pLN-FHNSDYPcKmJCa4vOYA