論文の概要: Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines

• arxiv url: http://arxiv.org/abs/2511.21886v1
• Date: Wed, 26 Nov 2025 20:08:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-01 19:47:55.284167
• Title: Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines
• Title（参考訳）: ブリッジング計画と実行:現実世界のデッドラインの下で見つかるマルチエージェントパス
• Authors: Jingtian Yan, Shuai Zhou, Stephen F. Smith, Jiaoyang Li,
• Abstract要約: 時間に敏感なアプリケーションのための実行インフォームドMAPF計画フレームワークであるREMAPを提案する。 我々のフレームワークは提案したExecTimeNetを統合し、計画されたパスに基づいて実行時間を正確に推定する。 実験の結果、REMAPはベースライン法よりもソリューション品質を最大20%改善することがわかった。
• 参考スコア（独自算出の注目度）: 9.228609005424348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Multi-Agent Path Finding (MAPF) problem aims to find collision-free paths for multiple agents while optimizing objectives such as the sum of costs or makespan. MAPF has wide applications in domains like automated warehouses, manufacturing systems, and airport logistics. However, most MAPF formulations assume a simplified robot model for planning, which overlooks execution-time factors such as kinodynamic constraints, communication latency, and controller variability. This gap between planning and execution is problematic for time-sensitive applications. To bridge this gap, we propose REMAP, an execution-informed MAPF planning framework that can be combined with leading search-based MAPF planners with minor changes. Our framework integrates the proposed ExecTimeNet to accurately estimate execution time based on planned paths. We demonstrate our method for solving MAPF with Real-world Deadlines (MAPF-RD) problem, where agents must reach their goals before a predefined wall-clock time. We integrate our framework with two popular MAPF methods, MAPF-LNS and CBS. Experiments show that REMAP achieves up to 20% improvement in solution quality over baseline methods (e.g., constant execution speed estimators) on benchmark maps with up to 300 agents.
• Abstract（参考訳）: MAPF問題(Multi-Agent Path Finding)は、コストの和やメースパンといった目的を最適化しながら、複数のエージェントの衝突のない経路を見つけることを目的としている。 MAPFは、自動倉庫、製造システム、空港の物流といった分野に広く応用されている。 しかし、ほとんどのMAPFの定式化は、キノダイナミック制約、通信遅延、コントローラの可変性といった実行時の要因を無視する、計画のための単純化されたロボットモデルを前提としている。 計画と実行のこのギャップは、時間に敏感なアプリケーションには問題があります。 このギャップを埋めるため,主要な検索ベースMAPFプランナと小さな変更を併用可能な,実行インフォームドMAPF計画フレームワークであるREMAPを提案する。 我々のフレームワークは提案したExecTimeNetを統合し、計画されたパスに基づいて実行時間を正確に推定する。 実世界デッドライン(MAPF-RD)問題を用いてMAPFを解く手法を実証する。 我々はこのフレームワークをMAPF-LNSとCBSという2つの人気のあるMAPFメソッドと統合する。 実験の結果、REMAPは最大300のエージェントを持つベンチマークマップ上で、ベースライン法(例えば、一定実行速度推定器)よりもソリューション品質を最大20%改善することがわかった。

関連論文リスト

• 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)
• Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning [46.35418789518417]
  マルチエージェントパスフィンディング(MAPF)は、マルチロボット軌道計画問題の共通の抽象化である。 本稿では,機械学習を活用した分散化サブ最適化MAPFソルバMAPF-GPT-DDGを紹介する。 本実験は,MAPF-GPT-DDGが既存の学習型MAPF解法を超えることを示した。
  論文  参考訳（メタデータ） (2025-06-30T12:34:31Z)
• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  MAPF(Multi-agent pathfinding)は、一般に、共有環境において複数のエージェントに対して衝突のない経路を見つけることを必要とする問題である。 近年、MAPFへの学習に基づくアプローチが注目されており、特に深層強化学習を活用している。 MAPF-GPTは,多種多様な問題インスタンスにおいて,現在最も優れた学習可能なMAPFソルバよりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-08-29T12:55:10Z)
• 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)
• 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)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  複数の自動誘導車両 (AGV) が共通作業空間をナビゲートし, 様々な作業を行う。 一つのアプローチは、Action Dependency Graph (ADG)を構築し、そのルートに沿って進むとAGVの順序を符号化する。 ワークスペースが人間やサードパーティロボットのような動的障害によって共有されている場合、AGVは大きな遅延を経験することができる。 本稿では,各AGVの経路完了時間を最小限に抑えるために,非循環ADGを繰り返し修正するオンライン手法を提案する。
  論文  参考訳（メタデータ） (2020-10-11T14:39:50Z)

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

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