論文の概要: DataSP: A Differential All-to-All Shortest Path Algorithm for Learning Costs and Predicting Paths with Context

• arxiv url: http://arxiv.org/abs/2405.04923v2
• Date: Thu, 30 May 2024 12:04:17 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 20:15:18.485723
• Title: DataSP: A Differential All-to-All Shortest Path Algorithm for Learning Costs and Predicting Paths with Context
• Title（参考訳）: DataSP: コストの学習と文脈による経路予測のための差分全短経路アルゴリズム
• Authors: Alan A. Lahoud, Erik Schaffernicht, Johannes A. Stork,
• Abstract要約: 本稿では,トラジェクトリからの遅延コストの学習を容易にするために,DataSPを提案する。 コンテキスト特徴からの複雑な遅延コスト関数は、ニューラルネットワーク近似を通じてアルゴリズムで表現することができる。 データSPは,グラフ上での経路予測において,最先端の機械学習手法よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 4.202961704179733
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning latent costs of transitions on graphs from trajectories demonstrations under various contextual features is challenging but useful for path planning. Yet, existing methods either oversimplify cost assumptions or scale poorly with the number of observed trajectories. This paper introduces DataSP, a differentiable all-to-all shortest path algorithm to facilitate learning latent costs from trajectories. It allows to learn from a large number of trajectories in each learning step without additional computation. Complex latent cost functions from contextual features can be represented in the algorithm through a neural network approximation. We further propose a method to sample paths from DataSP in order to reconstruct/mimic observed paths' distributions. We prove that the inferred distribution follows the maximum entropy principle. We show that DataSP outperforms state-of-the-art differentiable combinatorial solver and classical machine learning approaches in predicting paths on graphs.
• Abstract（参考訳）: グラフ上の遷移の遅延コストを、様々なコンテキスト特徴の下での軌跡から学習することは、パスプランニングには難しいが有用である。 しかし、既存の手法はコストの仮定を過度に単純化するか、観測された軌跡の数で不十分にスケールする。 本稿では,トラジェクトリからの遅延コストの学習を容易にするために,DataSPを提案する。 これにより、追加の計算をすることなく、各学習ステップにおける多数の軌跡から学習することができる。 コンテキスト特徴からの複雑な遅延コスト関数は、ニューラルネットワーク近似を通じてアルゴリズムで表現することができる。 さらに,観測された経路の分布を再構成し,再現するために,DataSPから経路をサンプリングする方法を提案する。 推定分布は最大エントロピー原理に従うことを証明している。 データSPは、グラフ上の経路予測において、最先端の微分可能な組合せ解法と古典的な機械学習アプローチより優れていることを示す。

関連論文リスト

• SSP-GNN: Learning to Track via Bilevel Optimization [3.1889516673296807]
  マルチオブジェクトトラッキング(MOT)のためのグラフベースのトラッキング形式を提案する。 本手法は,一組のフレーム上で定義された追跡グラフに対して,逐次最短経路 (SSP) アルゴリズムを適用した。 この追跡グラフのエッジコストは、グラフニューラルネットワーク(GNN)の変種であるメッセージパスネットワークを介して計算される。
  論文  参考訳（メタデータ） (2024-07-05T07:23:51Z)
• Generalized Differentiable RANSAC [95.95627475224231]
  $nabla$-RANSACは、ランダム化された堅牢な推定パイプライン全体を学ぶことができる、微分可能なRANSACである。 $nabla$-RANSACは、精度という点では最先端のシステムよりも優れているが、精度は低い。
  論文  参考訳（メタデータ） (2022-12-26T15:13:13Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares [8.443742714362521]
  我々は,従来のデータポイントの予測にほとんど変化しない方向にパラメータを変更しながら,すべての新しいデータポイントに完全に適合するワンパス学習アルゴリズムを開発した。 我々のアルゴリズムは、インクリメンタル・プリンシパル・コンポーネント分析(IPCA)を用いてストリーミングデータの構造を利用して、メモリを効率的に利用する。 本実験では,提案手法の有効性をベースラインと比較した。
  論文  参考訳（メタデータ） (2022-07-28T02:01:31Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。 我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。 特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
  論文  参考訳（メタデータ） (2022-06-15T18:20:01Z)
• GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
  3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。 提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
  論文  参考訳（メタデータ） (2022-05-30T16:22:53Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A* [12.117737635879037]
  データ駆動計画に関する最近の研究は、コスト関数またはプランナ関数を学習することを目的としているが、両方ではない。 グラフコストやプランナーとして、平面マップの表現を改善することができる差別化可能ないつでもプランナであるNeural Weighted A*を提案します。 我々は,複数のベースラインに対して神経重み付きa*をテストし,新たなタイルベースのナビゲーションデータセットを導入することで,クレームの妥当性を実験的に示す。
  論文  参考訳（メタデータ） (2021-05-04T13:17:30Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)

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

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