論文の概要: Multi-Agent Pathfinding with Non-Unit Integer Edge Costs via Enhanced Conflict-Based Search and Graph Discretization
- arxiv url: http://arxiv.org/abs/2604.05416v1
- Date: Tue, 07 Apr 2026 04:24:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-08 17:42:09.622241
- Title: Multi-Agent Pathfinding with Non-Unit Integer Edge Costs via Enhanced Conflict-Based Search and Graph Discretization
- Title（参考訳）: コンフリクトに基づく探索とグラフの離散化による非ユニット整数エッジコストによるマルチエージェントパスフィニング
- Authors: Hongkai Fan, Qinjing Xie, Bo Ouyang, Yaonan Wang, Zhi Yan, Jiawen He, Zheng Fang,
- Abstract要約: MAPF(Multi-Agent Pathfinding)は、様々な領域において重要な役割を担っている。
有限状態空間を保存する非単体整数コストを持つグラフ上の新しいMAPF変種を提案する。
また,非単位エッジコストの離散化手法を提案する。
- 参考スコア（独自算出の注目度）: 29.371700483074736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Pathfinding (MAPF) plays a critical role in various domains. Traditional MAPF methods typically assume unit edge costs and single-timestep actions, which limit their applicability to real-world scenarios. MAPFR extends MAPF to handle non-unit costs with real-valued edge costs and continuous-time actions, but its geometric collision model leads to an unbounded state space that compromises solver efficiency. In this paper, we propose MAPFZ, a novel MAPF variant on graphs with non-unit integer costs that preserves a finite state space while offering improved realism over classical MAPF. To solve MAPFZ efficiently, we develop CBS-NIC, an enhanced Conflict-Based Search framework incorporating time-interval-based conflict detection and an improved Safe Interval Path Planning (SIPP) algorithm. Additionally, we propose Bayesian Optimization for Graph Design (BOGD), a discretization method for non-unit edge costs that balances efficiency and accuracy with a sub-linear regret bound. Extensive experiments demonstrate that our approach outperforms state-of-the-art methods in runtime and success rate across diverse benchmark scenarios.
- Abstract（参考訳）: MAPF(Multi-Agent Pathfinding)は、様々な領域において重要な役割を担っている。
従来のMAPFメソッドは、通常、単位のエッジコストとシングルタイムステップアクションを前提としており、現実のシナリオに適用性を制限する。
MAPFRはMAPFを拡張して、実価値の高いエッジコストと連続的な動作で非単位コストを処理するが、幾何学的衝突モデルにより、解法効率を損なうような非有界な状態空間へと導かれる。
本稿では,非単体整数コストを持つグラフ上の新しいMAPF変種MAPFZを提案する。
MAPFZを効率的に解くために,時間間隔に基づく競合検出と改良されたセーフインターバルパス計画(SIPP)アルゴリズムを組み込んだ競合検索フレームワークであるCBS-NICを開発した。
さらに,非単位エッジコストの離散化手法であるBayesian Optimization for Graph Design (BOGD)を提案する。
大規模な実験により、我々の手法は様々なベンチマークシナリオで実行時の最先端の手法と成功率を上回っていることが示された。
関連論文リスト
- Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions [7.042035340772298]
MAPF(Multi-Agent Path Finding)は、各開始地点から各目標地点まで、複数のエージェントの衝突のない経路を求める。
既存のMAPFアルゴリズムの多くは、すべてのエージェントのアクションが同時に始まり、常に時間単位を取るという、同期されたアクションの一般的な仮定に依存している。
本稿では,MAPF-AAの完全性と解の最適性を保証する新しい手法である Conflict-based Search with Asynchronous Actions (CBS-AA) を提案する。
論文 参考訳（メタデータ） (2026-03-19T13:12:27Z) - Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines [9.228609005424348]
時間に敏感なアプリケーションのための実行インフォームドMAPF計画フレームワークであるREMAPを提案する。
我々のフレームワークは提案したExecTimeNetを統合し、計画されたパスに基づいて実行時間を正確に推定する。
実験の結果、REMAPはベースライン法よりもソリューション品質を最大20%改善することがわかった。
論文 参考訳（メタデータ） (2025-11-26T20:08:52Z) - Multi-Objective Multi-Agent Path Finding with Lexicographic Cost Preferences [7.18523391773903]
多目的経路探索(MO-MAPF)アルゴリズムは競合のない計画を生成する。
我々は,MO-MAPFをモデル化するためのレキシコグラフィーフレームワークと,アルゴリズムのテクスタイストLexicographic Conflict-Based Search (LCBS)を提案する。
LCBSは優先順位を意識した低レベルの$A*$検索とコンフリクトベースの検索を統合している。
私たちは最適性とスケーラビリティに関する洞察を提供し、LCBSが最大10の目的を持つインスタンスにスケーリングしながら最適なソリューションを計算していることを実証的に示しています。
論文 参考訳（メタデータ） (2025-10-08T17:40:41Z) - Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
マルチロボット運動計画(MPMP)は、共有された連続作業空間で動作する複数のロボットのための軌道を生成する。
離散マルチエージェント探索(MAPF)法は,その拡張性から広く採用されているが,粗い離散化の軌道品質は高い。
本稿では、制約付き生成拡散モデルを用いた離散MAPF解法を導入することにより、2つのアプローチの限界に対処する。
論文 参考訳（メタデータ） (2025-08-27T17:59:36Z) - Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。
GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。
本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-07-16T02:24:21Z) - Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
分散サーバ(DFL)はクライアント・クライアント・アーキテクチャへの依存をなくす。
非滑らかな正規化はしばしば機械学習タスクに組み込まれる。
本稿では,これらの問題を解決する新しいDNCFLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-17T08:32:25Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。
本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。
我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
論文 参考訳（メタデータ） (2024-11-05T13:55:52Z) - Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
対人的マルコフ決定過程における学習の問題を考える。
本稿では,APO-MVPと呼ばれるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-08T08:06:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。