論文の概要: Constrained Shortest Path Search with Graph Convolutional Neural Networks

• arxiv url: http://arxiv.org/abs/2108.00978v1
• Date: Mon, 2 Aug 2021 15:25:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-03 15:30:46.095472
• Title: Constrained Shortest Path Search with Graph Convolutional Neural Networks
• Title（参考訳）: グラフ畳み込みニューラルネットワークを用いた最小経路探索
• Authors: Kevin Osanlou, Christophe Guettier, Andrei Bursuc, Tristan Cazenave, Eric Jacopin
• Abstract要約: 無人地上車両(AUGV)の計画はまだ課題である。 本稿では,与えられた連結グラフ上の必須ノードを用いた最短経路探索に着目した。 本稿では,制約に基づく解法とグラフ畳み込みニューラルネットワークを組み合わせたハイブリッドモデルを提案する。
• 参考スコア（独自算出の注目度）: 12.457788665461312
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Planning for Autonomous Unmanned Ground Vehicles (AUGV) is still a challenge, especially in difficult, off-road, critical situations. Automatic planning can be used to reach mission objectives, to perform navigation or maneuvers. Most of the time, the problem consists in finding a path from a source to a destination, while satisfying some operational constraints. In a graph without negative cycles, the computation of the single-pair shortest path from a start node to an end node is solved in polynomial time. Additional constraints on the solution path can however make the problem harder to solve. This becomes the case when we need the path to pass through a few mandatory nodes without requiring a specific order of visit. The complexity grows exponentially with the number of mandatory nodes to visit. In this paper, we focus on shortest path search with mandatory nodes on a given connected graph. We propose a hybrid model that combines a constraint-based solver and a graph convolutional neural network to improve search performance. Promising results are obtained on realistic scenarios.
• Abstract（参考訳）: 無人地上車両の計画(AUGV)は、特に困難でオフロードで重要な状況において依然として課題である。 自動プランニングは、ミッション目標に達するために、ナビゲーションや操作のために使用することができる。 ほとんどの場合、問題は、いくつかの運用上の制約を満たしながら、ソースから目的地へのパスを見つけることにあります。 負のサイクルのないグラフでは、開始ノードから終了ノードまでの単対短経路の計算を多項式時間で解く。 しかし、ソリューションパスに関する追加の制約は、問題の解決を難しくする可能性がある。 これは、特定の訪問順序を必要とせずに、いくつかの必須ノードを通過するパスが必要な場合になります。 複雑さは、訪問するノードの数によって指数関数的に増加する。 本稿では,与えられた連結グラフ上の必須ノードを用いた最短経路探索に着目する。 本稿では,制約に基づく解法とグラフ畳み込みニューラルネットワークを組み合わせたハイブリッドモデルを提案する。 現実的なシナリオで結果が得られます。

関連論文リスト

• Towards Dynamic Message Passing on Graphs [104.06474765596687]
  グラフニューラルネットワーク(GNN)のための新しい動的メッセージパッシング機構を提案する。 グラフノードと学習可能な擬似ノードを、測定可能な空間関係を持つ共通空間に投影する。 ノードが空間内を移動すると、その進化する関係は動的メッセージパッシングプロセスのための柔軟な経路構築を促進する。
  論文  参考訳（メタデータ） (2024-10-31T07:20:40Z)
• Timetable Nodes for Public Transport Network [31.793066412010468]
  時間依存トランスポートネットワークにおける高速パスフィニングは、ナビゲーションシステムにおいて重要かつ困難な問題である。 本稿では,計算幾何学と異なる最適化手法を用いて,グラフベースのアプローチを進化させる手法を提案する。 我々のソリューションは他の時間依存ネットワークに適合し、他のパスフィンディングアルゴリズムに統合できる。
  論文  参考訳（メタデータ） (2024-10-21T07:34:04Z)
• The Mystery of the Pathological Path-star Task for Language Models [1.223779595809275]
  最近導入されたパススタータスクは、言語モデルの能力に対する制限を実証するために設計された最小限のタスクである。 代替設定で教師の強制でタスクが学習可能であることを実証し、一部は表現によるものであることを示した。
  論文  参考訳（メタデータ） (2024-10-17T17:18:30Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  言語エージェントにおけるタスクプランニングは、大規模言語モデル(LLM)の開発とともに重要な研究トピックとして浮上している。 本稿では,課題計画のためのグラフ学習に基づく手法について検討する。 我々のグラフ学習への関心は、注意のバイアスと自己回帰的損失が、グラフ上の意思決定を効果的にナビゲートするLLMの能力を妨げているという理論的な発見に起因している。
  論文  参考訳（メタデータ） (2024-05-29T14:26:24Z)
• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。 孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
  論文  参考訳（メタデータ） (2023-09-29T19:55:56Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search [12.457788665461312]
  本稿では,機械学習モデルと最適解法を併用したハイブリッド問題解決プランナを提案する。 我々は現実的なシナリオで実験を行い、GCNのサポートにより、より難しい問題に対して、大幅なスピードアップとスムーズなスケーリングが可能になることを示す。
  論文  参考訳（メタデータ） (2021-08-02T16:53:21Z)
• Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
  グラフニューラルネットワーク(GNN)は、入力グラフを介して学習されたメッセージパッシングを実行する。 最大100のメッセージパッシングステップを持つディープGNNをトレーニングし、いくつかの最先端の結果を得る。
  論文  参考訳（メタデータ） (2021-06-15T08:50:10Z)

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

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