論文の概要: Safe Interval Path Planning With Kinodynamic Constraints
- arxiv url: http://arxiv.org/abs/2302.00776v1
- Date: Wed, 1 Feb 2023 22:15:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-03 16:09:57.618797
- Title: Safe Interval Path Planning With Kinodynamic Constraints
- Title(参考訳): Kinodynamic Constraints を用いた安全なインターバルパス計画
- Authors: Zain Alabedeen Ali and Konstantin Yakovlev
- Abstract要約: 元のSIPPアルゴリズムは、エージェントが即座に停止できるという仮定に依存している。
本稿では,加速/減速を伴う計画に最適で,確実に完全であるSIPPの新たな変種を紹介する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Safe Interval Path Planning (SIPP) is a powerful algorithm for solving
single-agent pathfinding problem when the agent is confined to a graph and
certain vertices/edges of this graph are blocked at certain time intervals due
to dynamic obstacles that populate the environment. Original SIPP algorithm
relies on the assumption that the agent is able to stop instantaneously.
However, this assumption often does not hold in practice, e.g. a mobile robot
moving with a cruising speed is not able to stop immediately but rather
requires gradual deceleration to a full stop that takes time. In other words,
the robot is subject to kinodynamic constraints. Unfortunately, as we show in
this work, in such a case original SIPP is incomplete. To this end, we
introduce a novel variant of SIPP that is provably complete and optimal for
planning with acceleration/deceleration. In the experimental evaluation we show
that the key property of the original SIPP still holds for the modified version
-- it performs much less expansions compared to A* and, as a result, is notably
faster.
- Abstract(参考訳): セーフインターバルパス計画(SIPP)は、エージェントがグラフに制限され、このグラフの特定の頂点/辺が、環境に散らばる動的障害により、一定の時間間隔でブロックされるとき、単一エージェントパスフィニング問題を解決する強力なアルゴリズムである。
元のSIPPアルゴリズムは、エージェントが即座に停止できるという仮定に依存している。
しかし、この仮定は実際には成立しないことが多く、例えば、巡航速度で動く移動ロボットはすぐに止まることができず、時間を要するフルストップに徐々に減速する必要がある。
言い換えれば、ロボットは運動力学的制約を受けることになる。
残念なことに、我々がこの研究で示したように、そのような場合、元のSIPPは不完全である。
そこで本研究では,加速/減速を伴う計画に最適で完全であるSIPPの新たな変種を提案する。
実験的な評価では、元のSIPPの鍵特性が改良版に対してまだ保たれていることが示され、A*よりもはるかに少ない拡張を行い、その結果、顕著に高速である。
関連論文リスト
- Rethinking PGD Attack: Is Sign Function Necessary? [131.6894310945647]
本稿では,このような手話に基づく更新アルゴリズムが段階的攻撃性能にどのように影響するかを理論的に分析する。
本稿では,手話の使用を排除したRGDアルゴリズムを提案する。
提案したRGDアルゴリズムの有効性は実験で広く実証されている。
論文 参考訳(メタデータ) (2023-12-03T02:26:58Z) - Efficient Real-time Path Planning with Self-evolving Particle Swarm
Optimization in Dynamic Scenarios [6.951981832970596]
操作形式(TOF)は、粒子の操作をテンソル操作に変換する。
自己進化型粒子群最適化(SEPSO)を開発した。
SEPSOはより優れたパスを生成でき、リアルタイムのパフォーマンスがかなり向上する。
論文 参考訳(メタデータ) (2023-08-20T05:31:48Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-05-20T07:54:07Z) - Faster Approximate Dynamic Programming by Freezing Slow States [5.6928413790238865]
高速低速構造を持つ無限水平マルコフ決定過程(MDP)を考察する。
このような構造は、シーケンシャルな決定を高周波で行う必要がある実世界の問題では一般的である。
本稿では、遅い状態の「凍結」という概念に基づく近似動的プログラミングフレームワークを提案する。
論文 参考訳(メタデータ) (2023-01-03T01:35:24Z) - Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。
提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。
大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
論文 参考訳(メタデータ) (2022-11-02T14:35:13Z) - Revisiting and Advancing Fast Adversarial Training Through The Lens of
Bi-Level Optimization [60.72410937614299]
提案手法は,2レベルAT(FAST-BAT)と呼ばれる新しいアルゴリズムセットの設計と解析である。
FAST-BATは、グラデーションサインメソッドや明示的なロバスト正規化を呼ぶことなく、符号ベースの投射降下(PGD)攻撃を防御することができる。
論文 参考訳(メタデータ) (2021-12-23T06:25:36Z) - Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。
この問題をある程度緩和する手法を提案する。
論文 参考訳(メタデータ) (2021-08-11T10:42:11Z) - ADOM: Accelerated Decentralized Optimization Method for Time-Varying
Networks [124.33353902111939]
本稿では,時間変動ネットワーク上の滑らかかつ強凸分散最適化のための高速化手法である adom を提案する。
ネットワーク構造のみに依存する一定の要因まで、その通信は加速されたNesterovメソッドのそれと同じです。
論文 参考訳(メタデータ) (2021-02-18T09:37:20Z) - Parameter-free Locally Accelerated Conditional Gradients [91.19349793915615]
私たちは小説を紹介します。
自由局所加速cg(pf-lacg)アルゴリズムは,厳密な収束保証を提供する。
我々の理論結果は,局所加速度を実証し,非加速アルゴリズムに対するPF-LaCGの実用的改善を示す数値実験によって補完される。
論文 参考訳(メタデータ) (2021-02-12T22:50:01Z) - Escaping Saddle Points Efficiently with Occupation-Time-Adapted
Perturbations [12.251606057991237]
自己反発型ランダムウォークの超拡散性により,最適化アルゴリズムのための新しい摂動機構を開発した。
2つの新しいアルゴリズムが提案されている: 占有時間に適応した摂動勾配降下とその加速バージョン。
論文 参考訳(メタデータ) (2020-05-09T19:58:23Z) - Gradient descent with momentum --- to accelerate or to super-accelerate? [0.0]
「この加速を延長してアルゴリズムを改良できることを示せ」
スーパーアクセラレーションは、RMSPropやAdamのような適応アルゴリズムに簡単に組み込むことができる。
論文 参考訳(メタデータ) (2020-01-17T18:50:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。