論文の概要: Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling

• arxiv url: http://arxiv.org/abs/2607.25835v1
• Date: Tue, 28 Jul 2026 15:15:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-29 20:50:42.895806
• Title: Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling
• Title（参考訳）: オンライン学習と反復価格による分散型制約最適化と大規模衛星スケジューリングへの応用
• Authors: Itai Zilberstein, Pranav Rajbhandari, Steve Chien, Tuomas Sandholm,
• Abstract要約: 分散最適化問題(DCOP)は、限られた通信下での分散意思決定のための一般的なフレームワークを提供するが、現実世界の多くのインスタンスはモノリシックに解決するには大きすぎる。 我々は、DCOPと潜在的なゲームとの関係を再考し、DCOPとの平衡探索に近代的なオンライン学習アルゴリズムを適用した。 次に、大規模分散衛星スケジューリングを動機とした大規模DCOPの分解フレームワークに目を向ける。
• 参考スコア（独自算出の注目度）: 39.28018254600072
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions. We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs. We show that these algorithms are competitive with representative incomplete DCOP algorithms. We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers. Combining our online learning methods with our iterative pricing framework, we obtain near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared with 87% for state-of-the-art baselines.
• Abstract（参考訳）: 分散制約最適化問題(DCOP)は、限られた通信下での分散意思決定のための一般的なフレームワークを提供するが、多くの実世界のインスタンスはモノリシックに解決するには大きすぎる。 我々はこの課題を2つの相補的な方向から解決する。 我々は、DCOPと潜在的なゲームとの関係を再考し、DCOPとの平衡探索に近代的なオンライン学習アルゴリズムを適用した。 これらのアルゴリズムは代表的不完全DCOPアルゴリズムと競合することを示す。 次に、大規模分散衛星スケジューリングを動機とした大規模DCOPの分解フレームワークに目を向ける。 本稿では,DCOPを2つの相互作用するサブプロブレムに分割するフレームワークを提案する。 2つのレベルを分割するために,ローカルオプティマイザからのフィードバックを用いてメタレベルのユーティリティを更新する,新しい反復価格法を開発した。 オンライン学習手法と反復的な価格設定フレームワークを組み合わせることで、実世界の分散衛星スケジューリング問題インスタンスでほぼ最適性能を得ることができ、現状のベースラインの87%と比較して99%以上の観測要求を達成できる。

関連論文リスト

• Revisiting Decentralized Online Convex Optimization with Compressed Communication [68.72667170947358]
  圧縮通信を用いた2つのFTRL型D-OCOアルゴリズムを提案する。 我々の最初のアルゴリズムは、全情報設定を考慮し、既存の後悔の限界と一致させることができる。 第2のアルゴリズムは帯域設定のために設計されており、後悔の限界と通信コストの両方を大幅に改善することができる。
  論文  参考訳（メタデータ） (2026-07-02T03:45:41Z)
• ARMATA: Auto-Regressive Multi-Agent Task Assignment [6.2002105625228845]
  本稿では、アロケーション決定とルーティングシーケンスを協調的に生成する完全エンドツーエンドの自動回帰フレームワークを提案する。 提案手法のコアコントリビューションは,高レベルアロケーションと低レベルルーティングを単一自己回帰パスで統一するマルチステージデコーディング機構である。
  論文  参考訳（メタデータ） (2026-05-05T19:08:08Z)
• Large-Scale Continual Scheduling and Execution for Dynamic Distributed Satellite Constellation Observation Allocation [1.3467991712339638]
  衛星への自律的な展開には、効率的な計算と通信が必要である。 動的マルチサテライトコンステレーション観測スケジューリング問題(DCOSP)を提案する。 D-NSS(Dynamic Incremental Neighborhood Search)アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2026-01-08T00:10:45Z)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。 ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。 提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
  論文  参考訳（メタデータ） (2023-10-10T00:21:10Z)
• DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization [27.317118892531827]
  我々は、DIAMOND(運動量と勾配追跡を伴う分散単時間スケール近似)と呼ばれる新しい分散二段階最適化を開発する。 我々はDIAMONDが$mathcalO(epsilon-3/2)$をサンプルと通信の複雑さで楽しむことを示し、$epsilon$-stationaryソリューションを実現する。
  論文  参考訳（メタデータ） (2022-12-05T15:58:00Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Deep Learning-based Resource Allocation For Device-to-Device Communication [66.74874646973593]
  デバイス間通信(D2D)を用いたマルチチャネルセルシステムにおいて,リソース割り当ての最適化のためのフレームワークを提案する。 任意のチャネル条件に対する最適な資源配分戦略をディープニューラルネットワーク(DNN)モデルにより近似する深層学習(DL)フレームワークを提案する。 シミュレーションの結果,提案手法のリアルタイム性能を低速で実現できることが確認された。
  論文  参考訳（メタデータ） (2020-11-25T14:19:23Z)
• On Population-Based Algorithms for Distributed Constraint Optimization Problems [12.21350091202884]
  我々は、人口ベースのアルゴリズムとして広く呼ばれる、新しい不完全アルゴリズムのクラスについて研究する。 最初のアプローチであるAnytime Evolutionary DCOP(AED)は、進化最適化メタヒューリスティックを利用してDCOPを解く。 第2のコントリビューションでは、人口ベースのアプローチと局所的な検索アプローチを組み合わせることができることを示す。
  論文  参考訳（メタデータ） (2020-09-02T06:39:30Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。 深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-19T13:10:20Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。