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

• arxiv url: http://arxiv.org/abs/2402.01446v1
• Date: Fri, 2 Feb 2024 14:38:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-05 14:48:52.445813
• 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アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 50.9781867964022
• 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 directed guidance graph as a versatile representation of guidance for lifelong MAPF, framing Guidance Graph Optimization (GGO) 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 solves GGO by employing CMA-ES, a black-box optimization algorithm. The second method, PIU, optimizes an update model capable of generating guidance, demonstrating the ability to transfer optimized guidance graphs to larger maps with similar layouts. Empirically, we show that (1) our guidance graphs improve the throughput of three representative lifelong MAPF algorithms in four benchmark maps, and (2) our update model can generate guidance graphs for as large as $93 \times 91$ maps and as many as 3000 agents.
• Abstract（参考訳）: 本研究では,MAPF(Multi-Agent Path Finding)のスループット向上のためのガイダンスの活用方法について検討する。 従来の研究では、高速道路などのガイダンスを組み込むことでMAPFアルゴリズムを加速できるが、ソリューションの品質とのトレードオフをもたらすことが示されている。 さらに、優れたガイダンスを自動生成する方法はほとんど探索されておらず、現在の手法は手作業で設計したものを超えていない。 本稿では,生涯mapfのガイダンスの汎用表現としてdirected guidance graphを導入し,そのエッジ重みを最適化するタスクとしてframing guidance graph optimization(ggo)を提案する。 任意の寿命のMAPFアルゴリズムとマップのガイダンスを自動生成する2つのGGOアルゴリズムを提案する。 最初の方法はブラックボックス最適化アルゴリズムであるCMA-ESを用いてGGOを直接解く。 第2の方法であるPIUは、ガイダンスを生成することのできる更新モデルを最適化し、最適化されたガイダンスグラフを同様のレイアウトを持つ大きなマップに転送する機能を示す。 その結果,(1)誘導グラフは4つのベンチマークマップにおいて3つの代表的な長寿命mapfアルゴリズムのスループットを向上し,(2)更新モデルは最大93 \times 91$mapと最大3000エージェントの誘導グラフを生成することができることがわかった。

関連論文リスト

• An Automatic Graph Construction Framework based on Large Language Models for Recommendation [49.51799417575638]
  本稿では,大規模言語モデルに基づく自動グラフ構築フレームワークであるAutoGraphを紹介する。 LLMはユーザ好みとアイテムの知識を推論し、セマンティックベクターとして符号化する。 潜在因子は、ユーザ/イテムノードをリンクする余分なノードとして組み込まれ、結果として、深いグローバルビューセマンティクスを持つグラフとなる。
  論文  参考訳（メタデータ） (2024-12-24T07:51:29Z)
• 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)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  本稿では,新たなノードやエッジを自動的に拡張して,高密度サブグラフ内のラベル類似性を向上する,新しい前処理手法であるElectoral College(ELCO)を提案する。 テストされたすべての設定において、我々の手法はベースモデルの平均スコアを4.7ポイントの広いマージンで引き上げるとともに、常に最先端のモデルよりも優れています。
  論文  参考訳（メタデータ） (2020-06-10T14:48:48Z)
• 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)

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

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