複数のロボットが、ぶつからずに目的地へ着くには
Multi-Agent Path Finding（MAPF）は、複数のエージェントに対して、互いに衝突しない経路を同時に決める問題です。1 体ずつ最短経路を引くだけでは、必ずどこかでぶつかります。
このサイトは、MAPF とその拡張である Lifelong MAPF・ Multi-Agent Pickup and Delivery（MAPD）を、原論文に基づいて学ぶための教材です。 推測で書いた説明は載せません。出典は各ページに明記しています。
MAPD
目的地が固定されず、運搬タスクが次々に発生し続けます。 各タスクには荷物を取る地点（pickup）と届ける地点（delivery）があり、 誰がどのタスクをやるかの割当も同時に決める必要があります。
倉庫のロボットがこの形です。
推奨する学習順
MAPF は手法が多いですが、依存関係があります。この順に読むと後の手法が理解しやすくなります。
アルゴリズム分類
基礎探索Basic search2 手法時間拡張探索Space-time search2 手法優先順位付き計画Prioritized planning5 手法CBS系Conflict-Based Search family5 手法ICTS・結合状態・M*系ICTS / joint-state / M*2 手法PIBT・LaCAM系PIBT / LaCAM family4 手法Push系Push-based rule algorithms2 手法LNS系Large Neighborhood Search3 手法Lifelong MAPFLifelong MAPF1 手法MAPDMulti-Agent Pickup and Delivery8 手法TAPF・タスク割当TAPF / task assignment5 手法学習ベースLearning-based2 手法
このサイトの現状
「解説がある」ことと「実装が動く」ことは別です。混同しないよう、 各ページにバッジを出しています。
34
シミュレータで実行可
ブラウザ内で実際に動かせます。
5
内部実装あり
他の手法から使われる部品で、単体では実行しません。
2
解説のみ
コードによる再現実装はまだありません。
0
準備中
骨格だけで、解説本文はまだありません。
論文準拠であること
- 52 本の原論文をマニフェストで管理し、 タイトル・著者・年・会議・DOI をすべて一次情報で照合しています。
- 77 手法の理論保証は、原論文で確認できたものだけを載せます。 確認できていないものは「不明」と表示します。もっともらしい値で埋めません。
- 「完全」「最適」「有界準最適」「eventually optimal」を区別します。 たとえば PIBT は原論文が「neither complete nor optimal for MAPF」と明記しています。
- 論文 PDF は再配布が許諾されているものを除き同梱していません。配布元へのリンクを示します。