論文の概要: 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)は、特に困難でオフロードで重要な状況において依然として課題である。
自動プランニングは、ミッション目標に達するために、ナビゲーションや操作のために使用することができる。
ほとんどの場合、問題は、いくつかの運用上の制約を満たしながら、ソースから目的地へのパスを見つけることにあります。
負のサイクルのないグラフでは、開始ノードから終了ノードまでの単対短経路の計算を多項式時間で解く。
しかし、ソリューションパスに関する追加の制約は、問題の解決を難しくする可能性がある。
これは、特定の訪問順序を必要とせずに、いくつかの必須ノードを通過するパスが必要な場合になります。
複雑さは、訪問するノードの数によって指数関数的に増加する。
本稿では,与えられた連結グラフ上の必須ノードを用いた最短経路探索に着目する。
本稿では,制約に基づく解法とグラフ畳み込みニューラルネットワークを組み合わせたハイブリッドモデルを提案する。
現実的なシナリオで結果が得られます。
関連論文リスト
- Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳(メタデータ) (2024-01-12T17:57:07Z) - Reinforcement Learning for Node Selection in Branch-and-Bound [58.740509566888676]
現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。
本稿では,木全体の状態を考慮した強化学習(RL)を用いた2次元シミュレーション手法を提案する。
論文 参考訳(メタデータ) (2023-09-29T19:55:56Z) - Learning from A Single Graph is All You Need for Near-Shortest Path
Routing in Wireless Networks [8.22181379329857]
無線ネットワークの標準モデルにおいて,任意のランダムグラフに一般化しながら,単一のグラフから得られるデータサンプルを数個だけ必要とするような局所ルーティングポリシーの学習アルゴリズムを提案する。
そこで我々はディープニューラルネットワーク(DNN)を訓練し、局所的なルーティングポリシーを効率的に学習することで、全ペアに近い経路問題を解決する。
論文 参考訳(メタデータ) (2023-08-18T21:35:45Z) - 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) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳(メタデータ) (2022-05-30T16:22:53Z) - 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) - Learning to Solve Combinatorial Optimization Problems on Real-World
Graphs in Linear Time [12.43303621344215]
専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。
本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。
最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
論文 参考訳(メタデータ) (2020-06-06T01:35:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。