密集倉庫におけるオンライン複数エージェントのピックアップ・デリバリーのための固定避難所予約

本論文は、密集倉庫におけるオンラインMulti-Agent Pickup and Delivery (MAPD)問題を扱い、各エージェントが固定のSafe Haven（通常は開始セル）を所有し、他のエージェントはそれを障害物として扱う契約を提案する。有限タスクリリースに対して、Haven-Reachabilityと明示的な計画/進行の仮定の下で全タスク完了を保証する。実装としてSafe-Haven Retreat Planner (SHARP)を提案し、混雑した単一レーン通路や行き止まり、ツリー状ガイドパスを含む環境で有効性を示す。

既存のMAPD保証は、追加の待機ポイントや二重連結トポロジーに依存することが多く、密集倉庫の単一レーン通路や行き止まり、ツリー状ガイドパスでは失敗する可能性がある。本研究は、固定Haven予約という単純な契約を導入し、そのようなレイアウトでもタスク完了を保証する点が新しい。また、既存のTPやPIBTファミリーと比較して、ロバスト性（100%成功率）を達成する。

手法の核は、各エージェントが固定のSafe Havenを持ち、他のエージェントはそれをブロックされたものとして扱う契約である。SHARPは、ビジーまたは退避中のエージェントを衝突のない予約済みルートでHavenまで導く。計画は、Haven-Reachability条件と明示的な計画/進行の仮定に基づく。また、退避中の再割り当て（mid-retreat reassignment）を可能にする点も特徴的である。

代表的なMAPDベースライン（Token Passing (TP)、Priority Inheritance with Backtracking (PIBT)、PIBT with Temporary Priority and Temporary Avoidance (PIBTTP-TA)）と比較し、二重連結メインエリアと付属ツリーを持つ環境で実験した。ロバスト性スイープでは、SHARPのみが全テスト構成で100%成功した。また、ツリー状レイアウトでは中央集権的計画コストが大幅に増加した。TPスタイルの固定ホームリターン比較実験では、ロバスト性が回復し、固定リターンがロバスト性の中心メカニズムであることを示唆した。さらに、退避中の再割り当てを無効にすると、高負荷ツリー条件でサービス時間が1.89倍、メイクスパンが1.53倍悪化した。

議論として、固定Haven契約はロバスト性を提供するが、中央集権的計画コストが高いことが挙げられる。また、退避中の再割り当てが性能に重要であることが示された。しかし、要旨からは、Haven-Reachability条件の具体的な定義や、他の環境での一般化可能性、実世界での適用可能性などは不明である。

要旨で参照されている研究は、Token Passing (TP)、Priority Inheritance with Backtracking (PIBT)、PIBT with Temporary Priority and Temporary Avoidance (PIBTTP-TA)である。次に読むべき論文としては、これらのベースライン手法の詳細を扱った論文が挙げられる。