論文の概要: Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

• arxiv url: http://arxiv.org/abs/2402.01446v2
• Date: Thu, 9 May 2024 19:14:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-13 20:07:31.304541
• Title: Guidance Graph Optimization for Lifelong Multi-Agent Path Finding
• Title（参考訳）: 生涯マルチエージェントパス探索のためのガイダンスグラフ最適化
• Authors: Yulun Zhang, He Jiang, Varun Bhatt, Stefanos Nikolaidis, Jiaoyang Li,
• Abstract要約: MAPF(Multi-Agent Path Finding)のスループット向上のためのガイダンスの活用法について検討する。 本稿では、生涯MAPFのためのガイダンスの多目的表現としてガイダンスグラフを紹介する。 任意の寿命のMAPFアルゴリズムとマップのガイダンスを自動生成する2つのGGOアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 47.51678151084153
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study how to use guidance to improve the throughput of lifelong Multi-Agent Path Finding (MAPF). Previous studies have demonstrated that, while incorporating guidance, such as highways, can accelerate MAPF algorithms, this often results in a trade-off with solution quality. In addition, how to generate good guidance automatically remains largely unexplored, with current methods falling short of surpassing manually designed ones. In this work, we introduce the guidance graph as a versatile representation of guidance for lifelong MAPF, framing Guidance Graph Optimization as the task of optimizing its edge weights. We present two GGO algorithms to automatically generate guidance for arbitrary lifelong MAPF algorithms and maps. The first method directly optimizes edge weights, while the second method optimizes an update model capable of generating edge weights. Empirically, we show that (1) our guidance graphs improve the throughput of three representative lifelong MAPF algorithms in eight benchmark maps, and (2) our update model can generate guidance graphs for as large as $93 \times 91$ maps and as many as 3,000 agents. We include the source code at: \url{https://github.com/lunjohnzhang/ggo_public}. All optimized guidance graphs are available online at: \url{https://yulunzhang.net/publication/zhang2024ggo}.
• Abstract（参考訳）: 本研究では,MAPF(Multi-Agent Path Finding)のスループット向上のためのガイダンスの活用方法について検討する。 従来の研究では、高速道路などのガイダンスを組み込むことでMAPFアルゴリズムを加速できるが、ソリューションの品質とのトレードオフをもたらすことが示されている。 さらに、優れたガイダンスを自動生成する方法はほとんど探索されていないままであり、現在の手法は手作業で設計したものを超えていない。 本研究では,終生のMAPFのためのガイダンスの汎用表現としてガイダンスグラフを導入し,エッジウェイトを最適化するタスクとして指導グラフ最適化を提案する。 任意の寿命のMAPFアルゴリズムとマップのガイダンスを自動生成する2つのGGOアルゴリズムを提案する。 第1の方法はエッジウェイトを直接最適化し、第2の方法はエッジウェイトを生成する更新モデルを最適化する。 実験的な結果として,(1) ベンチマークマップの3つの寿命のMAPFアルゴリズムのスループットが向上し,(2) 更新モデルが最大9,3 \times 91$ Maps と 3,000 エージェントのガイダンスグラフを生成できることがわかった。 ソースコードは以下の通り: \url{https://github.com/lunjohnzhang/ggo_public}。 すべての最適化されたガイダンスグラフは、次のようにオンラインで入手できる。

関連論文リスト

• Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
  多エージェント経路探索(MAPF)は、衝突しない複数のエージェントの経路を見つける問題である。 MAPFの最適解を見つけることはNP-Hardであるが、現代の最適解法は数百のエージェントにスケールでき、場合によっては数千までスケールできる。 このエンコーディングが既存のエンコーディングと効果的に結合できることを示し、その結果、グラフ埋め込みによるMAPFアルゴリズム選択と呼ばれる新しいASメソッドが実現された。
  論文  参考訳（メタデータ） (2024-06-16T07:41:58Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  テキストグラフ学習におけるフラストレーションに富んだアプローチであるSimTeGを提案する。 まず、下流タスクで予め訓練されたLM上で、教師付きパラメータ効率の微調整(PEFT)を行う。 次に、微調整されたLMの最後の隠れ状態を用いてノード埋め込みを生成する。
  論文  参考訳（メタデータ） (2023-08-03T07:00:04Z)
• RNGDet++: Road Network Graph Detection by Transformer with Instance Segmentation and Multi-scale Features Enhancement [19.263691277963368]
  道路網のグラフ構造は、グローバルな計画、動き予測、制御など、自律運転システムの下流業務に不可欠である。 これまでは、道路ネットワークグラフは人の専門家によって手動で注釈付けされていた。 前者は、プロセス後セマンティックセグメンテーションマップや、ロードネットワークグラフを直接予測するグラフベースのアルゴリズムを提案している。 それまでの作業は、ハードコードされた処理アルゴリズムと劣った最終性能に悩まされていた。 提案されたアプローチはRNGDetから改善されているため、RNGDet++と呼ばれている。
  論文  参考訳（メタデータ） (2022-09-21T07:06:46Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Transferable Graph Optimizers for ML Compilers [18.353830282858834]
  計算グラフ最適化(GO)のためのエンドツーエンドで転送可能な深層強化学習法を提案する。 GOは個々のノードに対して自動回帰ではなく,グラフ全体の決定を生成する。 GOは、人間の専門家よりも21%改善し、先行技術よりも18%改善し、15倍早く収束する。
  論文  参考訳（メタデータ） (2020-10-21T20:28:33Z)
• Adaptive Graph Encoder for Attributed Graph Embedding [36.06427854846497]
  分散グラフ埋め込みは、グラフトポロジとノード特徴からベクトル表現を学ぶ。 本稿では,新しい属性グラフ埋め込みフレームワークであるAdaptive Graph(AGE)を提案する。 4つの公開ベンチマークデータセットを用いてノードクラスタリングとリンク予測タスクのAGEを検証する実験を行った。
  論文  参考訳（メタデータ） (2020-07-03T10:20:34Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  本稿では,新たなノードやエッジを自動的に拡張して,高密度サブグラフ内のラベル類似性を向上する,新しい前処理手法であるElectoral College(ELCO)を提案する。 テストされたすべての設定において、我々の手法はベースモデルの平均スコアを4.7ポイントの広いマージンで引き上げるとともに、常に最先端のモデルよりも優れています。
  論文  参考訳（メタデータ） (2020-06-10T14:48:48Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)
• 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)

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

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