論文の概要: Hybrid Search for Efficient Planning with Completeness Guarantees

• arxiv url: http://arxiv.org/abs/2310.12819v1
• Date: Thu, 19 Oct 2023 15:16:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-20 14:33:50.615584
• Title: Hybrid Search for Efficient Planning with Completeness Guarantees
• Title（参考訳）: 完全性保証による効率的な計画のハイブリッド探索
• Authors: Kalle Kujanp\"a\"a, Joni Pajarinen, Alexander Ilin
• Abstract要約: 本稿では,離散的な行動空間における完全性を実現するために,部分ゴール探索法を効果的に拡張する手法を提案する。 このソリューションは、高レベルの探索の実践的効率と低レベルの探索の完全性という、両方の世界のベストを達成している。
• 参考スコア（独自算出の注目度）: 63.02803974708516
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving complex planning problems has been a long-standing challenge in computer science. Learning-based subgoal search methods have shown promise in tackling these problems, but they often suffer from a lack of completeness guarantees, meaning that they may fail to find a solution even if one exists. In this paper, we propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces. Specifically, we augment the high-level search with low-level actions to execute a multi-level (hybrid) search, which we call complete subgoal search. This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search. We apply the proposed search method to a recently proposed subgoal search algorithm and evaluate the algorithm trained on offline data on complex planning problems. We demonstrate that our complete subgoal search not only guarantees completeness but can even improve performance in terms of search expansions for instances that the high-level could solve without low-level augmentations. Our approach makes it possible to apply subgoal-level planning for systems where completeness is a critical requirement.
• Abstract（参考訳）: 複雑な計画問題の解決は、コンピュータ科学における長年の課題である。 学習に基づく下位探索手法は、これらの問題に取り組むことには期待が持たれているが、それらはしばしば完全性保証の欠如に苦しめられている。 本稿では,離散的な行動空間における完全性を実現するために,部分ゴール探索法を効果的に拡張する手法を提案する。 具体的には、マルチレベル(ハイブリッド)検索を実行するために、低レベル動作による高レベル検索を増強する。 このソリューションは、高レベル検索の実用的効率と低レベル検索の完全性という、両方の世界のベストを達成する。 提案手法を最近提案したサブゴール探索アルゴリズムに適用し,複雑な計画問題に対するオフラインデータに基づく学習アルゴリズムの評価を行った。 完全なサブゴア検索は完全性を保証するだけでなく、低レベルの拡張なしに高レベルが解決できるインスタンスの検索拡張の観点からもパフォーマンスを向上させることができることを実証する。 当社のアプローチでは,完全性が必須要件であるシステムに対して,サブゴールレベルの計画を適用することができる。

関連論文リスト

• Planning In Natural Language Improves LLM Search For Code Generation [5.370466208990696]
  自然言語における問題解決のための新しい探索アルゴリズムであるPlanSearchを提案する。 PlanSearchはHumanEval+、MBPP+、LiveCodeBenchで強力な結果を示している。 すべてのモデル、検索アルゴリズム、および分析されたベンチマークにおいて、検索によるパフォーマンス向上を正確に予測できることが示される。
  論文  参考訳（メタデータ） (2024-09-05T17:44:49Z)
• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  ストロースト文字列問題(Closest String Problem)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。 本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。 第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
  論文  参考訳（メタデータ） (2024-07-17T21:26:27Z)
• What Matters in Hierarchical Search for Combinatorial Reasoning Problems? [0.0]
  近年の取り組みでは,階層的な高次探索戦略を取り入れたサブゴアル手法による計画の強化が試みられている。 有望ではあるが、従来の低レベルのプランナに対する彼らのパフォーマンスは一貫性がなく、アプリケーションコンテキストに関する疑問を提起している。 難解な値関数、複雑なアクション空間、環境におけるデッドエンドの存在、あるいは多様な専門家から収集されたデータなど、ハイレベル検索の利点を活用する上で重要な属性を同定する。
  論文  参考訳（メタデータ） (2024-06-05T15:14:58Z)
• Efficient Line Search Method Based on Regression and Uncertainty Quantification [7.724860428430271]
  制約のない最適化問題は、通常、最適なステップ長を決定するために反復法を用いて解決される。 本稿では,ベイズ最適化を用いた新しい線探索手法を提案する。 既存の最先端手法と比較して優れた性能を示し、同等のリソース使用量で最適性に多くの問題を解決している。
  論文  参考訳（メタデータ） (2024-05-17T16:35:20Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Fighting the curse of dimensionality: A machine learning approach to finding global optima [77.34726150561087]
  本稿では,構造最適化問題におけるグローバル最適化の方法を示す。 特定のコスト関数を利用することで、最適化手順が確立された場合と比較して、グローバルをベストに得るか、最悪の場合、優れた結果を得るかのどちらかを得る。
  論文  参考訳（メタデータ） (2021-10-28T09:50:29Z)
• C-Planning: An Automatic Curriculum for Learning Goal-Reaching Tasks [133.40619754674066]
  ゴール条件強化学習は、ナビゲーションや操作を含む幅広い領域のタスクを解決できる。 本研究では,学習時間における探索を用いて,中間状態を自動生成する遠隔目標獲得タスクを提案する。 E-stepはグラフ検索を用いて最適な経路点列を計画することに対応し、M-stepはそれらの経路点に到達するための目標条件付きポリシーを学習することを目的としている。
  論文  参考訳（メタデータ） (2021-10-22T22:05:31Z)
• Subgoal Search For Complex Reasoning Tasks [15.152111664776259]
  kSubSは学習されたサブゴールジェネレータで、解に近づき、達成可能なサブゴールの多様性を生み出す。 我々は,3つの挑戦的領域において,$k$-第2ステップのサブゴール生成という単純なアプローチが驚くほど効率的であることを示す。
  論文  参考訳（メタデータ） (2021-08-25T12:40:04Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding [86.40042104698792]
  スパース符号問題としてニューラルアーキテクチャ探索を定式化する。 実験では、CIFAR-10の2段階法では、検索にわずか0.05GPUしか必要としない。 本手法は,CIFAR-10とImageNetの両方において,評価時間のみのコストで最先端のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2020-10-13T04:34:24Z)

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

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