論文の概要: Accelerating Multi-Agent Planning Using Graph Transformers with Bounded Suboptimality

• arxiv url: http://arxiv.org/abs/2301.08451v1
• Date: Fri, 20 Jan 2023 07:22:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-23 13:39:18.123594
• Title: Accelerating Multi-Agent Planning Using Graph Transformers with Bounded Suboptimality
• Title（参考訳）: 有界部分最適性をもつグラフトランスフォーマーを用いたマルチエージェント計画の高速化
• Authors: Chenning Yu, Qingbiao Li, Sicun Gao, Amanda Prorok
• Abstract要約: 競合ベースの検索は、マルチエージェントパス探索の最も一般的な方法の1つである。 計画の高速化を目的とした学習ベースコンポーネントであるグラフトランスフォーマーを提案する。 その結果、提案したグラフトランスフォーマーは、比較的少ないエージェントで問題インスタンスでトレーニング可能であることがわかった。
• 参考スコア（独自算出の注目度）: 13.203261059264728
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conflict-Based Search is one of the most popular methods for multi-agent path finding. Though it is complete and optimal, it does not scale well. Recent works have been proposed to accelerate it by introducing various heuristics. However, whether these heuristics can apply to non-grid-based problem settings while maintaining their effectiveness remains an open question. In this work, we find that the answer is prone to be no. To this end, we propose a learning-based component, i.e., the Graph Transformer, as a heuristic function to accelerate the planning. The proposed method is provably complete and bounded-suboptimal with any desired factor. We conduct extensive experiments on two environments with dense graphs. Results show that the proposed Graph Transformer can be trained in problem instances with relatively few agents and generalizes well to a larger number of agents, while achieving better performance than state-of-the-art methods.
• Abstract（参考訳）: 競合ベースの検索は、マルチエージェントパス探索の最も一般的な方法の1つである。 完全かつ最適ではあるが、スケールが良くない。 様々なヒューリスティックを導入して加速する最近の研究が提案されている。 しかし、これらのヒューリスティックが非グリッドベースの問題設定に適用できるかどうかは、その有効性を維持しながら、未解決の問題である。 この研究では、答えがNoになる傾向があることが分かりました。 そこで本研究では,グラフ変換器を設計の高速化のためのヒューリスティック関数として,学習ベースのコンポーネントを提案する。 提案手法は任意の所望の因子で完全かつ有界に最適である。 密度グラフを持つ2つの環境に対して広範な実験を行う。 その結果,提案するグラフトランスフォーマーは,エージェントが比較的少ない問題インスタンスでトレーニングでき,より多数のエージェントに一般化できると同時に,最先端の手法よりも優れた性能が得られることがわかった。

関連論文リスト

• Fast Semi-supervised Learning on Large Graphs: An Improved Green-function Method [93.04936336359502]
  グラフに基づく半教師付き学習において、グリーン関数法はグラフ空間におけるグリーン関数の計算によって機能する古典的な方法である。 そこで本研究では,最適化の観点から詳細な解析を行い,新しい手法を提案する。 従来の手法とは異なり,改良手法ではガウス除去法とアンコレッドグラフ法という2つの高速化手法を適用できる。
  論文  参考訳（メタデータ） (2024-11-04T04:27:18Z)
• Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding [36.61907023057978]
  スペクトル埋め込みは強力なグラフ計算手法であり、グラフトランスフォーマーの有効性から最近多くの注目を集めている。 従来の手法は、新しい不変量を学び、高い複雑さに苦しむために、コストのかかるアプローチを開発した。 本研究では,固有ベクトルの正準方向を直接求めることにより,あいまいさを解消する最小限のアプローチを検討する。
  論文  参考訳（メタデータ） (2023-10-28T14:35:10Z)
• Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
  エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。 フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。 この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
  論文  参考訳（メタデータ） (2023-05-25T17:56:24Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Tensor Train for Global Optimization Problems in Robotics [6.702251803443858]
  多くの数値最適化手法の収束は、解法に与えられる初期推定に大きく依存する。 本稿では,グローバルオプティマ付近で既存の最適化解法を初期化するための手法を用いた新しい手法を提案する。 提案手法は,グローバル・オプティマに近づいたサンプルを複数モードで生成できることを示す。
  論文  参考訳（メタデータ） (2022-06-10T13:18:26Z)
• What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
  我々はハイパーキューブにおけるトークンインタラクションをモデル化し、バニラ変換器と同等あるいはそれ以上の結果を示すスパーストランスフォーマーHypercube Transformerを提案する。 様々なシーケンス長を必要とするタスクの実験は、グラフ関数の検証をうまく行いました。
  論文  参考訳（メタデータ） (2022-05-27T14:36:55Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。 この問題をある程度緩和する手法を提案する。
  論文  参考訳（メタデータ） (2021-08-11T10:42:11Z)
• Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning [92.05556163518999]
  MARLは、コミュニケーションと可観測性に様々な制約を課すことによって、問題を悪化させる。 値ベースの手法では、最適な値関数を正確に表現することが課題となる。 政策勾配法では、批判者の訓練を困難にし、遅れる批判者の問題を悪化させる。 学習理論の観点からは、関連するアクション値関数を正確に表現することで、両方の問題に対処できることが示される。
  論文  参考訳（メタデータ） (2021-05-31T23:08:05Z)
• On Satisficing in Quantitative Games [30.53498001438171]
  本研究は,割引コストモデルを用いた2プレイヤーグラフゲームにおける満足度問題を定義し,検討する。 最適化問題と同様に数値手法で満足度を解くことができるが、この手法は最適化よりも説得力のある利点を示さない。
  論文  参考訳（メタデータ） (2021-01-06T07:47:13Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。 本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
  論文  参考訳（メタデータ） (2020-04-30T01:50:37Z)

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

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