論文の概要: Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds
- arxiv url: http://arxiv.org/abs/2503.03779v1
- Date: Tue, 04 Mar 2025 20:39:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-07 15:58:20.552830
- Title: Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds
- Title（参考訳）: 太い下界を持つマルチエージェントパスにおける声道探索の高速化
- Authors: Yimin Tang, Zhenghong Yu, Jiaoyang Li, Sven Koenig,
- Abstract要約: MAPF (Multi-Agent Path Finding) は、NP困難問題であるコスト関数を最小化しながら、複数のエージェントの衝突のない経路を見つける。
本稿では、まず最大LB値を決定し、次にこのLBで導かれた最優先探索を用いて衝突のない経路を求めることにより、この問題に対処する新しい有界準最適アルゴリズム(DECBS)を提案する。
- 参考スコア（独自算出の注目度）: 18.390974792959685
- License:
- Abstract: Multi-Agent Path Finding (MAPF) involves finding collision-free paths for multiple agents while minimizing a cost function--an NP-hard problem. Bounded suboptimal methods like Enhanced Conflict-Based Search (ECBS) and Explicit Estimation CBS (EECBS) balance solution quality with computational efficiency using focal search mechanisms. While effective, traditional focal search faces a limitation: the lower bound (LB) value determining which nodes enter the FOCAL list often increases slowly in early search stages, resulting in a constrained search space that delays finding valid solutions. In this paper, we propose a novel bounded suboptimal algorithm, double-ECBS (DECBS), to address this issue by first determining the maximum LB value and then employing a best-first search guided by this LB to find a collision-free path. Experimental results demonstrate that DECBS outperforms ECBS in most test cases and is compatible with existing optimization techniques. DECBS can reduce nearly 30% high-level CT nodes and 50% low-level focal search nodes. When agent density is moderate to high, DECBS achieves a 23.5% average runtime improvement over ECBS with identical suboptimality bounds and optimizations.
- Abstract（参考訳）: MAPF (Multi-Agent Path Finding) は、NP困難問題であるコスト関数を最小化しながら、複数のエージェントの衝突のない経路を見つける。
ECBS (Enhanced Conflict-Based Search) や Explicit Estimation CBS (EECBS) のような境界部分最適化手法は、焦点探索機構を用いた計算効率のバランスを保っている。
FOCALリストにどのノードが入るかを決定するローバウンド(LB)値は、初期の検索段階では徐々に増加し、有効な解を見つけるのを遅らせる制約付き検索空間となる。
本稿では、まず最大LB値を決定し、次にこのLBで導かれた最良1次探索を用いて衝突のない経路を求めることにより、この問題に対処する新しい有界準最適アルゴリズム(DECBS)を提案する。
実験の結果,DECBSはほとんどのテストケースでECBSよりも優れており,既存の最適化手法と互換性があることがわかった。
DECBSは、30%近い高レベルCTノードと50%の低レベル焦点探索ノードを削減できる。
エージェント密度が中程度から高い場合、DECBSは同じ準最適境界と最適化を持つCBSに対して平均的なランタイム改善を23.5%達成する。
関連論文リスト
- Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
論文 参考訳（メタデータ） (2024-07-22T23:24:03Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem [20.090818762687565]
ITA-ECBS は ITA-CBS の最初の有界-準最適変種である。
54,033例中87.42%でCBS-TAより高速に動作している。
論文 参考訳（メタデータ） (2024-04-08T06:36:42Z) - Double-Bounded Optimal Transport for Advanced Clustering and
Classification [58.237576976486544]
本稿では,2つの境界内での目標分布の制限を前提としたDB-OT(Douubly bounded Optimal Transport)を提案する。
提案手法は,テスト段階における改良された推論方式により,良好な結果が得られることを示す。
論文 参考訳（メタデータ） (2024-01-21T07:43:01Z) - Solving Multi-Agent Target Assignment and Path Finding with a Single
Constraint Tree [9.518757918128799]
TAPF(Target-Assignment and Path-Finding problem)とTAPF(Target-Assignment and Path-Finding problem)は、エージェントに同時にターゲットを割り当てることを必要とする。
競合ベースのターゲティング・アサインメント(CBS-TA)は、TAPFに対処するための主要なアプローチである。
我々は,理論上,ITA-CBSは最適解を見つけることが保証され,実際は計算効率が高いことを示す。
論文 参考訳（メタデータ） (2023-07-02T20:52:16Z) - Analysis Of The Anytime MAPF Solvers Based On The Combination Of
Conflict-Based Search (CBS) and Focal Search (FS) [2.320417845168326]
競合ベースの探索 (CBS) は多エージェントパスフィンディング問題を最適に解くために広く用いられているアルゴリズムである。
CBSのバウンテッド・サブ最適の異なる変種を走らせるためのトレードオフ最適性を設計した。
CBSの双方のレベルのFocal Searchは、幅広いセットアップにおいて有益であることを示す。
論文 参考訳（メタデータ） (2022-09-20T11:05:14Z) - Fast Bayesian Optimization of Needle-in-a-Haystack Problems using
Zooming Memory-Based Initialization [73.96101108943986]
Needle-in-a-Haystack問題は、データセットのサイズに対して最適な条件が極端に不均衡であるときに発生する。
本稿では,従来のベイズ最適化原理に基づくズームメモリに基づく初期化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T23:57:41Z) - $\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture
Search [85.84110365657455]
本研究では,DARTSに基づくNAS探索過程を正規化するために,ベータデカイと呼ばれるシンプルだが効率的な正規化手法を提案する。
NAS-Bench-201の実験結果から,提案手法は探索過程の安定化に有効であり,探索されたネットワークを異なるデータセット間で転送しやすくする。
論文 参考訳（メタデータ） (2022-03-03T11:47:14Z) - LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial
Attack [74.5144793386864]
LSDATは、入力サンプルのスパース成分と対向サンプルのスパース成分によって形成される低次元部分空間における摂動を加工する。
LSDは画像ピクセル領域で直接動作し、スパース性などの非$ell$制約が満たされることを保証します。
論文 参考訳（メタデータ） (2021-03-19T13:10:47Z) - Improving Continuous-time Conflict Based Search [19.36475688888736]
Conflict-Based Search (CBS) はマルチエージェントパス探索 (MAPF) 問題を最適に解くための強力なフレームワークである。
Continuous-time CBS(CCBS)は、CBSの最近提案されたバージョンで、時間を差別することなく最適なソリューションを保証します。
コンフリクト(PC)、ディジョイン分割(DS)、ハイレベルエージェントをCCBSの連続時間設定に優先順位付けすることで、CBSの改善を成功させる方法を紹介します。
論文 参考訳（メタデータ） (2021-01-24T14:34:25Z) - EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding [40.0986954496361]
明示的推定CBS(英: Explicit Estimation CBS、英: Explicit Estimation CBS)は、オンライン学習を用いて、各ハイレベルノードのソリューションのコストの不可避な推定値を得る、制限付き最適化型CBSである。
EECBSは、さまざまなMAPFインスタンス上で、最先端の有界MAPFアルゴリズムであるECBS、BCP-7、eMDD-SATよりもはるかに高速に動作する。
論文 参考訳（メタデータ） (2020-10-03T14:19:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。