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）は、環境を共有するエージェントの集団について、2 体のエージェントが同時に同じ場所を占めたり、同じ辺の上で場所を入れ替えたりすることなく、各エージェントがスタートからゴールへ到達できるように経路を計画する問題である。環境は通常グラフとして、多くはグリッドとしてモデル化され、時間は離散的なステップに分けられ、各ステップで各エージェントは隣接する頂点へ移動するか待機する。

MAPF の解は通常、全エージェントがゴールに到達するまでにかかる時間の合計である sum of costs、または最後のエージェントが到着するまでの時間である makespan で評価される。これらの目的のもとで最適解を求めることは一般に NP 困難であるため、この分野では最適性と引き換えに速度を得るアルゴリズムが開発されてきた。最適手法には Conflict-Based Search（CBS）があり、各エージェントを独立に計画したうえで、探索木に制約を加えることで衝突を解消する。エージェントが一体ずつ計画し、先に計画したエージェントを動く障害物として扱う優先度付き計画のような準最適手法は、はるかに大きなチームにまでスケールする。

Lifelong MAPF は、エージェントが古いゴールに到達するとすぐに新しいゴールを受け取る派生問題であり、倉庫ロボットや仕分けロボットの実際の働き方に合っている。この場合、計画は多くは限られた時間窓の上で継続的に実行され、スループットが主な指標となる。

実際のロボットは教科書的な仮定も崩す。大きさ、加速度の制限、実行の遅れがあるため、MAPF の計画は通常、一部のロボットが予定より遅れたときにも安全を保つ追加の協調層とともに実行される。探索ベースのプランナーからの模倣学習を含む学習ベースの手法は、非常に大規模なフリートへスケールするための活発な研究分野である。

重要な理由

倉庫、工場、仕分けセンターでは、共有のフロア上で拡大し続ける移動ロボットのフリートが動いており、そのスループットはロボット同士をどれだけうまく協調させるかで決まる。MAPF は、フリートが大きくなっても、衝突やデッドロックなしにロボットを動かし続けるためのアルゴリズムを提供する。

主な用途

• 倉庫やフルフィルメントセンターのロボットフリート
• 多数の移動ロボットを用いた小包仕分けシステム
• 工場における無人搬送車の協調
• 複数ドローンや空港の地上交通の協調
• ビデオゲームのキャラクター移動と群衆シミュレーション

実際の使われ方

倉庫のフリートを運用するチームは、通常、フロアをグリッドグラフまたはロードマップグラフとしてモデル化し、各セルをロボット 1 台が収まる大きさにする。中央のプランナーは受注システムからゴールを受け取り、協調した経路を計算する。問題全体を最適に解くのではなく、数秒ごとに計画し直す優先度付き探索や時間窓付き探索を用いることが多い。経路は時刻付きのウェイポイントに変換されてロボットに送られ、行動依存グラフのような実行層が、前のロボットがセルを空けるまでロボットがそのセルに入らないようにする。実システムでフロアのレイアウトやアルゴリズムを変更する前に、エンジニアはフリート全体の規模のシミュレーションでスループット、待ち時間、デッドロックの頻度を測定する。

よくある誤解

• 各ロボットは自分の最短経路を独立に計画できる — 独立した経路は衝突するため、ロボットは空間だけでなく時間でも協調させなければならない
• 最適な 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