論文の概要: A Formalism for Optimal Search with Dynamic Heuristics
- arxiv url: http://arxiv.org/abs/2504.21131v1
- Date: Tue, 29 Apr 2025 19:25:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-09 23:38:01.605491
- Title: A Formalism for Optimal Search with Dynamic Heuristics
- Title(参考訳): 動的ヒューリスティックスを用いた最適探索のための形式主義
- Authors: Remo Christen, Florian Pommerening, Clemens Büchner, Malte Helmert,
- Abstract要約: 我々は動的アルゴリズムの考え方を定式化し、それらを汎用アルゴリズムフレームワークで使用する。
我々は、動的に$mathrmA*$をモデル化し、最適な一般化結果を示す特定のインスタンス化について研究する。
- 参考スコア(独自算出の注目度): 7.807210884802377
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While most heuristics studied in heuristic search depend only on the state, some accumulate information during search and thus also depend on the search history. Various existing approaches use such dynamic heuristics in $\mathrm{A}^*$-like algorithms and appeal to classic results for $\mathrm{A}^*$ to show optimality. However, doing so ignores the complexities of searching with a mutable heuristic. In this paper we formalize the idea of dynamic heuristics and use them in a generic algorithm framework. We study a particular instantiation that models $\mathrm{A}^*$ with dynamic heuristics and show general optimality results. Finally we show how existing approaches from classical planning can be viewed as special cases of this instantiation, making it possible to directly apply our optimality results.
- Abstract(参考訳): ヒューリスティック検索で研究される多くのヒューリスティックな研究は州にのみ依存するが、探索中に情報を蓄積するものもあるため、検索履歴にも依存する。
既存の様々なアプローチでは、そのような動的ヒューリスティックスを$\mathrm{A}^*$-likeアルゴリズムで使用し、古典的な結果に対して$\mathrm{A}^*$で最適性を示す。
しかし、そのようなことは、可変ヒューリスティックによる探索の複雑さを無視する。
本稿では,動的ヒューリスティックスの概念を定式化し,汎用的なアルゴリズムフレームワークとして利用する。
動的ヒューリスティックスを用いて$\mathrm{A}^*$をモデル化する特定のインスタンス化について検討し、一般的な最適性結果を示す。
最後に、古典的計画からの既存のアプローチを、このインスタンス化の特別なケースとみなすことができ、最適化結果を直接適用できることを示す。
関連論文リスト
- Modeling Local Search Metaheuristics Using Markov Decision Processes [0.0]
局所探索メタヒューリスティック解析のためのマルコフ決定過程(MDP)に基づく理論的枠組みを提案する。
このフレームワークは、個々のアルゴリズムに収束結果を提供するのに役立つだけでなく、探索-探索トレードオフの明示的な特徴も提供する。
論文 参考訳(メタデータ) (2024-07-29T11:28:30Z) - Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal [0.9217021281095907]
計画のための模倣学習では、関数のパラメータは一連の解決された問題インスタンスに対して最適化される。
次に、フォワード探索アルゴリズムの与えられた変種に合わせたランキングに基づいて、損失関数の族を提案する。
様々な問題の集合に関する実験的な比較は、導出理論を絶対的に支持する。
論文 参考訳(メタデータ) (2023-10-30T11:39:49Z) - A Multi-Heuristic Search-based Motion Planning for Automated Parking [0.0]
駐車場や建設現場のような非構造環境においては、リアルタイムな計画の実現が困難である。
我々は、複数の関数とその個々の利点を利用できるマルチヒューリスティック検索アプローチを採用しています。
Multi-Heuristic A*アルゴリズムは、非常に人気のある検索ベースのアルゴリズムであるHybrid A*に対してベンチマークされる。
論文 参考訳(メタデータ) (2023-07-15T17:33:06Z) - Optimistic Active Exploration of Dynamical Systems [52.91573056896633]
我々はOPAXと呼ばれる活発な探索のためのアルゴリズムを開発した。
我々は,OPAXを各エピソードで解決可能な最適制御問題に還元する方法を示す。
実験の結果,OPAXは理論的に健全であるだけでなく,新規な下流タスクのゼロショット計画にも有効であることがわかった。
論文 参考訳(メタデータ) (2023-06-21T16:26:59Z) - Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。
基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。
我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文 参考訳(メタデータ) (2022-09-27T17:51:31Z) - Run Time Analysis for Random Local Search on Generalized Majority
Functions [1.0965065178451106]
我々は、その性質の1つ、中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。
我々は、多くの最適化アルゴリズムに適用可能な定理を提案し、MAJORITYの実行時間と対称バージョンHASMAJORITYをリンクする。
論文 参考訳(メタデータ) (2022-04-27T08:40:33Z) - Searching for More Efficient Dynamic Programs [61.79535031840558]
本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。
実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
論文 参考訳(メタデータ) (2021-09-14T20:52:55Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳(メタデータ) (2021-06-09T08:05:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Learning Heuristic Selection with Dynamic Algorithm Configuration [44.91083687014879]
計画システムの動的選択力学に動的アルゴリズム構成を用いることができることを示す。
提案手法は,既存のアプローチよりも一般化し,ドメイン探索の性能を指数関数的に向上させることができることを示す。
論文 参考訳(メタデータ) (2020-06-15T09:35:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。