論文の概要: 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は多くの実世界のアプリケーションでそのような計画要件をモデル化するための有用なフレームワークを提供するが、結果として生じる問題は複雑化しており、ユーザがリアルタイムでリスクに敏感なアプリケーションに適用できないような最適なソリューションを見つけるのが困難である。
この問題に対処するため,提案アルゴリズムでは,分岐とバウンドのスキームに基づく下層計画問題に対して,コスト予算を反復的に割り当て,実現可能な解を高速かつ漸進的に更新するアルゴリズムを提案する。
提案手法を避難シナリオで実証し,最先端の数学的プログラミング手法よりも優れていることを示す。
関連論文リスト
- Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。
我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
論文 参考訳（メタデータ） (2025-03-01T21:25:21Z) - PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
制約,検証,選択という3つの重要な要素を持つモデルに依存しない,スケーラブルなエージェントフレームワークであるPlanGENを提案する。
具体的には、推論時間アルゴリズムの性能を向上させるために、制約誘導反復検証を提案する。
論文 参考訳（メタデータ） (2025-02-22T06:21:56Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。