論文の概要: Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max
Latency
- arxiv url: http://arxiv.org/abs/2005.02530v3
- Date: Tue, 14 Jul 2020 02:39:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 14:33:53.059972
- Title: Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max
Latency
- Title（参考訳）: ミニマックスレイテンシを用いたマルチロボットパトロールスケジューリングの近似アルゴリズム
- Authors: Peyman Afshani, Mark De Berg, Kevin Buchin, Jie Gao, Maarten Loffler,
Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang
- Abstract要約: 我々は、メートル法空間内の所定の$n$のサイトを訪れるために、$k$ロボットのパトロールスケジュールを見つけることの問題を考察する。
それぞれのロボットの最大速度は同じで、その目標は、どのサイトでも最大遅延を最小化することだ。
我々は,各サイトにおける最大重量と最小重量をそれぞれ$O(k2 log fracw_max$)と$w_min$の近似係数を持つa-timeアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 8.115135096974047
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding patrol schedules for $k$ robots to visit a
given set of $n$ sites in a metric space. Each robot has the same maximum speed
and the goal is to minimize the weighted maximum latency of any site, where the
latency of a site is defined as the maximum time duration between consecutive
visits of that site. The problem is NP-hard, as it has the traveling salesman
problem as a special case (when $k=1$ and all sites have the same weight). We
present a polynomial-time algorithm with an approximation factor of $O(k^2 \log
\frac{w_{\max}}{w_{\min}})$ to the optimal solution, where $w_{\max}$ and
$w_{\min}$ are the maximum and minimum weight of the sites respectively.
Further, we consider the special case where the sites are in 1D. When all sites
have the same weight, we present a polynomial-time algorithm to solve the
problem exactly. If the sites may have different weights, we present a
$12$-approximate solution, which runs in polynomial time when the number of
robots, $k$, is a constant.
- Abstract（参考訳）: 我々は、メートル法空間内の所定の$n$のサイトを訪れるために、$k$ロボットのパトロールスケジュールを見つける問題を考える。
各ロボットは、同じ最大速度を持ち、そのサイトの連続訪問間の最大時間と定義されている任意のサイトの重み付けされた最大レイテンシを最小限にすることを目的としている。
問題はnp-hardであり、旅行セールスマンの問題を特別なケースとして抱えている($k=1$、すべてのサイトが同じ重量を持つ場合)。
近似係数が o(k^2 \log \frac{w_{\max}}{w_{\min}}) の多項式時間アルゴリズムを最適解に与え、そこではそれぞれ $w_{\max}$ と $w_{\min}$ が各サイトの最大重みと最小重みである。
さらに, サイトが1次元の特別な場合についても検討する。
すべてのサイトが同じ重みを持つ場合、問題を正確に解くために多項式時間アルゴリズムを示す。
サイトが異なる重みを持つ場合、12ドル程度の解が提示され、ロボットの数であるk$が一定である場合、多項式時間で実行される。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Run Time Bounds for Integer-Valued OneMax Functions [0.9012198585960443]
探索空間 $mathbbZn$ を多値決定変数 $0,ldots,r-1n$ の観点から考える。
ステップサイズ適応のRSSが$Theta(n cdot log(|a|_1))$の最適化時間を達成することを示す。
本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
論文 参考訳（メタデータ） (2023-07-21T18:49:06Z) - A Near-Linear Time Algorithm for the Chamfer Distance [21.018781726524946]
チャンファー距離は点雲間の相似性の一般的な尺度である。
1+epsilon)$-approximate アルゴリズムは,Chamfer 距離をほぼ直線走行時間で推定する。
我々の実験は、大規模な高次元データセット上では正確かつ高速であることを示した。
論文 参考訳（メタデータ） (2023-07-06T15:07:48Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling
Problem [8.115135096974047]
問題は、ロボットの最小遅延のパトロールスケジュールを計算することである。
k=1$のとき、問題は旅行セールスマン問題(TSP)と等価であり、NPハードである。
我々のアルゴリズムは実際にはユークリッド設定における一般的な問題に対するPTASである。
論文 参考訳（メタデータ） (2022-03-14T16:54:33Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳（メタデータ） (2021-03-24T10:11:49Z) - Facility Reallocation on the Line [9.40406631624105]
我々は,$n$エージェントによって報告された位置に基づいて,施設を時間間隔で移動させる実数線上の多段施設再配置問題を考える。
再配置アルゴリズムの目的は、社会コストを最小化することであり、すなわち、施設と全てのエージェントのあらゆる段階の合計距離の合計と、施設を移動させるコストを最小化することである。
論文 参考訳（メタデータ） (2021-03-23T23:48:45Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。