TPTSToken Passing with Task Swaps
シミュレータで実行可解説: 原論文と照合済み
TP の token と Path1 / Path2 を保ったまま、未 pickup task の再割当を試す拡張。
概要
TPTS（Token Passing with Task Swaps）は TP の task set を「未実行 task 全体」へ広げ、未 pickup の task を、より早く pickup できる agent が引き取れるようにします[mapd-tp-tpts-central-2017, §4.2, Algorithm 2, p.4]。
まず何がうれしいのか
TP の早い token 順で遠い agent が task を取ったあとでも、近い agent がまだ pickup 前なら交換できます。計算量と通信量は増えます。
前提となる知識
TP、token、Path1 / Path2、MAPD の well-formed endpoint が前提です。
対象問題
online MAPD。サイトの loop が task の実行状態を管理し、TPTS strategy は token の path と未確定 assignment を更新します。
中心となるアイデア
GetTask は h 値順に候補を見ます。既に別 agent が未 pickup task を持っていて、現在 agent の pickup 到達が早ければ、一時的に元 agent の path を token から外して再計画します。
アルゴリズムの手順
- TP と同じ token を受け取る。
- h 値順に task を調べる。
- 未割当なら Path1。
- 未 pickup の割当済み task なら、より早い Path1 のとき swap を試す。
- 元 agent は別 task または Path2 を試す。
- path に沿って 1 step 進む。
小さな例
二体が同じ pickup を競うとき、先に token を受け取った agent が遠ければ、後の agent が task を引き取り、前者は別 task を探します。
データ構造
TP と同じ明示的 token に、task assignment を追加します。交換は swap-task event で可視化します。
疑似コード
for task τ in increasing h(a, pickup(τ)):
if τ is unassigned:
assign a; token[a] ← Path1(a, τ, token)
else if τ is not picked up and a reaches pickup earlier:
unassign old agent; token[old] ← removed
assign a; token[a] ← Path1(a, τ, token)
ask old agent to run GetTask again
otherwise restore token and try next τ原論文 Algorithm 2 の再帰的な token 返却を短く再構成しています[mapd-tp-tpts-central-2017, Algorithm 2, p.4]。
実装上の注意
PDF p.5 Theorem 5 は「well-formed instance を TPTS が解く」と述べます。非 well-formed の保証対象外警告は runMapdLoop に任せます。
よくある誤解
- TPTS は必ず TP より良い service time になるわけではありません。
- Theorem 5 は最適性を保証しません。
- swap は pickup 後の task を奪う操作ではありません。
他手法との比較
TP より assignment の柔軟性が高く、CENTRAL より分散的です。実験上の service time は CENTRAL、TPTS、TP の順に小さい傾向ですが、CENTRAL の解決性保証はありません[mapd-tp-tpts-central-2017, §7, p.8]。
サイト上の実装との差異
共通 token / Path1 / Path2 と MLA* を使います。old owner を同じ step の queue に戻す点は再帰的 GetTask の教育用再構成で、論文の通信スケジュール、full path 到達時刻比較、無限 stream は未対応です。
実験してみる
完全性・最適性などの保証
| 完全性 | 条件付き |
|---|---|
| 最適性 | 不明 |
| 対象 | MAPD |
適用範囲の注意: 既に割り当て済みで未 pickup のタスクを、より近いエージェントが奪えるようにした TP の拡張。PDF p.5 Theorem 5 の保証は well-formed に限る。サイト版は MapdStrategy API の制約から同一 timestep 内の未確定 assignment 交換までを実装。
保証の根拠（原論文の記述）
mapd-tp-tpts-central-2017 PDF p.5 Theorem 5「TPTS solves all well-formed MAPD instances.」well-formed を前提とする条件付き完全性。
原論文
公開実装
対応する公開実装は、まだマニフェストへ登録されていません。
最終照合日: