論文の概要: Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
- arxiv url: http://arxiv.org/abs/2412.08556v2
- Date: Thu, 12 Dec 2024 09:51:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-13 13:31:34.843958
- Title: Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
- Title（参考訳）: 木状構造上の通信制約を考慮したマルチエージェントパス探索のための厳密なアルゴリズム
- Authors: Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler,
- Abstract要約: パラメータ化複雑性フレームワークを用いて,通信制約問題を用いたマルチエージェントパス探索について検討する。
我々の主な貢献は、入力ネットワークの特定の構造を考える際に効率的である3つの正確なアルゴリズムである。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated by a measure known as the makespan of the proposed solution. This is the setting studied in the Multiagent Path Finding problem. In this work, we additionally provide the agents with a way to communicate with each other. Due to size constraints, it is reasonable to assume that the range of communication of each agent will be limited. What should be the trajectories of the agents to, additionally, maintain a backbone of communication? In this work, we study the Multiagent Path Finding with Communication Constraint problem under the parameterized complexity framework. Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network. We provide such algorithms for the case when the communication range and the number of agents (the makespan resp.) are provided in the input and the network has a tree topology, or bounded maximum degree (has a tree-like topology, i.e., bounded treewidth resp.). We complement these results by showing that it is highly unlikely to construct efficient algorithms when considering the number of agents as part of the input, even if the makespan is $3$ and the communication range is $1$.
- Abstract（参考訳）: 複数のエージェントが最適な方法でネットワークを経由し、各エージェントが衝突を避けながら終了位置に向かって移動しなければならないシナリオを考える。
最適に、我々はできるだけ早く、提案された解のメイスパンと呼ばれる尺度で評価する。
これはMultiagent Path Finding問題で研究された設定である。
この作業では、エージェントに相互に通信する方法も提供します。
サイズ制約のため、各エージェントの通信範囲が制限されると仮定することは妥当である。
さらに、通信のバックボーンを維持するために、エージェントの軌跡はどうあるべきか?
本研究では,パラメータ化複雑性フレームワークに基づくマルチエージェントパス探索と通信制約問題について検討する。
我々の主な貢献は、入力ネットワークの特定の構造を考える際に効率的である3つの正確なアルゴリズムである。
入力に通信範囲とエージェント数(mespan resp.)が設けられ、ネットワークがツリートポロジまたは有界最大度(木のようなトポロジ、すなわち有界木幅Resp.)を持つ場合のアルゴリズムを提供する。
通信範囲が$$$$3であっても,入力の一部としてエージェントの数を考えると,効率的なアルゴリズムを構築することは極めて不可能であることを示す。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳（メタデータ） (2025-02-14T15:21:27Z) - Solving Multiagent Path Finding on Highly Centralized Networks [0.0]
Mutliagent Path Finding (MAPF) 問題とは、あるネットワーク内でエージェントの集合が従うべき軌跡を特定することである。
MAPFは、与えられたネットワークが星のようなトポロジーを持つ場合や、11ドルの葉を持つ木の場合、NPハードであることが示される。
私たちの主な貢献は、入力の増大とともにスケールする正確なアルゴリズムです。
論文 参考訳（メタデータ） (2024-12-12T16:38:25Z) - 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) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Communication-Efficient Topologies for Decentralized Learning with
$O(1)$ Consensus Rate [35.698182247676414]
分散最適化は分散学習における新たなパラダイムであり、エージェントは中央サーバを使わずにピアツーピア通信によってネットワーク全体のソリューションを実現する。
エージェントの情報が混在する速度によって,ネットワーク全体のソリューションに到達するためのイテレーションの総数が影響を受けることを示す。
本稿では,(ほぼ)一定の等級とネットワークサイズに依存しないコンセンサス率を有する新しいトポロジであるEquiTopoを提案する。
論文 参考訳（メタデータ） (2022-10-14T15:02:01Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。
この問題をある程度緩和する手法を提案する。
論文 参考訳（メタデータ） (2021-08-11T10:42:11Z) - Scalable Anytime Planning for Multi-Agent MDPs [37.69939216970677]
動的協調を必要とする大規模マルチエージェント連続的決定問題に対するスケーラブルな木探索計画アルゴリズムを提案する。
提案アルゴリズムは,モンテカルロ木探索 (MCTS) を用いたオンライン計画,協調グラフを用いた局所エージェント相互作用の因子表現,および協調行動選択のための反復マックスプラス法からなる。
論文 参考訳（メタデータ） (2021-01-12T22:50:17Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。