論文の概要: Achieving Asymptotic Near-Optimality Without $δ$-Similarity

• arxiv url: http://arxiv.org/abs/2609.04464v1
• Date: Thu, 03 Sep 2026 20:46:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-07 18:15:23.817374
• Title: Achieving Asymptotic Near-Optimality Without $δ$-Similarity
• Title（参考訳）: δ$-類似性のない漸近的近接最適性を達成する
• Abstract要約: 多くのプランナーは、最適軌道に近いほぼ確実な軌道のサンプリングを証明することによって、ほぼ最適性を達成すると主張している。 本稿では、$-similarity の裏にある証明は、$-similar trajectory segments が一度サンプリングされたときに常に保持されるという未定の仮定に依存していることを示す。 しかし、クラウドアウトが適切に考慮された場合、$$s類似の解軌跡が保証されることなく、ほぼ最適保証が達成できることが示されている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sampling-based motion planning algorithms are a popular class of trajectory planning algorithm due to their speed in complex, high-dimensional environments and ability to handle kinodynamic constraints, specifically through the use of forward dynamics propagation. Many such planners claim to achieve asymptotic near-optimality by proving the almost sure sampling of trajectories that are close to an optimal trajectory in the state space, known as $δ$-similar trajectories. This paper shows that the proof behind asymptotic $δ$-similarity relies on an unstated assumption that $δ$-similar trajectory segments will always be kept once sampled. This assumption does not hold in general. A problematic case, referred to as ``crowding out,'' is described, where locally low-cost paths prevent trajectories that are $δ$-similar to the optimal trajectory from being added to the tree. It is shown, however, that asymptotic near-optimality guarantees can still be achieved without guarantees of $δ$-similar solution trajectories when crowding out is properly accounted for. An example environment and system are provided where crowding out is shown to occur, demonstrating a scenario where inductively sampling a $δ$-similar solution trajectory is impossible.
• Abstract（参考訳）: サンプリングに基づく運動計画アルゴリズムは、複雑な高次元環境における速度とキノダイナミックな制約を扱う能力、特にフォワードダイナミクスの伝搬を用いて、軌道計画アルゴリズムの一般的なクラスである。 そのようなプランナーの多くは、$δ$-similar trajectories(英語版)として知られる状態空間の最適軌道に近い軌道のほぼ確実なサンプリングを証明し、漸近的に近い最適性を達成すると主張している。 本稿では、漸近的な$δ$-similarityの裏にある証明が、$δ$-similar trajectory segmentsが一度サンプリングされたときに常に保持されるという未定の仮定に依存していることを示す。 この仮定は一般には成り立たない。 問題のあるケースとして ''crowding out,' が述べられており、局所的な低コストのパスは、最適な軌跡に類似した$δ$の軌跡が木に追加されるのを防ぐ。 しかし、クラウドアウトが適切に考慮されている場合、δ$類似の解軌道の保証なしに漸近的準最適保証が達成できることが示されている。 クラウドアウトが発生する環境とシステムは、$δ$類似の溶液軌道を誘導的にサンプリングすることが不可能なシナリオを示す。

関連論文リスト

• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  未知数の線形平面をデータに適合させることは、機械学習の根本的な課題である。 既存のアプローチはしばしば最適な最適化に苦しむか、幾何的整合性に欠ける。
  論文  参考訳（メタデータ） (2026-05-27T14:02:20Z)
• Stochastic global optimization of continuous functions via random walks on Grassmannians [19.659410865201384]
  グラスマン多様体上のランダムウォークに基づく大域的最適化手法を提案する。 この方法は、ランダムな$k$次元の線形部分空間を繰り返しサンプリングする。 我々は、反復が世界最小値に近づく速度を制御するギャップパラメータを同定する。
  論文  参考訳（メタデータ） (2026-05-13T22:06:50Z)
• Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees [0.0]
  サンプル状態軌跡のみを用いた未知離散時間力学系の有限地平線到達可能集合推定について検討した。 到達可能な集合推定にどのように調整できるかを示し、そこでは全体の軌道に基づいて集合の族を学ばなければならない。
  論文  参考訳（メタデータ） (2026-04-14T12:23:14Z)
• Using Linearized Optimal Transport to Predict the Evolution of Stochastic Particle Systems [42.49693678817552]
  我々は、線形化された最適輸送理論を用いて、測度値のアルゴリズムが、測度が滑らかに進化するときに、一階精度であることを証明する。」 本稿では,我々のアルゴリズムが長期動作を正確に近似するために必要なマイクロスケールステップの数を著しく削減することを示すことによって,本手法の有効性を実証する。
  論文  参考訳（メタデータ） (2024-08-03T20:00:36Z)
• EigenTrajectory: Low-Rank Descriptors for Multi-Modal Trajectory Forecasting [26.38308951284839]
  EigenTrajectory (mathbbET$) は、新しいトラジェクトリ記述子を用いてコンパクトな空間を形成するトラジェクトリ予測手法である。 EigenTrajectoryは、既存の軌道予測モデルの予測精度と信頼性の両方を大幅に向上させることができる。
  論文  参考訳（メタデータ） (2023-07-18T14:52:08Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  勾配アルゴリズムは線形系を解くのに有効な方法である。 最適値に収束しない場合であっても,勾配降下は正確な予測を導出することを示す。 実験的に、勾配降下は十分に大規模または不条件の回帰タスクにおいて最先端の性能を達成する。
  論文  参考訳（メタデータ） (2023-06-20T15:07:37Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Asymptotic Behaviors and Phase Transitions in Projected Stochastic Approximation: A Jump Diffusion Approach [20.1003622916701]
  線形制約付き最適化問題を考察し、ループレス投影近似(LPSA)を提案する。 実現可能性を保証するために、$n$-thの確率$p_n$でプロジェクションを実行する。 このアルゴリズムは興味深いバイアス分散トレードオフを示し、位相遷移現象を生じさせる。
  論文  参考訳（メタデータ） (2023-04-25T15:57:07Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Predictive Power of Nearest Neighbors Algorithm under Random Perturbation [21.79888306754263]
  古典的な$k$Nearest Neighbors(k$-NN)におけるデータ破損シナリオについて検討する。 このようなシナリオでは、後悔に対する汚職レベルの影響を慎重に評価する。
  論文  参考訳（メタデータ） (2020-02-13T01:35:35Z)

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

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