論文の概要: Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions

• arxiv url: http://arxiv.org/abs/2603.18866v1
• Date: Thu, 19 Mar 2026 13:12:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-20 17:19:06.156752
• Title: Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions
• Title（参考訳）: 非同期動作による複数エージェント経路の競合に基づく探索
• Authors: Xuemian Wu, Shizhe Zhao, Zhongqiang Ren,
• Abstract要約: MAPF(Multi-Agent Path Finding)は、各開始地点から各目標地点まで、複数のエージェントの衝突のない経路を求める。 既存のMAPFアルゴリズムの多くは、すべてのエージェントのアクションが同時に始まり、常に時間単位を取るという、同期されたアクションの一般的な仮定に依存している。 本稿では,MAPF-AAの完全性と解の最適性を保証する新しい手法である Conflict-based Search with Asynchronous Actions (CBS-AA) を提案する。
• 参考スコア（独自算出の注目度）: 7.042035340772298
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start locations to their respective goal locations while minimizing path costs. Most existing MAPF algorithms rely on a common assumption of synchronized actions, where the actions of all agents start at the same time and always take a time unit, which may limit the use of MAPF planners in practice. To get rid of this assumption, Continuous-time Conflict-Based Search (CCBS) is a popular approach that can find optimal solutions for MAPF with asynchronous actions (MAPF-AA). However, CCBS has recently been identified to be incomplete due to an uncountably infinite state space created by continuous wait durations. This paper proposes a new method, Conflict-Based Search with Asynchronous Actions (CBS-AA), which bypasses this theoretical issue and can solve MAPF-AA with completeness and solution optimality guarantees. Based on CBS-AA, we also develop conflict resolution techniques to improve the scalability of CBS-AA further. Our test results show that our method can reduce the number of branches by up to 90%.
• Abstract（参考訳）: MAPF (Multi-Agent Path Finding) は、経路コストを最小化しながら、各開始地点から各目標地点までの複数のエージェントの衝突のない経路を求める。 既存のMAPFアルゴリズムの多くは、すべてのエージェントのアクションを同時に開始し、常に時間単位を取るという、同期されたアクションの一般的な仮定に依存している。 この仮定を解消するために、Continuous-time Conflict-Based Search (CCBS) は、MAPFの非同期アクション(MAPF-AA)による最適ソリューションを見つけるための一般的なアプローチである。 しかし、CCBSは最近、連続した待ち時間によって生じる数え切れないほど無限の状態空間のために不完全であると認識されている。 本稿では,この理論問題を回避し,完全性と解の最適性を保証したMAPF-AAを解き明かす新しい手法である Conflict-based Search with Asynchronous Actions (CBS-AA) を提案する。 また,CBS-AAを基盤として,CBS-AAのスケーラビリティ向上のためのコンフリクト解決技術を開発した。 以上の結果から,本手法は分岐数を最大90%削減できることがわかった。

関連論文リスト

• 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)
• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。 我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。 古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
  論文  参考訳（メタデータ） (2024-04-25T07:41:47Z)
• 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)
• Target before Shooting: Accurate Anomaly Detection and Localization under One Millisecond via Cascade Patch Retrieval [49.45246833329707]
  異常検出(AD)の「マッチング」性を再検討する 本稿では,ADの精度と実行速度を同時に向上する新しいADフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-08-13T11:49:05Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。 また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。 提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
  論文  参考訳（メタデータ） (2022-10-07T00:40:59Z)
• Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions [10.354181009277623]
  マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。 この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。
  論文  参考訳（メタデータ） (2021-03-08T02:34:17Z)

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

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