study-mapfMAPF / Lifelong MAPF / MAPD 教材

LaCAM*LaCAM star

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

LaCAM の遅延探索を続行し、発見済み configuration graph の parent と cost を張り替えて sum-of-loss optimum へ収束する anytime 手法。

概要

LaCAM* は LaCAM が最初の goal configuration で止まる処理を、anytime optimization へ拡張します。初解を保持したまま lazy successor generation を続け、すでに見つけた configuration へ別の辺がつながるたびに cost-to-come と parent を張り替えます。探索を完了すれば累積 transition cost の最適解へ到達します[lacam-star-ijcai-2023, §3, Algorithm 3, p.4]。

まず何がうれしいのか

初解を得る速さと、解品質の改善を同じ探索で扱えます。configuration generator が promising な successor を先に出せば早く動く解を得られます。その後は新しく判明した shortcut を graph へ足し、時間が許すほど incumbent を改善します。

前提となる知識

対象問題

原論文は one-shot MAPF を configuration graph 上の pathfinding として定義します。2 configuration が connected なのは、全 agent が move / wait でき、vertex collision と edge collision がない場合です[lacam-star-ijcai-2023, §2.1, p.2]。サイト版は 4 近傍 unit-cost grid、following conflict 許可、stay-at-goal を扱います。

中心となるアイデア

LaCAM* の high-level node は LaCAM の情報に次を加えます。

未知 configuration を生成したら通常の tree edge を追加します。既知 configuration を生成したら「無駄な重複」と捨てず、新しい directed edge として保存します。その edge で g が下がる node があれば Dijkstra relaxation を子孫へ伝え、parent を新しい shortest-path tree に張り替えます。

アルゴリズムの手順

  1. LaCAM と同じ start node、constraint tree、Explored table を作ります。
  2. goal configuration を見つけても返さず、N_goal として保持します。
  3. g(N_goal) <= g(N)+h(N) なら、N は incumbent を改善できないので捨てます。
  4. lazy constraints から connected configuration Q を生成します。
  5. Q が未知なら node と edge を作り、g(parent)+costEdge で初期化します。
  6. Q が既知なら edge を追加し、source から Dijkstra relaxation します。
  7. g が下がった node の parent を更新し、改善可能なら Open へ戻します。
  8. Open が空になるまで続けます。中断時は incumbent があれば sub-optimal solution として保持します。

Algorithm 3 の gray 部分が LaCAM、追加部分が goal 保持と rewiring です[lacam-star-ijcai-2023, Algorithm 3, p.4]。

小さな例

start から configuration C へ、最初は cost 8 の親鎖が見つかったとします。後で別 node B から C への edge が生成され、g(B)+cost(B,C)=5 なら、C.g を 5 に下げて parent を B にします。C から既知の D、goal へ辺があれば、その改善も順に伝播します。configuration を作り直さず、発見済み graph の shortest-path tree だけを更新できます。

データ構造

疑似コード

goalNode ← none

while Open is not empty and not interrupted:
  N ← Open.top
  if N.config = goal: goalNode ← N
  if goalNode exists and g(goalNode) ≤ g(N) + h(N):
    Open.pop
    continue

  C ← next lazy constraint of N
  Q ← generateConnectedConfig(N.config, C)
  if Q is new:
    child.g ← N.g + edgeCost(N, child)
    child.parent ← N
    add edge N → child
    Open.push(child)
  else:
    add edge N → known(Q)
    dijkstraRelaxFrom(N)

if Open is empty and goalNode exists: return optimal incumbent
if interrupted and goalNode exists: return sub-optimal incumbent
if Open is empty: return no-solution
return failure

原論文 Algorithm 3 の graph update をサイトの node / event 名に合わせています。low-level expansion と generator は Algorithm 1 / 2 と共有します[lacam-star-ijcai-2023, Algorithm 1, p.3][lacam-star-ijcai-2023, Algorithm 2, p.3]。

実装上の注意

内部目的は原論文の sum-of-loss です。configuration X→Y の edge cost は、agent i が X と Y の両方で goal に stay するときだけ 0、そうでなければ 1 とします。heuristic は各 agent の goal distance の和で admissible です[lacam-star-ijcai-2023, §2.1, p.2]。

rewiring は strict improvement のみ採用します。同 cost の parent を何度も交換すると、説明に不要な非決定性や parent cycle の原因になります。サイト版は heap の同点を configuration ID で固定します。

よくある誤解

他手法との比較

サイト上の実装との差異

サイト版は Algorithm 3 の goal 保持、directed neighbor、Dijkstra rewiring、f 枝刈りを実装します。Algorithm 4 の PIBT swap detector、0.1% random restart、LaCAM3 の non-deterministic extraction / post-processing は含みません。これらは初解・収束速度の改善で、Theorem 1 の全列挙構造には必須ではありません。

lacam2 commit 61a4c40c... は argparse / googletest submodule 未取得で build できませんでした。pylacam commit 864a158f... の main branch は PIBT を random action selection に置換しています。依存 loguru が環境に無いため logger だけ無作用 stub にして公式 3×2 fixture を実行し、success、sum-of-loss 6、makespan 4、path validity を確認しました。サイト版も同 fixture で同じ 2 metric と validity を得ています。コードは転記していません。

timeout / node limit / maxPathLength に達した場合、incumbent path があっても outcome は中断理由を保ち、最適とは表示しません。4 近傍、following conflict 許可、stay-at-goal 以外は未対応です。

実験してみる

swap-conflict を detailed trace で実行し、最初の update-incumbent の後も configuration-expand が続くことを確認してください。rewire-configuration は既知 configuration への shortcut で g と parent が更新された瞬間です。maxExpansions を小さくすると incumbent を持ったまま中断し、完全 exhaust との差を比較できます。

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

理論保証。原論文で確認できた記述だけを載せています。 「不明」は「保証が無い」ではなく「原論文で未確認」の意味です。
完全性あり
最適性条件付き（eventually optimal 等。根拠欄を参照）
対象one-shot MAPF

適用範囲の注意: ★重要★ eventually optimal（OPEN を完了すれば累積 transition cost の最適解へ到達）であって、任意の有限 cutoff で最適ではない。ブラウザ版の内部目的は原論文の sum-of-loss。サイト共通 metrics.sumOfCosts とは goal 離脱を含む path で異なり得る。

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

lacam-star-ijcai-2023 p.4 Algorithm 3 lines 27-30 は OPEN 完了時を optimal、user interruption 時を sub-optimal と区別し、Theorem 1 は complete and optimal と証明。p.2 は保証対象を非負の累積 transition cost とし、実験目的は sum-of-loss。したがって optimal は OPEN exhaustion まで中断しない条件付き（eventually optimal）で、有限 cutoff やサイト表示 SOC の保証ではない。

原論文

確認済みの箇所

公開実装

最終照合日: