論文の概要: Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm

• arxiv url: http://arxiv.org/abs/2002.07407v2
• Date: Mon, 27 Apr 2020 06:28:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 20:27:45.673099
• Title: Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm
• Title（参考訳）: オークションアルゴリズムによる制約付きマルチエージェントロールアウトと多次元アサインメント
• Authors: Dimitri Bertsekas
• Abstract要約: 本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。 提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。 コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider an extension of the rollout algorithm that applies to constrained deterministic dynamic programming, including challenging combinatorial optimization problems. The algorithm relies on a suboptimal policy, called base heuristic. Under suitable assumptions, we show that if the base heuristic produces a feasible solution, the rollout algorithm has a cost improvement property: it produces a feasible solution, whose cost is no worse than the base heuristic's cost. We then focus on multiagent problems, where the control at each stage consists of multiple components (one per agent), which are coupled either through the cost function or the constraints or both. We show that the cost improvement property is maintained with an alternative implementation that has greatly reduced computational requirements, and makes possible the use of rollout in problems with many agents. We demonstrate this alternative algorithm by applying it to layered graph problems that involve both a spatial and a temporal structure. We consider in some detail a prominent example of such problems: multidimensional assignment, where we use the auction algorithm for 2-dimensional assignment as a base heuristic. This auction algorithm is particularly well-suited for our context, because through the use of prices, it can advantageously use the solution of an assignment problem as a starting point for solving other related assignment problems, and this can greatly speed up the execution of the rollout algorithm.
• Abstract（参考訳）: 我々は,組合せ最適化問題を含む制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張を考える。 このアルゴリズムはベースヒューリスティックと呼ばれる準最適ポリシーに依存している。 適切な仮定の下では、基本ヒューリスティックが実現可能な解を生成する場合、ロールアウトアルゴリズムがコスト改善特性を持つことを示す。 次に、各ステージの制御が複数のコンポーネント(エージェント毎に1つ)で構成され、コスト関数または制約によって結合されるマルチエージェント問題に焦点を当てます。 コスト改善特性は,計算要件を大幅に削減した代替実装で維持され,多数のエージェントが抱える問題に対するロールアウトが利用可能であることを示す。 この代替アルゴリズムを,空間構造と時間構造の両方を含む階層グラフ問題に適用することで実証する。 このような問題の顕著な例として,多次元代入法を基本ヒューリスティックとして2次元代入法として用いた多次元代入法を考える。 このオークションアルゴリズムは、価格を用いて、他の関連する代入問題を解くための出発点として代入問題の解を有利に利用でき、ロールアウトアルゴリズムの実行を大幅に高速化できるため、私たちの状況に特に適している。

関連論文リスト

• Time-Varying Convex Optimization with $O(n)$ Computational Complexity [0.0]
  コスト関数が時間とともに変化する非拘束凸最適化の問題を考える。 提案アルゴリズムは,決定変数に対するコスト関数の1次微分のみを必要とする。 具体的には、提案アルゴリズムは、計算コストを1タイムステップあたり$(n3)$から$O(n)$に削減する。
  論文  参考訳（メタデータ） (2024-10-19T06:45:05Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• An adaptive approach to Bayesian Optimization with switching costs [0.8246494848934447]
  逐次実験設計の資源制約設定に対するベイズ最適化の修正について検討する。 この逐次的問題定式化にプロセス制約付きバッチアルゴリズムを2つ適用し,コスト認識とコスト非依存の2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-05-14T21:55:02Z)
• Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
  各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。 この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。 本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-31T22:59:23Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Online and Streaming Algorithms for Constrained $k$-Submodular Maximization [25.15934533974176]
  制約付き$k$-submodularは、広告アロケーション、インフルエンス、パーソナライズされたレコメンデーションなど、多くの個別の最適化問題をキャプチャする一般的なフレームワークである。 本研究では,モノトーンと一般(おそらく非モノトーン)の両方の目的に制約された$k$サブモジュールのシングルパスストリーミングとオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-05-25T12:53:17Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems [1.6939372704265414]
  有限状態および制御空間,部分状態観測,マルチエージェント構造を有する無限地平面割引動的プログラミング問題を考える。 本手法は、部分的に観測可能なマルチエージェント問題の計算問題に特に対処する。
  論文  参考訳（メタデータ） (2020-11-09T06:51:50Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  本稿では,シーケンシャルなサブゴールタスクの超指数空間における解を高速に計算するための,Jump-Operator Dynamic Programmingという新しいフレームワークを提案する。 このアプローチでは、時間的に拡張された行動として機能する、再利用可能な目標条件付き警察のアンサンブルを制御する。 すると、この部分空間上の目的関数のクラスを、解がグラウンド化に不変であるものとして特定し、最適ゼロショット移動をもたらす。
  論文  参考訳（メタデータ） (2020-07-06T05:13:20Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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