論文の概要: Fast Ergodic Search with Kernel Functions
- arxiv url: http://arxiv.org/abs/2403.01536v2
- Date: Wed, 22 Jan 2025 17:06:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-23 13:28:20.906468
- Title: Fast Ergodic Search with Kernel Functions
- Title（参考訳）: カーネル関数を用いた高速エルゴード探索
- Authors: Max Muchen Sun, Ayush Gaggar, Peter Trautman, Todd Murphey,
- Abstract要約: カーネルベースのエルゴード計量を開発し、ユークリッド空間からリー群へ一般化する。
非線形システムに対するカーネルエルゴード計量の1次最適条件を導出する。
総合的な数値ベンチマークにより、提案手法は最先端のアルゴリズムよりも少なくとも2桁高速であることが示された。
- 参考スコア（独自算出の注目度）: 0.4499833362998487
- License:
- Abstract: Ergodic search enables optimal exploration of an information distribution while guaranteeing the asymptotic coverage of the search space. However, current methods typically have exponential computation complexity in the search space dimension and are restricted to Euclidean space. We introduce a computationally efficient ergodic search method. Our contributions are two-fold. First, we develop a kernel-based ergodic metric and generalize it from Euclidean space to Lie groups. We formally prove the proposed metric is consistent with the standard ergodic metric while guaranteeing linear complexity in the search space dimension. Secondly, we derive the first-order optimality condition of the kernel ergodic metric for nonlinear systems, which enables efficient trajectory optimization. Comprehensive numerical benchmarks show that the proposed method is at least two orders of magnitude faster than the state-of-the-art algorithm. Finally, we demonstrate the proposed algorithm with a peg-in-hole insertion task. We formulate the problem as a coverage task in the space of SE(3) and use a 30-second-long human demonstration as the prior distribution for ergodic coverage. Ergodicity guarantees the asymptotic solution of the peg-in-hole problem so long as the solution resides within the prior information distribution, which is seen in the 100% success rate.
- Abstract（参考訳）: エルゴディック探索は,検索空間の漸近的カバレッジを確保しつつ,情報分布の最適探索を可能にする。
しかし、現在の方法は通常、探索空間次元において指数計算の複雑さを持ち、ユークリッド空間に制限される。
本稿では,計算効率の良いエルゴード探索手法を提案する。
私たちの貢献は2倍です。
まず、カーネルベースのエルゴード計量を開発し、ユークリッド空間からリー群へ一般化する。
提案した計量は、探索空間次元の線形複雑性を保証しながら、標準エルゴード計量と整合性があることを正式に証明する。
次に、非線形システムに対するカーネルエルゴード計量の1次最適条件を導出し、効率的な軌道最適化を実現する。
総合的な数値ベンチマークにより、提案手法は最先端のアルゴリズムよりも少なくとも2桁高速であることが示された。
最後に,ペグ・イン・ホール・イン・ホール・イン・イン・イン・イン・イン・イン・インサート・タスクを用いて提案手法を実証する。
本稿では,SE(3)の空間におけるカバレッジタスクとして問題を定式化し,エルゴディックカバレッジの事前分布として30秒の人間による実演を用いた。
エルゴディディティは、その解が100%の成功率で見られる以前の情報分布内にある限り、ペグ・イン・ホール問題の漸近解を保証する。
関連論文リスト
- A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
ストロースト文字列問題(Closest String Problem)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。
本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。
第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
論文 参考訳（メタデータ） (2024-07-17T21:26:27Z) - l1-norm regularized l1-norm best-fit lines [3.0963566281269594]
簡単な比率とソート手法を用いた新しいフィッティング法を提案する。
提案アルゴリズムは、O$(n2 m log n)$の最悪の時間複雑性を示し、ある場合にはスパース部分空間に対する大域的最適性を達成する。
論文 参考訳（メタデータ） (2024-02-26T16:30:58Z) - AdaSub: Stochastic Optimization Using Second-Order Information in
Low-Dimensional Subspaces [0.0]
本稿では,低次元部分空間における2階情報に基づく探索方向の探索アルゴリズムであるAdaSubを紹介する。
一階法と比較して、二階法は収束特性が優れているが、繰り返しごとにヘッセン行列を計算する必要があるため、計算コストが過大になる。
予備的な数値結果から、AdaSubは所定の精度に達するのに必要なイテレーションの時間と回数で、一般的なイテレーションを超越していることが示される。
論文 参考訳（メタデータ） (2023-10-30T22:24:23Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Structural Kernel Search via Bayesian Optimization and Symbolical
Optimal Transport [5.1672267755831705]
ガウスのプロセスでは、カーネルの選択は重要なタスクであり、しばしば専門家が手動で行う。
本稿では,カーネル空間を包含する新しい効率的な探索法を提案する。
論文 参考訳（メタデータ） (2022-10-21T09:30:21Z) - On the Second-order Convergence Properties of Random Search Methods [7.788439526606651]
本研究では,2次情報に依存しない標準的なランダム検索手法が2次定常点に収束することを証明する。
本稿では,関数評価のみに依存する負曲率の新しい変種を提案する。
論文 参考訳（メタデータ） (2021-10-25T20:59:31Z) - Sequential Subspace Search for Functional Bayesian Optimization
Incorporating Experimenter Intuition [63.011641517977644]
本アルゴリズムは,実験者のガウス過程から引き出された一組の引き数で区切られた関数空間の有限次元ランダム部分空間列を生成する。
標準ベイズ最適化は各部分空間に適用され、次の部分空間の出発点(オリジン)として用いられる最良の解である。
シミュレーションおよび実世界の実験,すなわちブラインド関数マッチング,アルミニウム合金の最適析出強化関数の探索,深層ネットワークの学習速度スケジュール最適化において,本アルゴリズムを検証した。
論文 参考訳（メタデータ） (2020-09-08T06:54:11Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。
我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。
また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
論文 参考訳（メタデータ） (2020-02-16T09:01:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。