論文の概要: Approximate Dec-POMDP Solving Using Multi-Agent A*

• arxiv url: http://arxiv.org/abs/2405.05662v1
• Date: Thu, 9 May 2024 10:33:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-10 13:42:37.623247
• Title: Approximate Dec-POMDP Solving Using Multi-Agent A*
• Title（参考訳）: 多エージェントA*を用いた近似Dec-POMDP解法
• Authors: Wietze Koops, Sebastian Junges, Nils Jansen,
• Abstract要約: 有限水平DEC-POMDPに対するポリシを計算するためのA*アルゴリズムを提案する。 私たちのゴールは、より大きな地平線に対するスケーラビリティを優先して、最適性を犠牲にすることです。
• 参考スコア（独自算出の注目度）: 8.728372851272727
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an A*-based algorithm to compute policies for finite-horizon Dec-POMDPs. Our goal is to sacrifice optimality in favor of scalability for larger horizons. The main ingredients of our approach are (1) using clustered sliding window memory, (2) pruning the A* search tree, and (3) using novel A* heuristics. Our experiments show competitive performance to the state-of-the-art. Moreover, for multiple benchmarks, we achieve superior performance. In addition, we provide an A* algorithm that finds upper bounds for the optimum, tailored towards problems with long horizons. The main ingredient is a new heuristic that periodically reveals the state, thereby limiting the number of reachable beliefs. Our experiments demonstrate the efficacy and scalability of the approach.
• Abstract（参考訳）: 有限水平DEC-POMDPのポリシーを計算するためのA*に基づくアルゴリズムを提案する。 私たちのゴールは、より大きな地平線に対するスケーラビリティを優先して、最適性を犠牲にすることです。 提案手法の主な要素は,(1)クラスタリングウィンドウメモリ,(2)A*探索ツリーの刈り取り,(3)新しいA*ヒューリスティックスである。 我々の実験は最先端技術に対する競争力を示す。 さらに,複数のベンチマークに対して,優れた性能を実現している。 さらに、長い地平線を持つ問題に合わせた最適な上限を求めるA*アルゴリズムを提供する。 主な要素は、定期的に状態を明らかにする新しいヒューリスティックであり、それによって到達可能な信念の数を制限する。 提案手法の有効性と拡張性について実験を行った。

関連論文リスト

• Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
  本稿では,POMDPにおける最大到達可能性確率問題(indefinite-horizon)と呼ばれる問題について検討する。 割引問題に対するポイントベース手法の成功に触発され,MRPPへの拡張について検討した。 本稿では,これらの手法の強みを有効活用し,信念空間を効率的に探索するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-05T02:33:50Z)
• Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
  一般化されたOneMax関数の最初のランタイム解析を提供する。 r-cGAはこのr値のOneMax問題を効率的に解くことを示す。 実験の最後には、多値OneMax関数の別の変種が期待されるランタイムに関する予想を述べる。
  論文  参考訳（メタデータ） (2024-04-17T10:40:12Z)
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning [39.40838358438744]
  線形プログラム(ILP)は、多数の最適化問題のモデリングと解決のための強力なツールである。 アルゴリズムとしてLarge Neighborhood Search (LNS)は、ブランチやバウンドよりも高速に、ILPの高品質なソリューションを見つけることができる。 本稿では,メトリクスによって測定された複数のILPベンチマークに対して,最先端のリアルタイム性能を実現する新しいアプローチCL-LNSを提案する。
  論文  参考訳（メタデータ） (2023-02-03T07:15:37Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Coordinate Descent for SLOPE [6.838073951329198]
  SLOPE(Sorted L-One Penalized Estimation, SLOPE)は、ラッソの一般化であり、統計的に魅力的な性質を持つ。 SLOPEに適合する現在のソフトウェアパッケージは、高次元において性能の悪いアルゴリズムに依存している。 近似勾配降下と近似座標降下ステップを組み合わせたSLOPE最適化問題を高速に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-26T15:20:30Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)

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

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