はじめに．
ヒューリスティックな Multi-Agent 経路探索(path-plannning, path-finding)アルゴリズム：MAPF アルゴリズムの一部を簡単にまとめています．幅探索、深さ探索、均一コスト探索などの一般的な Singple-Agent 向けの経路探索アルゴリズムについては、知っていることを前提としています．
※筆者の理解に応じて追記する予定です．
2024/04/12 : A* と Extentions of A* (OD,ID)の説明記載．
通常 A* → Multi-Agent A* への適応.
Single-Agent について、最もオーソドックスかつ有効な探索アルゴリズムとして A* アルゴリズムが知られています．幅探索、深さ探索のアルゴリズムを発展させた「最良優先探索アルゴリズム」に含まれるアルゴリズムです．A* アルゴリズムは、ある状態 $s$ に対してセット $(s,g(s),h(s),f(s))$ を利用して探索を行います．ここで、
- $g(s)$ はスタート状態 $\rightarrow$ 現在状態 $s$ への最小コスト
- $h(s)$ は現在状態 $\rightarrow$ ゴール状態への推定コスト
です．A* アルゴリズムでは $f(s) = g(s)+h(s)$ の値を基に、コストの小さいノードを優先して探索することになります．A* アルゴリズムにおいては、推定コスト $h(s)$ がある条件を満たせば、解が見つかるという「完全性」と解が最短であるという「最適性」を持つ事が知られています．
この通常の A* を Multi-Agent の経路探索に用いることを考えます．この時、Agent の数を N 台、各 Agent の次に取れる行動集合を $A_i$ とすると、Multi-Agent の状態集合 $S = (s_1,...,s_N) $ を親ノードとする次の子(状態集合) S'の数は、$\Pi_{i\in N} |A_i|$ となります．仮に、全 Agent が「上、下、左、右」にしか移動しないとすると、その子ノード数の上限は $4^N$ となります．$1$ つの状態遷移でこれだけの分岐が増えることから、通常の A* を Multi-Agent に適応することは解の探索コストの観点から難しいことが理解出来ます．そして、この台数に対するスケーラビリティや探索のリアルタイム性を改善するために、これまで数多くの改良アルゴリズムが提案されてきました．
Extentions of A*：
Single-Agent 向けの経路探索アルゴリズムであった A* を Multi-Agent に拡張するために改善されたモデル達を、Extentions of A* と呼びます．前述の Multi-Agent 向けに通常の A* をそのまま用いた場合解の探索コストが指数関数的に増えてしまうという課題に対処することを目的としています．以降、Multi-Agent は $N$ 台の「上、下、左、右、静止」の $5$ つの行動を取る Agent から構成されているとします．
Operator Decomposition(OD).
Agent 達を優先度(priorlized)付きに変更し、優先度順に $1$ つのノード分岐を特定 Agent の状態変化のみで行う手法です．つまり、親-子ノードの差は $1$ つの Agent の状態変化のみで、他の Agents の状態は固定となっています．$1$ つの分岐では、通常の A* を適応した場合 $5^N$ 個の分岐があった一方で、OD では $5$ 個の分岐に減らすことが可能になっています．
(s_1,...,s_{i-1},s_{i},s_{i+1},...,s_N) \rightarrow (s_1,...,s_{i-1},s'_{i},s_{i+1},...,s_N)
一方で、構築される探索木の深さは通常の A* の適応よりも $n$ 倍深くなります．
Independence Detection(ID).
ID は、$N$ 台の MAPF 問題をより小さい台数の MAPF 問題に分解するアプローチです．MAPF 問題において難点を生じさせているのは、環境の非定常性と協調性でした．環境の非定常性とは、ある Agent $i$ が時刻 $t$ 移動した場合に、他の Agent が同じ時刻 $t$ で移動することで、Agent $i$ が時刻 $t$ で想定していた時刻 $t+1$ の状態に移動出来ない可能性が生じることです．ID では、衝突する Agent の経路ペアのみを取り出してしまえば、$N$ 台のMAPF問題を衝突のペア数 $k$ 台のMAPF問題に分割出来るという発想を基にしています．ただし、全ての Agent 経路に衝突が存在するような場合は分割が出来ません．また、これ自体で経路が求まる訳では無く、あくまで分割アプローチであって分割後の MAPF 問題は別のアルゴリズムで解く必要があります．勿論、A*$+$OD を分割後の問題を解くために使うことも出来ます．