論文の概要: Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding
- arxiv url: http://arxiv.org/abs/2602.23468v2
- Date: Mon, 02 Mar 2026 05:47:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-03 15:39:04.010546
- Title: Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding
- Title（参考訳）: 生涯マルチエージェントパス探索における混合誘導グラフのエッジ方向と重みの最適化
- Authors: Yulun Zhang, Varun Bhatt, Matthew C. Fontaine, Stefanos Nikolaidis, Jiaoyang Li,
- Abstract要約: 誘導グラフにおいて、エッジウェイトと方向の両方を最適化する2つの方法を提案する。
また、エッジ方向に関するトラフィックパターンをGGO手法に組み込んで、エッジ方向対応誘導グラフを生成する。
- 参考スコア（独自算出の注目度）: 37.533959881191485
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Path Finding (MAPF) aims to move agents from their start to goal vertices on a graph. Lifelong MAPF (LMAPF) continuously assigns new goals to agents as they complete current ones. To guide agents' movement in LMAPF, prior works have proposed Guidance Graph Optimization (GGO) methods to optimize a guidance graph, which is a bidirected weighted graph whose directed edges represent moving and waiting actions with edge weights being action costs. Higher edge weights represent higher action costs. However, edge weights only provide soft guidance. An edge with a high weight only discourages agents from using it, instead of prohibiting agents from traversing it. In this paper, we explore the need to incorporate edge directions optimization into GGO, providing strict guidance. We generalize GGO to Mixed Guidance Graph Optimization (MGGO), presenting two MGGO methods capable of optimizing both edge weights and directions. The first optimizes edge directions and edge weights in two phases separately. The second applies Quality Diversity algorithms to optimize a neural network capable of generating edge directions and weights. We also incorporate traffic patterns relevant to edge directions into a GGO method, making it capable of generating edge-direction-aware guidance graphs.
- Abstract（参考訳）: Multi-Agent Path Finding (MAPF)は、エージェントを開始時点から目標頂点へグラフ上で移動させることを目的としている。
Lifelong MAPF (LMAPF) は、エージェントに新しいゴールを割り当て、現在のゴールを完了させる。
LMAPFにおけるエージェントの動きを導くために、先行研究は誘導グラフを最適化する誘導グラフ最適化(GGO)手法を提案している。
エッジ重量の増大は、アクションコストの上昇を表している。
しかし、エッジウェイトはソフトガイダンスのみを提供する。
重みのあるエッジは、エージェントがそれをトラバースするのを防ぐ代わりに、エージェントの使用を妨げているだけである。
本稿では、エッジ方向最適化をGGOに組み込む必要性について検討し、厳密なガイダンスを提供する。
我々はGGOをMixed Guidance Graph Optimization (MGGO)に一般化し、エッジウェイトと方向の両方を最適化できる2つのMGGO法を提案する。
第1の方法は、2つのフェーズでエッジ方向とエッジウェイトを個別に最適化する。
2つ目は、エッジ方向とウェイトを生成するニューラルネットワークを最適化するために、品質の多様性アルゴリズムを適用している。
また、エッジ方向に関するトラフィックパターンをGGO手法に組み込んで、エッジ方向対応誘導グラフを生成する。
関連論文リスト
- DOGE: Differentiable Bezier Graph Optimization for Road Network Extraction [21.196497150995356]
微分可能なパラメトリック曲線に基づく表現であるベジエグラフを導入する。
我々のフレームワークDOGEは、セグメンテーションマスクから直接パラメトリックベジエグラフを学習することで、このパラダイムを運用する。
本手法は,大規模SpaceNetとCityScaleのベンチマークに基づいて,新しい最先端の手法を提案する。
論文 参考訳（メタデータ） (2025-11-25T02:28:53Z) - ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
グラフニューラルネットワーク(GNN)は、近隣ノードからグラフ構造化情報を収集する強力な能力を示した。
GNNの性能は、ノイズや冗長なグラフデータによって引き起こされる一般化の貧弱さと脆弱な堅牢性によって制限される。
本稿では,エッジの除去を誘導する対向エッジ予測器を利用する新しい対向エッジドロップ法 (ADEdgeDrop) を提案する。
論文 参考訳（メタデータ） (2024-03-14T08:31:39Z) - GSINA: Improving Subgraph Extraction for Graph Invariant Learning via
Graph Sinkhorn Attention [52.67633391931959]
グラフ不変学習(GIL)は,グラフデータとそのラベル間の不変性を発見するための効果的な手法である。
グラフシンクホーン注意機構(GSINA)を提案する。
GSINAは、制御可能な空間性と柔らかさを持つ有意義で微分可能な不変部分グラフを得ることができる。
論文 参考訳（メタデータ） (2024-02-11T12:57:16Z) - Guidance Graph Optimization for Lifelong Multi-Agent Path Finding [47.51678151084153]
MAPF(Multi-Agent Path Finding)のスループット向上のためのガイダンスの活用法について検討する。
本稿では、生涯MAPFのためのガイダンスの多目的表現としてガイダンスグラフを紹介する。
任意の寿命のMAPFアルゴリズムとマップのガイダンスを自動生成する2つのGGOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-02T14:38:04Z) - Adaptive Spatio-temporal Estimation on the Graph Edges via Line Graph Transformation [3.6448362316632115]
線形グラフ変換を利用したLGLMS (Line Graph Least Mean Square) アルゴリズムを提案する。
LGLMSは古典的なLMSアルゴリズムに類似した適応アルゴリズムであるが、グラフエッジに適用される。
論文 参考訳（メタデータ） (2023-11-01T17:02:41Z) - Bring Your Own View: Graph Neural Networks for Link Prediction with
Personalized Subgraph Selection [57.34881616131377]
異なるエッジに対して最適なサブグラフを自動,個人的,帰納的に識別するプラグイン・アンド・プレイ・フレームワークとしてパーソナライズされたサブグラフセレクタ(PS2)を導入する。
PS2は二段階最適化問題としてインスタンス化され、効率よく解ける。
GNNLPトレーニングに対する新たなアプローチとして,まずエッジの最適な部分グラフを識別し,次にサンプル部分グラフを用いて推論モデルをトレーニングすることを提案する。
論文 参考訳（メタデータ） (2022-12-23T17:30:19Z) - GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。
不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。
我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
論文 参考訳（メタデータ） (2022-11-04T16:10:50Z) - CSGO: Constrained-Softassign Gradient Optimization For Large Graph Matching [0.7456521449098222]
本稿では,よく知られたグラフマッチングアルゴリズムを,制約付き勾配法というフレームワークに統合する。
属性付きグラフマッチングタスクでは、CSGOは現在の制約付き勾配アルゴリズムに比べて10倍以上の速度向上を達成する。
論文 参考訳（メタデータ） (2022-08-17T11:25:03Z) - Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using
Stochastic Gradient Descent [33.31762612175859]
我々はODRM(Optimized Directed Roadmap Graph)と呼ばれる新しいアプローチを提案する。
ODRMは、マルチロボットナビゲーションにおける衝突回避を可能にする有向ロードマップグラフを構築する方法である。
実験の結果,単純な集中型プランナさえあれば,他のマルチエージェントプランナでは解決できない,多数のエージェントで解決できることがわかった。
論文 参考訳（メタデータ） (2020-03-29T02:18:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。