論文の概要: A-MHA*: Anytime Multi-Heuristic A*
- arxiv url: http://arxiv.org/abs/2508.21637v1
- Date: Fri, 29 Aug 2025 14:00:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-01 19:45:11.066041
- Title: A-MHA*: Anytime Multi-Heuristic A*
- Title（参考訳）: A-MHA*: いつでもマルチヒューリスティックなA*
- Authors: Ramkumar Natarajan, Muhammad Suhail Saleem, William Xiao, Sandip Aine, Howie Choset, Maxim Likhachev,
- Abstract要約: MHA*(Multi-Heuristic A*)において, 部分的には良いが許容不可能な部分を用いた境界下最適探索法を開発した。
本研究では,MHA* を任意のバージョンに拡張することでこの問題に対処する。
MHA* フレームワークにおける ARA* 概念の正確な適応は、元の最適化と完全性を保証するとともに、いつでも実行できるように MHA* を拡張できることを証明します。
- 参考スコア（独自算出の注目度）: 26.161068194960833
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Designing good heuristic functions for graph search requires adequate domain knowledge. It is often easy to design heuristics that perform well and correlate with the underlying true cost-to-go values in certain parts of the search space but these may not be admissible throughout the domain thereby affecting the optimality guarantees of the search. Bounded suboptimal search using several such partially good but inadmissible heuristics was developed in Multi-Heuristic A* (MHA*). Although MHA* leverages multiple inadmissible heuristics to potentially generate a faster suboptimal solution, the original version does not improve the solution over time. It is a one shot algorithm that requires careful setting of inflation factors to obtain a desired one time solution. In this work, we tackle this issue by extending MHA* to an anytime version that finds a feasible suboptimal solution quickly and continually improves it until time runs out. Our work is inspired from the Anytime Repairing A* (ARA*) algorithm. We prove that our precise adaptation of ARA* concepts in the MHA* framework preserves the original suboptimal and completeness guarantees and enhances MHA* to perform in an anytime fashion. Furthermore, we report the performance of A-MHA* in 3-D path planning domain and sliding tiles puzzle and compare against MHA* and other anytime algorithms.
- Abstract（参考訳）: グラフ探索のための優れたヒューリスティック関数の設計には適切なドメイン知識が必要である。
探索空間の特定の部分における真のコスト対ゴーの値と相関するヒューリスティックスの設計は容易であるが、これらはドメイン全体で許容されないため、探索の最適性を保証する。
このような部分的ではあるが許容できないヒューリスティックスを用いた境界下最適探索は、MHA*(Multi-Heuristic A*)で開発された。
MHA*は複数の非許容ヒューリスティックを利用してより高速な最適解を生成するが、原版は時間とともに解を改善しない。
所望のワンショット解を得るためには、インフレーション係数の慎重な設定を必要とするワンショットアルゴリズムである。
本研究では,MHA* を任意のバージョンに拡張することでこの問題に対処する。
私たちの仕事は、Anytime repairing A* (ARA*)アルゴリズムにインスパイアされています。
MHA* フレームワークにおける ARA* 概念の正確な適応は、元の最適化と完全性を保証するとともに、いつでも実行できるように MHA* を拡張できることを証明します。
さらに,3次元経路計画領域とスライディングタイルパズルにおけるA-MHA*の性能を報告する。
関連論文リスト
- Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳（メタデータ） (2025-01-23T12:28:09Z) - Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。
本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
論文 参考訳（メタデータ） (2024-01-19T07:40:24Z) - A Multi-Heuristic Search-based Motion Planning for Automated Parking [0.0]
駐車場や建設現場のような非構造環境においては、リアルタイムな計画の実現が困難である。
我々は、複数の関数とその個々の利点を利用できるマルチヒューリスティック検索アプローチを採用しています。
Multi-Heuristic A*アルゴリズムは、非常に人気のある検索ベースのアルゴリズムであるHybrid A*に対してベンチマークされる。
論文 参考訳（メタデータ） (2023-07-15T17:33:06Z) - AMRA*: Anytime Multi-Resolution Multi-Heuristic A* [21.927948636840682]
MRA* (Multi-Resolution A*) は複数の解像度を探索する。
AMRA* は、粗い分解能をできるだけ早く利用して、解を見つけようとする。
そして、粗い解像度では得られなかったかもしれないより良い経路を見つけるために、微細な解像度に頼ることで、解を洗練する。
論文 参考訳（メタデータ） (2021-10-11T14:51:29Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
ニューラルネットワークは複雑で非敵対的な関数を学ぶことができ、安全クリティカルな文脈でそれらの正しい振る舞いを保証することは困難である。
ネットワーク内の障害を見つけるための多くのアプローチ(例えば、敵の例)があるが、これらは障害の欠如を保証できない。
本稿では,最適化プロセスを検証手順に統合し,本手法よりも優れた性能を実現する手法を提案する。
論文 参考訳（メタデータ） (2020-10-07T08:19:48Z) - A General Large Neighborhood Search Framework for Solving Integer Linear
Programs [46.62993477453986]
我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。
我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
論文 参考訳（メタデータ） (2020-03-29T23:08:14Z) - Supervised Hyperalignment for multi-subject fMRI data alignment [81.8694682249097]
本稿では,MVP解析における機能的アライメントを改善するために,SHA(Supervised Hyperalignment)手法を提案する。
マルチオブジェクトデータセットの実験では、SHA法は最大19%の性能がマルチクラス問題に対して達成されている。
論文 参考訳（メタデータ） (2020-01-09T09:17:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。