論文の概要: 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つの方向を保持する硬さを補完する。
この結果は最適解の構造に新しい光を当て、一般的な問題に対するアルゴリズム設計を導くのに役立つかもしれない。
関連論文リスト
- Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
多エージェント経路探索(MAPF)は、衝突しない複数のエージェントの経路を見つける問題である。
MAPFの最適解を見つけることはNP-Hardであるが、現代の最適解法は数百のエージェントにスケールでき、場合によっては数千までスケールできる。
このエンコーディングが既存のエンコーディングと効果的に結合できることを示し、その結果、グラフ埋め込みによるMAPFアルゴリズム選択と呼ばれる新しいASメソッドが実現された。
論文 参考訳（メタデータ） (2024-06-16T07:41:58Z) - Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。
我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。
古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
論文 参考訳（メタデータ） (2024-04-25T07:41:47Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Improved Anonymous Multi-Agent Path Finding Algorithm [3.694001372535405]
エージェントの集合をグラフに限定する匿名多エージェントパスフィンディング(AMAPF)問題を考える。
我々は,検索空間を探索するアイデアを,個別の検索状態ではなく,一括して考えることによって活用する,特定の検索アルゴリズムを提案する。
その結果、AMAPFソルバは最先端の競合に比べて優れた性能を示し、30秒未満で利用可能なすべてのMAPFインスタンスを解決できる。
論文 参考訳（メタデータ） (2023-12-17T00:49:30Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search [43.40580211016752]
マルチエージェントパス発見(mapf)は,協調エージェントのチームに対して,衝突のないパスを計画することを求める課題である。
MAPFが解決しにくい理由の1つは、ペアワイズ対称性と呼ばれる現象によるものであることを示しています。
対称性の発生を効率的に検出し、特殊な制約を用いて解決する様々な推論手法を提案します。
論文 参考訳（メタデータ） (2021-03-12T07:27:35Z) - Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy
Minimization [96.1052289276254]
離散的グラフィカルモデルにおける最大姿勢推定問題と、二重ブロック座標法に基づく解法について考察する。
既存のすべてのソルバをひとつのフレームワークにマッピングし、設計原則をより深く理解できるようにします。
論文 参考訳（メタデータ） (2020-04-16T15:49:13Z) - sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission
Planning Problems [2.191505742658975]
いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。
本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。
このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
論文 参考訳（メタデータ） (2020-02-20T17:07:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。