論文の概要: A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning
- arxiv url: http://arxiv.org/abs/2608.17928v1
- Date: Tue, 18 Aug 2026 15:48:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-19 21:40:53.391109
- Title: A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning
- Title（参考訳）: グループ分散計画を用いた並列寿命MAPFの理論的枠組み
- Abstract要約: ローリング・水平衝突分解能は, 生涯多エージェント経路探索問題の最も優れた解の1つである。
それは計算コストを発生させ、その適用性を控えめなエージェント数にも制限する。
RHCR と GD-RHCR はともに指数関数的に最適に近い保証が得られることを示す。
- 参考スコア（独自算出の注目度）: 12.317345867465272
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the Lifelong Multi-Agent Path Finding (L-MAPF) problem, agents must repeatedly move from one destination to another while avoiding obstacles and inter-agent collisions. Widely regarded as one of the highest-performing solutions to this problem is the Rolling-Horizon Collision Resolution (RHCR) framework. However, commensurate with its quality solutions, it incurs a computational cost that limits its applicability to even modest agent counts. In this paper, leveraging theoretical methods from the Locally Interdependent Multi-Agent MDP literature, we first theoretically prove the near-optimality of RHCR in a discounted MDP formulation of the L-MAPF problem. Then, we leverage these results to naturally motivate an extended framework called Group Decentralized RHCR (GD-RHCR) which incorporates a group decentralized structure that partitions agents based on a transitive communication scheme and plans for each partition of agents in parallel. We show that both RHCR and GD-RHCR achieve similar exponentially close to optimal guarantees, establishing a theoretical duality between the time based restrictions performed by vanilla RHCR and the additional space based partitioning performed by GD-RHCR. Lastly, we show that across varying maps, GD-RHCR is able to attain high throughput that scales into higher agent counts while maintaining a significantly lower per plan cost.
- Abstract（参考訳）: Lifelong Multi-Agent Path Finding (L-MAPF) 問題では、エージェントは障害やエージェント間の衝突を避けながら、ある目的地から別の場所に何度も移動しなければならない。
この問題の最も優れた解の1つは、ローリング・水平衝突分解(RHCR)フレームワークである。
しかし、その高品質な解法と相まって計算コストを発生させ、その適用性は控えめなエージェント数にも制限される。
本稿では,局所的相互依存型マルチエージェントMDP文献の理論的手法を活用し,まず,L-MAPF問題の割引MDP定式化におけるRHCRの近似性を理論的に証明する。
そして,これらの結果を生かしてグループ分散RHCR(Group Decentralized RHCR, GD-RHCR)と呼ばれる拡張フレームワークを自然に動機づける。
RHCR と GD-RHCR の両者は、バニラ RHCR の時間的制約と GD-RHCR の時間的制約と、GD-RHCR の空間的パーティショニングとの理論的双対性を確立する。
最後に,GD-RHCRは多種多様な地図にまたがって高いスループットを達成でき,高いエージェント数にスケールアップできると同時に,計画コストあたりの大幅な削減を実現可能であることを示す。
関連論文リスト
- DISA: Offline Importance Sampling for Distribution-Matching LLM-RL [56.9445657766829]
本稿では、このキャリブレーション問題をRLループの外に移動させるdisAを紹介する。
DISAは提案トラジェクトリをオフラインに描画し、重要サンプリングによってパーティション関数を推定し、結果として発生するパーティション関数の推定を凍結する。
6つの数学と3つのコードベンチマークにまたがる2つのオープンウェイトなバックボーンでは、DisdisAはオンラインに結合した分散マッチングベースラインフローにマッチするか、超えている。
論文 参考訳（メタデータ） (2026-05-17T07:14:44Z) - Breaking $\textit{Winner-Takes-All}$: Cooperative Policy Optimization Improves Diverse LLM Reasoning [53.42577591449649]
グループ協力政策最適化は、トレーニングパラダイムをロールアウト競争からチーム協力へとシフトさせる。
GCPOは独立したロールアウトスコアをチームレベルのクレジット割り当てに置き換える。
チームへの平均的な限界貢献に従って、各ロールアウトに対して、グループチームの報酬を再分配する。
論文 参考訳（メタデータ） (2026-05-12T03:20:24Z) - Karma Mechanisms for Decentralised, Cooperative Multi Agent Path Finding [7.187733825162918]
MAPF(Multi-Agent Path Finding)は、大規模ロボットおよびサイバー物理システムにおける協調問題である。
本稿では,カーマ機構に基づくMAPFのための分散協調フレームワークを提案する。
論文 参考訳（メタデータ） (2026-04-09T08:35:13Z) - Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration [49.9937230730202]
本稿では,新たなアクター・リファイナ・コラボレーション・フレームワークであるSearch-R2を提案する。
提案手法は,生成過程をアクターに分解し,最初の推論軌道を生成する。
本稿では,検索-R2がモデルスケール全体にわたって強力なRAGとRLベースのベースラインを一貫して上回ることを示す。
論文 参考訳（メタデータ） (2026-02-03T15:32:09Z) - Statistical Analysis of Conditional Group Distributionally Robust Optimization with Cross-Entropy Loss [16.1456465253627]
本研究では、複数のソースドメインからラベル付きデータを入手でき、対象ドメインからラベルなしデータのみを観測できるマルチソース非教師付きドメイン適応について検討する。
本稿では,情報源領域からの条件付き結果分布の凸結合を最小化することにより,分類器を学習するグループ分散条件最適化フレームワークを提案する。
実験的なCG-DRO推定器の高速な統計的収束速度を,理論ブリッジとして機能する2つの代理極小最適化問題を構築することにより確立する。
論文 参考訳（メタデータ） (2025-07-14T04:21:23Z) - Distributionally Robust Constrained Reinforcement Learning under Strong Duality [37.76993170360821]
分布ロバスト制約付きRL(DRC-RL)の問題点について検討する。
目標は、環境分布の変化や制約の対象となる報酬を最大化することである。
本稿では, 第一の効率的かつ証明可能な解を可能にする, 強双対性に基づくアルゴリズムフレームワークを開発する。
論文 参考訳（メタデータ） (2024-06-22T08:51:57Z) - Modeling the Q-Diversity in a Min-max Play Game for Robust Optimization [61.39201891894024]
群分布的ロバスト最適化(群 DRO)は、事前定義された群に対する最悪の損失を最小限にすることができる。
グループDROフレームワークをQ-Diversityを提案して再構築する。
インタラクティブなトレーニングモードによって特徴付けられるQ-Diversityは、アノテーションからグループ識別を緩和し、直接パラメータ化を行う。
論文 参考訳（メタデータ） (2023-05-20T07:02:27Z) - The challenge of redundancy on multi-agent value factorisation [12.63182277116319]
協調型マルチエージェント強化学習(MARL)の分野において、標準パラダイムは集中型トレーニングと分散実行の利用である。
そこで我々は,LRP(Layerwise Relevance propagation)を利用して,結合値関数の学習と局所報酬信号の生成を分離する手法を提案する。
VDNとQmixの両方のベースラインの性能は冗長エージェントの数によって低下するが、RDNは影響を受けない。
論文 参考訳（メタデータ） (2023-03-28T20:41:12Z) - Optimizing Two-way Partial AUC with an End-to-end Framework [154.47590401735323]
ROC曲線のエリア(AUC)は、機械学習にとって重要な指標である。
最近の研究は、TPAUCが既存のPartial AUCメトリクスと本質的に矛盾していることを示している。
本論文では,この新指標を最適化するための最初の試行について述べる。
論文 参考訳（メタデータ） (2022-06-23T12:21:30Z) - Parallelized Reverse Curriculum Generation [62.25453821794469]
強化学習では, エージェントが, まばらな報酬のために, 特定の一連の行動を必要とするタスクをマスターすることが困難である。
逆カリキュラム生成(RCG)は、エージェントが学習するカリキュラムを自動的に生成する逆拡張アプローチを提供する。
本稿では,複数のACペアを同時に訓練し,定期的に批判を交換する並列化手法を提案する。
論文 参考訳（メタデータ） (2021-08-04T15:58:35Z) - Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
MAPF (Multi Agent Path Finding) は、空間的に拡張されたエージェントに対する競合のない経路の同定を必要とする。
これらは、Convoy Movement ProblemやTraning Schedulingといった現実世界の問題に適用できる。
提案手法であるDecentralized Multi Agent Path Finding (DeMAPF) は、MAPFを経路計画と割り当ての問題の系列として扱う。
論文 参考訳（メタデータ） (2021-06-03T18:07:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。