論文の概要: Scalable Mechanism Design for Multi-Agent Path Finding

• arxiv url: http://arxiv.org/abs/2401.17044v1
• Date: Tue, 30 Jan 2024 14:26:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-31 14:41:46.066425
• Title: Scalable Mechanism Design for Multi-Agent Path Finding
• Title（参考訳）: マルチエージェントパス探索のためのスケーラブルなメカニズム設計
• Authors: Paul Friedrich, Yulun Zhang, Michael Curry, Ludwig Dierks, Stephen McAleer, Jiaoyang Li, Tuomas Sandholm, Sven Seuken
• Abstract要約: MAPF (Multi-Agent Path Finding) は、複数のエージェントが特定の目標地点に向かって共有領域を同時に移動するための経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似アルゴリズムを用いることが不可欠である。 本稿では,MAPFのスケーラブルな機構設計の問題を紹介し,その対策として3つのメカニズムを提案する。
• 参考スコア（独自算出の注目度）: 90.68703851865585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously through a shared area toward particular goal locations. This problem is computationally complex, especially when dealing with large numbers of agents, as is common in realistic applications like autonomous vehicle coordination. Finding an optimal solution is often computationally infeasible, making the use of approximate algorithms essential. Adding to the complexity, agents might act in a self-interested and strategic way, possibly misrepresenting their goals to the MAPF algorithm if it benefits them. Although the field of mechanism design offers tools to align incentives, using these tools without careful consideration can fail when only having access to approximately optimal outcomes. Since approximations are crucial for scalable MAPF algorithms, this poses a significant challenge. In this work, we introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms. We test our mechanisms on realistic MAPF domains with problem sizes ranging from dozens to hundreds of agents. Our findings indicate that they improve welfare beyond a simple baseline.
• Abstract（参考訳）: MAPF(Multi-Agent Path Finding)は、複数のエージェントが特定の目標地点に向かって共有領域を同時に移動するための経路を決定する。 この問題は計算的に複雑であり、特に多数のエージェントを扱う場合、自動運転車の協調のような現実的な応用でよく見られる。 最適解を見つけることはしばしば計算上不可能であり、近似アルゴリズムの使用が不可欠である。 この複雑さを加味すれば、エージェントは自己関心と戦略的な方法で行動し、MAPFアルゴリズムにその目標を誤った表現をする可能性がある。 機構設計の分野はインセンティブを調整するためのツールを提供しているが、注意を払わずにこれらのツールを使用することは、ほぼ最適な結果にしかアクセスできない場合に失敗する可能性がある。 スケーラブルMAPFアルゴリズムには近似が不可欠であるため、これは大きな課題となる。 本稿では,mapfのスケーラブルな機構設計の問題を紹介し,その2つが近似mapfアルゴリズムを用いた3つの戦略耐性メカニズムを提案する。 私たちは、数十から数百のエージェントによる問題サイズの現実的なmapfドメインでメカニズムをテストする。 以上の結果から,単純な基準を超えた福祉の改善が期待できる。

関連論文リスト

• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  マルチエージェントパスフィンディング(Multi-agent pathfinding)は、共有環境における複数のエージェントの衝突のないパスを見つけることを必要とする、難しい計算問題である。 我々はMAPF-GPTと呼ばれるMAPF問題の基盤モデルを構築した。 擬似学習を用いて、部分観測可能性の条件下での行動を生成するための準最適専門家軌道のセットに関する政策を訓練した。 MAPF-GPTは、様々な問題インスタンスにおいて、現在最も優れた学習可能なMAPF解法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-08-29T12:55:10Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
  MAPF(Multi-Agent Path Finding)は、ロボット工学における基本的な問題であり、エージェントのチームに対して衝突のない経路の計算を求める。 本稿では,MAPFにエージェントを誘導する手法を提案する。 各エージェントが1つの宛先を持つワンショットMAPFと、エージェントが常に新しい宛先を割り当てる終身MAPFの2つの大規模設定でこのアイデアを評価する。
  論文  参考訳（メタデータ） (2023-08-22T07:17:39Z)
• Multi-Agent Reinforcement Learning for Microprocessor Design Space Exploration [71.95914457415624]
  マイクロプロセッサアーキテクトは、高性能でエネルギー効率の追求において、ドメイン固有のカスタマイズにますます頼っている。 この問題に対処するために,Multi-Agent RL (MARL) を利用した別の定式化を提案する。 評価の結果,MARLの定式化は単エージェントRLのベースラインよりも一貫して優れていた。
  論文  参考訳（メタデータ） (2022-11-29T17:10:24Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。 この問題をある程度緩和する手法を提案する。
  論文  参考訳（メタデータ） (2021-08-11T10:42:11Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。 我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。 コア最適化問題の実用的なパラメトリゼーションを提供する。
  論文  参考訳（メタデータ） (2021-07-08T18:01:02Z)
• Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
  MAPF (Multi Agent Path Finding) は、空間的に拡張されたエージェントに対する競合のない経路の同定を必要とする。 これらは、Convoy Movement ProblemやTraning Schedulingといった現実世界の問題に適用できる。 提案手法であるDecentralized Multi Agent Path Finding (DeMAPF) は、MAPFを経路計画と割り当ての問題の系列として扱う。
  論文  参考訳（メタデータ） (2021-06-03T18:07:26Z)
• Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities [7.766921168069532]
  このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。 最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
  論文  参考訳（メタデータ） (2021-04-23T20:13:12Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。 本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。 当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
  論文  参考訳（メタデータ） (2020-04-17T14:56:29Z)

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

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