論文の概要: Learning NP-Hard Multi-Agent Assignment Planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-learning

• arxiv url: http://arxiv.org/abs/1905.12204v4
• Date: Mon, 14 Aug 2023 02:18:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-20 16:45:32.191816
• Title: Learning NP-Hard Multi-Agent Assignment Planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-learning
• Title（参考訳）: GNNを用いたNP-Hardマルチエージェントアサインメント計画の学習:ランダムグラフと予測可能なオークション適合Q-ラーニングに基づく推論
• Authors: Hyunwook Kang, Taehwan Kwon, Jinkyoo Park, James R. Morrison
• Abstract要約: 本稿では,学習に基づくアルゴリズムを用いて,時間依存報酬を用いたマルチエージェント・マルチタスクNPハードプランニング問題をほぼ最適に解決する可能性について検討する。
• 参考スコア（独自算出の注目度）: 24.956507498394497
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper explores the possibility of near-optimally solving multi-agent, multi-task NP-hard planning problems with time-dependent rewards using a learning-based algorithm. In particular, we consider a class of robot/machine scheduling problems called the multi-robot reward collection problem (MRRC). Such MRRC problems well model ride-sharing, pickup-and-delivery, and a variety of related problems. In representing the MRRC problem as a sequential decision-making problem, we observe that each state can be represented as an extension of probabilistic graphical models (PGMs), which we refer to as random PGMs. We then develop a mean-field inference method for random PGMs. We then propose (1) an order-transferable Q-function estimator and (2) an order-transferability-enabled auction to select a joint assignment in polynomial time. These result in a reinforcement learning framework with at least $1-1/e$ optimality. Experimental results on solving MRRC problems highlight the near-optimality and transferability of the proposed methods. We also consider identical parallel machine scheduling problems (IPMS) and minimax multiple traveling salesman problems (minimax-mTSP).
• Abstract（参考訳）: 本稿では,学習に基づくアルゴリズムを用いて,時間依存報酬を用いたマルチエージェント・マルチタスクNPハードプランニング問題をほぼ最適に解決する可能性について検討する。 特に,マルチロボット報酬収集問題(MRRC)と呼ばれるロボット/機械スケジューリング問題について考察する。 このようなMRRCは、ライドシェアリング、ピックアップ・アンド・デリバリ、および様々な関連する問題をモデル化する。 MRRC問題を逐次決定問題として表現することで、各状態が確率的グラフィカルモデル(PGM)の拡張として表現可能であることを観察する。 次に、ランダムなPGMに対する平均場推定法を開発する。 次に,(1)次数変換可能なQ関数推定器を提案し,(2)次数変換可能なオークションを提案し,多項式時間で共同代入を選択する。 その結果、少なくとも1-1/e$の最適性を持つ強化学習フレームワークが生まれます。 MRRC問題を解く実験結果は,提案手法のほぼ最適性と伝達性を明らかにする。 また,同一並列マシンスケジューリング問題 (IPMS) とミニマックス複数走行セールスマン問題 (minimax-mTSP) についても検討する。

関連論文リスト

• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
  そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。 我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。 いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
  論文  参考訳（メタデータ） (2023-11-10T13:56:15Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。 近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。 本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
  論文  参考訳（メタデータ） (2022-02-07T18:52:56Z)
• An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents [1.3812010983144802]
  ジョブショップスケジューリング問題(JSSP)に対する深層強化学習手法を提案する。 目的は、ジョブやマシンの数によって異なるJSSPインスタンスのディストリビューションについて学べるgreedyのようなものを構築することである。 予想通り、モデルはある程度は、トレーニングで使用されるものと異なる分布から生じるより大きな問題やインスタンスに一般化することができる。
  論文  参考訳（メタデータ） (2021-10-18T07:55:39Z)
• Markov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flow [73.1896399783641]
  会員/加入者の獲得と保持では、複数のページを連続してマーケティングコンテンツを推奨する必要がある。 遷移確率行列をモデル化するためにBandits を用いた MDP としてこの問題を定式化することを提案する。 提案したMDPのBanditsアルゴリズムは,$epsilon$-greedyと$epsilon$-greedy,$epsilon$,IndependentBandits,InteractionBanditsでQ-learningを上回っている。
  論文  参考訳（メタデータ） (2021-07-01T03:54:36Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Explanation Generation for Multi-Modal Multi-Agent Path Finding with Optimal Resource Utilization using Answer Set Programming [1.7132914341329848]
  mMAPFの実際の応用には柔軟性と説明性が必要である。 本稿では,ソリューションの実現可能性と最適性に関する質問に対する説明を生成する手法を提案する。
  論文  参考訳（メタデータ） (2020-08-08T18:34:34Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。 本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-17T20:19:25Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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