Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding

作者: He Jiang, Yutong Wang, Rishi Veerapaneni, Tanishq Duhan, Guillaume Sartoretti, Jiaoyang Li · ICRA 2025

授權條款

• 開放取用
• 論文: CC BY 4.0

以下內容皆依據論文全文，依其 CC BY 4.0 授權條款使用；圖表已標示作者。

一句話摘要

SILLM 模仿一個強大的搜尋式求解器，加入空間通訊、交通引導與 PIBT 衝突修復，能以每步不到 1 s 的時間為 10,000 個代理進行規劃，並達到最高吞吐量。

為何重要

自動化倉庫已在運行數千台機器人（論文引用 2022 年 Amazon 物流中心有超過 4,000 台），因此能在這種規模下以每步不到一秒的規劃維持高吞吐量的規劃器，與車隊控制直接相關。結果顯示，學習而得的策略結合搜尋式的衝突處理與考量交通的引導，可以勝過最強的可擴展搜尋式求解器，而不只是勝過緩慢的最佳解求解器。

問題

終身多代理路徑規劃（LMAPF）在每個代理到達目標後立刻給它新的目標，因此必須持續重新規劃無碰撞路徑，同時最大化吞吐量（每個時間步達成的目標數）。學習式求解器能依局部觀測快速反應，但大多只在數十到數百個代理上測試過，也無法勝過 PIBT 等可擴展的次佳搜尋求解器。本文的目標是在 10,000 個代理的規模下，同時勝過學習式與搜尋式求解器。

提出的方法

SILLM 是一個由所有代理共用的卷積策略，視野為 11×11，並具備 Spatially Sensitive Communication 模組，把每個鄰居的特徵向量插入其精確的相對網格位置。觀測中編碼了三種啟發式引導圖之一（Backward Dijkstra、交叉高速通道式的 Static Guidance，或以 TrafficFlow 為基礎的 Dynamic Guidance），而簡化的 CS-PIBT 步驟會在學習到的動作沒有衝突時予以保留，否則以 PIBT 修復。此策略透過反覆模仿 Windowed MAPF-LNS 來訓練，後者是 2023 League of Robot Runners 冠軍方案 WPPL 的核心，訓練在縮小的地圖上以 600 個代理進行。

關鍵見解

• 把鄰居的特徵放在其精確的相對位置（空間敏感通訊），在消融實驗中勝過以注意力為基礎的通訊與無通訊，顯示精確的空間推理對 LMAPF 很重要。
• 模仿一個隨時可用（anytime）的大規模求解器（Windowed MAPF-LNS），避開了限制 PRIMAL2、SCRIMP 與 MAGAT 等早期模仿學習器的小型訓練實例（8–10 個代理）。
• 最佳的引導方式取決於地圖：Static Guidance 適合交叉分揀地圖與倉庫地圖，Backward Dijkstra 適合隨機地圖，Dynamic Guidance 則在 Paris 與 Berlin 城市地圖上表現最好。
• 以 PIBT 為基礎的衝突修復在學習到的動作沒有衝突時予以保留，避免了常見「凍結」策略造成的不必要等待與死結。
• 單純的 MAPPO 強化學習表現不如模仿學習，而在模仿之後再套用 MAPPO 也沒有可量測的提升。

主要結果

• 在六張有 10,000 個代理的大型地圖上，平均吞吐量比最佳的學習式基準方法高 137.7%，比最佳的搜尋式基準方法高 16.0%。
• 大型地圖上的競賽式分數：SILLM 0.99，SILLM（僅 Dynamic Guidance）0.94，WPPL 0.88，TrafficFlow 0.81，PIBT 0.61，Follower 0.52；RHCR 與 SCRIMP 每步需要數分鐘，無法在此規模下評估。
• 大型地圖上的平均單步規劃時間：SILLM 為 0.349 s，WPPL 為 4.143 s，Follower 為 4.125 s。
• 在大型地圖上，Learnable PIBT 在每種引導類型下都勝過一般 PIBT（平均分數：Backward Dijkstra 下 0.80 對 0.61，Static Guidance 下 0.85 對 0.75，Dynamic Guidance 下 0.94 對 0.81）。
• 在模擬倉庫中，10 台真實機器人無碰撞地抵達各自目標；在 100 台虛擬機器人下，Learnable PIBT 的吞吐量比 PIBT 高 50%。
• 每次模仿迭代在 50 個回合中蒐集 1,500 萬組動作-觀測對，重複 12 次；在配備 4 張 RTX 4090D GPU 的伺服器上，每張地圖的訓練時間不到 12 小時。

限制

• 作者表示，受硬體與軟體限制，實體驗證只限於迷你倉庫中的 10 台真實機器人加上 100 台虛擬機器人，而且真實機器人的實驗以定性方式報告。
• 規劃器假設每個代理的位置都完全已知；真實機器人需要 OptiTrack 動作捕捉系統來定位，並需要 Action Dependency Graph 來吸收執行誤差。
• 引導啟發式是人工設計的，最佳的一種取決於個別實例，必須依經驗選擇，而其超參數會影響效能。
• 由於記憶體需求，沒有在 10,000 個代理下訓練；策略是在縮小的地圖上以 600 個代理訓練，再於大型地圖上評估。
• 以目前測試的形式，強化學習並沒有幫助；作者把更好的團隊獎勵分配留待未來研究。

對領域的影響

這篇論文獲得 IEEE ICRA 2025 多機器人系統最佳論文獎與 IEEE ICRA 2025 最佳學生論文獎，被引用 35 次。論文表示程式碼將在論文被接受後釋出，官方專案頁面也連結了程式碼儲存庫。

摘要

終身多代理路徑規劃（Lifelong Multi-Agent Path Finding，LMAPF）是 MAPF 的一種變體，代理會持續被指派新目標，因此需要頻繁重新規劃以因應這些動態變化。近來，這個領域開始採用以學習為基礎的方法，依據各自的局部觀測以反應式方式產生單步動作。然而，這些方法仍難以達到最佳的搜尋式演算法的效能，在大規模情境下尤其如此。本研究提出一種以模仿學習為基礎的 LMAPF 求解器，引入新穎的通訊模組，以及系統化的單步衝突消解與全域引導技術。我們提出的求解器 Scalable Imitation Learning for LMAPF（SILLM）借助現代 GPU，同時繼承了學習式方法的快速推理速度與搜尋式方法的高解品質。在六張具有多達 10,000 個代理與不同障礙結構的大規模地圖上，SILLM 超越最佳的學習式與搜尋式基準方法，平均吞吐量分別提升 137.7% 與 16.0%。此外，SILLM 也擊敗了 2023 League of Robot Runners 的獲勝方案，這是一項由 Amazon Robotics 贊助的國際 LMAPF 競賽。最後，我們在模擬倉庫環境中，以 10 台真實機器人與 100 台虛擬機器人驗證了 SILLM。

連結

• arXiv 2410.21415: https://arxiv.org/abs/2410.21415
• DOI 10.1109/ICRA55743.2025.11127445: https://doi.org/10.1109/ICRA55743.2025.11127445
• PDF: https://arxiv.org/pdf/2410.21415v1
• 程式碼: https://github.com/DiligentPanda/Scalable-Imitation-Learning-for-LMAPF
• 專案頁面: https://diligentpanda.github.io/SILLM/