論文の概要: Semidefinite Relaxations for Collision-Free Motion Planning

• arxiv url: http://arxiv.org/abs/2606.14063v1
• Date: Fri, 12 Jun 2026 03:18:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-15 16:00:42.727919
• Title: Semidefinite Relaxations for Collision-Free Motion Planning
• Title（参考訳）: 衝突のない運動計画のための半有限緩和法
• Authors: Bernhard Paus Graesdal, Alexandre Amice, Pablo A. Parrilo, Russ Tedrake,
• Abstract要約: C4トラジェクトリの観点で,inmathbbRn制約を通じて開始からゴールへ移動するポイントロボットに焦点をあてる。 C4トラジェクトリによる最小スナップ連続計画のプランナとしての有効性を示す。
• 参考スコア（独自算出の注目度）: 53.160637667144876
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study semidefinite relaxations for collision-free motion planning. We focus on a point robot moving from start to goal through spherical obstacles in $\mathbb{R}^n$, subject to path continuity constraints and squared derivative costs; a setting that is conceptually simple yet captures the hardness of collision-free motion planning. We formulate this problem exactly as a nonconvex problem over polynomial curves, and present a natural semidefinite relaxation. We contribute two key theoretical insights; to our knowledge this is the first theoretical analysis of semidefinite relaxations for collision-free motion planning. First, we show that solving the convex relaxation is equivalent to solving, to global optimality, a related motion planning problem in a potentially higher-dimensional space. This geometric interpretation yields necessary and sufficient conditions for tightness, and a clear intuition for when the relaxation is loose. Second, we show that the relaxation admits a symmetry reduction that makes it significantly smaller than one might expect, with positive semidefinite cone sizes that scale linearly with the polynomial degree and are independent of the ambient dimension. The resulting relaxation is 10 to 100 times faster than direct nonlinear programming transcriptions solved with SNOPT and IPOPT, exhibits significantly lower variance in solve times, and reliably finds a locally optimal path for the original problem. We demonstrate its effectiveness as a convex steering function in an RRT planner for minimum-snap quadrotor planning with $C^4$ continuous trajectories.
• Abstract（参考訳）: 衝突のない運動計画のための半定緩和法について検討する。 我々は、経路連続性制約と2乗微分コストを対象とし、開始からゴールまで球面障害物を通した点ロボットに焦点を合わせ、概念上は単純だが衝突のない運動計画の難しさを捉える。 この問題を多項式曲線上の非凸問題として正確に定式化し、自然な半定値緩和を与える。 これは衝突のない運動計画のための半定緩和に関する最初の理論的解析である。 まず、凸緩和の解法は、潜在的に高次元空間における関連する運動計画問題である大域的最適性(英語版)の解法と等価であることを示す。 この幾何学的解釈は、きついために必要かつ十分な条件を導き、緩和が緩いときの明確な直感を与える。 第二に、緩和は期待するよりもかなり小さい対称性の還元を許容し、正の半定円錐サイズは多項式次数と線形にスケールし、周囲次元とは独立であることを示す。 その結果、SNOPTやIPOPTで解かれた直接非線形プログラミングの書き起こしよりも10倍から100倍の速度で緩和され、解時間における差が著しく小さくなり、元の問題に対して局所的に最適な経路が確実に見つかる。 C^4$連続軌道計画におけるRRTプランナの凸ステアリング関数としての有効性を実証する。

関連論文リスト

• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  未知数の線形平面をデータに適合させることは、機械学習の根本的な課題である。 既存のアプローチはしばしば最適な最適化に苦しむか、幾何的整合性に欠ける。
  論文  参考訳（メタデータ） (2026-05-27T14:02:20Z)
• Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle [51.714334316332476]
  Local Lは制約付き最適化のための新しいプロジェクションフリー型である。 局所LMOはGD(Gradient Descent)のオラクルと見なされる。
  論文  参考訳（メタデータ） (2026-05-09T10:03:24Z)
• Sliced Wasserstein Steering between Gaussian Measures [2.1485350418225244]
  我々は分散ステアリングのためのスライスされたフィードバックコントローラを開発した。 進化する法則は球面上の一次元の方向に投影される。 開発した制御器が所定の目標に対して法則を定めていることを示す。
  論文  参考訳（メタデータ） (2026-04-14T08:03:17Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation [26.277745106128197]
  一般関数近似を用いた強化学習における長期計画地平線問題に対処するアルゴリズムを提案する。 導出残差は、線形混合MDPを対数因子まで特殊化する場合のミニマックス下限と一致するため、エンフシャープと見なされる。 このような地平線に依存しない、インスタンスに依存しない、鋭い後悔に満ちたヒンジの達成は、(i)新しいアルゴリズム設計と(ii)きめ細かい解析に基づいている。
  論文  参考訳（メタデータ） (2023-12-07T17:35:34Z)
• Projected Langevin dynamics and a gradient flow for entropic optimal transport [0.8057006406834466]
  エントロピー規則化された最適輸送からサンプリングした類似拡散力学を導入する。 部分多様体 $Pi(mu,nu)$ の誘導されたワッサーシュタイン幾何学の研究により、SDE はこの結合空間上のワッサーシュタイン勾配フローとみなすことができると論じる。
  論文  参考訳（メタデータ） (2023-09-15T17:55:56Z)
• Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties [6.355764634492975]
  一般の二次制約計算に対して, 2次制約で記述した緩和法を提案する。 緩和は半確定緩和(SDP)と同じくらい強くすることができる。 これは、一連のサロゲートを必要とするアルゴリズムの加速に有効である。
  論文  参考訳（メタデータ） (2022-08-07T02:44:23Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Competitive Mirror Descent [67.31015611281225]
  制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。 本稿では, 競合ミラー降下法(CMD)を提案する。 特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-06-17T22:11:35Z)

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

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