論文の概要: 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は多くの実世界のアプリケーションでそのような計画要件をモデル化するための有用なフレームワークを提供するが、結果として生じる問題は複雑化しており、ユーザがリアルタイムでリスクに敏感なアプリケーションに適用できないような最適なソリューションを見つけるのが困難である。 この問題に対処するため,提案アルゴリズムでは,分岐とバウンドのスキームに基づく下層計画問題に対して,コスト予算を反復的に割り当て,実現可能な解を高速かつ漸進的に更新するアルゴリズムを提案する。 提案手法を避難シナリオで実証し,最先端の数学的プログラミング手法よりも優れていることを示す。

関連論文リスト

• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。 2つのよく知られた実世界のアプリケーションでその効果を実証する。
  論文  参考訳（メタデータ） (2024-06-14T15:59:36Z)
• An Option-Dependent Analysis of Regret Minimization Algorithms in Finite-Horizon Semi-Markov Decision Processes [47.037877670620524]
  有限ホライゾン問題における後悔最小化アルゴリズムに苦しむ後悔に対するオプション依存上界について述べる。 本稿では,階層構造によって強制される時間的抽象化によって誘導される計画的地平線低減から,性能改善が導かれることを示す。
  論文  参考訳（メタデータ） (2023-05-10T15:00:05Z)
• A Hierarchical Temporal Planning-Based Approach for Dynamic Hoist Scheduling Problems [11.66506213335498]
  ホイストスケジューリングは、自律デバイスの開発で産業応用の電気めっきのボトルネックとなっている。 適応型PDDLの形で新しい時間計画問題としてホイストスケジューリング問題を定式化する。 この問題に対するソリューションメソッドの評価に使用できる実生活ベンチマークインスタンスのコレクションを提供する。
  論文  参考訳（メタデータ） (2022-12-11T05:30:44Z)
• 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)
• Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
  絡み合いルーティングは、2つの任意のノード間のリモート絡み合い接続を確立する。 量子ネットワークにおける複数のソース・デスティネーション(SD)ペアの忠実性を保証するために、精製可能な絡み合わせルーティング設計を提案する。
  論文  参考訳（メタデータ） (2021-11-15T14:07:22Z)
• Anytime Stochastic Task and Motion Policies [12.72186877599064]
  本稿では,タスクと動作計画を統合するための新しい手法を提案する。 我々のアルゴリズムは確率論的に完全であり、いつでも実現可能な解ポリシーを計算できる。
  論文  参考訳（メタデータ） (2021-08-28T00:23:39Z)
• Constrained Motion Planning Networks X [15.047777217748889]
  拘束運動計画ネットワークX(CoMPNetX)について述べる。 これはニューラルプランニングアプローチであり、条件付きディープニューラルジェネレータとニューラルグラデーションベースの高速投射演算子を持つ判別器から構成される。 提案手法は,従来のパスフィニングツールよりも高い成功率と低い時間で経路解を求める。
  論文  参考訳（メタデータ） (2020-10-17T03:34:38Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  本稿では,シーケンシャルなサブゴールタスクの超指数空間における解を高速に計算するための,Jump-Operator Dynamic Programmingという新しいフレームワークを提案する。 このアプローチでは、時間的に拡張された行動として機能する、再利用可能な目標条件付き警察のアンサンブルを制御する。 すると、この部分空間上の目的関数のクラスを、解がグラウンド化に不変であるものとして特定し、最適ゼロショット移動をもたらす。
  論文  参考訳（メタデータ） (2020-07-06T05:13:20Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  暗黙的な逐次計画の仮定に代わるものを検討する。 本稿では,最適計画の近似を行うため,Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS)を提案する。 計画順序に対するこのアルゴリズム的柔軟性は,グリッドワールドにおけるナビゲーションタスクの改善に繋がることを示す。
  論文  参考訳（メタデータ） (2020-04-23T18:08:58Z)
• A Novel Multi-Agent System for Complex Scheduling Problems [2.294014185517203]
  本稿では,様々な問題領域に適用可能なマルチエージェントシステムの概念と実装について述べる。 提案手法の有効性を示すため,NP-hardスケジューリング問題をシミュレートする。 本稿では,レイアウトの複雑さの低減,複雑なシステムの制御の改善,拡張性など,エージェントベースのアプローチの利点を強調した。
  論文  参考訳（メタデータ） (2020-04-20T14:04:58Z)

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

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