論文の概要: Grouping Auction-Consensus Algorithm for Decentralized Task Allocation in Multi-Robot Systems
- arxiv url: http://arxiv.org/abs/2608.15884v1
- Date: Sun, 16 Aug 2026 18:17:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-18 19:59:03.459632
- Title: Grouping Auction-Consensus Algorithm for Decentralized Task Allocation in Multi-Robot Systems
- Title（参考訳）: マルチロボットシステムにおける分散タスク割当のためのグループオークション・コンセンサスアルゴリズム
- Abstract要約: 分散マルチロボットタスクアロケーション(MRTA)は、スケーラブルでレジリエンスな自律システムに不可欠である。
本稿では,Grouping Auction-Consensus Algorithm (GACA)を紹介する。
- 参考スコア（独自算出の注目度）: 17.366159929862402
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decentralized multi-robot task allocation (MRTA) is essential for scalable and resilient autonomous systems. The Consensus-Based Bundle Algorithm (CBBA) is a widely adopted decentralized baseline. However, its individual task-level bidding is poorly aligned with the min-sum objective of minimizing total team travel distance, leading to suboptimal allocations in spatially distributed environments. This paper introduces the Grouping Auction-Consensus Algorithm (GACA). This decentralized MRTA framework adopts the two-phase auction-consensus architecture of CBBA while fundamentally redesigning its bidding mechanism to reason over groups of spatially proximate tasks. A nearest-neighbor preprocessing step partitions tasks into spatially coherent groups before allocation. Agents then iteratively propose structured group-level actions: claiming unassigned groups, acquiring partial groups, or contesting groups held by other agents. Competing actions are resolved through a consensus phase. Operating in the MT-SR-IA problem class, GACA is evaluated against CBBA using a Mixed-Integer Linear Program as the ground-truth optimality reference. Across four swarm sizes and 4,000 test worlds, GACA achieves a median percent optimality of approximately 97% compared to 81--84% for CBBA, while converging in equal or fewer iterations. A scalability evaluation over 3,280 additional problem instances spanning swarm sizes of 5 to 20 agents and task counts of 10 to 50 confirms that these gains generalize robustly across a wide range of problem configurations.
- Abstract（参考訳）: 分散マルチロボットタスクアロケーション(MRTA)は、スケーラブルでレジリエンスな自律システムに不可欠である。
Consensus-Based Bundle Algorithm (CBBA) は広く採用されている分散ベースラインである。
しかし、個々のタスクレベルの入札は、チーム全体の移動距離を最小化するという最小目標と不一致であり、空間的に分散した環境での最適以下の割り当てにつながっている。
本稿では,GACA(Grouping Auction-Consensus Algorithm)を提案する。
この分散化MRTAフレームワークはCBBAの2段階のオークション・コンセンサス・アーキテクチャを採用しつつ、その入札機構を根本的に再設計し、空間的に近似したタスク群を推論する。
最寄りの処理ステップは、割り当て前にタスクを空間的に一貫性のあるグループに分割する。
エージェントは、割り当てられていないグループを主張する、部分的なグループを取得する、または他のエージェントが保持するグループと競合する、構造化されたグループレベルのアクションを反復的に提案する。
競合動作はコンセンサスフェーズによって解決される。
The MT-SR-IA problem class, GACA is evaluation against CBBA using a Mixed-Integer Linear Program as the ground-truth optimality reference。
4つのSwarmサイズと4000のテストワールドで、GACAはCBBAの81～84%に対して平均97%の最適性を達成し、同じまたは少ないイテレーションで収束する。
5から20のエージェントと10から50のタスク数にまたがる3,280以上の追加問題インスタンスのスケーラビリティ評価により、これらのゲインが幅広い問題構成にわたって堅牢に一般化されることを確認した。
関連論文リスト
- Auction-Consensus Algorithm with Learned Bidding Scheme for Multi-Robot Systems [16.187002302872028]
Auction-Consensusアルゴリズムは、証明可能な収束を伴うスケーラブルな分散調整を提供する。
本稿では、CBBAの決定論的入札機構を強化学習を用いて訓練されたニューラル入札ポリシーに置き換える学習強化オークション・コンセンサス・フレームワークを提案する。
様々なSwarmサイズにまたがる実験結果から、学習入札政策は古典的なCBBAよりも解の質を向上させることが示されている。
論文 参考訳（メタデータ） (2026-05-21T03:00:47Z) - Breaking $\textit{Winner-Takes-All}$: Cooperative Policy Optimization Improves Diverse LLM Reasoning [53.42577591449649]
グループ協力政策最適化は、トレーニングパラダイムをロールアウト競争からチーム協力へとシフトさせる。
GCPOは独立したロールアウトスコアをチームレベルのクレジット割り当てに置き換える。
チームへの平均的な限界貢献に従って、各ロールアウトに対して、グループチームの報酬を再分配する。
論文 参考訳（メタデータ） (2026-05-12T03:20:24Z) - GoAgent: Group-of-Agents Communication Topology Generation for LLM-based Multi-Agent Systems [55.12339141172908]
GoAgentは、協調グループをMAS構築の原子単位として明示的に扱う通信トポロジ生成手法である。
6つのベンチマークの実験では、GoAgentの最先端のパフォーマンスを93.84%の平均精度で証明し、トークン消費を約17%削減した。
論文 参考訳（メタデータ） (2026-03-20T06:21:32Z) - Towards a Science of Scaling Agent Systems [79.64446272302287]
エージェント評価の定義を定式化し,エージェント量,コーディネーション構造,モデル,タスク特性の相互作用として,スケーリング法則を特徴付ける。
協調指標を用いて予測モデルを導出し,R2=0をクロスバリデーションし,未知のタスク領域の予測を可能にする。
ツールコーディネーショントレードオフ: 固定的な計算予算の下では, ツールヘビータスクはマルチエージェントのオーバーヘッドから不均衡に悩まされ, 2) 能力飽和: 調整が減少または負のリターンを, 単一エージェントのベースラインが45%を超えると達成できる。
論文 参考訳（メタデータ） (2025-12-09T06:52:21Z) - Generalizing Fair Clustering to Multiple Groups: Algorithms and Applications [1.6398837165722515]
本研究は,グループ数(2以上)の任意の設定に対して,最良クラスタリング問題の研究を一般化する。
任意のサイズの複数グループを効率的に扱うニア線形時間近似アルゴリズムを提案する。
我々は,複数のグループ(2つ以上のグループ)を含むEmphfairコンセンサスクラスタリング問題に対して,近似アルゴリズムを初めて提供する。
論文 参考訳（メタデータ） (2025-11-14T18:19:18Z) - GroupCoOp: Group-robust Fine-tuning via Group Prompt Learning [57.888537648437115]
Group Context Optimization (GroupCoOp) は、単純で効果的な微調整アルゴリズムである。
微調整視覚言語モデル(VLM)の群ロバスト性を高める
GroupCoOpは、5つのCLIPアーキテクチャにわたる5つのベンチマークで最高の結果を得た。
論文 参考訳（メタデータ） (2025-09-28T09:54:30Z) - Group-in-Group Policy Optimization for LLM Agent Training [17.243181792126563]
Group-in-Group Policy Optimization (GiGPO) は、LLMエージェントのきめ細かいクレジット割り当てを実現する新しいRLアルゴリズムである。
我々は, ALFWorld や WebShop などのエージェントベンチマークに対する GiGPO の評価と,検索強化されたQA タスクに対するツール統合推論を行った。
論文 参考訳（メタデータ） (2025-05-16T08:26:59Z) - Cluster-Based Multi-Agent Task Scheduling for Space-Air-Ground Integrated Networks [60.085771314013044]
低高度経済は、コミュニケーションやセンシングなどの分野で発展する大きな可能性を秘めている。
本稿では,SAGINにおけるマルチUAV協調タスクスケジューリング問題に対処するため,クラスタリングに基づく多エージェントDeep Deterministic Policy Gradient (CMADDPG)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-14T06:17:33Z) - Fair Clustering with Minimum Representation Constraints [2.707154152696381]
我々は、各群が少なくとも指定された数のクラスタにおいて、最小レベルの表現を達成しなければならないという追加の公平性制約の下で、k平均およびkメディアンクラスタリング問題について検討する。
大規模なデータセットであっても,このアプローチを実用的にするための戦略をいくつか提示する。
論文 参考訳（メタデータ） (2024-09-04T00:13:40Z) - Fair Labeled Clustering [28.297893914525517]
クラスタリングのダウンストリーム適用と,そのような設定に対してグループフェアネスをどのように確保するかを検討する。
このような問題に対するアルゴリズムを提供し、グループフェアクラスタリングにおけるNPハードのアルゴリズムとは対照的に、効率的な解が可能であることを示す。
また、距離空間における中心位置に関係なく、意思決定者が自由にクラスタにラベルを割り当てることができるような、モチベーションのよい代替設定についても検討する。
論文 参考訳（メタデータ） (2022-05-28T07:07:12Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。