MLAMulti-Label A

内部実装あり（単体では実行不可）解説: 原論文と照合済み

pickup と delivery のような ordered goals を一つの A* 探索で扱う低レベル探索。

概要

MLA*（Multi-Label A*）は、agent が順番に訪れる複数の goal を一つの探索で扱います。MAPD の pickup → delivery を、pickup で一度探索を止めるのではなく label の変化として表します[mla-star-icaps-2019, §Multi-Label A* Algorithm, Algorithm 1, p.3]。

まず何がうれしいのか

pickup に着いたあと delivery へすぐ進む経路も探索に含められます。pickup で待ち続けると、別 agent の予定と不必要に衝突する経路を選ぶことがあります。

前提となる知識

A*、時刻付き path、vertex conflict / edge-swap conflict、MAPD の task を知っていると読みやすくなります。

対象問題

入力は現在位置、ordered goals（このページでは pickup と delivery）、token に保存された他 agent の path です。サイトでは 4 近傍・離散時間・wait を使い、token の path と衝突する状態を捨てます。

中心となるアイデア

探索状態 (position, time, label) の label は「pickup 前 / pickup 後」です。pickup に到着した node から、同じ位置・同じ時刻の pickup 後 label を作ります。delivery に pickup 後 label で到達したら解です。

アルゴリズムの手順

現在位置を pickup 前 label で OPEN に入れる。
f = g + h が最小の node を取り出す。
pickup に到着したら label を進める。
token と衝突しない wait / move successor を追加する。
delivery に到着した node を返す。

小さな例

agent が (0,0)、pickup が (1,0)、delivery が (1,1) なら、label 0 の (1,0) から label 1 の同じ node を作り、次の移動で delivery に到着します。pickup で止まり続ける予約は作りません。

データ構造

priority queue、(cell,time,label) ごとの parent、token の時刻付き path を使います。heuristic は pickup / delivery までの壁考慮距離です。

疑似コード

OPEN ← {(start, t, before-pickup)}
while OPEN is not empty:
  n ← min_f(OPEN)
  if n is after-pickup and n.cell = delivery: return path(n)
  if n is before-pickup and n.cell = pickup:
    OPEN.add((n.cell, n.time, after-pickup))
  for next in {wait} ∪ neighbors(n.cell):
    if next conflicts with token: continue
    OPEN.add(next with the same label)
return failure

これは論文 Algorithm 1 の構造を共通モデルへ短く写したものです。tmax（別 path の pickup 終端より遅い pickup を捨てる条件）もサイト版で扱います[mla-star-icaps-2019, Algorithm 1, p.3]。

実装上の注意

MLA* は TP / TPTS / CENTRAL の低レベルで使われます。token は予約表の代用ではなく、他 agent の path と task assignment を保持する共有状態です。

よくある誤解

label は agent の優先順位ではなく、ordered goals の段階です。
pickup と delivery を別々の A* で呼ぶ実装は MLA* ではありません。
実験で service time が改善しても、理論保証を意味しません。

他手法との比較

TP の原論文は sequential A* を使います。MLA* はその低レベルを一つの label 探索へ置き換え、HBH は割当順を決める上位 heuristic です[mla-star-icaps-2019, §The Multi-Agent Pickup and Delivery Problem, p.2]。

サイト上の実装との差異

サイト版は token の path を直接照合し、同点を f、h、生成順で決めます。大規模実験用の C++ 環境、複数 task の一般 ordered goals、無制限の探索時間は扱いません。MLA* は単独 MAPD Solver ではなく内部ライブラリです。

実験してみる

TP / TPTS / CENTRAL を選ぶと、内部で MLA* の expand-node と token 更新を確認できます。

完全性・最適性などの保証

理論保証。**原論文で確認できた記述だけ**を載せています。「不明」は「保証が無い」ではなく「原論文で未確認」の意味です。
完全性	不明
最適性	不明
対象	MAPD

適用範囲の注意: pickup → delivery のように途中で必ず経由すべき地点がある単一エージェント探索。ラベル（未 pickup / pickup 済み）で状態を分ける。原論文に保証定理を確認できなかったため guarantees は unknown のまま。TP / TPTS / HBH の内部ライブラリで、単独 MAPD Solver ではない。

保証の根拠（原論文の記述）

mla-star-icaps-2019 PDF pp.2–3（誌面 pp.182–183）Algorithm 1 を確認したが、MLA* 固有の完全性・最適性・準最適性を述べる定理・補題は確認できなかった。

原論文

A Multi-Label A* Algorithm for Multi-Agent Pathfinding
Florian Grenouilleau, Willem-Jan van Hoeve, John N. Hooker (2019) A Multi-Label A* Algorithm for Multi-Agent Pathfinding. ICAPS 2019, pp. 181-185
DOI外部リンクのみPDF 非同梱

公開実装

対応する公開実装は、まだマニフェストへ登録されていません。

最終照合日: 2026-08-02