論文の概要: 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次元代入法として用いた多次元代入法を考える。
このオークションアルゴリズムは、価格を用いて、他の関連する代入問題を解くための出発点として代入問題の解を有利に利用でき、ロールアウトアルゴリズムの実行を大幅に高速化できるため、私たちの状況に特に適している。
関連論文リスト
- 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) - Portfolio optimization with discrete simulated annealing [0.0]
離散凸関数と非凸コスト関数の存在下で最適なポートフォリオを求めるための整数最適化法を提案する。
これにより、与えられた品質でソリューションを実現できる。
論文 参考訳(メタデータ) (2022-10-03T10:39:05Z) - Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。
この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
論文 参考訳(メタデータ) (2022-05-16T15:47:41Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳(メタデータ) (2021-11-24T07:14:57Z) - A Data-Driven Line Search Rule for Support Recovery in High-dimensional
Data Analysis [5.180648702293017]
適切なステップサイズを適応的に決定する新しい,効率的なデータ駆動行探索法を提案する。
線形回帰問題とロジスティック回帰問題における最先端アルゴリズムとの比較は,提案アルゴリズムの安定性,有効性,優越性を示す。
論文 参考訳(メタデータ) (2021-11-21T12:18:18Z) - The Best of Many Worlds: Dual Mirror Descent for Online Allocation
Problems [7.433931244705934]
本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。
様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。
我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
論文 参考訳(メタデータ) (2020-11-18T18:39:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。