轉載從: Tech News 科技新報
最近一篇技術論文，南加州大學和亞馬遜機器人公司（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 倍。
「我們的設計框架不僅適用於一般圖形，而且還能產生更好的吞吐量，」共同作者寫道：「整體而言，我們的框架適用一般圖形，透過使用者指定的頻率呼叫執行重新規劃，並能生成靈活的計劃，不僅可適應在線設置，而且還可避免對遙遠未來的期待會浪費不必要的運算量。」
（首圖來源：亞馬遜）