論文の概要: Planning over MAPF Agent Dependencies via Multi-Dependency PIBT
- arxiv url: http://arxiv.org/abs/2603.23405v1
- Date: Tue, 24 Mar 2026 16:38:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-25 19:53:37.587666
- Title: Planning over MAPF Agent Dependencies via Multi-Dependency PIBT
- Title（参考訳）: 多依存PIBTを用いたMAPFエージェント依存の計画
- Authors: Zixiang Jiang, Yulun Zhang, Rishi Veerapaneni, Jiaoyang Li,
- Abstract要約: MAPF(Multi-Agent Path Finding)アルゴリズムは、密集した環境で数百から数千のエージェントを1秒以内に計画する必要がある。
PIBTはそのような状況下で効果的に計画できる一般的なアルゴリズムである。
エージェント依存を検索する多依存PIBT(MD-PIBT)を提案する。
- 参考スコア（独自算出の注目度）: 26.73382486796029
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Modern Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second, requiring highly efficient algorithms. Priority Inheritance with Backtracking (PIBT) is a popular algorithm capable of effectively planning in such situations. However, PIBT is constrained by its rule-based planning procedure and lacks generality because it restricts its search to paths that conflict with at most one other agent. This limitation also applies to Enhanced PIBT (EPIBT), a recent extension of PIBT. In this paper, we describe a new perspective on solving MAPF by planning over agent dependencies. Taking inspiration from PIBT's priority inheritance logic, we define the concept of agent dependencies and propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies. MD-PIBT is a general framework where specific parameterizations can reproduce PIBT and EPIBT. At the same time, alternative configurations yield novel planning strategies that are not expressible by PIBT or EPIBT. Our experiments demonstrate that MD-PIBT effectively plans for as many as 10,000 homogeneous agents under various kinodynamic constraints, including pebble motion, rotation motion, and differential drive robots with speed and acceleration limits. We perform thorough evaluations on different variants of MAPF and find that MD-PIBT is particularly effective in MAPF with large agents.
- Abstract（参考訳）: 現代のマルチエージェントパス探索(MAPF)アルゴリズムは、数百から数千のエージェントを1秒以内で計画し、高い効率のアルゴリズムを必要とする。
Priority Inheritance with Backtracking (PIBT) はそのような状況下で効果的に計画できる一般的なアルゴリズムである。
しかし、PIBTはルールベースの計画手順に制約されており、他のエージェントと競合するパスへの探索を制限するため、汎用性に欠ける。
この制限は、PIBTの最近の拡張であるEPIBT(Enhanced PIBT)にも適用される。
本稿ではエージェント依存を計画することでMAPFを解く新しい視点について述べる。
PIBTの優先継承論理から着想を得て,エージェント依存の概念を定義し,エージェント依存を検索するMD-PIBT(Multi-Dependency PIBT)を提案する。
MD-PIBTは、特定のパラメータ化がPIBTとEPIBTを再現できる一般的なフレームワークである。
同時に、代替構成はPIBTやEPIBTでは表現できない新しい計画戦略をもたらす。
実験の結果,MD-PIBTは,小石運動,回転運動,速度・加速度制限のあるディファレンシャルドライブロボットなど,様々なキノダイナミック制約の下で,最大1万個の均質エージェントを効果的に計画していることがわかった。
我々はMAPFの異なる変種について徹底的な評価を行い、MD-PIBTがMAPFに特に有効であることが判明した。
関連論文リスト
- Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines [9.228609005424348]
時間に敏感なアプリケーションのための実行インフォームドMAPF計画フレームワークであるREMAPを提案する。
我々のフレームワークは提案したExecTimeNetを統合し、計画されたパスに基づいて実行時間を正確に推定する。
実験の結果、REMAPはベースライン法よりもソリューション品質を最大20%改善することがわかった。
論文 参考訳（メタデータ） (2025-11-26T20:08:52Z) - WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning [7.2069924323665235]
エージェントの大規模なグループに対する衝突のない経路の計画は、多くの現実世界のアプリケーションにおいて難しい問題である。
我々は,MAPFプランをキノダイナミックに実現可能なプランに効率的に洗練するマルチエージェント速度最適化アルゴリズムである,キノダイナミック時空間グラフ計画(kTPG)を提案する。
kTPGをベースとしたMAPF実行フレームワークであるWindowed kTPG(WinkTPG)を提案する。
論文 参考訳（メタデータ） (2025-08-02T21:33:08Z) - Budget Allocation Policies for Real-Time Multi-Agent Path Finding [11.050047263054985]
リアルタイムMAPFは、計画と実行がインターリーブされる現実的なMAPFセットアップを具現化する。
RT-MAPFの既存のソリューションは、計画期間毎にMAPFアルゴリズムのウィンドウバージョンを反復的に呼び出す。
標準MAPFアルゴリズムのウィンドウ化バージョンにおける計画予算の配分について検討する。
論文 参考訳（メタデータ） (2025-07-22T08:32:55Z) - PGPO: Enhancing Agent Reasoning via Pseudocode-style Planning Guided Preference Optimization [58.465778756331574]
本稿では,効果的なエージェント学習のためのPGPOと呼ばれる疑似コード型計画優先最適化手法を提案する。
2つの計画指向の報酬により、PGPOは、高品質なPコードプランを生成するLLMエージェントの能力をさらに強化する。
実験により、PGPOは代表エージェントベンチマークよりも優れた性能を示し、現在のリードベースラインより優れていることが示された。
論文 参考訳（メタデータ） (2025-06-02T09:35:07Z) - Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding [10.174848090916669]
本稿では,PIBTにおけるタイブレーキングの簡易かつ効果的な2つの手法について検討する。
最初のテクニックでは、エージェントが他のエージェントをインテリジェントにドッジし、各アクションが次のステップの進行を妨げるかどうかを考慮に入れます。
第2のテクニックは、複数のPIBT実行を通じて、アクションが他人に後悔を引き起こす方法を学び、この情報を使って、後悔を最小化することである。
論文 参考訳（メタデータ） (2025-05-19T02:12:29Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。
本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。
MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文 参考訳（メタデータ） (2023-12-26T06:57:22Z) - Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。
MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。
本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
論文 参考訳（メタデータ） (2023-03-30T14:42:41Z) - The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
マルチエージェントPPO(MAPPO)は、集中型値関数を採用するマルチエージェントPPOバリアントである。
MAPPOは,3つの一般的なマルチエージェントテストベッドにおいて,最先端技術に匹敵する性能を実現していることを示す。
論文 参考訳（メタデータ） (2021-03-02T18:59:56Z) - Exploiting Submodular Value Functions For Scaling Up Active Perception [60.81276437097671]
アクティブな知覚タスクでは、エージェントは1つ以上の隠れ変数の不確実性を減少させる感覚行動を選択することを目的としている。
部分的に観測可能なマルコフ決定過程(POMDP)は、そのような問題に対する自然なモデルを提供する。
エージェントが利用できるセンサーの数が増えるにつれて、POMDP計画の計算コストは指数関数的に増加する。
論文 参考訳（メタデータ） (2020-09-21T09:11:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。