論文の概要: SLOPE: Search with Learned Optimal Pruning-based Expansion
- arxiv url: http://arxiv.org/abs/2406.04935v1
- Date: Fri, 7 Jun 2024 13:42:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-10 13:51:43.662122
- Title: SLOPE: Search with Learned Optimal Pruning-based Expansion
- Title（参考訳）: SLOPE:学習された最適プルーニングに基づく探索
- Authors: Davor Bokan, Zlatan Ajanovic, Bakir Lacevic,
- Abstract要約: SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。
ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。
これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
- 参考スコア（独自算出の注目度）: 2.0618817976970103
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Heuristic search is often used for motion planning and pathfinding problems, for finding the shortest path in a graph while also promising completeness and optimal efficiency. The drawback is it's space complexity, specifically storing all expanded child nodes in memory and sorting large lists of active nodes, which can be a problem in real-time scenarios with limited on-board computation. To combat this, we present the Search with Learned Optimal Pruning-based Expansion (SLOPE), which, learns the distance of a node from a possible optimal path, unlike other approaches that learn a cost-to-go value. The unfavored nodes are then pruned according to the said distance, which in turn reduces the size of the open list. This ensures that the search explores only the region close to optimal paths while lowering memory and computational costs. Unlike traditional learning methods, our approach is orthogonal to estimating cost-to-go heuristics, offering a complementary strategy for improving search efficiency. We demonstrate the effectiveness of our approach evaluating it as a standalone search method and in conjunction with learned heuristic functions, achieving comparable-or-better node expansion metrics, while lowering the number of child nodes in the open list. Our code is available at https://github.com/dbokan1/SLOPE.
- Abstract（参考訳）: ヒューリスティック探索は、グラフ内の最短経路を見つけると同時に、完全性と最適効率を約束するために、運動計画やパスフィニング問題によく用いられる。
欠点は、メモリに拡張されたすべての子ノードを格納し、アクティブなノードの大規模なリストをソートする、という空間の複雑さにある。
これに対抗するために,SLOPE (Search with Learned Optimal Pruning-based Expansion) を提案する。
好ましくないノードは、その距離に応じてプルーニングされ、その結果、オープンリストのサイズが減少する。
これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
従来の学習手法とは異なり,本手法はコスト・ツー・ゴ・ゴ・ヒューリスティックスを推定するための直交的手法であり,探索効率を向上させるための補完的戦略を提供する。
提案手法は,学習したヒューリスティック関数と組み合わせて,オープンリスト内の子ノード数を減らしつつ,同等あるいはベタノード拡張の指標を達成し,独立探索手法として評価する手法の有効性を実証する。
私たちのコードはhttps://github.com/dbokan1/SLOPEで利用可能です。
関連論文リスト
- Pathfinding with Lazy Successor Generation [12.02023514105999]
位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。
単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。
そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
論文 参考訳（メタデータ） (2024-08-27T23:25:25Z) - LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳（メタデータ） (2024-06-29T05:14:04Z) - A Cover Time Study of a non-Markovian Algorithm [18.23492383352517]
提案手法は,無作為なランダムウォークサーチよりも負のフィードバック戦略(カウントベース探索法)が優れていることを示す。
また、クリッドグラフやツリーグラフなど、特別なが重要なグラフのカバータイムも小さくする。
論文 参考訳（メタデータ） (2023-06-08T03:09:49Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳（メタデータ） (2022-05-30T16:22:53Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - 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) - Best-First Beam Search [78.71330480725668]
本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。
ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
論文 参考訳（メタデータ） (2020-07-08T05:56:01Z) - A Practical Index Structure Supporting Fr\'echet Proximity Queries Among
Trajectories [1.9335262420787858]
我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。
計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。
本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
論文 参考訳（メタデータ） (2020-05-28T04:12:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。