study-mapfMAPF / Lifelong MAPF / MAPD 教材

優先順位付き計画Prioritized Planning

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

固定した優先順位に従い、先行経路を避けてエージェントを 1 体ずつ計画する。

概要

優先順位付き計画（Prioritized Planning）は、エージェントへ全順序を与え、高優先度から 1 体ずつ経路を決める MAPF 手法です。後続エージェントは、すでに決まった経路を動的障害物として避けます。計画済みの経路を後から変えないため高速で分かりやすい一方、順序の選択に強く依存します。

まず何がうれしいのか

全エージェントの直積状態を同時探索せず、単一エージェント探索を n 回行えばよいのが利点です。Silver の CA* も、この分離型（decoupled）構造を space-time search と reservation table で具体化しています[cooperative-pathfinding-2005, p.2]。

前提となる知識

対象問題

サイト版は one-shot MAPF を対象にします。既定の順序は scenario.agents の配列順で、SolverOptions.extra.priorityOrder に全 agent ID の順列を渡すと順序を固定できます。

中心となるアイデア

高優先度エージェントは他を無視して最短路を選べます。次のエージェントはその経路を予約として避け、以後も同様に続けます。高優先度の選択を覆さないことが、速さと不完全性の両方の原因です。

アルゴリズムの手順

  1. 全エージェントの priority order を決めます。
  2. reservation table を空にします。
  3. 順番の先頭から、現在の予約を避ける個別最短路を求めます。
  4. 成功した経路の vertex と edge を予約します。
  5. 全員が成功すれば経路集合を返します。1 体でも失敗すれば、その priority order は失敗です。

小さな例

1 本の通路を左右から交換する 2 体と、中央付近に 1 個の退避セルを考えます。先に計画した agent が直進して退避セルを使わないと、後続 agent は避けられないことがあります。しかし先行 agent の別経路や逆順なら解ける場合があります。これは探索バグではなく、固定済み経路を戻さない設計の限界です。

データ構造

疑似コード

reservations ← empty
paths ← empty
for agent in priorityOrder:
  path ← shortestPathAvoiding(agent, reservations)
  if path does not exist:
    return failure for this priority order
  paths.add(path)
  reservations.reserve(path)
return paths

固定順方式の構造をサイト記法にしたものです。PBS は priority order 自体を探索する別アルゴリズムなので、この疑似コードには含めません。

実装上の注意

本実装の低レベルは静的障害物を考慮した true-distance heuristic を使う Space-Time A* です。同値状態は f 昇順、g 降順、生成順で選びます。PBS 論文は、順序だけでなく個別最短路のタイブレークにも成功が左右される例を示します[pbs-aaai-2019, p.3]。そのため、この規則を決定的に固定しています。

失敗時は failureReason: priority-order を返し、例外や一般的な「解なし」証明へ置き換えません。set-priority、reserve、reject-reserved-state で判断過程を追跡できます。

よくある誤解

他手法との比較

サイト上の実装との差異

論文で定義される一般的な方式に対し、本実装は配列順を既定にし、任意順序は extra.priorityOrder で明示します。PBS の順序探索、random restart、局所優先順位は行いません。有限 maxHorizon とブラウザ上限を加え、サイト既定の edge-swap / following / goal behavior を守ります。

公開 libmultirobotplanning の固定順 SIPP 例や pibt2 の HCA 優先規則は比較のために読みましたが、コードは転記していません。本サイトは順序依存を再現しやすくするため、距離順を暗黙に採用していません。

実験してみる

同じ scenario の JSON で agents の順番だけを逆転し、成功・失敗、cost、trace を比べてください。中央退避所の例では、参照 joint-state BFS が解を見つけても固定順が失敗することを単体テストで確認しています。

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

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

適用範囲の注意: 固定した優先順位でエージェントを 1 体ずつ計画する。PDF p.3 Theorem 3 の well-formed instances では条件付き完全だが、一般 MAPF の metadata は complete: false。PDF p.7 の 4% は実験観測であり bounded-suboptimal 保証ではない。

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

pbs-aaai-2019 PDF p.2 Theorem 1 は任意の priority ordering による prioritized planning が一般 MAPF で incomplete と示す。同 p.3 Theorem 4 と Corollary 5 は flowtime と makespan について一般に suboptimal と示す。

原論文

確認済みの箇所

公開実装

最終照合日: