論文の概要: Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles
- arxiv url: http://arxiv.org/abs/2104.06681v1
- Date: Wed, 14 Apr 2021 07:59:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-15 13:22:48.204263
- Title: Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles
- Title（参考訳）: 動的障害物を用いた時間最適任意の角度経路計画に向けて
- Authors: Konstantin Yakovlev, Anton Andreychuk
- Abstract要約: パス探索は、しばしばグラフ検索としてフレーム化されるAIのよく研究された問題です。
同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
- 参考スコア（独自算出の注目度）: 1.370633147306388
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Path finding is a well-studied problem in AI, which is often framed as graph
search. Any-angle path finding is a technique that augments the initial graph
with additional edges to build shorter paths to the goal. Indeed, optimal
algorithms for any-angle path finding in static environments exist. However,
when dynamic obstacles are present and time is the objective to be minimized,
these algorithms can no longer guarantee optimality. In this work, we elaborate
on why this is the case and what techniques can be used to solve the problem
optimally. We present two algorithms, grounded in the same idea, that can
obtain provably optimal solutions to the considered problem. One of them is a
naive algorithm and the other one is much more involved. We conduct a thorough
empirical evaluation showing that, in certain setups, the latter algorithm
might be as fast as the previously-known greedy non-optimal solver while
providing solutions of better quality. In some (rare) cases, the difference in
cost is up to 76%, while on average it is lower than one percent (the same cost
difference is typically observed between optimal and greedy any-angle solvers
in static environments).
- Abstract（参考訳）: パス探索はAIにおいてよく研究されている問題であり、しばしばグラフ探索として扱われる。
任意の角度の経路探索は、目標への短いパスを構築するために、エッジを追加して初期グラフを拡張するテクニックである。
実際、静的環境における任意の角度経路探索のための最適アルゴリズムが存在する。
しかし、動的障害が存在し、時間が最小化の目的である場合、これらのアルゴリズムはもはや最適性を保証することができない。
そこで本研究では,なぜこのような問題になるのか,どのような手法が最適に解決できるのかについて詳述する。
同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
そのうちの1つはナイーブアルゴリズムであり、もう1つはより深く関わっている。
我々は、ある設定において、後者のアルゴリズムは、より優れた品質のソリューションを提供しながら、既知のグリード非最適解法と同等に高速であることを示す、徹底的な経験的評価を行う。
一部の(まれに)ケースでは、コストの差は最大で76%、平均では1%以下である(静的環境では、最適と強欲な任意の角解法の間で同じコスト差が観察される)。
関連論文リスト
- Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。
我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
論文 参考訳（メタデータ） (2024-05-08T09:25:39Z) - Tightest Admissible Shortest Path [4.928034044959278]
グラフにおける最短経路問題はAIの基本である。
本稿では,最適コストに縛られた最短経路である許容最短経路(TASP)の探索問題を紹介する。
我々は、ソリューションの品質を保証し、TASPを解くための完全なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-15T14:39:05Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates [13.046825574678579]
グラフにおける最短経路問題は、AI理論と応用の基礎である。
本稿では,エッジウェイトを複数回(推定)計算できる重み付き有向グラフのフレームワークを提案する。
次に、一般化問題に対する2つの完全アルゴリズムを提示し、その有効性を実証的に示す。
論文 参考訳（メタデータ） (2022-08-22T22:07:27Z) - Leveraging Experience in Lazy Search [37.75223642505171]
遅延グラフ探索アルゴリズムは、エッジ評価が計算ボトルネックとなる動き計画問題の解法において効率的である。
我々は,この問題を探索問題の状態に関するマルコフ決定過程 (MDP) として定式化する。
我々は,訓練中にMDPを解くことができる分子セレクタを計算可能であることを示す。
論文 参考訳（メタデータ） (2021-10-10T00:46:44Z) - Instance Specific Approximations for Submodular Maximization [45.91235224228292]
実世界のインスタンス上で最適な解に対して,アルゴリズムの性能をベンチマークする手法を模索する。
大きな疑問は、実際に遭遇したインスタンスの最適なソリューションと比較して、アルゴリズムのパフォーマンスを測定する方法です。
我々の主な貢献は、サブモジュラー最小化のための新しいアルゴリズムではなく、サブモジュラーインスタンスのアルゴリズムがいかに最適かを測定する分析手法である。
論文 参考訳（メタデータ） (2021-02-23T19:39:32Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。