TPToken Passing

シミュレータで実行可解説: 原論文と照合済み

全 agent の path と task 集合を token で共有する decoupled MAPD 手法。

概要

TP（Token Passing）は、全 agent の path、task 集合、assignment を共有 token に入れ、token を受け取った agent が自分の task と path を更新する MAPD 手法です[mapd-tp-tpts-central-2017, §4.1, Algorithm 1, p.3]。

まず何がうれしいのか

agent ごとに全体の MAPD を解き直さず、token の既存 path を時空間障害物として順番に計画します。well-formed infrastructure では、Path2 が空いた agent を non-task endpoint へ退避させます。

前提となる知識

MAPD、endpoint、well-formed、A*、vertex / edge-swap conflict が前提です。well-formed は解けるための十分条件であって必要条件ではありません[mapd-tp-tpts-central-2017, §3.2, Definition 1, p.2]。

対象問題

release 済み task を pickup して delivery する lifelong MAPD。サイト版は runMapdLoop の release → strategy → move → pickup/delivery の順序をそのまま使います。

中心となるアイデア

task を選べるときは pickup までの h 値が最小の task を選び、Path1 で pickup → delivery を計画します。選べない agent が task delivery 上にいるときは、Path2 で non-task endpoint へ退避します。

アルゴリズムの手順

token に release 済み task を追加する。
token を要求した free agent を決定的な順で処理する。
他 path の終端が pickup / delivery にない task を候補にする。
h 値最小の task を選び、MLA* で Path1 を token に書く。
task を選べない agent は、必要なら Path2 で endpoint へ移す。
全 agent を path の次の 1 step だけ進める。

小さな例

中央通路の delivery endpoint に free agent が止まっていると、次の task の path を塞ぐことがあります。TP はその agent に task を割り当てられない場合、空いている non-task endpoint へ動かします。

データ構造

token は Map<agentId, TimedPath>、Map<taskId, agentId>、未割当 task の集合です。予約表だけで token を代用していません。

疑似コード

while tasks remain:
  add released tasks to T
  for agent a requesting token:
    T' ← tasks whose pickup/delivery are not path endpoints in token
    if T' is not empty:
      τ ← argmin h(a, pickup(τ))
      assign τ; token[a] ← Path1(a, τ, token)
    else if a is at a delivery location in T:
      token[a] ← Path2(a, token)
    else:
      token[a] ← [current(a)]
  move one step along token paths

原論文 Algorithm 1 の構造を短く再構成しています[mapd-tp-tpts-central-2017, Algorithm 1, p.3]。

実装上の注意

TP の完全性は PDF p.4 Theorem 3 の well-formed 前提付きです。mapd-not-well-formed では loop が保証対象外の警告を出します。同じ警告を strategy から重ねて出しません。

よくある誤解

token は単なる占有予約表ではありません。
well-formed でない入力が必ず解けないわけではありません。
TP の Theorem 3 は最適性を主張していません。

他手法との比較

TPTS は未 pickup task の交換を許し、CENTRAL は中央で assignment と path を計画します。MLA* は TP の低レベル path planner です[mapd-tp-tpts-central-2017, §4.2, p.4]。

サイト上の実装との差異

サイト版は token、Path1 / Path2、endpoint 規律を実装しますが、原論文の sequential A* を MLA* に置き換えています。通信遅延、無限 task stream、実験 warehouse の規模は扱いません。

実験してみる

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

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

適用範囲の注意: 共有トークン（現在の経路・タスク集合）を 1 体ずつ受け渡し、空いたエージェントがタスクを取って経路を書き込む方式。PDF p.4 Theorem 3 の保証は well-formed に限る。サイト版は token を明示的に持ち、低レベルを MLA* に置き換えた教育用実装。

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

mapd-tp-tpts-central-2017 PDF p.4 Theorem 3「All well-formed MAPD instances are solvable, and TP solves them.」well-formed を前提とする条件付き完全性。

原論文

Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks
Hang Ma, Jiaoyang Li, T. K. Satish Kumar ほか (2017) Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks. AAMAS 2017, pp. 837-845
DOI外部リンクのみPDF 非同梱

公開実装

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

最終照合日: 2026-08-02