LNS-PBSLNS-PBS

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

LNS で task sequence を組み替え、PBS で multi-goal path を計画する MAPD 手法。

概要

LNS-PBS は、エージェントへ task の列を割り当て、列に含まれる複数 goal を順に訪れる path を PBS で求める MAPD 手法です。多目的地を扱う MG-MAPD にも拡張されます[mg-mapd-iros-2022, §Abstract, p.1]。

まず何がうれしいのか

次の task まで見て割り当てるため、一件ずつ割り当てる方法より将来の移動を考慮できます。well-formed MG-MAPD では完全性が定理として述べられています[mg-mapd-iros-2022, Theorem 1, p.5]。

中心となるアイデア

task sequence を初期化し、近傍の task を一度外して別の agent・位置へ再挿入します。各列には dummy endpoint を末尾に置き、PBS の優先順に従って他 agent の path と衝突しないように計画します。

アルゴリズムの手順

release 済み task を決定的な初期 sequence に入れる。
各 agent の pickup と goal 列を順序付き時空間 A* で計画する。
近傍を破壊・修復し、改善した sequence を採用する。
1 timestep 進め、完了した task を sequence から外す。

データ構造

サイト版は assignSequence、carryingTasks、token path と reservation table を使います。TaskSpec.goals が未指定なら旧 MAPD の delivery 1 点です。

よくある誤解

LNS-PBS の完全性は well-formed と finite task set の条件付きです。
PBS 単体が完全になった、という意味ではありません。dummy path との組合せが前提です。
objective として表示する average service time が小さい実験結果は、最適性の保証ではありません。

実験してみる

MG-MAPD: multi-goal を選び、LNS-PBS の assign-task、expand-node、update-token と、平均 service time / throughput を確認してください。

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

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

適用範囲の注意: 多目的地 MAPD 向け。論文の完全性は well-formed MG-MAPD と dummy path の前提に限られる。サイト版は task sequence と順序付き時空間 A* を示す教育用骨格で、論文の全 anytime LNS 近傍と dummy-path 証明を再現していない。

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

mg-mapd-iros-2022 p.5 Theorem 1: Given a well-formed MG-MAPD instance with a finite number of tasks, LNS-PBS is guaranteed to find collision-free paths in finite time that allow each agent to execute all tasks assigned to it.

原論文

Multi-Goal Multi-Agent Pickup and Delivery
Qinghong Xu, Jiaoyang Li, Sven Koenig ほか (2022) Multi-Goal Multi-Agent Pickup and Delivery. IEEE/RSJ IROS 2022
DOI外部リンクのみPDF 非同梱

公開実装

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