論文の概要: Leveraging Experience in Lazy Search

• arxiv url: http://arxiv.org/abs/2110.04669v1
• Date: Sun, 10 Oct 2021 00:46:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-12 19:39:18.526853
• Title: Leveraging Experience in Lazy Search
• Title（参考訳）: 遅延探索における経験の活用
• Authors: Mohak Bhardwaj, Sanjiban Choudhury, Byron Boots, Siddhartha Srinivasa
• Abstract要約: 遅延グラフ探索アルゴリズムは、エッジ評価が計算ボトルネックとなる動き計画問題の解法において効率的である。 我々は,この問題を探索問題の状態に関するマルコフ決定過程 (MDP) として定式化する。 我々は,訓練中にMDPを解くことができる分子セレクタを計算可能であることを示す。
• 参考スコア（独自算出の注目度）: 37.75223642505171
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lazy graph search algorithms are efficient at solving motion planning problems where edge evaluation is the computational bottleneck. These algorithms work by lazily computing the shortest potentially feasible path, evaluating edges along that path, and repeating until a feasible path is found. The order in which edges are selected is critical to minimizing the total number of edge evaluations: a good edge selector chooses edges that are not only likely to be invalid, but also eliminates future paths from consideration. We wish to learn such a selector by leveraging prior experience. We formulate this problem as a Markov Decision Process (MDP) on the state of the search problem. While solving this large MDP is generally intractable, we show that we can compute oracular selectors that can solve the MDP during training. With access to such oracles, we use imitation learning to find effective policies. If new search problems are sufficiently similar to problems solved during training, the learned policy will choose a good edge evaluation ordering and solve the motion planning problem quickly. We evaluate our algorithms on a wide range of 2D and 7D problems and show that the learned selector outperforms baseline commonly used heuristics. We further provide a novel theoretical analysis of lazy search in a Bayesian framework as well as regret guarantees on our imitation learning based approach to motion planning.
• Abstract（参考訳）: 遅延グラフ探索アルゴリズムは、エッジ評価が計算ボトルネックとなる動き計画問題の解法において効率的である。 これらのアルゴリズムは、潜在的に最も短い経路を遅延的に計算し、その経路に沿ってエッジを評価し、実現可能な経路が見つかるまで繰り返す。 エッジが選択される順序は、エッジ評価の総数を最小化するために重要であり、良いエッジセレクタは、無効になる可能性のあるエッジを選択するだけでなく、将来のパスも考慮しない。 我々はそのようなセレクタを事前の経験を活用して学びたい。 我々は,この問題を探索問題の状態に関するマルコフ決定過程(MDP)として定式化する。 この大規模なMDPの解法は一般に難易度が高いが,訓練中にMDPを解けるような分子セレクタを計算できることが示される。 このようなオラクルにアクセスすることで、我々は効果的なポリシーを見つけるために模倣学習を使います。 新しい検索問題がトレーニング中に解決された問題と十分に類似している場合、学習したポリシーは優れたエッジ評価順序を選択し、モーションプランニング問題を迅速に解決する。 アルゴリズムを2次元および7次元の幅広い問題で評価し、学習したセレクタが一般的なヒューリスティックよりも優れていることを示す。 さらに,ベイジアンフレームワークにおける遅延探索の新たな理論的解析や,模倣学習に基づく動作計画へのアプローチに対する後悔の保証も提供する。

関連論文リスト

• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Fast Line Search for Multi-Task Learning [0.0]
  マルチタスク学習における行探索アルゴリズムの新しいアイデアを提案する。 この考え方は、ステップサイズを見つけるためにパラメータ空間の代わりに潜在表現空間を使用することである。 本稿では,MNIST,CIFAR-10,Cityscapesタスクの学習速度を一定とする古典的バックトラック法と勾配法を比較した。
  論文  参考訳（メタデータ） (2021-10-02T21:02:29Z)
• (Machine) Learning to Improve the Empirical Performance of Discrete Algorithms [0.0]
  我々は、人間の専門家の意見なしに、与えられたデータに対して最適なアルゴリズムを選択するために機械学習手法を訓練する。 我々のフレームワークは、固定されたデフォルトのピボットルールを使用するだけで全体のパフォーマンスを改善する様々なピボットルールを推奨しています。 最短経路問題に対して、訓練されたモデルは大幅に改善され、我々の選択は最適な選択から平均.7パーセント離れている。
  論文  参考訳（メタデータ） (2021-09-29T08:33:09Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)
• Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
  パス探索は、しばしばグラフ検索としてフレーム化されるAIのよく研究された問題です。 同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
  論文  参考訳（メタデータ） (2021-04-14T07:59:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Towards Meta-Algorithm Selection [78.13985819417974]
  インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。 メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
  論文  参考訳（メタデータ） (2020-11-17T17:27:33Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)

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

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