Amazon Robotics 與南加大合力解決 MAPF 問題,為 1 千台倉儲機器人規劃無碰撞路徑

作者 | 發布日期 2020 年 05 月 19 日 13:38 | 分類 Amazon , 尖端科技 , 機器人 follow us in feedly


最近一篇技術論文,南加州大學和亞馬遜機器人公司(Amazon Robotics)研究人員開發一款解決終身多智慧型代理人路徑查找(Multi-Agent Path Finding,MAPF)問題的解決方案,其中一組智慧型代理人(機器人)必須移動到不斷變化的目標位置而不發生碰撞。他們指出,實驗可為多達 1 千台智慧代理機器人提供「高品質」解決方案,表現遠勝現有方法。

MAPF 是許多自動化系統的核心,如自駕車、無人機群,甚至電子遊戲的 AI。毫無疑問,亞馬遜最感興趣的是倉儲機器人(Warehouse Robot)適用性,截至去年 12 月,亞馬遜在物流配送網路(Fulfillment Network)擁有超過 20 萬台移動機器人。驅動單元(Drive Unit)會自動將庫存箱或平裝包裹從一個位置移動到另一位置,且必須持續移動,以便不斷指派新的目標位置。

研究人員的解決方案將 MAPF 問題建模成一個圖形,包含由一系列邊(線)連接的頂點(點)。頂點對應位置,而邊則對應兩個相鄰位置與一組智慧代理人(例如驅動單元)之間的連結。每台智慧型代理人都可在每個時步(Timestep)移動到相鄰位置,或在目前位置等待。如果兩台智慧型代理人計劃同一時步占據相同位置,就會發生碰撞。

(圖片來源:ARXIV

此方案機器人吞吐量更甚其他方法,在少量時步可提升 6 倍速度

此解決方案旨在規劃無碰撞路徑,以便將智慧型代理人移動到目標位置,同時最大化平均訪問位置數。考量到每次碰撞的時間範圍必須解決,同時每條路徑的頻率必須重新規劃,此方案更新每個時步的每台智慧型代理的起點與目標位置,並計算智慧代理人需要訪問所有位置的步數,也會不斷指派新目標位置給智慧代理人,直到找到無碰撞路徑,並沿著生成的路徑移動智慧代理人,並按順序刪除訪問過的目標位置。

模擬實驗中,研究人員將一個物流配送倉庫映射到一個 33×46 的網格,上有 16% 的障礙物,研究人員表示,吞吐量方面,他們的方法優於其他方法。將物流分揀中心(Logistic Sorting Center)映射到 37×77 網格(有 10% 障礙物),某些格子代表輸送槽及人們會將包裹放在驅動單元上的工作站,論文並指出,少量時步可在不影響吞吐量的情況下讓整體設計框架的速度提高 6 倍。

「我們的設計框架不僅適用於一般圖形,而且還能產生更好的吞吐量,」共同作者寫道:「整體而言,我們的框架適用一般圖形,透過使用者指定的頻率呼叫執行重新規劃,並能生成靈活的計劃,不僅可適應在線設置,而且還可避免對遙遠未來的期待會浪費不必要的運算量。」

(首圖來源:亞馬遜