論文の概要: Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems

• arxiv url: http://arxiv.org/abs/2412.15573v1
• Date: Fri, 20 Dec 2024 05:10:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-23 16:19:51.363283
• Title: Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems
• Title（参考訳）: 逐次衛星割り当て問題に対するマルチエージェント強化学習
• Authors: Joshua Holder, Natasha Jaques, Mehran Mesbahi,
• Abstract要約: 割り当て問題は、エージェントのグループをタスクのグループに割り当てる古典的な最適化問題である。 衛星、電力網、移動ロボットスケジューリングといった現代の多くの応用において、割り当て問題は時間とともに展開される。 この問題にマルチエージェント強化学習を適用し、既知のRL時間グリージーソルバからのブートストラップによる代入値の学習を行う。 我々は,本アルゴリズムが理論的に正当化され,他のアルゴリズムが経験した落とし穴を回避することを実証した。
• 参考スコア（独自算出の注目度）: 5.896440476510869
• License:
• Abstract: Assignment problems are a classic combinatorial optimization problem in which a group of agents must be assigned to a group of tasks such that maximum utility is achieved while satisfying assignment constraints. Given the utility of each agent completing each task, polynomial-time algorithms exist to solve a single assignment problem in its simplest form. However, in many modern-day applications such as satellite constellations, power grids, and mobile robot scheduling, assignment problems unfold over time, with the utility for a given assignment depending heavily on the state of the system. We apply multi-agent reinforcement learning to this problem, learning the value of assignments by bootstrapping from a known polynomial-time greedy solver and then learning from further experience. We then choose assignments using a distributed optimal assignment mechanism rather than by selecting them directly. We demonstrate that this algorithm is theoretically justified and avoids pitfalls experienced by other RL algorithms in this setting. Finally, we show that our algorithm significantly outperforms other methods in the literature, even while scaling to realistic scenarios with hundreds of agents and tasks.
• Abstract（参考訳）: 代入問題(英: Assignment problem)とは、代入制約を満たすとともに、最大ユーティリティが達成されるようなタスク群にエージェントのグループを割り当てなければならない古典的な組合せ最適化問題である。 各タスクを完了した各エージェントの実用性を考えると、多項式時間アルゴリズムはその最も単純な形式で1つの代入問題を解くことができる。 しかし、衛星コンステレーション、電力網、移動ロボットスケジューリングといった現代の多くの応用において、割り当て問題は時間とともに展開され、システムの状態に大きく依存する。 この問題にマルチエージェント強化学習を適用し、既知の多項式時間グリージーソルバからブートストラップを学習し、さらに経験から学習する。 次に、直接選択するのではなく、分散最適代入機構を用いて代入を選択する。 我々は,このアルゴリズムが理論的に正当化され,他のRLアルゴリズムが経験した落とし穴を回避することを実証した。 最後に,我々のアルゴリズムは,数百のエージェントやタスクで現実的なシナリオにスケールしても,文学における他の手法よりも著しく優れていることを示す。

関連論文リスト

• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding [25.11387753357413]
  本稿では,多目的タスク割り当てと経路探索(MG-TAPF)問題を理論的およびアルゴリズム的観点から検討する。 理論的には、MG-TAPF問題は最適解法としてNPハードであることが証明される。 本稿では,多エージェントパス探索問題に対するアルゴリズムに基づくアルゴリズムを提案し,MG-TAPF問題を最適・準最適に解く。
  論文  参考訳（メタデータ） (2022-08-02T03:17:29Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• 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)
• A Machine Learning Approach for Task and Resource Allocation in Mobile Edge Computing Based Networks [108.57859531628264]
  無線ネットワークにおいて,共同作業,スペクトル,送信電力配分問題について検討する。 提案アルゴリズムは、標準Q-ラーニングアルゴリズムと比較して、収束に必要なイテレーション数と全ユーザの最大遅延を最大18%、11.1%削減することができる。
  論文  参考訳（メタデータ） (2020-07-20T13:46:42Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)
• A Novel Multi-Agent System for Complex Scheduling Problems [2.294014185517203]
  本稿では,様々な問題領域に適用可能なマルチエージェントシステムの概念と実装について述べる。 提案手法の有効性を示すため,NP-hardスケジューリング問題をシミュレートする。 本稿では,レイアウトの複雑さの低減,複雑なシステムの制御の改善,拡張性など,エージェントベースのアプローチの利点を強調した。
  論文  参考訳（メタデータ） (2020-04-20T14:04:58Z)
• Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm [0.0]
  本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。 提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。 コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
  論文  参考訳（メタデータ） (2020-02-18T07:09:06Z)

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

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