論文の概要: Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding

• arxiv url: http://arxiv.org/abs/2603.26684v1
• Date: Wed, 11 Mar 2026 11:04:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-06 02:36:13.071545
• Title: Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding
• Title（参考訳）: スケーラブルなマルチエージェントパス探索における幾何学的計画と実行のデカップリング
• Authors: Fernando Salanova, Cristian Mahulea, Eduardo Montijano,
• Abstract要約: Multi-Agent Path Finding (MAPF) は、共有グラフ上の複数のエージェントに対して衝突のない軌道を必要とする。 本稿では,幾何計画と実行時競合解決を分離するハイブリッドな優先順位付けフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 44.79409119345322
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph, often with the objective of minimizing the sum-of-costs (SOC). Many optimal and bounded-suboptimal solvers rely on time-expanded models and centralized conflict resolution, which limits scalability in large or dense instances. We propose a hybrid prioritized framework that separates geometric planning from execution-time conflict resolution. In the first stage, Geometric Conflict Preemption (GCP) plans agents sequentially with A* on the original graph while inflating costs for transitions entering vertices used by higher-priority paths, encouraging spatial detours without explicit time reasoning. In the second stage, a Decentralized Local Controller (DLC) executes the geometric paths using per-vertex FIFO authorization queues and inserts wait actions only when required to avoid vertex and edge-swap conflicts. Experiments on standard benchmark maps with up to 1000 agents show that the method scales with an empirically near-linear runtime trend and attains a 100% success rate on instances satisfying the geometric feasibility assumption. On bottleneck-heavy maps, GCP reduces synchronization-induced waiting and often improves SOC on bottleneck-heavy maps
• Abstract（参考訳）: MAPF (Multi-Agent Path Finding) は、共有グラフ上の複数のエージェントに対する衝突のない軌跡を必要とし、しばしばコストの和 (SOC) を最小限にすることを目的としている。 多くの最適かつ有界な準最適解法は、時間拡張モデルと集中型コンフリクト解決に依存しており、大きなインスタンスや高密度インスタンスのスケーラビリティを制限している。 本稿では,幾何計画と実行時競合解決を分離するハイブリッドな優先順位付けフレームワークを提案する。 最初の段階では、Geometric Conflict Preemption (GCP) は元のグラフ上で A* と逐次的にエージェントを計画し、高優先度パスで使用される頂点への遷移のコストを膨らませ、明示的な時間的推論なしに空間的なデトゥールを奨励する。 第2段階では、分散ローカルコントローラ(DLC)は、頂点ごとのFIFO認証キューを使用して幾何学的パスを実行し、頂点やエッジスワップの衝突を避けるために必要な場合にのみ待機アクションを挿入する。 最大1000のエージェントによる標準ベンチマークマップの実験では、この手法は経験的にほぼ直線的な実行トレンドでスケールし、幾何学的実現可能性の仮定を満たすインスタンスで100%の成功率に達することが示されている。 ボトルネック重みマップでは、GCPは同期による待ち時間を短縮し、ボトルネック重みマップのSOCを改善する。

関連論文リスト

• A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling [6.655206888698601]
  異種有向非巡回グラフ(DAG)のためのエンドツーエンド強化学習フレームワークを提案する。 WeCANはタスクプール互換性係数と生成誘起最適性ギャップに対処する。 グラフと実世界のTPC-H DAGの実験は、古典に匹敵する推論時間で、強いベースラインよりも改善されたメイスパンを示す。
  論文  参考訳（メタデータ） (2026-03-24T14:16:08Z)
• Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM [0.0]
  構造化マルチエージェントプロジェクトでは、エージェントは事前に定義されたルートをたどらなければならず、リルーチンや不可能となる。 本稿では,各エージェントの割り当てられた経路の順序と名前付き経路の割り当てを保ちながら,経路制約付きマルチエージェント協調に対処する。
  論文  参考訳（メタデータ） (2026-03-23T12:34:18Z)
• Speedup Techniques for Switchable Temporal Plan Graph Optimization [7.478072166004144]
  MAPF (Multi-Agent Path Finding) は、複数エージェントの衝突のない経路を計画することに焦点を当てている。 MAPF計画の実行中、エージェントは予期せぬ遅延に遭遇し、非効率性、デッドロック、さらには衝突に至る可能性がある。 本稿では,グラフベーススイッチブルエッジサーチ(GSES)を4つの高速化手法により大幅に高速化する改良GSESを提案する。
  論文  参考訳（メタデータ） (2024-12-20T13:59:15Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。 提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。 本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
  論文  参考訳（メタデータ） (2023-04-28T07:09:23Z)
• GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
  精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。 不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。 我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
  論文  参考訳（メタデータ） (2022-11-04T16:10:50Z)
• Decoupled Multi-task Learning with Cyclical Self-Regulation for Face Parsing [71.19528222206088]
  顔解析のための周期的自己統制型デカップリング型マルチタスク学習を提案する。 具体的には、DML-CSRは、顔解析、バイナリエッジ、カテゴリエッジ検出を含むマルチタスクモデルを設計する。 提案手法は,Helen,CelebA-HQ,LapaMaskのデータセット上での最先端性能を実現する。
  論文  参考訳（メタデータ） (2022-03-28T02:12:30Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
  k-Robust Conflict-BasedSearch (k-CBS)は、最大k遅延のロバストな座標と衝突のない計画を生成するアルゴリズムです。 そこで我々は,k-robust計画に特有な様々な対称性の破れ制約を導入し,矛盾するエージェントのペアに対して,効率よく相反する最適経路を見つける。
  論文  参考訳（メタデータ） (2021-02-17T11:09:33Z)
• 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)

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

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