論文の概要: Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization
- arxiv url: http://arxiv.org/abs/2604.00428v1
- Date: Wed, 01 Apr 2026 03:14:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-02 16:44:31.812782
- Title: Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization
- Title（参考訳）: 遺伝性因子分析による認証駆動閉ループマルチエージェントパスの探索
- Authors: Jiarui Li, Runyu Zhang, Gioele Zardini,
- Abstract要約: クローズループMAPFアルゴリズムは、次の動きのみを計画し、オンラインを再計画することでスケーラビリティを向上させる。
この問題は、特にAnytime Closed-Loop Conflict-Based Search (ACCBS)で見ることができる。
クローズドループ更新をフィルタリングするための一般的なメカニズムとして,認証トラジェクトリとその関連するフリート予算を導入する。
- 参考スコア（独自算出の注目度）: 9.832339001385828
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-agent coordination in automated warehouses and logistics is commonly modeled as the Multi-Agent Path Finding (MAPF) problem. Closed-loop MAPF algorithms improve scalability by planning only the next movement and replanning online, but this finite-horizon viewpoint can be shortsighted and makes it difficult to preserve global guarantees and exploit compositional structure. This issue is especially visible in Anytime Closed-Loop Conflict-Based Search (ACCBS), which applies Conflict-Based Search (CBS) over dynamically extended finite horizons but, under finite computational budgets, may terminate with short active prefixes in dense instances. We introduce certificate trajectories and their associated fleet budget as a general mechanism for filtering closed-loop updates. A certificate provides a conflict-free fallback plan and a monotone upper bound on the remaining cost; accepting only certificate-improving updates yields completeness. The same budget information induces a budget-limited factorization that enables global, inheritable decomposition across timesteps. Instantiating the framework on ACCBS yields Certificate-Driven Conflict-Based Search (CDCBS). Experiments on benchmark maps show that CDCBS achieves more consistent solution quality than ACCBS, particularly in dense settings, while the proposed factorization reduces effective group size.
- Abstract（参考訳）: 自動倉庫や物流におけるマルチエージェント協調は、一般的にMAPF(Multi-Agent Path Finding)問題としてモデル化されている。
閉ループMAPFアルゴリズムは、次の動きのみを計画し、オンラインで再計画することでスケーラビリティを向上させるが、この有限水平視点は短絡し、グローバルな保証を維持し、構成構造を利用するのが困難になる。
この問題は、Anytime Closed-Loop Conflict-Based Search (ACCBS) において特に顕著であり、これは、動的に拡張された有限地平線に対して Conflict-Based Search (CBS) を適用するが、有限の計算予算の下では、高密度インスタンスにおいて短いアクティブプレフィックスで終了する可能性がある。
クローズドループ更新をフィルタリングするための一般的なメカニズムとして,認証トラジェクトリとその関連するフリート予算を導入する。
証明書は、競合のないフォールバックプランと、残りのコストに対するモノトーン上限を提供する。
同じ予算情報は、グローバルかつ継承可能なタイムステップ間の分解を可能にする、予算限定の分解を誘導する。
このフレームワークをACCBSにインストールすると、CDCBS (Certificate-Driven Conflict-Based Search) が得られる。
ベンチマークマップを用いた実験により,CDCBSはACCBSよりも一貫した解の質が向上し,特に密集した環境では解の質が向上し,提案した因子は有効群のサイズを減少させることがわかった。
関連論文リスト
- 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) - Improving Search Agent with One Line of Code [68.58667107354253]
ツールベースのエージェント強化学習(TARL)は,検索エージェントが外部ツールと対話できるようにトレーニングするための,有望なパラダイムとして登場した。
textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO)を提案する。
論文 参考訳（メタデータ） (2026-03-10T04:07:39Z) - PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure [0.0]
ほぼすべてのPACサンプルの複雑さを3つの要因に分解するCoverage-Objective-Structure(CSO)フレームワークを提案する。
CSOは定理ではなく、ボトルネックを特定し、クロスセット比較を即座に行う解釈テンプレートである。
我々は、CSO座標でインデックス付けされたレート・ルックアップ・テーブル、ベルマン残差診断、配置ゲートによるカバレッジ推定、エポソードごとのポリシー証明書を提供する。
論文 参考訳（メタデータ） (2026-03-01T22:33:16Z) - Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding [10.628717510399046]
MAPFは、倉庫や物流の自動化において、大規模なロボット群の中核的な調整問題である。
既存のアプローチは、固定軌道を生成するオープンループプランナか、信頼性の高い性能保証のないクローズループである。
本稿では,CBSの有限水平変速器をベースとした閉ループであるACCBSについて述べる。
論文 参考訳（メタデータ） (2026-02-12T14:55:16Z) - PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
制約,検証,選択という3つの重要な要素を持つモデルに依存しない,スケーラブルなエージェントフレームワークであるPlanGENを提案する。
具体的には、推論時間アルゴリズムの性能を向上させるために、制約誘導反復検証を提案する。
論文 参考訳（メタデータ） (2025-02-22T06:21:56Z) - Client Orchestration and Cost-Efficient Joint Optimization for
NOMA-Enabled Hierarchical Federated Learning [55.49099125128281]
半同期クラウドモデルアグリゲーションの下で非直交多重アクセス(NOMA)を実現するHFLシステムを提案する。
提案手法は,HFLの性能改善と総コスト削減に関するベンチマークよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-11-03T13:34:44Z) - Scalable Incomplete Multi-View Clustering with Structure Alignment [71.62781659121092]
本稿では,新しいアンカーグラフ学習フレームワークを提案する。
ビュー固有のアンカーグラフを構築し、異なるビューから補完情報をキャプチャする。
提案したSIMVC-SAの時間と空間の複雑さはサンプル数と線形に相関していることが証明された。
論文 参考訳（メタデータ） (2023-08-31T08:30:26Z) - Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive
Privacy Analysis and Beyond [57.10914865054868]
垂直ロジスティック回帰(VLR)をミニバッチ降下勾配で訓練した。
我々は、オープンソースのフェデレーション学習フレームワークのクラスにおいて、VLRの包括的で厳密なプライバシー分析を提供する。
論文 参考訳（メタデータ） (2022-07-19T05:47:30Z) - 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) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。