Multi-Agent Path Finding

• 又稱: MAPF, multi-agent pathfinding, multi-robot path planning
• 類別: Learning & autonomy › Multi-robot
• 標籤: multi-robot, path-planning, warehouse-automation, coordination, graph-search

為許多同時在共用圖上移動的代理人（例如網格上的倉儲機器人）計算無碰撞路徑的問題，讓每個代理人都能在沒有衝突的情況下抵達目標。

定義

多代理人路徑規劃（Multi-Agent Path Finding，MAPF）是為共用同一環境的一群代理人規劃路徑的問題，讓每個代理人都能從起點抵達目標，同時不會有兩個代理人在同一時間占據同一位置，或沿著同一條邊互換位置。環境通常以圖來建模，常見的是網格，時間則切分為離散的步驟，每一步中每個代理人不是移動到相鄰頂點，就是原地等待。

MAPF 的解通常以總成本（所有代理人抵達各自目標所花的總時間）或完工時間（直到最後一個代理人抵達的時間）來評判。在這些目標下尋找最佳解一般而言是 NP 困難的，因此這個領域發展出以最佳性換取速度的演算法。最佳方法包括以衝突為基礎的搜尋（Conflict-Based Search，CBS），它先獨立為每個代理人規劃，再於搜尋樹中加入限制條件來化解衝突。次佳方法，例如優先順序規劃（代理人一次規劃一個，並把先前規劃的代理人視為移動中的障礙物），能擴展到規模大得多的團隊。

終身 MAPF 是一種變體，代理人一抵達舊目標就會收到新目標，這與倉儲及分揀機器人實際的運作方式相符。此時規劃會持續進行，通常在有限的時間窗口內執行，而吞吐量成為主要的衡量指標。

真實的機器人也會打破教科書的假設：它們有尺寸、加速度限制與執行延遲，因此 MAPF 計畫通常要搭配額外的協調層來執行，在部分機器人落後於排程時確保安全。以學習為基礎的方法，包括從以搜尋為基礎的規劃器進行模仿學習，是擴展到超大型車隊的活躍研究方向。

為何重要

倉庫、工廠與分揀中心在共用的場地上運行規模持續擴大的移動機器人車隊，而它們的吞吐量取決於這些機器人協調得多好。MAPF 提供的演算法，讓機器人在車隊擴大時仍能持續移動，不發生碰撞或死結。

主要應用

• 倉庫與物流履行中心的機器人車隊
• 使用大量移動機器人的包裹分揀系統
• 協調工廠中的無人搬運車
• 多架無人機與機場地面交通的協調
• 電子遊戲中的角色移動與人群模擬

實際應用

經營倉庫車隊的團隊通常把場地建模為網格圖或路線圖，每個格子的大小剛好容納一台機器人。中央規劃器從訂單系統接收目標並計算協調後的路徑，通常使用每隔幾秒就重新規劃的優先順序搜尋或時間窗口搜尋，而不是對整個問題求最佳解。路徑會轉換成帶有時間的路徑點並傳送給機器人，再由執行層（例如動作相依圖）確保機器人在前方的機器人離開某個格子之前不會進入。在真實系統上變更場地配置或演算法之前，工程師會在完整車隊規模的模擬中量測吞吐量、等待時間與死結發生頻率。

常見誤解

• 每台機器人都可以獨立規劃自己的最短路徑 — 獨立的路徑會互相碰撞，因此機器人必須在時間與空間上同時協調
• 最佳 MAPF 可擴展到任何車隊規模 — 最佳求解是 NP 困難的，因此大型車隊仰賴次佳或時間窗口式的方法
• MAPF 計畫可以完全照計算結果執行 — 真實機器人會提早或延遲，因此執行需要自己的安全與協調層

誰需要了解

• 倉儲自動化與車隊管理工程師
• 多機器人規劃研究人員
• 自主移動機器人（AMR）與 AGV 系統整合商
• 從事物流的作業研究人員

相關技術

• 以衝突為基礎的搜尋（Conflict-Based Search）
• 優先順序規劃（Prioritized Planning）
• A 搜尋（A Search）
• 車隊管理系統（Fleet Management Systems）
• 模仿學習（Imitation Learning）

相關術語

• Swarm Robotics
• Motion Planning
• AMR

相關專案

• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
• IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
• Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots