=== 要約 ===

技術要約：制約のある倉庫におけるマルチエージェント・ピックアップ＆デリバリーのための動的なヘイブン選択

問題提起

本論文は、単一エージェント幅の通路、行き止まりのワークステーション、およびツリー状のガイドパスを特徴とする、制約のある倉庫環境における**マルチエジェント・ピックアップ＆デリバリー（MAPD）**問題に取り組んでいる。このようなレイアウトでは、標準的なマルチエージェント・パス・ファインディング（MAPF）の仮定（例：well-formednessやbiconnectivity）がしばしば成立せず、待機中または帰還中のエージェントが狭い通路を塞いでしまうデッドロックが発生する可能性がある。

有限リリース完了性（finite-release completeness）（放出されたすべてのタスクが最終的に配送されること）を保証するために、先行研究では**Safe HAven Retreat Planner (SHARP)*が導入された。SHARPは、コミットされた各タスクの経路と、エージェントの専用の初期位置*（「ヘイブン（避難所）」）への検証済み退避経路をペアにする。これは安全性を確保する一方で、退避先が実行期間中固定されているという硬直性の問題を抱えている。エージェントが異なる安全な待機場所の近くで配送を完了した場合でも、遠く離れた初期ヘイブンまで戻ることを強制されることがあり、不要な移動時間が発生し、メイクスパン（総所要時間）を増大させる可能性がある。

本研究が取り組む核心的な課題は、安全性の不変性を損なうことなく、エージェントの退避先を動的に変更（利用可能な近くのヘイブンを選択）する方法である。単純な切り替えアプローチは、以下の2つの失敗モードを招くリスクがある：

1. 実行安全性の違反： エージェントが物理的に出発する前に現在のヘイブンを解放してしまうことで、他のエージェントがまだ物理的に占有されている頂点を通過するように計画してしまう。
2. 予約除外の違反： エージェントが、現在は所有されていないものの、他のエージェントの将来の経路のために予約されているヘイブンを選択してしまい、頂点と時間の衝突を引き起こす。

手法：A♯ (Adaptive SHARP)

著者らは、SHARPフレームワークを拡張した動的なヘイブン選択手法である**A♯*を提案している。A♯はA探索の変種ではなく、オンラインMAPDのための適応型プランニングアルゴリズムである。

コアメカニズム

1. 動的なヘイブン選択： タスク割り当て時に、エージェントは初期ヘイブンに限定されるのではなく、配送場所への近接性に基づいて、利用可能な候補集合からターゲットとなるヘイブンを選択する。
2. 可用性テスト： 候補となるヘイブンは、以下の場合にのみ「利用可能」とみなされる：
   • 他のエージェントによって現在所有されていない（排他的集合によって確認）。
   • 他のエージェントのコミットされた将来の経路予約によって占有されていない。
3. 保留リリース規則（Pending-Release Rule）： 実行安全性の違反を防ぐため、エージェントが現在占有しているヘイブンから切り替える場合、エージェントがその頂点から物理的に出発するまで、古いヘイブンはエージェントの排他的集合（保護対象）内に留まる。これにより、頂点の所有権ビューと実行ビューの一貫性が保たれる。
4. 原子的な状態遷移（Atomic State Transition）： 経路、ヘイブン割り当て、および排他的集合の所有権の更新は、単一の原子的な状態遷移として行われる。これにより、パスはコミットされているが所有権がまだ転送されていないという、部分的な状態を他のエージェントが観測することを防ぐ。

アルゴリズムの流れ

• 割り当てループ： 各タイムステップにおいて、アルゴリズムは対象となる（アイドル状態または退避中の）エージェントを反復処理する。
• 貪欲な選択： 各エージェントに対し、直近の保留タスクと、直近の利用可能なヘイブンを選択する。
• 検証： Safe Interval Path Planning (SIPP) を用いて、完全な経路（現在地 → ピックアップ → デリバリー → 選択されたヘイブン）を検証する。
• コミットメント： 有効である場合、エージェントの将来の予約は原子的に置き換えられ、ヘイブン割り当てが更新され、切り替えが発生した場合には保留リリース規則が適用される。

主な貢献

1. A♯アルゴリズム： 可用性チェック機能付きの保留リリース所有権転送プロトコルを備えた、動的なヘイブン拡張型のセーフヘイブン退避プランニング。
2. 理論的保証： 著者らは、明示的なヘイブン構造条件（接続されたタスクコア、コアに隣接するヘイブン、コア内のタスクエンドポイント）およびSIPPの仮定の下で、以下を証明している：
   • 不変性の保持： 動的な更新は、排他性（複数のエージェントが一つのヘイブンを共有しないこと）および予約の不変性を維持する。
   • 有限リリース完了性： いかなる有限リリースシーケンスにおいても、すべてのタスクが配送される。
3. 実証的評価： 14,400のマップ・エージェント・レート・シードの組み合わせを用いた計72,000回の実行による広範なテスト。

実験結果

評価では、固定ヘイブンのSHARPベースライン、および他の構造的仮定に基づく手法（TP, PIBT, PIBTTP-TA）に対し、4つのマップタイプ（well-formed、narrow-biconnected、narrow-biconnected with dead ends、およびtree-structured map）を用いてA♯を比較した。

• 成功率： SHARPとA♯は共に、テストされたすべての構成において100%の成功率を達成し、動的なヘイブン転送がセーフヘイブン退避メカニズムの堅牢性を損なわないことを確認した。対照的に、well-formednessやbiconnectivityの仮定に依存する手法は、制約のあるマップ上で失敗した。
• メイクスパンの改善：
  • ツリーマップ（高度に制約された環境）において、A♯はSHARPと比較して中央値のメイクスパンを**16.7%**削減した。
  • 138の「ヘイブン余剰」構成（$|A| < |H|$）において、A♯は107の構成で有意に優れており、Holm補正後もSHARPより著しく劣ることはなかった。
  • 公開されているwell-formedベンチマークでは、固定ヘイブンが開放的なレイアウトにおいて不利になりにくいことが予想通りであるため、改善は緩やかであった（~1.8%）。
• サービス時間： A♯はツリーマップにおいて概してサービス時間を改善したが、narrow-biconnectedマップでは結果が混在した。一部のケースでは、貪欲な「最近のヘイブン」ヒューリスティックが局所的な混雑を引き起こし、固定ヘイブンベースラインと比較してサービス時間がわずかに増加した。著者らは、これはヒューリスティックの限界であり、所有権転送プロトコルの失敗ではないと述べている。
• 計算時間： A♯が計算コストを一貫して高くすることはない。多くの場合、短い退避コミットメントが追加の可用性チェックのコストを相殺した。

意義と主張

本論文は、狭い通路や行き止まりが多いレイアウトにおいて、安全性や完了性の保証を崩すことなく、完了指向のセーフヘイブン退避プランニングを動的にできることを主張している。

• 安全性 vs 柔軟性： 本研究は、安全性を確保するために退避先を静的にしておく必要はないことを示している。提案された所有権転送プロトコルは、オンラインのタスク割り当て、将来の経路予約、および排他的な待機場所の所有権をうまく結合させている。
• 実用的影響： この手法は、固定ヘイブンが不要な移動を強いる、空間効率の高い倉庫レイアウト（例：ツリー状のガイドパス）において特に効果的である。
• ヒューリスティクスに関する謙虚な姿勢： 著者らは、性能向上は動的な選択能力と最近のヘイブンヒューリスティックの組み合わせによるものであることを明言している。最近のヘイブンヒューリスティックは混雑回避には最適ではないことを認めており、将来的に、同じ可用性とコミットメントのセマンティクスに従う限り、学習型または最適化ベースのセレクターをサポートできる可能性を示唆している。
• 限界： 保証は、決定論的な離散時間実行と中央集約型の予約テーブルに基づいている。本論文は、実行の遅延、位置推定誤差、または計画されたチーム外の動的な障害物に対する堅牢性については主張していない。また、本フレームワークは、明確に区別されたヘイブン（$|A| \le |H|$）を想定している。より高密度なフリートには、カバーされていない共有パーキングメカニズムが必要となる。