論文の概要: Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget Allocation

• arxiv url: http://arxiv.org/abs/2205.05228v1
• Date: Wed, 11 May 2022 01:25:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-13 08:09:22.983012
• Title: Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget Allocation
• Title（参考訳）: コスト予算配分による階層的制約付き確率的最短経路計画
• Authors: Sungkweon Hong and Brian C. Williams
• Abstract要約: 本稿では,これら2つの重要な要件を満たす階層的制約付き最短経路問題(HC-SSP)を提案する。 結果として生じる問題は非常に複雑であり、最適な解を見つけるのが難しくなる。 提案手法は,提案手法を高速かつ漸進的に更新するために,ブランチ・アンド・バウンド・スキームに基づく低レベルの計画問題に対して,コスト予算を反復的に割り当てるアルゴリズムである。
• 参考スコア（独自算出の注目度）: 16.150627252426936
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic sequential decision making often requires hierarchical structure in the problem where each high-level action should be further planned with primitive states and actions. In addition, many real-world applications require a plan that satisfies constraints on the secondary costs such as risk measure or fuel consumption. In this paper, we propose a hierarchical constrained stochastic shortest path problem (HC-SSP) that meets those two crucial requirements in a single framework. Although HC-SSP provides a useful framework to model such planning requirements in many real-world applications, the resulting problem has high complexity and makes it difficult to find an optimal solution fast which prevents user from applying it to real-time and risk-sensitive applications. To address this problem, we present an algorithm that iteratively allocates cost budget to lower level planning problems based on branch-and-bound scheme to find a feasible solution fast and incrementally update the incumbent solution. We demonstrate the proposed algorithm in an evacuation scenario and prove the advantage over a state-of-the-art mathematical programming based approach.
• Abstract（参考訳）: 確率的逐次決定は、各ハイレベルなアクションがプリミティブな状態とアクションでさらに計画される問題において階層的な構造を必要とすることが多い。 さらに、多くの現実世界のアプリケーションでは、リスク測定や燃料消費といった二次コストの制約を満たす計画が必要となる。 本稿では,これら2つの重要な要件を満たす階層的制約付き確率的最短経路問題(hc-ssp)を提案する。 HC-SSPは多くの実世界のアプリケーションでそのような計画要件をモデル化するための有用なフレームワークを提供するが、結果として生じる問題は複雑化しており、ユーザがリアルタイムでリスクに敏感なアプリケーションに適用できないような最適なソリューションを見つけるのが困難である。 この問題に対処するため,提案アルゴリズムでは,分岐とバウンドのスキームに基づく下層計画問題に対して,コスト予算を反復的に割り当て,実現可能な解を高速かつ漸進的に更新するアルゴリズムを提案する。 提案手法を避難シナリオで実証し,最先端の数学的プログラミング手法よりも優れていることを示す。
• 全文 参考訳へのリンク

関連論文リスト

• Preliminary Results on Using Abstract AND-OR Graphs for Generalized Solving of Stochastic Shortest Path Problems [25.152899734616298]
  最短経路問題(SSP)は、現実世界におけるゴール指向の問題である。 SSPの計算における重要な課題は、適度な大きさの問題を難解に解決する方法を見つけることである。 提案手法は任意のSSPソルバに組み込んで階層的最適ポリシーを計算可能であることを示す。
  論文  参考訳（メタデータ） (2022-04-08T21:30:47Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• Anytime Stochastic Task and Motion Policies [12.72186877599064]
  本稿では,タスクと動作計画を統合するための新しい手法を提案する。 我々のアルゴリズムは確率論的に完全であり、いつでも実現可能な解ポリシーを計算できる。
  論文  参考訳（メタデータ） (2021-08-28T00:23:39Z)
• A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback [22.17503016665027]
  各アクションが未知の関節分布からランダムな報酬、コスト、ペナルティを返す問題を考える。 我々は、$tt LyOn$という新しい低複雑さアルゴリズムを提案し、$O(sqrtBlog B)$ regretと$O(log B/B)$ constraint-violationを達成することを証明した。 計算コストの低い$tt LyOn$は、Lyapunovをベースとしたアルゴリズム設計手法が制約付き帯域最適化問題の解決に有効であることを示唆している。
  論文  参考訳（メタデータ） (2021-06-09T16:12:07Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。 我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
  論文  参考訳（メタデータ） (2021-05-01T10:18:34Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Extended Task and Motion Planning of Long-horizon Robot Manipulation [28.951816622135922]
  タスクとモーション計画(TAMP)には、シンボリック推論とメトリックモーション計画の統合が必要です。 ほとんどのtampアプローチは、シンボリックレベルで環境に関する知識が欠けている場合、実現可能なソリューションを提供しない。 本稿では,計画骨格と行動パラメータに対する決定空間の拡張に関する新たな意思決定手法を提案する。
  論文  参考訳（メタデータ） (2021-03-09T14:44:08Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• MPC-MPNet: Model-Predictive Motion Planning Networks for Fast, Near-Optimal Planning under Kinodynamic Constraints [15.608546987158613]
  Kinodynamic Motion Planning (KMP) は、ロボットの動きを同時に運動学や力学の制約を受ける計算である。 ほぼ最適経路の解を求める,スケーラブルで模倣可能なモデル予測型運動計画ネットワークフレームワークを提案する。 提案アルゴリズムは, 時間, 経路特性, 既存手法に対する成功率の大幅な改善を示す結果から, 乱雑な, キノダイナミックに制約された, 不安定な計画上の問題に対して評価を行う。
  論文  参考訳（メタデータ） (2021-01-17T23:07:04Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)

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

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