論文の概要: Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids
- arxiv url: http://arxiv.org/abs/2305.16303v1
- Date: Thu, 25 May 2023 17:56:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 13:13:05.097367
- Title: Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids
- Title（参考訳）: 2次元格子上のマルチエージェントパスの微細粒度解析
- Authors: Tzvika Geft
- Abstract要約: エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。
フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。
この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
- 参考スコア（独自算出の注目度）: 0.190365714903665
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Path Finding (MAPF) is a fundamental motion coordination problem
arising in multi-agent systems with a wide range of applications. The problem's
intractability has led to extensive research on improving the scalability of
solvers for it. Since optimal solvers can struggle to scale, a major challenge
that arises is understanding what makes MAPF hard. We tackle this challenge
through a fine-grained complexity analysis of time-optimal MAPF on 2D grids,
thereby closing two gaps and identifying a new tractability frontier. First, we
show that 2-colored MAPF, i.e., where the agents are divided into two teams,
each with its own set of targets, remains NP-hard. Second, for the flowtime
objective (also called sum-of-costs), we show that it remains NP-hard to find a
solution in which agents have an individually optimal cost, which we call an
individually optimal solution. The previously tightest results for these MAPF
variants are for (non-grid) planar graphs. We use a single hardness
construction that replaces, strengthens, and unifies previous proofs. We
believe that it is also simpler than previous proofs for the planar case as it
employs minimal gadgets that enable its full visualization in one figure.
Finally, for the flowtime objective, we establish a tractability frontier based
on the number of directions agents can move in. Namely, we complement our
hardness result, which holds for three directions, with an efficient algorithm
for finding an individually optimal solution if only two directions are
allowed. This result sheds new light on the structure of optimal solutions,
which may help guide algorithm design for the general problem.
- Abstract（参考訳）: MAPF(Multi-Agent Path Finding)は、多エージェントシステムにおける動作調整の基本的な問題である。
問題の難易度は、解決者のスケーラビリティを改善するための広範な研究に繋がった。
最適解法はスケールに苦しむことができるため、MAPFの難しさを理解することが大きな課題となる。
2次元格子上での時間最適MAPFの微細な複雑性解析により、この課題に対処し、2つのギャップを閉じ、新たなトラクタビリティフロンティアを同定する。
まず,2色のMAPF,すなわちエージェントが2つのチームに分けられ,それぞれがそれぞれのターゲットを持つ場合,NPハードのままであることを示す。
第二に、フロータイムの目的(コスト総和とも呼ばれる)について、エージェントが個別に最適なコストを持つソリューションを見つけることはnp困難であり、これを個別に最適なソリューションと呼ぶ。
これらのMAPF変種に対する最も厳密な結果は(非グリッド)平面グラフに対するものである。
私たちは、以前の証明を置き換え、強化し、統一する単一の硬さ構成を使います。
平面ケースの証明も従来のものよりも簡単で、最小限のガジェットを使って1つの図で完全に視覚化できると考えている。
最後に, フロータイムの目的に対して, エージェントの移動可能な方向数に基づく移動性フロンティアを確立する。
すなわち, 2つの方向のみを許せば, 個別に最適な解を求める効率的なアルゴリズムで, 3つの方向を保持する硬さを補完する。
この結果は最適解の構造に新しい光を当て、一般的な問題に対するアルゴリズム設計を導くのに役立つかもしれない。
関連論文リスト
- MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。
バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
論文 参考訳（メタデータ） (2022-02-18T02:54:58Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities [7.766921168069532]
このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。
最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
論文 参考訳（メタデータ） (2021-04-23T20:13:12Z) - Revisiting the Complexity Analysis of Conflict-Based Search: New
Computational Techniques and Improved Bounds [5.158632635415881]
最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である
CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
論文 参考訳（メタデータ） (2021-04-18T07:46:28Z) - Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search [43.40580211016752]
マルチエージェントパス発見(mapf)は,協調エージェントのチームに対して,衝突のないパスを計画することを求める課題である。
MAPFが解決しにくい理由の1つは、ペアワイズ対称性と呼ばれる現象によるものであることを示しています。
対称性の発生を効率的に検出し、特殊な制約を用いて解決する様々な推論手法を提案します。
論文 参考訳（メタデータ） (2021-03-12T07:27:35Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z) - Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。
本稿では, 競合ミラー降下法(CMD)を提案する。
特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-06-17T22:11:35Z) - Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy
Minimization [96.1052289276254]
離散的グラフィカルモデルにおける最大姿勢推定問題と、二重ブロック座標法に基づく解法について考察する。
既存のすべてのソルバをひとつのフレームワークにマッピングし、設計原則をより深く理解できるようにします。
論文 参考訳（メタデータ） (2020-04-16T15:49:13Z) - Joint Wasserstein Distribution Matching [89.86721884036021]
JDM問題(Joint Distribution matching)は、2つのドメインの関節分布を一致させるために双方向マッピングを学習することを目的としており、多くの機械学習およびコンピュータビジョンアプリケーションで発生している。
2つの領域における関節分布のワッサーシュタイン距離を最小化することにより、JDM問題に対処することを提案する。
そこで我々は,難解な問題を簡単な最適化問題に還元する重要な定理を提案し,その解法を開発した。
論文 参考訳（メタデータ） (2020-03-01T03:39:00Z) - sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission
Planning Problems [2.191505742658975]
いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。
本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。
このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
論文 参考訳（メタデータ） (2020-02-20T17:07:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。