論文の概要: Divide and Collapse: MAPF-Collapse via Exact Decomposition into Independent Sub-Instances

• arxiv url: http://arxiv.org/abs/2609.39559v1
• Date: Wed, 30 Sep 2026 11:57:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.634317
• Title: Divide and Collapse: MAPF-Collapse via Exact Decomposition into Independent Sub-Instances
• Title（参考訳）: 分割と崩壊: MAPF-Collapse via Exact Decomposition into independent sub-Instances
• Abstract要約: MAPFC(Multi-Agent Path Finding, MAPF)計画の最適化後の課題について検討する。 このNPハード問題は、最先端解法(SOTA)を使用すると自然に発生する。 我々は、非常に軽量な解決器を、ジャッジライトより1,900times$$で導入する。
• 参考スコア（独自算出の注目度）: 7.716156977428555
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we study the problem of MAPFC, a post-optimization step for Multi-Agent Path Finding (MAPF) plans where we are given a feasible plan produced by a modern MAPF solver and are tasked with removing avoidable moves while preserving feasibility. This NP-hard problem naturally arises when using learning-based state-of-the-art (SOTA) solvers which construct plans that contain redundant moves that can be removed. Recently, Tang et al. presented Judgelight, which uses Integer Linear Programming (ILP) to solve MAPFC. Importantly, the ILP is constructed over all agents jointly, so its cost is governed by the full instance rather than by the small coupled residue that actually requires joint reasoning. Our key insight, motivating this work, is that MAPFC instances naturally decompose into independent sub-problems, most of which involve a single agent and can be solved without any inter-agent reasoning. To this end, we first identify which agents need to coordinate their motion and partition the instance into sub-problems accordingly. For the cases where no coordination is required, we introduce an extremely lightweight solver that is $\approx\!1{,}900\times$ faster than Judgelight. For cases where coordination is required, Judgelight can be used but we introduce an alternative CBS-like solver which is more efficient on easier problems. The resulting framework is exact, uses no commercial ILP solver, and matches Judgelight's quality while running substantially faster on the coordination-light majority of instances; on the coordination-heavy instances we propose a regime-aware hybrid planner that falls back to Judgelight. Over all benchmarks tested, this planner achieves a median $10.5\times$ per-instance speedup over Judgelight.
• Abstract（参考訳）: 本研究では, MAPFCの課題について検討し, 現時点のMAPFソルバによって実現可能な計画が与えられ, 実現可能性を維持しつつ回避可能な動きを除去するタスクが課されるマルチエージェントパス探索(MAPF)計画の最適化後のステップである。 このNPハード問題は、除去可能な冗長な動きを含む計画を構築する学習ベース最先端解決器(SOTA)を使用することで自然に発生する。 近年,TangらはMAPFCの解法としてILP(Integer Linear Programming)を用いたジャッジライトを発表した。 重要なことに、ILPは全てのエージェントに共同で構築されるので、そのコストは、実際に共同推論を必要とする小さな結合残基ではなく、全インスタンスによって管理される。 この研究の動機となる重要な洞察は、MAPFCインスタンスが自然に独立したサブプロブレムに分解され、その多くは単一のエージェントを含み、エージェント間推論なしで解決できるということである。 この目的のために、まず、どのエージェントがそれらの動作を調整する必要があるかを特定し、それに応じてインスタンスをサブプロブレムに分割する。 調整が不要な場合、非常に軽量で$\approx\! 1{,}900\times$ judgelightより速い。 調整が必要な場合には、より簡単な問題に対してより効率的なCBSライクな解法を導入する。 結果のフレームワークは正確で、商用のILP解決器は使用せず、コーディネーションライトの大多数のインスタンスでかなり高速に動作しながら、ジャッジライトの品質にマッチします。 テストされたすべてのベンチマークにおいて、このプランナーはジャッジライトよりも中央値の10.5\times$インスタンスあたりのスピードアップを達成した。

関連論文リスト

• Alternating Target-Path Planning for Scalable Multi-Agent Coordination [11.193867567895353]
  並列ターゲット割り当てとパスフィンディング問題は、マルチエージェントパスフィンディングを拡張する。 本稿では,パスフィニングから目的の割り当てを分離する反復的精錬フレームワークを提案する。 これは現実のセットアップに適した実用的で大規模なTAPFに向けた確かなステップである。
  論文  参考訳（メタデータ） (2026-05-08T13:50:51Z)
• Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing [10.510038680299223]
  MAPF(Multi-Agent Path Finding)は、倉庫の自動化と複数ロボットの協調におけるNPハード問題である。 本稿では、MAPFソルバが実行可能なスケジュールを生成した後、軌道品質を向上させるポスト最適化層であるジャッジライトを提案する。
  論文  参考訳（メタデータ） (2026-01-27T09:20:14Z)
• Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines [9.228609005424348]
  時間に敏感なアプリケーションのための実行インフォームドMAPF計画フレームワークであるREMAPを提案する。 我々のフレームワークは提案したExecTimeNetを統合し、計画されたパスに基づいて実行時間を正確に推定する。 実験の結果、REMAPはベースライン法よりもソリューション品質を最大20%改善することがわかった。
  論文  参考訳（メタデータ） (2025-11-26T20:08:52Z)
• Efficient LLM Collaboration via Planning [56.081879390960204]
  小規模で大規模なモデルでは、プランナーと実行担当者として交代で行動し、タスクを協調的に解決するために、多段階のカスケードでプランを交換する。 私たちはCOPEが大規模プロプライエタリモデルに匹敵するパフォーマンスを実現し,推論APIのコストを大幅に削減できることを実証した。
  論文  参考訳（メタデータ） (2025-06-13T08:35:50Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding [9.2127262112464]
  MAPF(Multi-Agent Path Finding)は、各開始点から目標地点までの複数のエージェントに対する競合のないパスを見つける。 我々は、この学習に基づくシングルエージェントプランナーをM*に統合することにより、LM*と呼ばれる新しいマルチエージェントプランナーを開発する。 以上の結果から,M* と比較した場合,LM* はコンフリクトが少なく,高速に動作し,高い成功率を享受できることがわかった。
  論文  参考訳（メタデータ） (2021-09-29T20:01:04Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。 本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。 当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
  論文  参考訳（メタデータ） (2020-04-17T14:56:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。