論文の概要: Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of
Treelike Topology
- arxiv url: http://arxiv.org/abs/2312.09646v1
- Date: Fri, 15 Dec 2023 09:42:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-18 16:28:07.839122
- Title: Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of
Treelike Topology
- Title（参考訳）: マルチエージェントパスファイニングのための厳密なアルゴリズムと下限:木状トポロジーのパワー
- Authors: Foivos Fioravantes, Du\v{s}an Knop, Jan Maty\'a\v{s}
K\v{r}i\v{s}\v{t}an, Nikolaos Melissinos, Michal Opler
- Abstract要約: 我々は、与えられたグラフの$G上の一組の$kエージェントの経路を効率的に見つけることに重点を置いており、各エージェントはそのソースからターゲットへの経路を求める。
解の質の重要な尺度は提案されたスケジュールの長さ$ell$、すなわち最長経路の長さである。
MAPFは$G$+$ell$に対してW[1]ハードであり、FPTは$G$+$ell$であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the Multiagent Path Finding problem (MAPF for short), we focus on
efficiently finding non-colliding paths for a set of $k$ agents on a given
graph $G$, where each agent seeks a path from its source vertex to a target. An
important measure of the quality of the solution is the length of the proposed
schedule $\ell$, that is, the length of a longest path (including the waiting
time). In this work, we propose a systematic study under the parameterized
complexity framework. The hardness results we provide align with many
heuristics used for this problem, whose running time could potentially be
improved based on our fixed-parameter tractability results.
We show that MAPF is W[1]-hard with respect to $k$ (even if $k$ is combined
with the maximum degree of the input graph). The problem remains NP-hard in
planar graphs even if the maximum degree and the makespan$\ell$ are fixed
constants. On the positive side, we show an FPT algorithm for $k+\ell$.
As we delve further, the structure of~$G$ comes into play. We give an FPT
algorithm for parameter $k$ plus the diameter of the graph~$G$. The MAPF
problem is W[1]-hard for cliquewidth of $G$ plus $\ell$ while it is FPT for
treewidth of $G$ plus $\ell$.
- Abstract（参考訳）: マルチエージェントパス探索問題(MAPF: Multiagent Path Finding problem)では、各エージェントが元の頂点からターゲットへの経路を求める場合、与えられたグラフ上の1組の$k$エージェントの非衝突経路を効率的に見つけることに重点を置いている。
解の質に関する重要な尺度は、提案されたスケジュール$\ell$の長さ、すなわち最長経路の長さ(待ち時間を含む)である。
本研究では,パラメータ化複雑性フレームワークに基づく体系的研究を提案する。
この問題に使用される多くのヒューリスティックと整合して提供する硬度結果は、固定パラメータのトラクタビリティ結果に基づいて実行時間を改善できる可能性がある。
MAPF は$k$ に対して W[1]-ハードであることが示される($k$ と入力グラフの最大次数の組み合わせであっても)。
この問題は、最大次数とmakepan$\ell$が固定定数であっても、平面グラフにおいてnp-hardのままである。
正の面では、$k+\ell$に対するFPTアルゴリズムを示す。
さらに詳しく調べると、~$G$の構造が現れます。
パラメータ$k$とグラフの直径~$G$に対してFPTアルゴリズムを与える。
MAPF 問題は、$G$ + $\ell$ のクリッド幅に対して W[1]-ハードであり、$G$ + $\ell$ のツリー幅に対して FPT である。
関連論文リスト
- Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。
最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。
2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
論文 参考訳（メタデータ） (2024-08-19T21:30:02Z) - A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。
時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。
この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
論文 参考訳（メタデータ） (2024-06-07T11:40:54Z) - Dynamic algorithms for k-center on graphs [3.568439282784197]
エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。
完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
論文 参考訳（メタデータ） (2023-07-28T13:50:57Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。
我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文 参考訳（メタデータ） (2020-12-02T15:32:52Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。