論文の概要: Solving Multiagent Path Finding on Highly Centralized Networks

• arxiv url: http://arxiv.org/abs/2412.09433v1
• Date: Thu, 12 Dec 2024 16:38:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-13 13:31:30.289470
• Title: Solving Multiagent Path Finding on Highly Centralized Networks
• Title（参考訳）: 高集中型ネットワーク上でのマルチエージェントパス探索の解法
• Authors: Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler, Tung Anh Vu,
• Abstract要約: Mutliagent Path Finding (MAPF) 問題とは、あるネットワーク内でエージェントの集合が従うべき軌跡を特定することである。 MAPFは、与えられたネットワークが星のようなトポロジーを持つ場合や、11ドルの葉を持つ木の場合、NPハードであることが示される。 私たちの主な貢献は、入力の増大とともにスケールする正確なアルゴリズムです。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destinations as soon as possible, but without colliding with each other. We aim to minimize the maximum time any agent takes to reach their goal, ensuring optimal path length. In this work, we complement a recent thread of results that aim to systematically study the algorithmic behavior of this problem, through the parameterized complexity point of view. First, we show that MAPF is NP-hard when the given network has a star-like topology (bounded vertex cover number) or is a tree with $11$ leaves. Both of these results fill important gaps in our understanding of the tractability of this problem that were left untreated in the recent work of [Fioravantes et al. Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology. AAAI'24]. Nevertheless, our main contribution is an exact algorithm that scales well as the input grows (FPT) when the topology of the given network is highly centralized (bounded distance to clique). This parameter is significant as it mirrors real-world networks. In such environments, a bunch of central hubs (e.g., processing areas) are connected to only few peripheral nodes.
• Abstract（参考訳）: Mutliagent Path Finding (MAPF) 問題(英語版)は、エージェントの集合ができるだけ早く所望の目的地に到達するために所定のネットワーク内で従うべき軌跡を特定することであるが、互いに衝突することはない。 エージェントが目標を達成するのに要する最大時間を最小限に抑え、最適な経路長を確保することを目的としている。 本稿では,パラメータ化複雑性の観点から,この問題のアルゴリズム的振る舞いを体系的に研究することを目的とした最近の結果のスレッドを補完する。 まず、MAPFは、与えられたネットワークが星のようなトポロジー(有界頂点被覆数)を持つ場合、または、11ドルの葉を持つ木である場合、NPハードであることが示される。 これらの結果は,近年の論文『Fioravantes et al Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology. AAAI'24]に残されている,この問題のトラクタビリティの理解における重要なギャップを埋めるものである。 それにもかかわらず、我々の主な貢献は、与えられたネットワークのトポロジが高度に集中しているときに、入力の増大(FPT)とともにスケールする正確なアルゴリズムである。 このパラメータは現実世界のネットワークを反映しているため重要である。 このような環境では、中央ハブ(例えば処理領域)の束は、ごく少数の周辺ノードにのみ接続される。

関連論文リスト

• Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures [0.0]
  パラメータ化複雑性フレームワークを用いて,通信制約問題を用いたマルチエージェントパス探索について検討する。 我々の主な貢献は、入力ネットワークの特定の構造を考える際に効率的である3つの正確なアルゴリズムである。
  論文  参考訳（メタデータ） (2024-12-11T17:17:31Z)
• 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)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• Active search and coverage using point-cloud reinforcement learning [50.741409008225766]
  本稿では,目的探索とカバレッジのためのエンドツーエンドの深層強化学習ソリューションを提案する。 RLの深い階層的特徴学習は有効であり、FPS(Fastthest Point sample)を用いることで点数を削減できることを示す。 また、ポイントクラウドに対するマルチヘッドの注意がエージェントの学習を高速化する上で有効であるが、同じ結果に収束することを示す。
  論文  参考訳（メタデータ） (2023-12-18T18:16:30Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。 接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
  論文  参考訳（メタデータ） (2022-05-11T17:43:54Z)
• Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
  アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。 バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-18T02:54:58Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Community detection using low-dimensional network embedding algorithms [1.052782170493037]
  我々はDeepWalkとnode2vecという2つの主要なアルゴリズムが、標準ネットワークモデルのためのコミュニティを回復する際の性能を厳格に理解している。 固定された共起窓を考えると、非追跡確率の低いランダムウォークを用いた node2vec は、多くのスペーサーネットワークで成功することを示す。
  論文  参考訳（メタデータ） (2021-11-04T14:57:43Z)
• PCAM: Product of Cross-Attention Matrices for Rigid Registration of Point Clouds [79.99653758293277]
  PCAMは、キー要素がクロスアテンション行列のポイントワイズ積であるニューラルネットワークである。 そこで本研究では,PCAMがステップ(a)とステップ(b)をディープネットを介して共同で解決する手法によって,最先端の成果が得られることを示す。
  論文  参考訳（メタデータ） (2021-10-04T09:23:27Z)

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

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