論文の概要: T*$\varepsilon$ -- Bounded-Suboptimal Efficient Motion Planning for
Minimum-Time Planar Curvature-Constrained Systems
- arxiv url: http://arxiv.org/abs/2204.01673v1
- Date: Mon, 4 Apr 2022 17:38:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-05 16:00:17.278420
- Title: T*$\varepsilon$ -- Bounded-Suboptimal Efficient Motion Planning for
Minimum-Time Planar Curvature-Constrained Systems
- Title（参考訳）: t*$\varepsilon$ --最小時間平面曲率制約系の有界-最適効率的な運動計画
- Authors: Doron Pinsky and Petr V\'a\v{n}a and Jan Faigl and Oren Salzman
- Abstract要約: 本研究では,障害物の存在下での曲率制約系の衝突のない経路を見つけることの問題点を考察する。
有界-準最適解を求めることにより、使用した時間-最適遷移の数を劇的に削減できることを示す。
- 参考スコア（独自算出の注目度）: 7.277760003553328
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding collision-free paths for
curvature-constrained systems in the presence of obstacles while minimizing
execution time. Specifically, we focus on the setting where a planar system can
travel at some range of speeds with unbounded acceleration. This setting can
model many systems, such as fixed-wing drones. Unfortunately, planning for such
systems might require evaluating many (local) time-optimal transitions
connecting two close-by configurations, which is computationally expensive.
Existing methods either pre-compute all such transitions in a preprocessing
stage or use heuristics to speed up the search, thus foregoing any guarantees
on solution quality. Our key insight is that computing all the time-optimal
transitions is both~(i)~computationally expensive and~(ii)~unnecessary for many
problem instances. We show that by finding bounded-suboptimal solutions
(solutions whose cost is bounded by $1+\varepsilon$ times the cost of the
optimal solution for any user-provided $\varepsilon$) and not time-optimal
solutions, one can dramatically reduce the number of time-optimal transitions
used. We demonstrate using empirical evaluation that our planning framework can
reduce the runtime by several orders of magnitude compared to the
state-of-the-art while still providing guarantees on the quality of the
solution.
- Abstract（参考訳）: 本研究では, 障害物の存在下での曲率制約系に対する衝突のない経路の探索について検討する。
具体的には、平面系が一定の速度で非拘束加速度で走行できるような設定に注目する。
この設定は固定翼ドローンなど多くのシステムをモデル化することができる。
残念なことに、このようなシステムの計画には、2つのクローズバイ構成を接続する多くの(ローカルな)時間最適遷移を評価する必要がある。
既存の手法は、前処理の段階で全ての遷移をプリコンプリートするか、あるいはヒューリスティックを使って検索を高速化する。
私たちの重要な洞察は、時間-最適遷移のコンピューティングが両方であることです。
(i)～計算コストが高くて～
(ii)-多くの問題例では不要。
任意のユーザ提供の$\varepsilon$ に対する最適解のコストを 1+\varepsilon$ で割った)有界な最適解を見つけることにより、時間最適化解ではなく、使用中の時間最適化遷移の数を劇的に削減できることを示した。
我々は、我々の計画フレームワークが、ソリューションの品質の保証を提供しながら、最先端と比較してランタイムを数桁削減できるという実証的評価を用いて実証する。
関連論文リスト
- Time-Varying Convex Optimization with $O(n)$ Computational Complexity [0.0]
コスト関数が時間とともに変化する非拘束凸最適化の問題を考える。
提案アルゴリズムは,決定変数に対するコスト関数の1次微分のみを必要とする。
具体的には、提案アルゴリズムは、計算コストを1タイムステップあたり$(n3)$から$O(n)$に削減する。
論文 参考訳（メタデータ） (2024-10-19T06:45:05Z) - Optimal Chaining of Vehicle Plans with Time Windows [0.0]
本研究は,時間ウィンドウで許容される遅延を考慮した新しい計画連鎖定式化と解法を提案する。
静的ダイヤル・ア・ライド問題を解くための新しい車両ディスパッチ手法を提案する。
論文 参考訳（メタデータ） (2024-01-05T16:04:55Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - COSMIC: fast closed-form identification from large-scale data for LTV
systems [4.10464681051471]
データから離散時間線形時変系を同定するための閉形式法を提案する。
我々は、最適性を保証するアルゴリズムを開発し、軌跡ごとに考慮されるインスタントの数を線形に増加させる複雑性を持つ。
本アルゴリズムは,彗星インターセプタミッション用の低忠実度および機能工学シミュレーションの両方に適用した。
論文 参考訳（メタデータ） (2021-12-08T16:07:59Z) - On Constraints in First-Order Optimization: A View from Non-Smooth
Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。
提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。
結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文 参考訳（メタデータ） (2021-07-17T11:45:13Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。