論文の概要: Preliminary Results on Using Abstract AND-OR Graphs for Generalized Solving of Stochastic Shortest Path Problems

• arxiv url: http://arxiv.org/abs/2204.04301v1
• Date: Fri, 8 Apr 2022 21:30:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-12 15:43:55.944633
• Title: Preliminary Results on Using Abstract AND-OR Graphs for Generalized Solving of Stochastic Shortest Path Problems
• Title（参考訳）: 確率的最短経路問題の一般化解法における抽象的AND-ORグラフの適用に関する予備的結果
• Authors: Rushang Karia, Rashmeet Kaur Nayyar, Siddharth Srivastava
• Abstract要約: 最短経路問題(SSP)は、現実世界におけるゴール指向の問題である。 SSPの計算における重要な課題は、適度な大きさの問題を難解に解決する方法を見つけることである。 提案手法は任意のSSPソルバに組み込んで階層的最適ポリシーを計算可能であることを示す。
• 参考スコア（独自算出の注目度）: 25.152899734616298
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several goal-oriented problems in the real-world can be naturally expressed as Stochastic Shortest Path Problems (SSPs). However, a key difficulty for computing solutions for problems in the SSP framework is that the computational requirements often make finding solutions to even moderately sized problems intractable. Solutions to many of such problems can often be expressed as generalized policies that are quite easy to compute from small examples and are readily applicable to problems with a larger number of objects and/or different object names. In this paper, we provide a preliminary study on using canonical abstractions to compute such generalized policies and represent them as AND-OR graphs that translate to simple non-deterministic, memoryless controllers. Such policy structures naturally lend themselves to a hierarchical approach for solving problems and we show that our approach can be embedded in any SSP solver to compute hierarchically optimal policies. We conducted an empirical evaluation on some well-known planning benchmarks and difficult robotics domains and show that our approach is promising, often computing optimal policies significantly faster than state-of-art SSP solvers.
• Abstract（参考訳）: 現実世界のいくつかのゴール指向問題は、SSP(Stochastic Shortest Path Problems)として自然に表現できる。 しかし、SSPフレームワークにおける問題に対する解の計算の難しさは、計算要求がしばしば適度な大きさの問題の解を見つけることを困難にしていることである。 このような問題に対する解は、小さな例から非常に容易に計算でき、多数のオブジェクトや異なるオブジェクト名を持つ問題に容易に適用できる一般化されたポリシーとして表されることが多い。 本稿では,そのような一般化されたポリシーを計算し,単純な非決定論的メモリレスコントローラへ変換するグラフとして表現するための,標準的抽象化を用いた予備的研究を行う。 このような政策構造は自然に問題を解くための階層的アプローチに結びつき、我々のアプローチを任意のSSP解決器に組み込んで階層的最適ポリシーを計算できることを示します。 我々は、よく知られた計画ベンチマークと難しいロボティクス領域で実証的な評価を行い、我々のアプローチが有望であることを示し、しばしば最先端のSSP解法よりもはるかに高速に最適ポリシーを計算した。

関連論文リスト

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming [5.070542698701157]
  本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する新しいエンドツーエンドアプローチを提案する。 当社のアプローチでは,既存のCPソルバを活用して,プライオリティ・ディスパッチ・ルール(PDR)を学ぶエージェントをトレーニングする。
  論文  参考訳（メタデータ） (2023-06-09T08:24:56Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。 これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。 制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
  論文  参考訳（メタデータ） (2022-08-23T18:56:05Z)
• Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach [0.0]
  本稿では,パラメータ化複雑性解析を用いて,アルゴリズムの選択肢を体系的に探索する方法を示す。 環境、実演、ポリシーに対する多くの(しばしば同時に)制限に対して、我々の問題は、一般的にも、あるいは相対的に、効率的に解決できないことを示す。
  論文  参考訳（メタデータ） (2022-05-10T15:54:06Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Learning General Policies from Small Examples Without Supervision [18.718037284357834]
  一般化計画は、計画ドメインの複数のインスタンスを一度に解決する一般的なポリシーの計算に関するものです。 近年、これらのポリシーは2つのステップで計算可能であることが示されている。まず、定性的数値計画問題(QNP)の形で適切な抽象化をサンプル計画から学習する。 本稿では,サンプルプランやqnpプランナーを必要とせず,より表現力のある汎用ポリシーを計算するための代替手法を提案する。
  論文  参考訳（メタデータ） (2021-01-03T19:44:13Z)

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

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