論文の概要: Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding

• arxiv url: http://arxiv.org/abs/2505.12623v1
• Date: Mon, 19 May 2025 02:12:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:11.352138
• Title: Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding
• Title（参考訳）: 大規模マルチエージェントパスフィニングのためのPIBTの軽量化と有効優先構成
• Authors: Keisuke Okumura, Hiroki Nagai,
• Abstract要約: 本稿では,PIBTにおけるタイブレーキングの簡易かつ効果的な2つの手法について検討する。 最初のテクニックでは、エージェントが他のエージェントをインテリジェントにドッジし、各アクションが次のステップの進行を妨げるかどうかを考慮に入れます。 第2のテクニックは、複数のPIBT実行を通じて、アクションが他人に後悔を引き起こす方法を学び、この情報を使って、後悔を最小化することである。
• 参考スコア（独自算出の注目度）: 10.174848090916669
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: PIBT is a computationally lightweight algorithm that can be applied to a variety of multi-agent pathfinding (MAPF) problems, generating the next collision-free locations of agents given another. Because of its simplicity and scalability, it is becoming a popular underlying scheme for recent large-scale MAPF methods involving several hundreds or thousands of agents. Vanilla PIBT makes agents behave greedily towards their assigned goals, while agents typically have multiple best actions, since the graph shortest path is not always unique. Consequently, tiebreaking about how to choose between these actions significantly affects resulting solutions. This paper studies two simple yet effective techniques for tiebreaking in PIBT, without compromising its computational advantage. The first technique allows an agent to intelligently dodge another, taking into account whether each action will hinder the progress of the next timestep. The second technique is to learn, through multiple PIBT runs, how an action causes regret in others and to use this information to minimise regret collectively. Our empirical results demonstrate that these techniques can reduce the solution cost of one-shot MAPF and improve the throughput of lifelong MAPF. For instance, in densely populated one-shot cases, the combined use of these tiebreaks achieves improvements of around 10-20% in sum-of-costs, without significantly compromising the speed of a PIBT-based planner.
• Abstract（参考訳）: PIBTは計算的に軽量なアルゴリズムであり、様々なマルチエージェントパスフィニング(MAPF)問題に適用でき、次の衝突のないエージェントの位置を生成する。 その単純さとスケーラビリティのため、数百から数千のエージェントを含む最近の大規模MAPF手法の基盤となっている。 バニラPIBTは、エージェントが割り当てられた目標に対して優しく振る舞うのに対して、エージェントは通常、グラフの最短経路が必ずしもユニークであるとは限らないため、複数のベストアクションを持つ。 結果として、これらのアクションをどのように選択するかというタイブレークは、結果のソリューションに大きく影響します。 本稿では,PIBTにおいて,計算上の優位性を損なうことなく,簡易かつ効果的にタイブレークを行う2つの手法について検討する。 最初のテクニックでは、エージェントが他のエージェントをインテリジェントにドッジし、各アクションが次のステップの進行を妨げるかどうかを考慮に入れます。 第2のテクニックは、複数のPIBT実行を通じて、アクションが他人に後悔を引き起こす方法を学び、この情報を使って、後悔を最小化することである。 実験により,これらの技術はワンショットMAPFの解法コストを低減し,寿命が長いMAPFのスループットを向上させることができることが示された。 例えば、密集したワンショットの場合、これらのタイブレイクの組み合わせは、PIBTベースのプランナーの速度を著しく向上させることなく、コストの合計で約10-20%の改善を実現する。

関連論文リスト

• Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions [5.5233853454863615]
  MAPF(Multi-Agent Path Finding)は、各開始地点から各目標地点まで、複数のエージェントの衝突のない経路を求める。 多くのMAPFアルゴリズムは数千のエージェントを処理できるが、エージェントの各アクションが時間単位を必要とするという仮定に依存している。 本稿では,新たなプランナを開発し,スケーラビリティのためのソリューション品質をトレードオフする。
  論文  参考訳（メタデータ） (2024-12-16T11:36:24Z)
• Cooperative Reward Shaping for Multi-Agent Pathfinding [4.244426154524592]
  MAPF(Multi-Agent Pathfinding)の主な目的は、全てのエージェントに対して効率的で競合のないパスを計画することである。 従来のマルチエージェントパス計画アルゴリズムは、複数のエージェントに対して効率的な分散パス計画を実現するのに苦労する。 独立Q-Learning(IQL)に基づく独自の報酬形成手法を紹介する。
  論文  参考訳（メタデータ） (2024-07-15T02:44:41Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである 本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。 マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-02-11T01:51:15Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
  本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。 疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。 後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
  論文  参考訳（メタデータ） (2023-05-30T16:05:44Z)
• Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
  MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。 MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。 本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
  論文  参考訳（メタデータ） (2023-03-30T14:42:41Z)
• Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectification [74.10976684469435]
  オフライン強化学習(RL)アルゴリズムは、直接マルチエージェント設定に転送することができる。 本稿では,この重要な課題に対処するために,Actor Rectification (OMAR) を用いたオフラインマルチエージェント RL を提案する。 OMARはマルチエージェント連続制御ベンチマークにおける最先端性能と強いベースラインを著しく上回る。
  論文  参考訳（メタデータ） (2021-11-22T13:27:42Z)
• The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
  マルチエージェントPPO(MAPPO)は、集中型値関数を採用するマルチエージェントPPOバリアントである。 MAPPOは,3つの一般的なマルチエージェントテストベッドにおいて,最先端技術に匹敵する性能を実現していることを示す。
  論文  参考訳（メタデータ） (2021-03-02T18:59:56Z)
• Scalable Multi-Agent Inverse Reinforcement Learning via Actor-Attention-Critic [54.2180984002807]
  マルチエージェント逆逆強化学習 (MA-AIRL) は, 単エージェントAIRLをマルチエージェント問題に適用する最近の手法である。 本稿では,従来の手法よりもサンプル効率が高く,スケーラブルなマルチエージェント逆RLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-24T20:30:45Z)

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

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