論文の概要: 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エージェントの誘導グラフを生成することができることがわかった。
関連論文リスト
- Unleashing the Potential of Large Language Models as Prompt Optimizers:
An Analogical Analysis with Gradient-based Model Optimizers [115.2038169433773]
本稿では,大規模言語モデル(LLM)に基づくプロンプトの設計について検討する。
モデルパラメータ学習における2つの重要な要素を同定する。
特に、勾配に基づく最適化から理論的な枠組みや学習手法を借用し、改良された戦略を設計する。
論文 参考訳(メタデータ) (2024-02-27T15:05:32Z) - Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
本研究では、動的プログラミング(DP)にインスパイアされた最大独立集合(MIS)問題を解決するグラフニューラルネットワーク(GNN)フレームワークを提案する。
GNNをベースとしたDPライクな再帰アルゴリズムを提案し、まず2つの小さなサブグラフを構築し、より大きなMISを持つサブグラフを予測し、次に再帰呼び出しを行う。
MISサイズに関する異なるグラフの比較を注釈付けすると、自己学習プロセスが発生し、比較をより正確に自己アノテーションし、その逆も引き起こされる。
論文 参考訳(メタデータ) (2023-10-28T10:58:25Z) - A Fast and Optimal Learning-based Path Planning Method for Planetary
Rovers [6.139022993099647]
本研究では,NNPPと呼ばれる標高マップの最適経路を高速に探索する学習手法を提案する。
NNPPモデルは、多くの事前注釈付き最適経路のデモから、スタート地点とゴール地点のセマンティック情報とマップ表現を学習する。
NNPPモデルにより生成された誘導場は,同じハードウェア条件下での最適経路の探索時間を著しく短縮できることを示す。
論文 参考訳(メタデータ) (2023-08-09T08:31:05Z) - SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
テキストグラフ学習におけるフラストレーションに富んだアプローチであるSimTeGを提案する。
まず、下流タスクで予め訓練されたLM上で、教師付きパラメータ効率の微調整(PEFT)を行う。
次に、微調整されたLMの最後の隠れ状態を用いてノード埋め込みを生成する。
論文 参考訳(メタデータ) (2023-08-03T07:00:04Z) - Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。
基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。
我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文 参考訳(メタデータ) (2022-09-27T17:51:31Z) - RNGDet++: Road Network Graph Detection by Transformer with Instance
Segmentation and Multi-scale Features Enhancement [19.263691277963368]
道路網のグラフ構造は、グローバルな計画、動き予測、制御など、自律運転システムの下流業務に不可欠である。
これまでは、道路ネットワークグラフは人の専門家によって手動で注釈付けされていた。
前者は、プロセス後セマンティックセグメンテーションマップや、ロードネットワークグラフを直接予測するグラフベースのアルゴリズムを提案している。
それまでの作業は、ハードコードされた処理アルゴリズムと劣った最終性能に悩まされていた。
提案されたアプローチはRNGDetから改善されているため、RNGDet++と呼ばれている。
論文 参考訳(メタデータ) (2022-09-21T07:06:46Z) - Transferable Graph Optimizers for ML Compilers [18.353830282858834]
計算グラフ最適化(GO)のためのエンドツーエンドで転送可能な深層強化学習法を提案する。
GOは個々のノードに対して自動回帰ではなく,グラフ全体の決定を生成する。
GOは、人間の専門家よりも21%改善し、先行技術よりも18%改善し、15倍早く収束する。
論文 参考訳(メタデータ) (2020-10-21T20:28:33Z) - Optimization of Graph Neural Networks with Natural Gradient Descent [1.3477333339913569]
グラフに基づく半教師付き学習のための最適化アルゴリズムを,最適化プロセスにおける自然な勾配情報を用いて開発する。
我々の知る限りでは、グラフニューラルネットワークの最適化に自然勾配を利用した最初の研究である。
論文 参考訳(メタデータ) (2020-08-21T18:00:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。