study-mapfMAPF / Lifelong MAPF / MAPD 教材

Push and SwapPush and Swap

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

空き vertex を使う push と局所的な swap primitive で agent を順に goal へ運ぶ rule-based 手法。

概要

Push and Swap は search tree を最適 cost 順に広げる代わりに、push と swap という局所操作で agent を priority 順に goal へ置く rule-based pathfinding です。各 action は 1 agent が隣接する空き vertex へ移る操作です[push-and-swap-ijcai-2011, §2, p.2]。

まず何がうれしいのか

時間展開した全 configuration を探索せず、空き vertex を作業領域として障害 agent を動かします。逐次操作なので同じ timestep の vertex conflict や edge-swap conflict を作らず、長い path でも primitive の意味を追いやすい手法です。

前提となる知識

対象問題

原論文は connected undirected graph G=(V,E) と n ≤ |V|-2、すなわち少なくとも 2 個の空き vertex を仮定します。1 step に 1 agent だけを隣接する空き vertex へ動かします[push-and-swap-ijcai-2011, §2, p.2]。サイト版は 4 近傍 grid graph に限定し、逐次 step を全 agent の TimedPath frame に変換します。

中心となるアイデア

push は planning agent の shortest path 上の次 vertex を空けます。そこに blocker がいれば、blocker から最寄りの空き vertex まで occupancy を連鎖的にずらし、planning agent を 1 step 進めます。

swap は隣接する 2 agent を degree 3 以上の swap vertex まで multipush し、隣接空き vertex を 2 個作ります。6 move の exchange で 2 体の位置を交換し、準備中の move を agent 2 体だけ読み替えて逆再生します[push-and-swap-ijcai-2011, §3.2, p.3]。

アルゴリズムの手順

  1. priority 順に planning agent を 1 体選びます。
  2. goal への shortest path を求めます。
  3. 次 vertex が空なら 1 step move します。
  4. occupied なら blocker を nearest empty へ push します。
  5. push できなければ、degree 3 以上の候補へ 2 体を multipush して swap します。
  6. planning agent が goal に着いたら次 agent へ進みます。
  7. primitive がどれも適用できなければ、その priority order は失敗です。

小さな例

3×2 grid の上段両端に 2 agent を置き、goal を交換します。直線上では edge-swap になるため、そのまま交換できません。片方を degree 3 の中央へ運び、下段の空き 2 cell を使って exchange し、準備 move を逆再生すると 2 体の順序だけが入れ替わります。

データ構造

疑似コード

for agent in priorityOrder:
  while agent is not at goal:
    next ← second vertex of shortestPath(agent, goal)
    if next is occupied:
      if clear(next) fails:
        if swap(agent, occupant(next)) fails: return failure
        continue
    move agent to next
return sequential plan

swap(a, b):
  multipush pair to a degree≥3 vertex
  clear two adjacent vertices
  exchange a and b using six legal moves
  reverse preparation moves with a/b identities exchanged

原論文 Algorithms 1–3 の main loop、push、swap を、サイトの move / clear / swap 実行器へ合わせて再構成しています[push-and-swap-ijcai-2011, Algorithm 1, p.2][push-and-swap-ijcai-2011, Algorithm 2, p.3][push-and-swap-ijcai-2011, Algorithm 3, p.3]。

実装上の注意

swap candidate を試す途中で失敗しても、準備 move を本計画へ残してはいけません。サイト版は positions、occupancy、frame list を snapshot し、成功した trial だけを commit します。全 commit move は「隣接か」「移動先が空か」を実行時に検査します。

よくある誤解

他手法との比較

サイト上の実装との差異

サイト版は input order を既定 priority にし、extra.agentOrder で全 ID の明示順を受けます。shortest path、empty vertex、swap vertex の tie は row-major index です。原論文の clear は概略だけで後続論文が欠落ケースを示したため、サイト版は Push and Rotate の著者補足資料にある 4-stage clear を共通 primitive として採用します。solution smoothing / parallel compression は行わず、primitive の逐次 frame をそのまま表示します。

pibt2 commit faab5b91… は start-goal distance 降順、拡張 clear、既定 compression を使います。MIT license は確認しましたがコードは転記していません。この checkout は submodule 不足のため固定 build 比較を完了できていません。

実験してみる

3×2 の交換例を detailed trace で実行し、push-agent、clear-vertex、swap-agents を追ってください。agentOrder を逆にすると success / failure や move 数が変わる場合があります。

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

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

適用範囲の注意: ★重要★ push-and-rotate-aamas-2013 の 1 ページ目脚注が「一部のインスタンスでは Push and Swap が解を見つけられるかどうかがエージェントの処理順に依存する」と指摘している。完全性を説明する際は必ず両論文を併記すること（SOURCE_POLICY.md 第 4 条）。

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

push-and-swap-ijcai-2011 p.4 Theorem 3.1 は n≤|V|-2 で complete と主張するが、後続一次資料 push-and-rotate-aamas-2013 p.1 および pp.2-4 は同じ条件内の反例と agent 処理順依存を示す。最適性は push-and-swap-ijcai-2011 p.7 §5 が solution-quality guarantee を目的にしないと明記。

原論文

確認済みの箇所

公開実装

最終照合日: