論文の概要: New Mechanisms in Flex Distribution for Bounded Suboptimal Multi-Agent Path Finding
- arxiv url: http://arxiv.org/abs/2507.17054v1
- Date: Tue, 22 Jul 2025 22:25:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-24 22:33:14.791765
- Title: New Mechanisms in Flex Distribution for Bounded Suboptimal Multi-Agent Path Finding
- Title（参考訳）: 境界下最適マルチエージェントパス探索のためのフレキシブル分布の新しいメカニズム
- Authors: Shao-Hung Chan, Thomy Phan, Jiaoyang Li, Sven Koenig,
- Abstract要約: MAPF (Multi-Agent Path Finding) は、衝突のない経路の集合を見つける問題である。
その目的は、各エージェントの経路コストを、開始位置から目標位置への移動時間として定義するパスコスト(SOC)の総和を最小化することである。
EECBSは、有界-最適MAPFの第一のアルゴリズムであり、ソリューションのSOCは、最大でユーザ指定因子である$w$を最適から遠ざけている。
- 参考スコア（独自算出の注目度）: 21.260600668359178
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths, one for each agent in a shared environment. Its objective is to minimize the sum of path costs (SOC), where the path cost of each agent is defined as the travel time from its start location to its target location. Explicit Estimation Conflict-Based Search (EECBS) is the leading algorithm for bounded-suboptimal MAPF, with the SOC of the solution being at most a user-specified factor $w$ away from optimal. EECBS maintains sets of paths and a lower bound $LB$ on the optimal SOC. Then, it iteratively selects a set of paths whose SOC is at most $w \cdot LB$ and introduces constraints to resolve collisions. For each path in a set, EECBS maintains a lower bound on its optimal path that satisfies constraints. By finding an individually bounded-suboptimal path with cost at most a threshold of $w$ times its lower bound, EECBS guarantees to find a bounded-suboptimal solution. To speed up EECBS, previous work uses flex distribution to increase the threshold. Though EECBS with flex distribution guarantees to find a bounded-suboptimal solution, increasing the thresholds may push the SOC beyond $w \cdot LB$, forcing EECBS to switch among different sets of paths instead of resolving collisions on a particular set of paths, and thus reducing efficiency. To address this issue, we propose Conflict-Based Flex Distribution that distributes flex in proportion to the number of collisions. We also estimate the delays needed to satisfy constraints and propose Delay-Based Flex Distribution. On top of that, we propose Mixed-Strategy Flex Distribution, combining both in a hierarchical framework. We prove that EECBS with our new flex distribution mechanisms is complete and bounded-suboptimal. Our experiments show that our approaches outperform the original (greedy) flex distribution.
- Abstract（参考訳）: MAPF (Multi-Agent Path Finding) は、衝突のない経路の集合を見つける問題である。
その目的は、各エージェントの経路コストを、開始位置から目標位置への移動時間として定義するパスコスト(SOC)の総和を最小化することである。
明示的推定競合ベースサーチ(EECBS)は、制限付き最適MAPFの主要なアルゴリズムであり、ソリューションのSOCは、最大でユーザ指定因子である$w$を最適から遠ざけている。
EECBS は最適 SOC 上でパスのセットと低い境界$LB$ を維持している。
そして、SOCが少なくとも$w \cdot LB$であるパスの集合を反復的に選択し、衝突を解決するための制約を導入する。
セットの各パスに対して、EECBSは制約を満たす最適パスの低いバウンダリを維持している。
個々の有界-準最適経路をコストが最低でも$w$の閾値で見つけることで、EECBSは有界-準最適解を見つけることを保証している。
EECBSを高速化するために、以前の作業ではフレックス分布を使用してしきい値を増加させた。
フレックス分布を持つEECBSは、有界-準最適解を見つけることを保証しているが、しきい値は$w \cdot LB$を超え、EECBSは特定の経路の衝突を解消するのではなく、異なる経路の集合に切り替えざるを得ず、効率を低下させる。
この問題に対処するため,衝突回数に比例してフレキシブルを分散するConflict-based Flex Distributionを提案する。
また、制約を満たすのに必要な遅延を見積もり、遅延ベースのFlexディストリビューションを提案します。
その上で、階層的なフレームワークと組み合わせたMixed-Strategy Flex Distributionを提案します。
我々は新しい反射分布機構を持つEECBSが完全かつ有界な準最適であることを証明した。
実験により、我々のアプローチは、元の(欲求)反射分布よりも優れていることが示された。
関連論文リスト
- Parametrized Multi-Agent Routing via Deep Attention Models [1.0377683220196872]
パラメタライズドシーケンシャル意思決定のためのスケーラブルなディープラーニングフレームワーク(ParaSDM)を提案する。
この設定の重要なサブクラスは、複数のエージェントシステムが最適なルートと位置を同時に決定する必要がある施設と場所(FLPO)である。
これを解決するために、最大エントロピー原理(MEP)と、最短経路ネットワーク(SPN)と呼ばれるニューラルポリシーモデルを統合する。
論文 参考訳（メタデータ） (2025-07-30T02:46:45Z) - SlimCaching: Edge Caching of Mixture-of-Experts for Distributed Inference [29.49615352723995]
Mixture-of-Experts (MoE)モデルは、入力ごとに関連する専門家の小さなサブセットだけを活性化する。
MoEモデルのエキスパートネットワークの数が多ければ多いほど、エッジデバイスにはかなりのストレージ負荷が伴う。
本稿では,元の問題を一連のサブプロブレムに分解するグリーディ分解法を提案する。
論文 参考訳（メタデータ） (2025-07-09T05:43:43Z) - Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds [18.390974792959685]
MAPF (Multi-Agent Path Finding) は、NP困難問題であるコスト関数を最小化しながら、複数のエージェントの衝突のない経路を見つける。
本稿では、まず最大LB値を決定し、次にこのLBで導かれた最優先探索を用いて衝突のない経路を求めることにより、この問題に対処する新しい有界準最適アルゴリズム(DECBS)を提案する。
論文 参考訳（メタデータ） (2025-03-04T20:39:00Z) - Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。
トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。
証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
論文 参考訳（メタデータ） (2025-02-19T07:10:32Z) - 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) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - 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) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Client Orchestration and Cost-Efficient Joint Optimization for
NOMA-Enabled Hierarchical Federated Learning [55.49099125128281]
半同期クラウドモデルアグリゲーションの下で非直交多重アクセス(NOMA)を実現するHFLシステムを提案する。
提案手法は,HFLの性能改善と総コスト削減に関するベンチマークよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-11-03T13:34:44Z) - You Only Compress Once: Towards Effective and Elastic BERT Compression
via Exploit-Explore Stochastic Nature Gradient [88.58536093633167]
既存のモデル圧縮アプローチでは、さまざまなハードウェアデプロイメントに対応するために、さまざまな制約にまたがる再圧縮や微調整が必要となる。
圧縮を一度行い、至るところに展開するための新しいアプローチであるYOCO-BERTを提案する。
最先端のアルゴリズムと比較すると、YOCO-BERTはよりコンパクトなモデルを提供するが、GLUEベンチマークの平均精度は2.1%-4.5%向上している。
論文 参考訳（メタデータ） (2021-06-04T12:17:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。