study-mapfMAPF / Lifelong MAPF / MAPD 教材

LNS-wPBSLNS-wPBS

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

LNS-PBS の windowed 版。効率を重視するが完全性保証はない。

概要

LNS-wPBS は task sequence を LNS で組み替え、windowed PBS で短い先読みを行う手法です。論文は LNS-PBS より効率・安定性を重視する一方、完全性の保証を明示していません[mg-mapd-iros-2022, §Abstract, p.1]。

中心となるアイデア

次に進む window だけを衝突解消の対象にします。goal までの探索を w で打ち切るのではなく、 full path を求めたうえで最初の w step だけを予約し、w step 実行後に再計画します。 w は extra.windowSize（無ければ planningWindow、既定 10）で指定します。 sequence assignment と multi-goal の表現は LNS-PBS と同じです。

アルゴリズムの手順

  1. release 済み task を sequence に挿入する。
  2. window の衝突を避ける path を PBS で作る。
  3. window 分だけ実行し、必要なら再計画する。

よくある誤解

速い、または average service time が小さいことは「必ず解ける」ことを意味しません。LNS-wPBS の guarantees.complete は false です。

実験してみる

mapd-well-formed と MG-MAPD: multi-goal を LNS-PBS と並べ、残存衝突が 0 でも完全性保証が無いことを保証表と一緒に確認してください。

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

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

適用範囲の注意: LNS-PBS の windowed 版。論文が明示するように完全性保証は無く、良い service time は保証を意味しない。サイト版は windowed planning の教育用骨格である。

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

mg-mapd-iros-2022 p.1 abstract: LNS-wPBS provides no completeness guarantee.

原論文

公開実装

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