論文の概要: TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers

• arxiv url: http://arxiv.org/abs/2212.11730v1
• Date: Thu, 22 Dec 2022 14:26:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-23 14:01:31.533551
• Title: TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers
• Title（参考訳）: TransPath:トランスフォーマーによるグリッドベースのパスフィニングのためのヒューリスティック学習
• Authors: Daniil Kirilenko, Anton Andreychuk, Aleksandr Panov, Konstantin Yakovlev
• Abstract要約: 探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
• 参考スコア（独自算出の注目度）: 64.88759709443819
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heuristic search algorithms, e.g. A*, are the commonly used tools for pathfinding on grids, i.e. graphs of regular structure that are widely employed to represent environments in robotics, video games etc. Instance-independent heuristics for grid graphs, e.g. Manhattan distance, do not take the obstacles into account and, thus, the search led by such heuristics performs poorly in the obstacle-rich environments. To this end, we suggest learning the instance-dependent heuristic proxies that are supposed to notably increase the efficiency of the search. The first heuristic proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one (computed offline at the training phase). Unlike learning the absolute values of the cost-to-go heuristic function, which was known before, when learning the correction factor the knowledge of the instance-independent heuristic is utilized. The second heuristic proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path. This heuristic can be utilized in the Focal Search framework as the secondary heuristic, allowing us to preserve the guarantees on the bounded sub-optimality of the solution. We learn both suggested heuristics in a supervised fashion with the state-of-the-art neural networks containing attention blocks (transformers). We conduct a thorough empirical evaluation on a comprehensive dataset of planning tasks, showing that the suggested techniques i) reduce the computational effort of the A* up to a factor of $4$x while producing the solutions, which costs exceed the costs of the optimal solutions by less than $0.3$% on average; ii) outperform the competitors, which include the conventional techniques from the heuristic search, i.e. weighted A*, as well as the state-of-the-art learnable planners.
• Abstract（参考訳）: ヒューリスティック検索アルゴリズム(例えば、a*)は、グリッド上のパス検索、すなわちロボット工学やビデオゲームなどの環境を表現するために広く使われる正規構造のグラフとして一般的に使用されるツールである。 グリッドグラフのインスタンスに依存しないヒューリスティック(例えばマンハッタン距離)は障害を考慮せず、そのようなヒューリスティックによる探索は障害物の多い環境では不十分である。 この目的のために,探索効率を顕著に向上させると考えられる,インスタンス依存のヒューリスティックプロキシの学習を提案する。 私たちが学ぶべき最初のヒューリスティックなプロキシは、修正係数、すなわち、インスタンスに依存しないコスト対ゴーの見積もりと完璧なもの(トレーニングフェーズでオフラインで計算される)の比率です。 以前知られていたコスト・ツー・ゴーヒューリスティック関数の絶対値とは異なり、補正係数を学習する際には、インスタンス非依存ヒューリスティックの知識が利用される。 第2のヒューリスティックプロキシはパス確率であり、グリッドセルが最短経路に横たわっている可能性を示している。 このヒューリスティックはFocal Searchフレームワークで二次ヒューリスティックとして利用することができ、解の有界部分最適性に関する保証を維持することができる。 我々は,アテンションブロック(トランスフォーマー)を含む最先端ニューラルネットワークを用いて,提案するヒューリスティックスを教師付きで学習する。 我々は,計画課題の包括的データセットを徹底的に評価し,提案手法が有効であることを示す。 一 最適解のコストを平均で0.3%未満のコストで超えるような解を生産している間に、a*の計算労力を四十倍まで削減すること。 ii) ヒューリスティック検索の従来の手法,すなわち重み付きA*, および最先端の学習可能なプランナーを含む競技者を上回る。

関連論文リスト

• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  自動回路発見の効率的かつスケーラブルなソリューションとしてエッジプルーニングを提案する。 本手法は,従来の手法に比べてエッジ数の半分未満のGPT-2の回路を探索する。 その効率のおかげで、Edge PruningをCodeLlama-13Bにスケールしました。
  論文  参考訳（メタデータ） (2024-06-24T16:40:54Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• On Using Admissible Bounds for Learning Forward Search Heuristics [9.749638953163391]
  学習において,受理者が提供する情報を効果的に活用する方法に焦点をあてる。 学習対象は、学習対象ではなく、この分布の下位境界として、許容値が使用される、切り裂かれたssianとしてモデル化する。 その結果,提案手法はトレーニング中により高速に収束し,より優れたガウスが得られることがわかった。
  論文  参考訳（メタデータ） (2023-08-23T04:14:45Z)
• Unsupervised Learning for Solving the Travelling Salesman Problem [28.62497359169851]
  旅行セールスマン問題(TSP)を解決するための教師なし学習フレームワークUTSPを提案する。 我々は、代理損失を用いてグラフニューラルネットワーク(GNN)を訓練する。GNNは、各エッジが最適経路の一部である確率を表すヒートマップを出力する。 次に、熱マップに基づいて最終予測を生成するために局所探索を適用する。
  論文  参考訳（メタデータ） (2023-03-19T02:30:27Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learning [65.52675802289775]
  本研究では,不確かさを意識した分類器が,強化学習の難しさを解消できることを示す。 正規化最大度(NML)分布の計算法を提案する。 得られたアルゴリズムは、カウントベースの探索法と、報酬関数を学習するための先行アルゴリズムの両方に多くの興味深い関係を持つことを示す。
  論文  参考訳（メタデータ） (2021-07-15T08:19:57Z)
• Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A* [12.117737635879037]
  データ駆動計画に関する最近の研究は、コスト関数またはプランナ関数を学習することを目的としているが、両方ではない。 グラフコストやプランナーとして、平面マップの表現を改善することができる差別化可能ないつでもプランナであるNeural Weighted A*を提案します。 我々は,複数のベースラインに対して神経重み付きa*をテストし,新たなタイルベースのナビゲーションデータセットを導入することで,クレームの妥当性を実験的に示す。
  論文  参考訳（メタデータ） (2021-05-04T13:17:30Z)
• Robot Navigation in a Crowd by Integrating Deep Reinforcement Learning and Online Planning [8.211771115758381]
  これは、群衆の中で時間効率と衝突のない道を移動するモバイルロボットにとって、まだオープンで挑戦的な問題です。 深層強化学習はこの問題に対する有望な解決策である。 グラフに基づく深部強化学習手法SG-DQNを提案する。 私たちのモデルは、ロボットが群衆をよりよく理解し、群衆ナビゲーションタスクで0.99以上の高い成功率を達成するのに役立ちます。
  論文  参考訳（メタデータ） (2021-02-26T02:17:13Z)

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

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