論文の概要: Learning Empirically Admissible Neural Heuristics for Combinatorial Search

• arxiv url: http://arxiv.org/abs/2606.04860v1
• Date: Wed, 03 Jun 2026 13:27:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-04 20:44:18.779621
• Title: Learning Empirically Admissible Neural Heuristics for Combinatorial Search
• Title（参考訳）: 組合せ探索のための経験的許容型ニューラルヒューリスティックスを学習する
• Authors: Siddharth Sahay,
• Abstract要約: 本稿では,検証校正可能なニューラルネットワークを学習するための一般化可能なフレームワークを提案する。 評価プロトコルの下では,我々の神経が観察された許容性違反を達成できないことを示す。
• 参考スコア（独自算出の注目度）: 0.33842793760651557
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding optimal solution paths for combinatorial puzzles like the Rubik's Cube, sliding tile puzzles, and Lights Out remains a classical challenge in artificial intelligence. Heuristic search algorithms, such as A* , guarantee path optimality only when using an admissible heuristic-one that never overestimates the true remaining cost-to-go. Deep reinforcement learning (RL) methods like DeepCubeA train deep neural networks to approximate cost-to-go heuristics. However, standard mean-squared error (MSE) training regularly yields overestimations, violating admissibility and compromising solution optimality. In this paper, we introduce a generalizable framework for learning validation-calibrated admissible neural heuristics. We train a value network using an underestimating Admissible Bellman Operator combined with an Asymmetric Loss function to penalize overestimation. To account for residual neural function approximation errors, we propose a post-hoc calibration safety offset computed over validation scrambles. We demonstrate that our calibrated neural heuristics achieve no observed admissibility violations under the evaluation protocol and preserve path optimality in practice while reducing search node expansions by up to 83.0% on a 2 by 2 Rubik's Cube, 19.9% on a 3 by 3 Lights Out grid, and 1.9% on an 8-Puzzle compared to standard analytical baselines.
• Abstract（参考訳）: ルービックキューブ、スライディングタイルパズル、ライトズアウトといった組み合わせパズルの最適解法を見つけることは、人工知能における古典的な課題である。 A*のようなヒューリスティックな探索アルゴリズムは、真のコスト対ゴーを過大評価しない許容可能なヒューリスティックなアルゴリズムを使用する場合にのみ経路最適性を保証する。 DeepCubeAのようなディープ強化学習(Deep reinforcement Learning, RL)メソッドは、ディープニューラルネットワークをトレーニングして、コスト対Goのヒューリスティックを近似する。 しかし、標準平均二乗誤差(MSE)トレーニングは、過大評価、許容性への違反、解の最適性を最適化する。 本稿では,検証校正型許容神経ヒューリスティックスを学習するための一般化可能なフレームワークを提案する。 我々は,非対称ロス関数と組み合わさって過大評価を行う過小評価ベルマン演算子を用いて,値ネットワークを訓練する。 残差ニューラルネットワークの近似誤差を考慮し,検証スクランブルによって計算された保温後安全性オフセットを提案する。 我々は,2×2ルービックキューブで最大83.0%,3×3ルービックアウトグリッドで19.9%,標準解析ベースラインで1.9%の探索ノード拡張を減らしながら,評価プロトコルの下で観測された許容可能性違反を達成せず,経路最適性を維持することを実証した。

関連論文リスト

• Learning Admissible Heuristics for A*: Theory and Practice [8.408138419383747]
  ディープラーニングアプローチは、しばしば許容性を無視し、トレーニングデータ以外の一般化に関して制限された保証を提供する。 本稿では,これら2つの制約に対処する。まず,制約付き最適化問題として学習を行い,学習中に許容度を強制する損失関数であるクロスエントロピー適応性(CEA)を導入する。 ルービックキューブ領域では、圧縮されたパターンデータベース(PDB)のガイダンスよりもはるかに強いほぼ許容値が得られる。
  論文  参考訳（メタデータ） (2025-09-26T17:51:26Z)
• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  ニューロシンボリックアプローチは一般に確率論的目的のファジィ近似を利用する。 トラクタブル回路において,これを効率的に計算する方法を示す。 我々は,Warcraftにおける最小コストパスの予測,最小コスト完全マッチングの予測,スドクパズルの解法という3つの課題に対して,アプローチを検証した。
  論文  参考訳（メタデータ） (2023-02-28T00:04:22Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awareness [33.09831377640498]
  本研究では,1つの決定論的表現に基づく1つのネットワークの不確実性向上手法について検討する。 本稿では,現代のDNNにおける距離認識能力を向上させる簡易な手法として,スペクトル正規化ニューラルガウス過程(SNGP)を提案する。 ビジョンと言語理解のベンチマークスイートでは、SNGPは予測、キャリブレーション、ドメイン外検出において、他の単一モデルアプローチよりも優れている。
  論文  参考訳（メタデータ） (2022-05-01T05:46:13Z)
• Meta-Solver for Neural Ordinary Differential Equations [77.8918415523446]
  本研究では,ソルバ空間の変動がニューラルODEの性能を向上する方法について検討する。 解法パラメータ化の正しい選択は, 敵の攻撃に対するロバスト性の観点から, 神経odesモデルに大きな影響を与える可能性がある。
  論文  参考訳（メタデータ） (2021-03-15T17:26:34Z)
• Neural Control Variates [71.42768823631918]
  ニューラルネットワークの集合が、積分のよい近似を見つけるという課題に直面していることを示す。 理論的に最適な分散最小化損失関数を導出し、実際に安定したオンライントレーニングを行うための代替の複合損失を提案する。 具体的には、学習した光場近似が高次バウンスに十分な品質であることを示し、誤差補正を省略し、無視可能な可視バイアスのコストでノイズを劇的に低減できることを示した。
  論文  参考訳（メタデータ） (2020-06-02T11:17:55Z)

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

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