論文の概要: Hybrid Search for Efficient Planning with Completeness Guarantees
- arxiv url: http://arxiv.org/abs/2310.12819v2
- Date: Tue, 28 Nov 2023 19:23:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-01 00:43:16.142630
- 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(参考訳): 複雑な計画問題の解決は、コンピュータ科学における長年の課題である。
学習に基づく下位探索手法は、これらの問題に取り組むことには期待が持たれているが、それらはしばしば完全性保証の欠如に苦しめられている。
本稿では,離散的な行動空間における完全性を実現するために,部分ゴール探索法を効果的に拡張する手法を提案する。
具体的には、マルチレベル(ハイブリッド)検索を実行するために、低レベル動作による高レベル検索を増強する。
このソリューションは、高レベル検索の実用的効率と低レベル検索の完全性という、両方の世界のベストを達成する。
提案手法を最近提案したサブゴール探索アルゴリズムに適用し,複雑な計画問題に対するオフラインデータに基づく学習アルゴリズムの評価を行った。
完全なサブゴア検索は完全性を保証するだけでなく、低レベルの拡張なしに高レベルが解決できるインスタンスの検索拡張の観点からもパフォーマンスを向上させることができることを実証する。
当社のアプローチでは,完全性が必須要件であるシステムに対して,サブゴールレベルの計画を適用することができる。
関連論文リスト
- A machine learning framework for neighbor generation in metaheuristic
search [4.521119623956821]
メタヒューリスティック検索における近隣世代のための汎用機械学習フレームワークを提案する。
メタヒューリスティックな2つの応用法について検証する。
論文 参考訳(メタデータ) (2022-12-22T01:58:04Z) - 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 [5.327281724367013]
kSubSは学習されたサブゴールジェネレータで、解に近づき、達成可能なサブゴールの多様性を生み出す。
我々は,3つの挑戦的領域において,$k$-第2ステップのサブゴール生成という単純なアプローチが驚くほど効率的であることを示す。
論文 参考訳(メタデータ) (2021-08-25T12:40:04Z) - A Meta-Heuristic Search Algorithm based on Infrasonic Mating Displays in
Peafowls [0.0]
探索アルゴリズムの解空間が増大するにつれて、網羅的探索のような単純な手法は計算コストが高く、信頼性が低いものとなる。
本研究では, 重力探索アルゴリズムとオオカミの交尾行動から着想を得た赤外探索アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-28T09:04:51Z) - Exploiting Learned Policies in Focal Search [0.49723239539321284]
政策学習を有界-準最適探索アルゴリズムに統合する方法を示す。
提案手法は3つのベンチマーク領域を対象とし,15-puzzleでは150万のサンプルを用いて学習したニューラルネットワークを用いて解析を行った。
本稿では,emphDiscrepancy Focal Searchにおいて,対応する経路が最適経路の接頭辞である確率の近似を最大化するノードを拡大し,実行時および解の質の観点から最もよい結果が得られることを示す。
論文 参考訳(メタデータ) (2021-04-21T13:50:40Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - C-Learning: Horizon-Aware Cumulative Accessibility Estimation [29.588146016880284]
本研究では,所定の地平線内の所定の状態から目標の到達可能性を測定する累積アクセシビリティ関数の概念を導入する。
これらの関数は、オフライン相互作用から学習できる繰り返し関係に従うことを示す。
我々は,複数ゴールの離散的かつ連続的な制御タスクの集合に対するアプローチを評価する。
論文 参考訳(メタデータ) (2020-11-24T20:34:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。