論文の概要: A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks

• arxiv url: http://arxiv.org/abs/2102.04518v1
• Date: Mon, 8 Feb 2021 20:36:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-10 16:57:16.602101
• Title: A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks
• Title（参考訳）: 拡張のないA*検索:深層Q-Networksによるヒューリスティック関数の学習
• Authors: Forest Agostinelli, Alexander Shmakov, Stephen McAleer, Roy Fox, Pierre Baldi
• Abstract要約: A*検索(A* search)は、ノードが拡張される順序を導く関数を使用する情報検索アルゴリズムである。 DeepAQはDeepCubeAアルゴリズムとディープQ-networksをベースにしたディープ強化学習と検索アルゴリズムである。 次にDeepAQはA*検索の新たな変種であるAQ*検索を使用し、深層Qネットワークを用いて検索を誘導する。
• 参考スコア（独自算出の注目度）: 73.12941276331314
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A* search is an informed search algorithm that uses a heuristic function to guide the order in which nodes are expanded. Since the computation required to expand a node and compute the heuristic values for all of its generated children grows linearly with the size of the action space, A* search can become impractical for problems with large action spaces. This computational burden becomes even more apparent when heuristic functions are learned by general, but computationally expensive, deep neural networks. To address this problem, we introduce DeepCubeAQ, a deep reinforcement learning and search algorithm that builds on the DeepCubeA algorithm and deep Q-networks. DeepCubeAQ learns a heuristic function that, with a single forward pass through a deep neural network, computes the sum of the transition cost and the heuristic value of all of the children of a node without explicitly generating any of the children, eliminating the need for node expansions. DeepCubeAQ then uses a novel variant of A* search, called AQ* search, that uses the deep Q-network to guide search. We use DeepCubeAQ to solve the Rubik's cube when formulated with a large action space that includes 1872 meta-actions and show that this 157-fold increase in the size of the action space incurs less than a 4-fold increase in computation time when performing AQ* search and that AQ* search is orders of magnitude faster than A* search.
• Abstract（参考訳）: A*検索は、ノードが拡大される順序を導くためにヒューリスティック関数を使用する情報検索アルゴリズムです。 ノードを拡大し、生成したすべての子供のヒューリスティック値を計算するのに必要な計算は、アクション空間のサイズとともに線形に成長するので、A*探索は大きなアクション空間の問題に対して実用的ではない。 この計算負荷は、ヒューリスティック関数が一般の計算コストが高いディープニューラルネットワークによって学習されるとさらに顕著になる。 この問題に対処するため,DeepCubeAアルゴリズムと深層Q-networksをベースにしたディープ強化学習検索アルゴリズムであるDeepCubeAQを導入する。 DeepCubeAQは、単一のフォワードがディープニューラルネットワークを通過することで、ノードのすべての子供の移行コストとヒューリスティック値の合計を明示的に生成することなく計算し、ノード拡張を不要とするヒューリスティック関数を学習する。 DeepCubeAQは、ディープQネットワークを使用して検索を導くAQ*検索と呼ばれる、A*検索の新しい変種を使用します。 私たちは、DeepCubeAQを使用して、1872のメタアクションを含む大きなアクションスペースで定式化されるとルービックキューブを解決し、アクションスペースのサイズが157倍に拡大すると、AQ*検索を行う際の計算時間が4倍以下になり、AQ*検索がA*検索よりも桁違いに速くなることを示します。

関連論文リスト

• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• A Differentiable Loss Function for Learning Heuristics in A* [0.0]
  本稿は、絶対値ではなく相対値に依存するため、A*アルゴリズムの高速化につながるとは限らない、と論じる。 緩和策として,A*探索における過度に拡張された状態の上限となるL*損失を提案する。 ソコバンやモーゼなどの迷路ドメインにおける自動計画のための最先端のディープニューラルネットワークの最適化に使用されるL*損失は、解決された問題の割合、確立された計画の品質を大幅に改善し、拡張された状態の数を約50%削減する。
  論文  参考訳（メタデータ） (2022-09-12T12:43:05Z)
• The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems [25.641418039598587]
  A*アルゴリズムはNP-ハード最適化問題の解法として一般的に用いられる。 このような問題の多くに対する正確な近似もNPハードであることを示す。
  論文  参考訳（メタデータ） (2022-09-07T18:02:02Z)
• Spatial search by continuous-time quantum walks on renormalized Internet networks [0.0]
  実世界の複雑なネットワーク上での連続的な量子ウォークを用いた空間探索について検討する。 実世界の複素ネットワーク上での量子空間探索アルゴリズムの挙動を初めて推測する。
  論文  参考訳（メタデータ） (2022-05-04T15:46:14Z)
• Learning heuristics for A* [9.701208207491879]
  我々は,近年のニューラル推論の進歩と,グラフ上の経路探索問題に対する効率的な関数の学習を組み合わせる。 我々はマルチタスク学習を利用してDijkstraのアルゴリズムとA*探索アルゴリズムの一貫性のある関数を学習する。 その結果、学習した値上でA*を実行すると、Dijkstraと比較してターゲットノード探索が大幅に高速化されることがわかった。
  論文  参考訳（メタデータ） (2022-04-11T10:13:53Z)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。 我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。 回路コストの削減は、システムの成功率を著しく向上させる。
  論文  参考訳（メタデータ） (2021-03-26T01:08:50Z)
• AutoSpace: Neural Architecture Search with Less Human Interference [84.42680793945007]
  現在のニューラルネットワークアーキテクチャ検索(NAS)アルゴリズムは、ネットワーク構築のための検索空間を設計するための専門知識と努力を必要とします。 探索空間を最適なものに進化させる新しい微分可能な進化フレームワークであるAutoSpaceを提案する。 学習した検索空間では、最近のNASアルゴリズムの性能は、以前手作業で設計した空間に比べて大幅に改善できる。
  論文  参考訳（メタデータ） (2021-03-22T13:28:56Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Continuous Ant-Based Neural Topology Search [62.200941836913586]
  この研究は、アリコロニー最適化に基づく、自然に着想を得たニューラルアーキテクチャサーチ(NAS)アルゴリズムを導入している。 連続アントベースのニューラルトポロジーサーチ(CANTS)は、アリが現実世界でどのように動くかに強く影響を受けている。
  論文  参考訳（メタデータ） (2020-11-21T17:49:44Z)
• 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)

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

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