論文の概要: UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding

• arxiv url: http://arxiv.org/abs/2602.23789v1
• Date: Fri, 27 Feb 2026 08:34:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-02 19:48:24.318498
• Title: UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding
• Title（参考訳）: UPath: グリッドベースのパスフィニングのためのトポロジ的不均一性にまたがるユニバーサルプランナー
• Authors: Aleksandr Ananikian, Daniil Drozdov, Konstantin Yakovlev,
• Abstract要約: 本研究では,タスクを一般化できるモデルの設計により,普遍的な予測器を設計することで,このギャップを埋める。 我々の経験的アプローチは、A*の計算労力を2.2倍に縮める一方で、平均係数2.2の3%以内の解を提供することを示唆している。
• 参考スコア（独自算出の注目度）: 43.22339935902436
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The performance of search algorithms for grid-based pathfinding, e.g. A*, critically depends on the heuristic function that is used to focus the search. Recent studies have shown that informed heuristics that take the positions/shapes of the obstacles into account can be approximated with the deep neural networks. Unfortunately, the existing learning-based approaches mostly rely on the assumption that training and test grid maps are drawn from the same distribution (e.g., city maps, indoor maps, etc.) and perform poorly on out-of-distribution tasks. This naturally limits their application in practice when often a universal solver is needed that is capable of efficiently handling any problem instance. In this work, we close this gap by designing an universal heuristic predictor: a model trained once, but capable of generalizing across a full spectrum of unseen tasks. Our extensive empirical evaluation shows that the suggested approach halves the computational effort of A* by up to a factor of 2.2, while still providing solutions within 3% of the optimal cost on average altogether on the tasks that are completely different from the ones used for training $\unicode{x2013}$ a milestone reached for the first time by a learnable solver.
• Abstract（参考訳）: グリッドベースのパスフィンディングにおける探索アルゴリズムの性能は、探索に集中するために使用されるヒューリスティック関数に大きく依存する。 近年の研究では、障害の位置や要因を考慮に入れた情報ヒューリスティックスが、ディープニューラルネットワークと近似できることが示されている。 残念ながら、既存の学習ベースのアプローチは、トレーニングとテストグリッドマップが同じ分布(例えば、都市地図、屋内地図など)から引き出され、アウト・オブ・ディストリビューション(out-of-distriion)タスクでは不十分である、という前提に大きく依存している。 これにより、問題インスタンスを効率的に処理できる普遍的な解決器がしばしば必要となる場合に、その応用が自然に制限される。 本研究は,統一ヒューリスティック予測器を設計することで,このギャップを埋めるものである。 我々の広範な経験的評価は、提案手法がA*の計算労力を最大2.2倍に抑える一方で、学習可能な解法によって初めて到達したマイルストーンである$\unicode{x2013}とは全く異なるタスクに対して、平均的な最適コストの3%以内のソリューションを提供することを示している。

関連論文リスト

• Learning Admissible Heuristics for A*: Theory and Practice [8.408138419383747]
  ディープラーニングアプローチは、しばしば許容性を無視し、トレーニングデータ以外の一般化に関して制限された保証を提供する。 本稿では,これら2つの制約に対処する。まず,制約付き最適化問題として学習を行い,学習中に許容度を強制する損失関数であるクロスエントロピー適応性(CEA)を導入する。 ルービックキューブ領域では、圧縮されたパターンデータベース(PDB)のガイダンスよりもはるかに強いほぼ許容値が得られる。
  論文  参考訳（メタデータ） (2025-09-26T17:51:26Z)
• OFA$^2$: A Multi-Objective Perspective for the Once-for-All Neural Architecture Search [79.36688444492405]
  once-for-All(OFA)は、異なるリソース制約を持つデバイスのための効率的なアーキテクチャを探索する問題に対処するために設計された、ニューラルネットワーク検索(NAS)フレームワークである。 我々は,探索段階を多目的最適化問題として明示的に考えることにより,効率の追求を一歩進めることを目指している。
  論文  参考訳（メタデータ） (2023-03-23T21:30:29Z)
• 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)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Combining Optimal Path Search With Task-Dependent Learning in a Neural Network [4.1712273169097305]
  コスト値をシナプス重みに変換することにより,経路探索問題のニューラルネットワーク表現を定義することができることを示す。 ネットワーク学習機構は, ネットワーク内の重みを手作業に応じて強化し, ネットワークの重み付けに適応できることを示す。
  論文  参考訳（メタデータ） (2022-01-26T18:29:00Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Training Binary Neural Networks using the Bayesian Learning Rule [19.01146578435531]
  二分重のニューラルネットワークは計算効率が良く、ハードウェアに優しいが、そのトレーニングには離散的な最適化の問題が伴うため、難しい。 本稿では、既存のアプローチを正当化し、拡張するバイナリニューラルネットワークをトレーニングするための原則的アプローチを提案する。 私たちの研究は、既存のアプローチを正当化し拡張するバイナリニューラルネットワークをトレーニングするための原則化されたアプローチを提供します。
  論文  参考訳（メタデータ） (2020-02-25T10:20:10Z)

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

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