論文の概要、ライセンス

# (参考訳) コスト予算配分による階層的制約付き確率的最短経路計画 [全文訳有]

Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget Allocation ( http://arxiv.org/abs/2205.05228v1 )

ライセンス: CC BY 4.0
Sungkweon Hong and Brian C. Williams(参考訳) 確率的逐次決定は、各ハイレベルなアクションがプリミティブな状態とアクションでさらに計画される問題において階層的な構造を必要とすることが多い。 さらに、多くの現実世界のアプリケーションでは、リスク測定や燃料消費といった二次コストの制約を満たす計画が必要となる。 本稿では,これら2つの重要な要件を満たす階層的制約付き確率的最短経路問題(hc-ssp)を提案する。 HC-SSPは多くの実世界のアプリケーションでそのような計画要件をモデル化するための有用なフレームワークを提供するが、結果として生じる問題は複雑化しており、ユーザがリアルタイムでリスクに敏感なアプリケーションに適用できないような最適なソリューションを見つけるのが困難である。 この問題に対処するため,提案アルゴリズムでは,分岐とバウンドのスキームに基づく下層計画問題に対して,コスト予算を反復的に割り当て,実現可能な解を高速かつ漸進的に更新するアルゴリズムを提案する。 提案手法を避難シナリオで実証し,最先端の数学的プログラミング手法よりも優れていることを示す。

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.
公開日: Wed, 11 May 2022 01:25:38 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
Hierarchical Constrained Stochastic Shortest Path Planning via Cost コストによる階層的制約付き確率的最短経路計画 0.69
Budget Allocation Sungkweon Hong1 and Brian C. Williams1 予算配分 Sungkweon Hong1とBrian C. Williams1 0.47
In fact, hierarchical structure in the planning problem has been widely studied in stochastic sequential decision making problems [4], [5], [6], [7], [8]. 実際,計画問題の階層構造は,[4],[5],[6],[7],[8]という確率的逐次意思決定問題において広く研究されている。
訳抜け防止モード: 実際, 計画問題の階層構造は, 確率的逐次意思決定問題において広く研究されてきた[4]。 [ 5 ], [ 6 ], [ 7 ], [ 8 ] .
0.80
In those works, options, also known as macro actions or skills, were introduced to abstract the underlying problem space into a higher-level space to scale both learning and planning processes. これらの作品では、マクロアクションやスキルとして知られるオプションが導入され、基礎となる問題空間を学習と計画プロセスの両方をスケールするために高レベルな空間に抽象化された。 0.59
However, most of the works in hierarchical planning focus on minimizing the expected cost (or maximizing the expected reward). しかしながら、階層的な計画の作業のほとんどは、期待されるコストを最小化(あるいは期待される報酬を最大化)することに焦点を当てています。
訳抜け防止モード: しかし 階層的計画の作業の多くは 期待コストの最小化(または期待報酬の最大化)。
0.73
In many of the real-world applications, however, naively minimizing the expected cost might not be desirable. しかし、現実世界のアプリケーションの多くでは、期待するコストを最小限に抑えることは望ましくないかもしれない。
訳抜け防止モード: しかし、現実世界の多くのアプリケーションでは 期待するコストを最小化します 望ましくないかもしれない。
0.70
For example, when we want an aircraft to navigate to the destination as fast as possible, it is also important to ensure the aircraft can complete the mission with the onboard fuel or stays outside of the unsafe region for safety. 例えば、航空機をできるだけ早く目的地まで移動させたい場合、機内燃料でミッションを完了するか、安全のために安全でない領域の外に留まることも重要である。 0.62
2 2 0 2 y a M 1 1 2 2 0 2 y a m 1 1 である。 0.54
] I A . s c [ 【私】 A! sc [ 0.50
1 v 8 2 2 5 0 1 v 8 2 2 5 0 0.42
. 5 0 2 2 : v i X r a . 5 0 2 2 : v i X r a 0.42
Abstract— Stochastic sequential decision making often requires hierarchical structure in the problem where each highlevel action should be further planned with primitive states and actions. 抽象 – 確率的シーケンシャルな意思決定は、しばしば、各ハイレベルなアクションがプリミティブな状態とアクションでさらに計画される問題において階層的な構造を必要とする。 0.63
In addition, many real-world applications require a plan that satisfies constraints on the secondary costs such as risk measure or fuel consumption. さらに、多くの現実世界のアプリケーションでは、リスク測定や燃料消費といった二次コストの制約を満たす計画が必要となる。 0.75
In this paper, we propose a hierarchical constrained stochastic shortest path problem (HCSSP) that meets those two crucial requirements in a single framework. 本稿では,この2つの重要な要件を満たす階層的制約付き確率的最短経路問題 (HCSSP) を提案する。 0.73
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. HC-SSPは多くの実世界のアプリケーションでそのような計画要件をモデル化するための有用なフレームワークを提供するが、結果として生じる問題は複雑化しており、ユーザがリアルタイムでリスクに敏感なアプリケーションに適用できないような最適なソリューションを見つけるのが困難である。 0.67
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. この問題に対処するため,提案アルゴリズムでは,分岐とバウンドのスキームに基づく下層計画問題に対して,コスト予算を反復的に割り当て,実現可能な解を高速かつ漸進的に更新するアルゴリズムを提案する。 0.72
We demonstrate the proposed algorithm in an evacuation scenario and prove the advantage over a state-of-the-art mathematical programming based approach. 提案手法を避難シナリオで実証し,最先端の数学的プログラミング手法よりも優れていることを示す。 0.70
I. INTRODUCTION I. イントロダクション 0.64
As human beings, making decisions is one of the daily tasks to improve our lives, where many, if not most, decisions are sequential. 人間として、意思決定は私たちの生活を改善するための日々のタスクの1つです。
訳抜け防止モード: 人間として 決定を下す 日々の課題の一つです 人生を改善するために、多くの意思決定が連続的に行われます。
0.74
Sequential decision making has been one of the core topics in Artificial Intelligence (AI) to support those pervasive tasks [1], [2], [3]. 逐次意思決定は人工知能(AI)の中核的なトピックの1つであり、これらの普及したタスク [1], [2], [3] をサポートする。 0.78
The major role of sequential decision making is generating a course of actions that achieves the goals of an agent. シーケンシャルな意思決定の主要な役割は、エージェントの目標を達成する一連のアクションを生成することである。 0.80
Actions are defined from the domain of the problem and describe the states where they can be executed and how the states are changed by executing them. アクションは問題のドメインから定義され、実行可能な状態と、それらを実行することで状態がどのように変化するかを記述する。 0.77
In commercial aircraft operation, for example, nominal unit operations are based on air route segments and standard departure/arrival procedures, and hence those can be reasonable choices of actions sets. 例えば、商用航空機の運用では、名目上の単位操作は、航空経路のセグメントと標準の出発/到着手順に基づいており、そのためアクションセットの合理的な選択となる。 0.65
In sequential decision making problems, a crucial assumption is that the actions are well defined and an agent is capable of executing those actions. 逐次意思決定問題において、重要な前提は、アクションが明確に定義され、エージェントがそのアクションを実行することができることである。
訳抜け防止モード: 逐次意思決定問題において,重要な仮定は アクションは明確に定義され、エージェントはこれらのアクションを実行することができる。
0.77
For many real-world problems, however, such assumption is too strong to hold, especially for online applications. しかし、現実世界の多くの問題では、特にオンラインアプリケーションでは、そのような仮定は強すぎる。 0.67
Again, in aircraft operations, even though each air route segment is well established and can be flown as a routine procedure, there might be a novel circumstance that prohibits an aircraft from flying the segment as published, such as convective weather conditions. また、航空機の運用においては、各航空路セグメントが十分に確立されており、定期的な手順として飛行できるとしても、対流気象条件など、航空機がセグメントを飛行することを禁じる新たな状況が存在するかもしれない。 0.70
In such situation, travelling the air route segment forms another planning problem, which makes the problem hierarchical. このような状況下では、航空経路セグメントの走行は別の計画問題となり、この問題は階層的になる。 0.61
1Computer Science and Artificial 1コンピュータ科学と人工知能 0.72
Intelligence Lab, Massachusetts Institute of Technology, Cambridge, MA 01239, USA, {sk5050, williams}@csail.mit.edu. Intelligence Lab, Massachusetts Institute of Technology, Cambridge, MA 01239, USA, {sk5050, williams}@csail.mit.edu.com 0.45
The work was supported by the Boeing Corporation. この事業はボーイング社によって支援された。 0.53
Despite being non-hierarchical, stochastic sequential decision making problems have been widely extended to include constraints. 非階層的であるにもかかわらず、確率的な逐次決定問題は制約を含むように広く拡張されている。 0.50
One of the most well-known frameworks is constrained stochastic shortest path problems (C-SSPs) [9], which optimize the primary cost function while constraining the secondary cost functions. 最もよく知られているフレームワークの1つは制約付き確率的短経路問題(c-ssps)[9]であり、二次コスト関数を制約しながら一次コスト関数を最適化する。 0.71
In this paper, we propose a new framework, hierarchical constrained stochastic shortest path problem (HC-SSP), that extends C-SSP to hierarchical problem structure. 本稿では,C-SSPを階層的問題構造に拡張する,階層的制約付き確率的最短経路問題(HC-SSP)を提案する。 0.77
To the authors’ knowledge, this extension has been little attempted, yet there is some work on this direction [10]. 著者の知る限りでは、この拡張はほとんど試みられていないが、この方向についてはいくつかの研究がある[10]。 0.63
However, the previous work focuses on abstracting the existing state space to find an approximated solution to the original problem. しかし、以前の研究は、既存の状態空間を抽象化して、元の問題に対する近似解を見つけることに重点を置いている。
訳抜け防止モード: しかし 前回の研究は 既存の状態空間を抽象化して元の問題に対する近似解を見つける。
0.60
In our approach, on the other hand, we focus on finding (near-)optimal solution given the hierarchical structure of the problem. 一方,本手法では,問題の階層構造を考慮した最適解の探索に注目する。 0.55
Although the extension from C-SSP to HC-SSP looks straightforward, this extension poses a unique challenge that has not been present in the previous works. C-SSP から HC-SSP への拡張は単純に見えるが、この拡張は以前の研究には存在しなかった独特な挑戦である。 0.73
A hierarchical approach has its advantage based on decoupled high-level actions that can be learned individually. 階層的なアプローチは、個別に学習できる分離されたハイレベルなアクションに基づく利点がある。 0.71
However, with a constraint, they are no longer decoupled due to shared cost budget given by the constraint. しかし、制約により、制約によって与えられる共有コスト予算のため、もはや分離されない。 0.63
To address this problem, we propose a cost budget allocation approach based on the wellknown branch-and-bound scheme. この問題に対処するため,よく知られた分岐・分岐方式に基づく予算配分手法を提案する。 0.65
This paper makes two main contributions. 本論文の主な貢献は2つある。 0.69
First, we propose a hierarchical constrained stochastic shortest path problem (HC-SSP) that extends C-SSP with hierarchical structure. まず,C-SSPを階層構造で拡張する階層的制約付き確率的最短経路問題(HC-SSP)を提案する。 0.72
Second, we propose a budget-allocation-ba sed algorithm that finds a deterministic hierarchical policy to a HC-SSP in an anytime fashion. 第2に,hc-sspに対する決定論的階層ポリシーを随時求める予算割当に基づくアルゴリズムを提案する。 0.77
The algorithm is shown to be theoretically optimal given a specific condition and can be approximated based on the user-defined approximation level. このアルゴリズムは特定の条件で理論的に最適であることが示され、ユーザ定義近似レベルに基づいて近似することができる。 0.79
The experimental results show that the algorithm can find near-optimal solutions in most cases even with high 実験の結果, アルゴリズムは高値であってもほとんど最適に近い解を見つけることができることがわかった。
訳抜け防止モード: 実験結果は アルゴリズムは高い場合でもほとんどの場合においてほぼ最適解を見つけることができる
0.75
英語(論文から抽出)日本語訳スコア
approximation level. The remainder of this paper is organized as follows. 近似レベル。 本論文の残りは以下のとおり整理される。 0.70
Section II summarizes the most relevant backgrounds to our work. 第2節は我々の作品に最も関係のある背景をまとめたものである。 0.46
Section III presents the proposed HC-SSP problem definition with an intuitive example. 第3節では、hc-ssp問題の定義を直感的な例で示す。 0.47
Section IV elaborates our proposed algorithm, followed by evaluation results in Section V. Finally, we conclude and present future work in Section VI. 第4節では提案したアルゴリズムを詳述し,第5節では評価結果が得られた。
訳抜け防止モード: 第4節では提案したアルゴリズムを詳述し、第5節では評価結果が得られた。 第6節の結論と今後の課題
0.51
II. PRELIMINARIES II。 プレリミナリス 0.61
A. Constrained Stochastic Shortest Path Problem A. 制約付き確率的最短経路問題 0.74
A constrained stochastic shortest path problem (C-SSP) is a tuple (cid:104)S, ¯s,G,A, T, (cid:126)C, (cid:126)∆(cid:105) in which S is a set of discrete states; ¯s ∈ S is the initial state; G ⊂ S is a set of goal states; A is a set of discrete actions; T : S × A × S → [0, 1] is the state transition function, where T (s, a, s(cid:48)) = P r(s(cid:48)|s, a) is the probability of being in state s(cid:48) after executing action a in state s; (cid:126)C is the indexed set of cost functions {C0, ..., CN}, where each Ci : S × A × S → R+ is the cost function and Ci(s, a, s(cid:48)) is the i-th cost of executing action a in the state s and resulting in the state s(cid:48); and (cid:126)∆ is the indexed set of bounds {∆1, . . . , ∆N}, where ∆i is the bound for i-th cost function for i = 1, . . . , N [9], [11]. A constrained stochastic shortest path problem (C-SSP) is a tuple (cid:104)S, ¯s,G,A, T, (cid:126)C, (cid:126)∆(cid:105) in which S is a set of discrete states; ¯s ∈ S is the initial state; G ⊂ S is a set of goal states; A is a set of discrete actions; T : S × A × S → [0, 1] is the state transition function, where T (s, a, s(cid:48)) = P r(s(cid:48)|s, a) is the probability of being in state s(cid:48) after executing action a in state s; (cid:126)C is the indexed set of cost functions {C0, ..., CN}, where each Ci : S × A × S → R+ is the cost function and Ci(s, a, s(cid:48)) is the i-th cost of executing action a in the state s and resulting in the state s(cid:48); and (cid:126)∆ is the indexed set of bounds {∆1, . . . , ∆N}, where ∆i is the bound for i-th cost function for i = 1, . . . , N [9], [11].
訳抜け防止モード: 制約付き確率的最短経路問題(c - ssp)はタプル(cid:104)sである。 s, g, a, t, ( cid:126)c, ( cid:126) ) (cid:105 ) ここで s は離散状態の集合であり、 s ∈ s は初期状態 ; s はゴール状態のセットである ; a は離散作用の集合 ; t : s × a × s → [ 0, 1 ] は状態遷移関数であり、 t ( s, a, s(cid:48 ) ) = p r(s(cid:48)|s である。 a ) は状態 s におけるアクション a の実行後に状態 s(cid:48 ) になる確率である; ( cid:126)c はコスト関数 { c0, ..., cn } のインデックス付き集合である。 各ci : s × a × s → r+ がコスト関数である場合 ci(s, a, s(cid:48 ) ) は i 番目のコストである。 状態sでアクションaを実行し、状態s(cid:48)になる ( cid:126) ) ; ; ( cid:126) ) は境界 {1, . . . . . . .n } のインデックス付き集合である。 ここで、i は i - th cost function for i = 1, ..., のバウンドである。 N [ 9 ] , [ 11 ] .
0.86
A solution to a C-SSP is a policy π : S × A → [0, 1] which maps states to a probability distribution over actions. C-SSPの解はポリシー π : S × A → [0, 1] であり、状態が作用上の確率分布に写像される。 0.81
If a policy maps every state to a probability distribution with a single outcome, the policy is called “deterministic,” and is called “stochastic” otherwise. 政策が全ての状態を一つの結果で確率分布にマッピングすると、その政策は「決定論的」と呼ばれ、それ以外は「確率的」と呼ばれる。 0.72
In the former case, we denote π(s) as the action selected by the policy π for the state s. 前者の場合、状態 s に対するポリシー π によって選択された作用として π(s) を示す。 0.75
An optimal solution to a C-SSP is a policy π∗ which minimizes the total expected cost, but in addition, the expected cost of the secondary cost function Ci should be upper bounded by ∆i for i = 1, . . . , N. In other words, an optimal policy π∗ for a C-SSP is defined as follows: c-ssp の最適解は、期待される総コストを最小化するポリシー π∗ である。さらに、二次コスト関数 ci の期待コストは、i = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . である。
訳抜け防止モード: C - SSP に対する最適解は、期待される総コストを最小化するポリシー π∗ である。 さらに、二次コスト関数 Ci の期待コストは、i = 1, ... に対して .i によって上界化されるべきである。 言い換えれば、C - SSP に対する最適ポリシー π∗ は次のように定義される。
0.78
argmin π∈Π s.t. アルミン πππ s.t. 0.43
f (π) gi(π) ≤ 0 f(π) gi(π) ≤ 0 0.42
where Π is the set of all policies and はすべての政策の集合であり 0.59
f (π) = E C0(st, at, st+1) f (π) = E C0(st, at, st+1) 0.43
(cid:34) ∞(cid:88) (cid:34) ∞(cid:88) (cid:34) ∞(cid:88) (cid:34) ∞(cid:88) 0.38
t=0 t=0 for i = 1, . . . , N , t=0 t=0 i = 1 の場合、N である。 0.41
(cid:35) (cid:12)(cid:12)(cid :12)(cid:12)s0 = ¯s, π (cid:35) (cid:12)(cid:12)(cid :12)(cid:12)s0 = ¯s, π (cid:35) (cid:12)(cid:12)(cid :12)(cid:12)s0 = ss, π (cid:35) (cid:12)(cid:12)(cid :12)(cid:12)s0 = s, π 0.38
gi(π) = E Ci(st, at, st+1) gi(π) = E Ci(st, at, st+1) 0.45
− ∆i. Note that every optimal policy for a C-SSP might be stochastic [9]. 通称「イ」。 C-SSP に対する任意の最適ポリシーは確率的かもしれない [9]。 0.52
In this paper, however, we limit the policy space to deterministic ones which are preferred due to explainability and reliability in the safety-critical applications such as aircraft operations. しかし,本稿では,航空機操作などの安全クリティカルな応用における説明可能性や信頼性から望ましい決定性に,政策空間を限定する。 0.86
Note that it is known that limiting the policy space to deterministic ones significantly increases the complexity of the problem [12]. 政策空間を決定論的に制限することは問題の複雑さを著しく増大させることが知られている [12]。 0.82
B. Anytime Algorithm for C-SSPs b. c-sspsのためのanytimeアルゴリズム 0.61
In this section, we introduce a recently developed anytime algorithm for C-SSPs in [13] which we use as a subroutine in our proposed method. 本稿では,提案手法のサブルーチンとして使用する[13]において,最近開発されたc-sspsのanytimeアルゴリズムを提案する。 0.78
The algorithm has two stages where アルゴリズムには2つの段階がある 0.72
Fig. 1: Visualization of the second stage of the anytime algorithm. 第1図:anytimeアルゴリズムの第2段階の可視化。 0.73
the first stage finds a Lagrangian dual solution of a C-SSP and then the second stage incrementally closes a duality gap, if there is any. 第一段階は C-SSP のラグランジアン双対解を見つけ、次に第二段階は、もしあるならば、段階的に双対性ギャップを閉じる。
訳抜け防止モード: 第一段階は、C-SSPのラグランジアン双対解を見つける そして第2段階は 二重性ギャップを漸進的に閉じます
0.72
In the first stage, the Lagrangian function is defined as follows: 第1段階では、ラグランジュ函数を次のように定義する。 0.70
L(λ, π) = f (π) + λ · g(π), L(λ, π) = f(π) + λ · g(π) 0.40
where λ = [λ1, . . . , λN ] ∈ RN the Lagrangian dual problem is defined as follows: λ = [λ1, . . , λN ] ∈ RN において、ラグランジュ双対問題は次のように定義される。 0.76
(1) + and g = [g1, . . . , gN ](cid:62). 1)+およびg = [g1, . , gN](cid:62)。 0.73
Then where L∗ = L(λ∗) = max λ≥0 そして どこに L∗ = L(λ∗) = max λ≥0 0.62
L(λ), L(λ) = min π∈Π l(λ) である。 l(λ) = min πππ 0.51
L(λ, π). l(λ, π) である。 0.84
(2) (3) Note that the following statement holds, according to the weak duality [14]: (2) (3) 下記の声明は、[14]の弱双対性に従って成り立つことに注意する。 0.50
L(λ) ≤ f∗, L(λ) ≤ f∗, 0.42
∀λ ≥ 0, (4) where f∗ is the primal optimal cost. ∀λ ≥ 0, (4) f∗ が最優先の最適コストである。 0.64
If L(λ) = f∗, where the strong duality holds, the dual solution coincides with a true optimal solution. L(λ) = f∗ ならば、強双対性は成り立つが、双対解は真の最適解と一致する。 0.75
However, strong duality usually does not hold in our problem and a duality gap exists. しかし、強い双対性は通常我々の問題には成立せず、双対性ギャップが存在する。 0.62
The purpose of the second stage is to reduce such gap and find a primal optimal solution. 第2段階の目的は、そのようなギャップを減らし、原始最適解を見つけることである。 0.62
Conceptually, the way the algorithm obtains a primal optimal policy is quite simple. 概念的には、アルゴリズムが原始最適ポリシーを得る方法は極めて単純である。 0.79
From the dual optimal policy, we can find a primal optimal solution by iteratively finding the next best solutions, with respect to the Lagrangian function value L(λ∗, π). 双対最適ポリシーから、ラグランジュ関数の値 L(λ∗, π) に関して、次の最適解を反復的に見つけることによって、原始最適解を見つけることができる。 0.77
This procedure is illustrated in Fig 1 with an intuitive example which only includes a single secondary cost function. この手順は、直感的な例で図1に示され、1つの二次コスト関数のみを含む。 0.77
The figure shows all the deterministic policies in (λ, L) space, including feasible ones (g1(π) ≤ 0) and infeasible ones (g1(π) > 0), in green solid lines and red dotted lines, respectively. この図は、(λ, l) 空間における決定論的な方針を全て示しており、実現可能な1(g1(π) ≤ 0) と実行不可能な1(g1(π) > 0) は、それぞれ緑色固形線と赤点線である。
訳抜け防止モード: 図は ( λ, L ) 空間におけるすべての決定論的ポリシーを示している。 実現可能なもの(g1(π ) ≤ 0 )と不可能なもの(g1(π ) > 0 )を含む。 緑色の固形線と赤い点線で
0.82
Note that the true primal optimal policy π∗ is indicated with a bold line. 真の原始最適ポリシー π∗ は大胆な直線で表されることに注意。 0.70
Fig 1 also shows the Lagrangian function value L(λ∗, π) for each policy as an intersection of the policy with the dotted vertical line at λ∗. 図1はまた、各ポリシーに対するラグランジュ関数の値 L(λ∗, π) を λ∗ における点のある垂直線との交点として示している。 0.80
Similarly, a y-intercept of a policy π is the primal cost f (π). 同様に、政策 π の y-受理は原価 f (π) である。 0.77
In addition, π1 is the solution associated with λ∗ which can be obtained from the first stage, where πk denotes k-th さらに π1 は λ∗ に付随する解であり、πk が k-th を表す最初の段階から得られる。 0.78
英語(論文から抽出)日本語訳スコア
Fig. 2: Illustration of the robot evacuation scenario. 図2:ロボット避難シナリオの図示。 0.59
best policy with respect to the Lagrangian function value L(λ∗, π). ラグランジュ函数の値 L(λ∗, π) に関する最良のポリシー。 0.67
Starting from π1, we find the next best policies in terms of L(λ∗, π), in a non-decreasing manner, until we obtain a primal optimal policy π∗, and update the incumbent policy whenever we obtain a better feasible policy. π1 から始めて、L(λ∗, π) という観点で次の最良のポリシーが非減少的な方法で見つかる。
訳抜け防止モード: π1 から始めて、L(λ∗, π ) という観点で次の最良のポリシーを見つける。 非減少的な方法で、それまで 原始最適ポリシー π∗ を得る。 実現可能な政策を得るたびに 既存の方針を更新します
0.79
Note that the Lagrangian function value and incumbent cost at any time set lower and upper bounds on the optimal cost of the C-SSP, respectively. ラグランジアン関数の値と既存のコストは、それぞれC-SSPの最適コストについて下限と上限を設定している。 0.71
We refer to [13] for the details of the anytime algorithm. 我々はanytimeアルゴリズムの詳細について[13]を参照する。 0.76
III. HIERARCHICAL CONSTRAINED STOCHASTIC III。 階層構造ストーカ 0.53
SHORTEST PATH PROBLEM In this section, we define a hierarchical constrained stochastic shortest path problem (HC-SSP). 最短経路問題 本稿では,階層的制約付き確率的最短経路問題 (HC-SSP) を定義する。 0.55
We begin this section with an intuitive example of a HC-SSP followed by a formal definition. この節はhc-sspの直観的な例から始まり、形式的な定義が続く。 0.61
A. HC-SSP in a Nutshell A. HC-SSP in a Nutshell 0.39
Consider a grounded example shown in Fig 2, in which a robot is evacuating from a building with six rooms in a hazardous environment. 危険な環境で6つの部屋のある建物からロボットが脱出する、図2に示されている接地した例を考えてみよう。 0.78
In this example, a robot should make a series of decisions about which hallway or door to approach to get to the exit point. この例では、ロボットは出口に到達するためにどの廊下やドアに近づくべきかを一連の決定を下さなければならない。 0.77
At a quick glance, using door 1 and door 2 seems to let the robot evacuate faster than the other options. 一見すると、ドア1とドア2を使えば、ロボットは他の選択肢よりも速く避難できるようだ。 0.76
However, the decision should be made carefully since the robot has only partial information on the building: the robot knows that the hallways are always clear, but also knows that the doors are locked with a 0.1 probability, in which case the robot should take a roundabout way. ロボットは廊下が常に明確であることを知っているが、ドアが0.1の確率でロックされていることも知っている。
訳抜け防止モード: しかし、ロボットは建物に関する部分的な情報しか持っていないため、慎重に決めるべきである。 ロボットは廊下が常に明確であることを知っています しかし それも知っています ドアは0.1の確率でロックされています。
0.80
By assuming that a set of activities that move a robot from a specific landmark to another is well defined, the problem can be formulated as a conditional procedural planning problem, which is shown in Fig 3 graphically. ロボットを特定のランドマークから他のランドマークへ移動させる一連のアクティビティが適切に定義されていると仮定し、図3に示すような条件付き手続き計画問題として定式化することができる。 0.78
Note that, each circle and oval represents a notable event and activities, respectively. それぞれの円と楕円は、それぞれ注目すべき出来事と活動を表す。 0.67
Also note that, double circle and dotted double circle represent controllable and uncontrollable choices, respectively. また、二重円と点状の二重円はそれぞれ制御不能かつ制御不能な選択を表す。 0.70
One of the keys to our approach is noting that each activity (e g , go-to-door1) is not necessarily predefined. このアプローチの鍵のひとつは、各アクティビティ(例えば、go-to-door1)が必ずしも事前に定義されていないことだ。 0.65
Rather, each of the activities can be defined as an another planning problem with its own state and action space. むしろ、それぞれのアクティビティは、自身の状態と行動空間を持つ別の計画問題として定義することができる。 0.72
For example, each activity can be considered as a stochastic shortest path problem in a grid world as shown in Fig 3. 例えば、各アクティビティは、図3に示すように、グリッド世界における確率的最短経路問題とみなすことができる。 0.78
Another key to our approach is constraints on secondary costs defined over a set of activities. このアプローチのもうひとつの鍵は,アクティビティセット上で定義されたセカンダリコストの制約です。 0.65
Consider a global Fig. 3: Graphical representation of the procedural planning problem for the evacuation scenario in Fig 2. グローバルを考える 第3図:第2図における避難シナリオの手続き計画問題の図式表現 0.72
An example of planning problem for go-to-door1 activity is also shown, where red shaded states are hazardous states and blue and green states are initial and goal states, respectively. ゴー・トゥ・ドア1(go-to-door1)活動の計画上の問題の例としては、赤い日陰状態が有害な状態であり、青と緑の状態がそれぞれ初期状態と目標状態である。
訳抜け防止モード: go - to - door1アクティビティの計画問題の一例も示す。 赤いシェード状態が危険な状態であり、青と緑の状態がそれぞれ初期状態と目標状態である。
0.72
constraint for the evacuation scenario is defined verbally as follows: “The damage caused by fire must be less than or equal to ∆ until evacuation.” 避難シナリオの制約は,「火災による被害は,避難するまでは,...以下でなければならない。」と口頭で定義されている。 0.67
With such constraint, the planning problem for go-to-door1 in Fig 3 is now a constrained stochastic shortest path problem. このような制約により、fig 3 における go-to-door1 の計画問題は制約付き確率的最短経路問題となっている。 0.61
There is another yet more important implication of having such global constraint. このようなグローバル制約を持つことの、さらに重要な意味合いがある。 0.60
Due to the global constraint, activities are no longer independent. 世界的制約のため、活動はもはや独立していない。 0.67
Suppose we are planning for an activity go-to-door1 as a sub-problem for our evacuation planning problem. 避難計画問題のサブプロブレムとして、活動go-to-door1を計画しているとしよう。 0.55
Then, how much of the cost out of the global damage budget ∆ should be allocated for this activity? では、世界的な損害予算のうち、どれだけのコストをこの活動に充てるべきなのか? 0.73
For example, using budget parsimoniously in planning go-to-door1 might result in a conservative and suboptimal plan if optimal solutions for other activities cause negligible damage. 例えば、go-to-door1計画の予算を同時に使うと、他の活動に対する最適な解決策が無視できるダメージを与える場合、保守的かつ準最適の計画がもたらされる。 0.56
On the other hand, using too much of the budget in planning go-to-door1 might result in suboptimality as well, since other activities could reduce global cost by using more budget. 一方で、予算の過剰な活用は、より多くの予算を使用することでグローバルコストを削減できるため、go-to-door1の計画にサブオプティリティ(suboptimality)を発生させる可能性がある。 0.59
This motivates us to allocate the budget systematically for different activities to obtain global optimality which will be discussed in more detail in Section IV. これは、第4節でより詳細に論じられるようなグローバル最適性を得るために、異なる活動のための予算を体系的に割り当てる動機付けとなる。
訳抜け防止モード: これは、異なる活動のために予算を体系的に割り当てるモチベーションになります 第4節で詳述する大域的最適性を得る。
0.63
Finally, a solution to HC-SSP is a hierarchical policy that consists of both procedural policy and policies for every associated activity. 最後に、hc-sspの解決策は、関連するアクティビティごとに手続きポリシーとポリシーの両方からなる階層ポリシーである。 0.70
There are two desirable properties for a solution. 解には2つの望ましい性質がある。 0.67
First, the solution should be feasible, which means that the solution should not violate any constraint. まず、ソリューションは実現可能でなければならない。つまり、ソリューションはいかなる制約にも違反してはならない。 0.65
In the evacuation scenario, we only have one global constraint that requires the damage caused by fire to be less than or equal to ∆. 避難シナリオでは、火災によって引き起こされる損害が s 以下であることを要求する1つのグローバルな制約しかありません。 0.68
Therefore, the weighted sum of the damage cost for every activity that is selected by a procedural policy should be less than or equal to ∆, where a weight for an activity is the likelihood of executing that activity. したがって、手続き的方針によって選択されたすべての活動に対する損傷コストの重み付け和は、その活動の実行可能性の重み付けとなる場合、s に満たないか等しくすべきである。 0.72
Second, the solution should minimize the expected cost. 第二に、ソリューションは期待するコストを最小限に抑えるべきである。 0.58
It is not always possible, however, to obtain an optimal solution, especially when the planning time is limited. しかし、特に計画時間が限られている場合には、最適解が得られるとは限らない。 0.68
Therefore, we want to develop a solution method with an anytime property which can output an incumbent feasible solution at timeout while the solution eventually converges to a true optimal solution with sufficient planning time. そこで本研究では,既存の実現可能な解をタイムアウト時に出力し,最終的には十分な計画時間で真の最適解に収束する解法を開発したい。 0.72
英語(論文から抽出)日本語訳スコア
B. Problem Definition • P : T ×(cid:83) B.問題定義 • P : T ×(cid:83) 0.63
A HC-SSP is a tuple (cid:104)S,I,T ,V,E,P,{Cj}j∈J(cid:105), where • S is a set of discrete states. HC-SSP はタプル (cid:104)S,I,T ,V,E,P,{Cj}j・J(cid:105) であり、S は離散状態の集合である。 0.80
• I : S → [0, 1] is the initial distribution. • I : S → [0, 1] は初期分布である。 0.83
• T is a set of notable events. • T は注目すべきイベントの集合である。 0.76
Note that ts and te are two special events, where ts is the start event and te is the end event. tsとteは2つの特別なイベントであり、tsはスタートイベント、teは終了イベントである。 0.79
• V is a set of choice variables, each v ∈ V being a discrete, finite domain variable. • v は選択変数の集合であり、それぞれの v ∈ v は離散有限領域変数である。 0.81
Note that each v ∈ V is associated with an event t ∈ T , where we denote V(t) = v. • E is a set of activities. 各 v ∈ v はイベント t ∈ t に関連付けられており、ここで v(t) = v. • e はアクティビティの集合である。
訳抜け防止モード: 各 v ∈ V はイベント t ∈ T に関連付けられており、V(t ) を表すことに注意。 = v. • E はアクティビティの集合である。
0.88
An activity E ∈ E is activated if both start and end events of the activity are activated. アクティビティの開始イベントと終了イベントの両方が活性化されると、アクティビティ E ∈ E が活性化される。 0.80
t∈T Dom{V(t)} × T → [0, 1] is a probabilistic transition function between events based on the assignments of choice variables, where P(t, a, t(cid:48)) = P r(t(cid:48)|t, a) is the probability of being in event t(cid:48) after executing choice a in event t. t(t, a, t(cid:48)) = p r(t(cid:48)|t, a) はイベント t(cid:48) における選択 a の実行後にイベント t(cid:48) に含まれる確率である。
訳抜け防止モード: t⋅T Dom{V(t ) } × T → [ 0, 1 ] は選択変数の代入に基づく事象間の確率的遷移関数である。 ここで P(t, a, t(cid:48 ) ) = P r(t(cid:48)|t, a)が確率である イベントt(cid:48)にあるさま ) 選択aをイベントtで実行した後。
0.87
• {Cj}j∈J is an indexed set of constraints, where J = {1, . . . , M} and M is the number of constraints. ここで、J = {1, . . , M} と M は制約の数である。
訳抜け防止モード: • { cj}jftpj は制約のインデックス付き集合であり、ここで j = { 1, ..., である。 m } と m は制約の数である。
0.73
Each Cj is a tuple (cid:104)Ψj, Ij, ∆j(cid:105), where Ψj ⊂ E is a set of activities associated with the constraint Cj, ∆j is an upper bound and Ij : Ψj → N is an index function for each E ∈ Ψj that indicates which secondary cost function is used for Cj. 各々の cj はタプル (cid:104)ψj, ij, sj(cid:105) であり、そこで ψj は制約 cj に付随するアクティビティの集合であり、ij : ψj → n は各 e ∈ ψj に対する指数関数であり、どの二次コスト関数が cj に使用されるかを示す。 0.84
Note that in this paper we assume that a secondary cost function of an activity is included in at most one constraint for simplicity. 本稿では,アクティビティの二次的コスト関数が,少なくとも1つの制約に含まれると仮定する。 0.72
This assumption, however, can be easily generalized with little modification. しかし、この仮定はほとんど修正することなく容易に一般化できる。 0.71
E ∈ T are the start and end events of the activity, E ∈ T はアクティビティの開始と終了のイベントである。 0.81
E,SE,AE, TE, (cid:126)CE,GE(cid:1 05), where E, te respectively. E,SE,AE,TE, (cid:126)CE,GE(cid:1 05), それぞれE, Te。 0.82
A HC-SSP abstracts the underlying state-action space and dynamics based on events and activities, where the activities are selected by choice variables and the transitions between events are governed by transition function P. Then each activity is defined over a subset of underlying state space and has its own action space and dynamics with its sub-goal. HC-SSPは、選択変数によってアクティビティが選択され、イベント間の遷移が遷移関数Pによって制御されるイベントとアクティビティに基づいて、基礎となる状態-アクション空間とダイナミクスを抽象化する。
訳抜け防止モード: HC - SSPは根底にある状態 - アクション空間を抽象化する 活動が選択変数によって選択されるイベントやアクティビティに基づくダイナミクス イベント間の遷移は遷移関数 P によって制御される。 そして、そのサブ - ゴール で独自のアクション空間とダイナミクスを持っています。
0.81
Formally, an activity E ∈ E is a tuple (cid:104)ts E, te • ts • SE ⊂ S is a set of discrete states. 形式的には、アクティビティ E ∈ E はタプル(cid:104)ts E, te • ts • SE > S は離散状態の集合である。 0.81
• AE is a set of discrete actions. • AE は離散的な作用の集合である。 0.77
• TE : SE×AE×SE → [0, 1] is the state transition function, where TE(s, a, s(cid:48)) = P r(s(cid:48)|s, a) is the probability of being in state s(cid:48) after executing action a in state s. • TE : SE×AE×SE → [0, 1] は状態遷移関数であり、 TE(s, a, s(cid:48)) = P r(s(cid:48)|s, a) は状態 s の後に状態 s(cid:48) となる確率である。 0.84
E } is an indexed set of cost funcE, ..., C NE E : SE × AE × SE → R+ is the tions, where each C i i-th cost function that defines the i-th cost of executing action a in state s and resulting in state s(cid:48) and NE is the number of secondary cost functions for the activity E. E } はコストfuncE, ..., C NE E : SE × AE × SE → R+ のインデックス化された集合であり、各 C i 番目のコスト関数は状態 s におけるアクション a を実行する i 番目のコスト関数を定義し、状態 s(cid:48) と NE はアクティビティ E の二次コスト関数の数である。 0.90
• GE ⊂ SE is the set of goal state. GE > SE はゴール状態の集合である。 0.54
In this paper, we refer to the planning problem over the events and activities as procedural planning and the planning problem for each activity as activity planning, which will be discussed in more detail in Section IV-B. 本稿では,イベントや活動に関する計画問題を手続き的計画とみなし,各活動の計画問題を活動計画とみなし,第4節-B節でより詳細に論じる。 0.79
• (cid:126)CE = {C 0 • (cid:126)CE = {C 0 0.49
(cid:34) ∞(cid:88) (cid:34) ∞(cid:88) (cid:34) ∞(cid:88) (cid:34) ∞(cid:88) 0.38
t=0 (cid:35) t=0 (cid:35) 0.34
(cid:35) (cid:12)(cid:12)(cid :12)(cid:12)ΓI (cid:12)(cid:12)(cid :12)(cid:12)ΓI (cid:35) (cid:12)(cid:12)(cid :12)(cid:12)-I(cid:1 2)(cid:12)(cid:12)(c id:12)-I 0.37
C. Solution to HC-SSP C. HC-SSPへのソリューション 0.60
A solution to a HC-SSP problem is a tuple (cid:104)ρ, Γ(cid:105), where • ρ is a procedural policy which fully assigns every choice HC-SSP問題の解はタプル (cid:104)ρ, sh(cid:105) である。
訳抜け防止モード: HC-SSP問題の解は、タプル (cid:104)ρ, sh(cid:105 ) である。 ここで ρ はすべての選択を完全に割り当てる手続き的方針です
0.78
variable V. • Γ is a set of policies for every activated activity by ρ, where a policy ΓE : SE → AE is a mapping from states to actions for an activity E. Note that, abusing the notation, E ∈ ρ if an activity E ∈ E is activated by ρ, and E (cid:54)∈ ρ otherwise. 変数 v. • γ は ρ によるすべての活性化アクティビティのポリシーの集合であり、ポリシー γe : se → ae は状態からアクティビティのアクションへのマッピングである。
訳抜け防止モード: 変数 v. • γ は ρ によるすべての活性化アクティビティに対するポリシーの集合である。 ここでポリシー γe : se → ae は状態からアクティビティのアクションへのマッピングである。 表記を乱用する。 e ∈ ρ のとき 活性 e ∈ e は ρ によって活性化される。 そして e (cid:54) でなければ ρ である。
0.74
Then, an optimal solution to a HC-SSP is defined as follows: 次に、HC-SSPに対する最適解を次のように定義する。 0.63
(cid:1)(cid:105) (cid:1)(cid:105) 0.37
(cid:104) f E(cid:0)ΓE E for E ∈ ρ such that ts E = ts, E(cid:48) for E, E(cid:48) ∈ ρ such that te L(E|ρ) · gE ts E = ts, E(cid:48) for E, E(cid:48) ∈ ρ で te L(E|ρ) · gE であるような E ∈ ρ に対する f E(cid:0) = E(cid:48) 0.90
(cid:0)ΓE (cid:1) ≤ ∆j for j ∈ J, (cid:0)γe (cid:1) ≤j は j ∈ j に対して成立する。 0.45
E = ts Ij (E) E = ts Ij (複数形 Ijs) 0.51
(5) (6) E(cid:48), (7) (8) (5) (6)E(cid:48),(7)(8) 0.40
argmin ρ,Γ EE∼ρ s.t. I = ΓI ΓT E = ΓI アルグミン ρ,Γ EE ρ s.t. I = >I >T E = >I 0.38
(cid:88) E∈Ψj (cid:88) eψψj の略。 0.25
E and ΓT E are initial and termination distributions where ΓI of the policy ΓE for an activity E, respectively, L(E|ρ) is a likelihood of executing an activity E given procedural policy ρ, and f E(ΓE) is the expected primary cost for an activity E which is defined as follows: e と γt E は初期および終端分布であり、ここでは L(E|ρ) は与えられた手続き的方針 ρ のアクティビティ E を実行する確率であり、fE(は次のとおり定義されるアクティビティ E の期待プライマリコストである。
訳抜け防止モード: e と γt E は初期分布と終端分布であり、それぞれの活動 E に対するポリシー ρI は、それぞれ L(E|ρ ) は、手続き的方針 ρ が与えられたときのアクティビティ E を実行する確率である。 以下に定義するアクティビティEの期待プライマリコストは、fE(\E ) である。
0.70
f E(ΓE) = E E (複数形 Es) 0.48
C 0 E(st, at, st+1) c 0 である。 E(st, at, st+1) 0.50
E, ΓE E (複数形 Es) 0.35
, and gE activity E which is defined as follows: , gE アクティビティ E は次のように定義されます。 0.58
i (ΓE) is the expected i-th secondary cost for an i は a の予想 i 番目の二次コストである 0.62
i (ΓE) = E gE i (γe) = e ge 0.29
C i E(st, at, st+1) C i E(st, at, st+1) 0.45
E, ΓE E (複数形 Es) 0.35
. t=0 IV. APPROACH . t=0 iv。 アプローチ 0.41
In this section, we present our proposed approach for a HC-SSP. 本稿では,HC-SSPに対する提案手法を提案する。 0.73
We begin with an intuitive introduction of the approach and then present algorithms and formal analysis. まず、直感的なアプローチの導入から始め、アルゴリズムと形式解析を提示します。 0.72
A. Overview For the purpose of illustration, let us consider a simple problem shown in Fig 4a which has two activities and a single constraint including both activities. A.概要 図示のために、図4aに示す2つのアクティビティと2つのアクティビティを含む1つの制約を持つ単純な問題を考える。 0.79
Our approach is based on the fact that we can decouple the procedural and each activity planning problems if the constraint budget ∆ is allocated properly to each of the activities. 我々のアプローチは、制約予算 s が各アクティビティに適切に割り当てられている場合、手続きと各アクティビティ計画の問題を切り離すことができるという事実に基づいている。 0.72
Fig. 4b shows the constraint budget allocation space for the example problem, where x− and y−axes are the allocated budget for activities E1 and E2, respectively, and the green shaded region conceptually shows the region where a feasible solution to HC-SSP exists. 図4bは、x−とy−axがそれぞれアクティビティE1とE2の割り当て予算となる例問題に対する制約予算配分空間を示し、グリーンシェード領域は、HC-SSPに対する実現可能な解が存在する領域を概念的に示す。 0.74
Then if we allocate a specific budget to E1 and E2, respectively, then we can find policies for each activity based on the allocation, which in turn allows us to find procedural policy based on f and g values of each activity. そして、E1 と E2 にそれぞれ特定の予算を割り当てれば、割り当てに基づいて各アクティビティに対するポリシーを見つけることができ、それによって各アクティビティの f と g の値に基づいて手続き的なポリシーを見つけることができる。 0.76
However, since the allocation space is continuous, it is computationally intractable to check every possible budget allocation to find an optimal solution. しかし、割り当て空間は連続的であるため、可能な予算割り当てをすべてチェックして最適な解を見つけることは計算的に難解である。 0.61
Instead, we frame the allocation problem based on the branch-and-bound scheme [15], [16]. 代わりに、分岐とバウンドのスキーム [15], [16] に基づいてアロケーション問題をフレーム化する。 0.77
英語(論文から抽出)日本語訳スコア
(a) Example procedural planning problem with two activities. (a)二つの活動を伴う手続き計画問題の例 0.86
(b) Budget allocation space where x− and y− axes are allocated cost budget for E1 and E2. b) x−およびy−軸がE1及びE2のコスト予算に割り当てられる予算配分空間。 0.82
Fig. 4: Illustration of budget allocation for an example with only two activities and a single global constraint. 図4: たった2つの活動と1つのグローバル制約のある例に対する予算配分の図示。 0.83
Let M− E,Ij (E) and M + m を E,Ij (E) と M + 0.64
E,Ij (E) be lower and upper limits of budget allocation for a constraint Cj and an activity E ∈ Ψj. e,ij(e) は制約 cj とアクティビティ e ∈ ψj に対する予算割り当ての上限を低くする。 0.72
Then the allocation space that we are interested in, which we denote as Qinit, is defined as follows: そして、私たちが興味を持っている割り当て空間は、qinitと表記され、次のように定義されます。 0.67
Qinit = M− Qinit = M− 0.41
E,Ij (E), M + E,Ij (E), M + 0.38
E,Ij (E) E (複数形 Es) 0.51
(cid:89) (cid:89) (89年) (89年) 0.62
(cid:104) j∈J (cid:104) j・J 0.42
E∈Ψj (cid:105) eψψj の略。 (定員105名) 0.31
. 1 Note that a simple choice of such lower and upper limits for E ∈ Ψj is 0 and L(E) · ∆j, where L(E) is the minimum likelihood of activity E, although a more sophisticated bound can be found based on pre-processing. . 1 e ∈ ψj のそのような下限と上限の単純な選択は 0 であり、l(e) · sj であり、ここで l(e) は活動 e の最小確率である。
訳抜け防止モード: . 1 注意すべき点は、そのような E ∈ sj に対する下限と上限の単純な選択は 0 であり、L(E ) · sj である。 ただし、L(E) は E の最小の確率である。 より洗練された境界はpre-処理に基づいて見つけることができる。
0.51
Then the branch-andbound algorithm keeps splitting Qinit into smaller partitions and computes upper (α) and lower bounds (β) for the newly generated partitions, which can be used not only to guide the search toward an optimal solution but also to determine the quality of the current incumbent solution. 次に、分岐結合アルゴリズムは、Qinitをより小さな分割に分割し、新たに生成された分割に対して上(α)と下限(β)を演算し、探索を最適解へ導くだけでなく、現在の既存解の質を決定するためにも使用できる。 0.84
Algorithm 1 shows the branch-and-bound algorithm for a HC-SSP, where α(Q) and β(Q) denote upper and lower bounds for a partition Q, respectively, and αk and βk denotes global upper and lower bounds at the k-th iteration, respectively. アルゴリズム1はHC-SSPの分岐とバウンドのアルゴリズムを示し、α(Q) と β(Q) はそれぞれ分割 Q の上下境界を表し、αk と βk は k-次反復で大域上と下界を表す。 0.81
After initialization (lines 1–9), the algorithm splits a partition with the lowest lower bound into two partitions along its longest edge to form a new partition (lines 11–13). 初期化(ライン1〜9)後、アルゴリズムは最小のバウンドを持つパーティションを最短辺に沿って2つのパーティションに分割する(ライン11〜13)。 0.80
Then it computes lower and upper bounds for newly generated partitions (lines 14–19) and updates the global lower and upper bounds (lines 20–21). その後、新たに生成された分割(14–19行)の下位境界と上部境界を計算し、グローバルな下限と上部境界(20–21行)を更新する。 0.64
In addition, whenever a better feasible solution is found, it updates the incumbent solution (lines 4–6 and 16–18). さらに、より良い実現可能な解が見つかると、既存の解(4–6および16–18)を更新する。 0.71
The core parts of Algorithm 1 are Compute-LB and Compute-UB subroutines which highly affect the performance of the algorithm. アルゴリズム1の中核部はCompute-LBとCompute-UBのサブルーチンであり、アルゴリズムの性能に大きな影響を与える。 0.70
Before presenting the proposed Compute-LB and Compute-UB subroutines, let us begin with introducing procedural and activity planning in more detail, which has been briefly introduced in Section III-B. 提案するCompute-LBおよびCompute-UBサブルーチンを提示する前に,第III節-B節で紹介された手続き的および活動的計画についてより詳しく紹介することから始める。 0.71
B. Procedural and Activity Planning ロ.手続き及び活動計画 0.64
In this section, we define procedural planning and activity planning, and then show that both of the planning problems can be reduced to an instance of C-SSP. 本稿では,手続き的計画と活動計画を定義し,これらの問題をC-SSPの事例に還元できることを示す。 0.76
Let us begin with the definition of procedural planning. まずは手続き計画の定義から始めましょう。 0.62
Definition 1. (Procedural Planning) 定義1。 (手続き計画) 0.74
Suppose estimates for the primary and i-th secondary cost functions for every 1次とi次の各二次費用関数の見積もりを仮定する 0.64
Algorithm 1: Branch-and-Bound Input: HC-SSP instance H, initial budget allocation アルゴリズム1:ブランチ・アンド・バウンド入力:HC-SSPインスタンスH、初期予算割り当て 0.68
space Qinit, approximation parameter l, optimality tolerance  空間 Qinit, 近似パラメータ l, 最適性寛容 ... 0.69
1 k = 0 2 M0 = {Qinit} 3 α(Qinit),(cid:104)ρ0, Π0(cid:105) ← Compute-UB(H, Qinit, l) 4 if (cid:104)ρ0, Π0(cid:105) is not None then 1 k = 0 2 M0 = {Qinit} 3 α(Qinit), (cid:104)ρ0, .0(cid:105) , Compute-UB(H, Qinit, l) 4 if (cid:104)ρ0, .0(cid:105) はヌーンではない。
訳抜け防止モード: 1 k = 0 2 m0 = { qinit } 3 α(qinit),(cid:104)ρ0。 π0(cid:105 ) の計算 - ub(h, qinit, l ) 4 if ( cid:104)ρ0, π0(cid:105 ) は無でない
0.79
5 6 (cid:104)ρinc, Πinc(cid:105) ← (cid:104)ρ0, Π0(cid:105) αinc ← α(Qinit) 5 6 (cid:104)ρinc, πinc(cid:105) ] (cid:104)ρ0, π0(cid:105) αinc ] α(qinit) 0.39
11 12 7 β(Qinit) ← Compute-LB(H, Qinit, l) 8 α0 ← α(Qinit) 9 β0 ← β(Qinit) 10 while αk − βk >  do Qk ← argminQ∈Mk split Qk along one of its longest edges into Q(cid:48) and Q(cid:48)(cid:48) for Q ∈ {Q(cid:48) 11 12 Q ∈ {Q(cid:48) に対して Qk を Q(cid:48) と Q(cid:48)(cid:48) に分割し、Q ∈ {Q(cid:48) に対して Qk を Q(cid:48) と Q(cid:48)(cid:48) に分割する。 0.52
13 Mk+1 ←(cid:0)Mk\{Qk}(cid:1) ∪(cid:0)Q(cid:48) 13 Mk+1 >(cid:0)Mk\{Qk}(cid:1) >(cid:0)Q(cid:48) 0.38
k} do α(Q),(cid:104)ρ(cid:48), Π(cid:48)(cid:105) ← Compute-UB(H, Q, l) if α(Q) < αinc then k} do α(q),(cid:104)ρ(cid:48), π(cid:48)(cid:105) , compute-ub(h, q, l) if α(q) < αinc である。 0.79
k ∪ Q(cid:48)(cid:48) q(cid:48)(cid:48) である。 0.65
k,Q(cid:48)(cid:48) k,Q(cid:48)(cid:48) 0.42
β(Q) (cid:1) β(Q) (cid:1) 0.41
k k k (cid:104)ρinc, Πinc(cid:105) ← (cid:104)ρ(cid:48), Π(cid:48)(cid:105) αinc ← α(Q) k k k (cid:104)ρinc, πinc(cid:105) ] (cid:104)ρ(cid:48), π(cid:48)(cid:105) αinc ] α(q) 0.73
β(Q) ← Compute-LB(H, Q, l) β(q) を計算-lb(h, q, l) とする。 0.59
14 15 16 17 18 14 15 16 17 18 0.42
19 20 21 22 19 20 21 22 0.42
αk ← minQ∈Mk α(Q) βk ← minQ∈Mk β(Q) k ← k + 1 αk - ミンクギムク α(q) βk - ミンクギムク β(q) k - k + 1 0.59
23 return (cid:104)ρinc, Πinc(cid:105) 23 return (cid:104)ρinc, sinc (cid:105) 0.38
activity E ∈ E and i ∈ {1, . . . , NE} are given, where the former and the latter are denoted as ¯f E and ¯gE i , respectively. アクティビティ E ∈ E と i ∈ {1, . , . . , NE} が与えられ、前者および後者はそれぞれ sf E と sgE i と表記される。 0.71
Then we define planning for a procedural plan ρ based on the given estimates as procedural planning. 得られた推定値に基づいて手続き計画ρの計画を手続き計画として定義する。 0.79
Similarly, we define activity planning as follows. 同様に、アクティビティプランニングも次のように定義します。 0.56
Definition 2. (Activity Planning) 定義2。 (活動計画) 0.57
For E ∈ E, suppose the initial distribution, δ− i are given for i = 1, . . . , NE, where δ− i are lower and upper bounds on i-th cost function. e ∈ e に対して、初期分布 δ− i が i = 1, . . . , ne に対して与えられると仮定する。
訳抜け防止モード: E ∈ E について、初期分布を仮定すると、δ− i は i = 1, ... に対して与えられる。 NE, δ− i は i - th のコスト関数上界である。
0.83
Then we define planning for an activity E based on the given bounds as activity planning. 次に,与えられた範囲に基づいた活動Eの計画を活動計画として定義する。 0.75
i and δ+ i and δ+ i と δ+ i と δ+ 0.93
Now, we show that both procedural and activity planning さて 手続き計画と活動計画の両方が 0.57
are reducible to C-SSPs in the following theorem. 以下の定理で C-SSP に再帰可能である。 0.58
Theorem 1. Both procedural and activity planning can be reduced to an instance of C-SSP. 理論1。 手続き計画と活動計画の両方をc-sspのインスタンスに還元できる。 0.70
Proof Sketch. First, it is obvious that an activity planning is an instance of a C-SSP given initial distribution and bounds on the secondary cost functions. スケッチの証明。 まず、アクティビティプランニングが初期分布と二次コスト関数のバウンドを与えられたC-SSPのインスタンスであることは明らかである。 0.71
Now, given ¯f E and ¯gE i では、sf E と sgE i が与えられます。 0.37
for every E ∈ E and i ∈ {1, . . . , NE}, it can be shown that a procedural planning can be reduced to a C-SSP by matching each element as t∈T Dom{V(t)}, すべての e ∈ e と i ∈ {1, . , . , ne} に対して、手続き計画が各要素を tservlett dom{v(t)} と一致させることで c-ssp に還元できることを示すことができる。 0.86
follows: S = T , ¯s = I, G = {te}. 以下は S = T , s = I, G = {te} である。 0.78
A =(cid:83) A =(cid:83) 0.44
英語(論文から抽出)日本語訳スコア
T (t, a, t(cid:48)) = P(t, a, t(cid:48)), (cid:126)C = [C0, C1, . . . , CJ ], where E = t T (t, a, t(cid:48)) = P(t, a, t(cid:48)), (cid:126)C = [C0, C1, . . , CJ ] ここで E = t となる。 0.97
C0(t, a, t(cid:48)) = C0(t, a, t(cid:48)) = 0.48
E = t(cid:48), and te otherwise, E = t(cid:48) でなければte。 0.83
 ¯f E if ∃E ∈ E such that ts ¯gE ts {\displaystyle t} が e {\displaystyle e} であるとき、 ts {\displaystyle t} は e {\displaystyle e} である。 0.14
if ∃E ∈ E such that ts E = t(cid:48) and E ∈ Ψj, te otherwise, E が ts E = t(cid:48) であり、E ∈ sj がそうでなければ、 0.79
0 0 i and 0 0 私は そして 0.53
Cj(t, a, t(cid:48)) = Cj(t, a, t(cid:48)) = 0.49
E = t, e = t である。 0.59
i for every j ∈ J, and (cid:126)∆ = [∆1, . . . , ∆J ]. 私は すべての j ∈ J に対して、かつ (cid:126) = [, 1, . . . . . , . J ] に対して。 0.61
E ∈ E, and similarly, ¯g as a collection of ¯gE E ∈ E and i ∈ {1, . . . , NE}. E ∈ E, および同様に、i ∈ E ∈ E と i ∈ {1, . . . . . . , NE} の集合である。 0.85
Note that we denote ¯f as a collection of ¯f E for every for every 注意すべき点として、我々は、すべての点について sf E の集合として sf を表わす。 0.32
Finally, we provide algorithms for activity and procedural planning in Algorithm 2 and 3. 最後に、アルゴリズム2と3のアクティビティと手続き計画のためのアルゴリズムを提供する。 0.78
Both algorithms basically instantiate a C-SSP and solve it based on the anytime algorithm to produce lower and upper bounds along with the incumbent policy, as introduced in Section II-B. どちらのアルゴリズムも基本的にはC-SSPをインスタンス化し、第2節-B節で導入されたように、下限と上限を生成する任意のアルゴリズムに基づいて解決する。 0.63
The parameter l used in the algorithms governs the approximation level of the anytime algorithm by limiting the number of iterations for the second stage of the algorithm. アルゴリズムで使用されるパラメータ l は、アルゴリズムの第2段階の反復数を制限することにより、任意の時間アルゴリズムの近似レベルを規定する。 0.86
For example, if l = 0, then the algorithm returns a Lagrangian dual solution, and if l = ∞, then the algorithm runs until it converges and returns a true optimal solution. 例えば、l = 0 であれば、アルゴリズムはラグランジュ双対解を返し、l = ∞ ならば、アルゴリズムは収束して真の最適解を返す。
訳抜け防止モード: 例えば、l = 0 ならば、 アルゴリズムはラグランジアン双対解を返す。 l = ∞ ならば、アルゴリズムは収束して真の最適解を返すまで実行されます。
0.72
Algorithm 2: Activity-Planning Input: Activity E, partition Q, approximation 1 Instantiate a C-SSP based on E and Q 2 Run stage 1 of the anytime algorithm to produce アルゴリズム2: アクティビティプランニング入力: アクティビティe、パーティションq、近似1は、anytimeアルゴリズムのeとq2のステージ1に基づいてc-sspをインスタンス化して生成する。
訳抜け防止モード: アルゴリズム2 : アクティビティ - プランニング入力 : アクティビティE, パーティションQ, 近似 1 E と Q 2 に基づいた C - SSP を任意のアルゴリズムの実行ステージ 1 にインストールして生成する
0.77
parameter l LB, U B and πinc パラメータl lb, u b, πinc 0.55
3 if l > 0 then 4 3 > l > 0 ならば 4 である。 0.69
5 return πinc, LB, U B 5 は πinc, LB, UB を返す 0.77
Run stage 2 of the anytime algorithm for l-iterations to update LB, U B and πinc lb, u b, πinc更新のためのl-イテレーションのためのanytimeアルゴリズムのステージ2 0.69
Algorithm 3: Procedural-Planning Input: HC-SSP problem instance H, primary cost アルゴリズム3:手続き計画入力:hc-ssp問題インスタンスh,プライマリコスト 0.82
estimate ¯f, secondary cost estimate ¯g, approximation parameter l 推定値 ^f, 二次コスト推定値 ^g, 近似パラメータ l 0.71
1 Instantiate a C-SSP based on H, ¯f and ¯g 2 Run stage 1 of the anytime algorithm to produce 1anytimeアルゴリズムのh,f,g2ステージ1に基づいてc-sspをインスタンス化し、生成する。
訳抜け防止モード: 1 C-SSPのH, sfに基づく確立 生成する任意のアルゴリズムのステージ1を実行します。
0.79
LB, U B and πinc lb, u b, πinc 0.35
3 if l > 0 then 4 3 > l > 0 ならば 4 である。 0.69
Run stage 2 of the anytime algorithm for l-iterations to update LB, U B and πinc lb, u b, πinc更新のためのl-イテレーションのためのanytimeアルゴリズムのステージ2 0.69
5 return πinc, LB, U B 5 は πinc, LB, UB を返す 0.77
C. Computing Lower and Upper Bounds c.下限と上限の計算 0.71
In this section, we provide methods for computing lower and upper bounds on the optimum of a HC-SSP given a partition Q, which are used as subroutines in Algorithm 1. 本稿では,アルゴリズム1のサブルーチンとして使用される分割Qを与えられたHC-SSPの最適値の下位値と上位値の計算方法を提案する。 0.82
Algorithm 4 shows Compute-LB subroutine, where Q− E,i denotes a lower limit of the i-th secondary cost for an activity E defined by a partition Q ⊂ Qinit. アルゴリズム4はCompute-LBサブルーチンを示し、Q−E,iはパーティションQ,Qinitで定義されるアクティビティEのi番目の二次コストの低い極限を表す。 0.74
Given a partition Q and an approximation parameter l, Algorithm 4 performs the activity planning for each activity in a topological order so that the flow constraints in Eqs. アルゴリズム4は、分割Qと近似パラメータlを与えられた後、トポロジカルな順序で各アクティビティのアクティビティ計画を行い、Eqs内のフロー制約を行う。 0.77
(6) and (7) are satisfied. (6)及び(7)を満足させる。 0.78
To obtain a lower bound, the primary cost of each activity is estimated as a lower bound (φ− E) computed from Algorithm 2. 下限を得るには、各アクティビティの一次コストをアルゴリズム2から計算された下限(φ−E)として推定する。 0.79
In addition, the secondary cost of each activity is estimated as a lower limit of the given partition. さらに、各アクティビティの二次コストを、所定のパーティションの低い限度として推定する。 0.68
Similarly, Algorithm 5 shows Compute-UB subroutine. 同様に、アルゴリズム5はCompute-UBサブルーチンを示す。 0.65
Different from Compute-LB, Algorithm 5 estimates the primary cost of each activity based on an upper bound (φ+ E) computed from Algorithm 2, which is the associated expected primary cost of the incumbent solution. Compute-LBと異なり、アルゴリズム5はアルゴリズム2から計算された上限(φ+E)に基づいて各アクティビティの一次コストを推定する。
訳抜け防止モード: Compute - LBと異なり、アルゴリズム5はアルゴリズム2から計算された上界(φ+E)に基づいて各アクティビティの一次コストを推定する。 これは既存のソリューションの 予想される第一コストです
0.82
In addition, the secondary cost is estimated as the expected secondary cost of the corresponding incumbent solution. さらに、二次コストを、対応する既存溶液の予想二次コストとして推定する。 0.72
Finally, Algorithm 5 collects policies for each activity to form a solution to the HC-SSP. 最後に、アルゴリズム5は各アクティビティのポリシーを収集し、HC-SSPのソリューションを形成する。 0.66
The following theorem formally shows that both Algorithm 4 and 5 correctly compute lower and upper bounds. 次の定理は、アルゴリズム 4 と 5 の両方が下界と上界を正しく計算していることを示している。 0.65
Theorem 2. Algorithm 4 computes a lower bound on the optimum to the given HC-SSP within the given partition Q. Similarly, Algorithm 5 computes an upper bound on the optimum to the given HC-SSP within the given partition Q. Proof Sketch. 定理2。 アルゴリズム4は、与えられた分割Q内のHC-SSPに対する最適値の上限を演算し、同様に、アルゴリズム5は与えられた分割Q内のHC-SSPに対する最適値の上限を計算する。 0.67
First, Algorithm 4 computes lower bounds on the optimal expected primary cost of each activity given the secondary cost bounds by Q and uses them as cost estimates (lines 2 and 3). まず、アルゴリズム4は、qによる二次コスト境界が与えられた各アクティビティの最適な一次コストの下限を計算し、コスト見積として使用する(ライン2、ライン3)。 0.69
In addition, the algorithm uses lower limits of the given partition Q as the secondary cost estimates (line 5). さらに、アルゴリズムは、与えられた分割Qの低い限界を二次コスト推定として使用する(ライン5)。 0.80
Let ρ∗ and Γ∗ E be optimal procedural and activity policies in Q. Let also Φ− be the lower bound provided by Algorithm 4. Q において ρ∗ と ρ∗ E を最適な手続き的および活動的ポリシーとする。 0.43
Then (cid:104) そして (cid:104) 0.56
f E(cid:0)Γ∗ f E(cid:0) =∗ 0.44
E (cid:1)(cid:105) ≥ EE∼ρ∗(cid:2) ¯f E(cid:3) ≥ Φ−, へえ (cid:1)(cid:105) ≥ ee ρ∗(cid:2) かつ f e(cid:3) ≥ φ− である。 0.57
EE∼ρ∗ where the first inequality is based on the fact that ¯f and ¯g underestimate the cost functions, and the second inequality comes from the fact that the anytime algorithm used for a procedural planning gives a lower bound with any l. 台頭ρ∗ 第1の不等式がコスト関数を過小評価するという事実に基づく場合、第2の不等式は手続き計画に使用される時間アルゴリズムが任意の l に対して下限を与えるという事実から生じる。 0.45
For Algorithm 5, it is easy to see that an upper bound is based on a feasible solution if one has been found, or infinity otherwise, which is obviously an upper bound on the optimum within the partition Q. アルゴリズム5では、上界が、分割 Q 内の最適値上の上界であるような無限大が発見された場合、実現可能な解に基づいていることが容易に分かる。
訳抜け防止モード: アルゴリズム5では、上界が実現可能な解に基づいていることが分かりやすい。 1つが発見されました あるいは無限大の場合、これは明らかに分割 Q 内の最適値の上界である。
0.73
D. Convergence D. Convergence 0.44
Now, we show that Algorithm 1 is convergent, i.e., for every  > 0, αk − βk <  is satisfied within finite iterations given a certain condition. さて、アルゴリズム 1 が収束していること、すなわち、すべての s > 0 に対して、ある条件が与えられた有限の反復の中で αk − βk < s が満たされることを示す。 0.63
For this, we leverage a convergence analysis in [15] which showed that the branch-and-bound algorithm is convergent if the following two conditions are satisfied: (R1) β(Q) ≤ f∗(Q) ≤ α(Q). このために、[15] の収束解析を利用して、次の 2 つの条件が満たされるとき、分岐とバウンドのアルゴリズムが収束することを示した: (R1) β(Q) ≤ f∗(Q) ≤ α(Q) である。 0.83
In other words, the functions Compute-LB and Compute-UB compute lower and upper bounds on f∗(Q), respectively, where f∗(Q) is the optimum within partition Q. 言い換えれば、関数 Compute-LB と Compute-UB はそれぞれ f∗(Q) 上の下界と上界を計算し、ここで f∗(Q) は分割 Q 内の最適値である。 0.82
英語(論文から抽出)日本語訳スコア
Algorithm 4: Compute-LB Input: HC-SSP problem instance H, partition Q, 1 for E ∈ E in a topological order do 2 3 アルゴリズム 4: Compute-LB入力:HC-SSP問題インスタンス H, partition Q, 1 for E ∈ E in a topological order do 2 3 0.92
E ← Activity-Planning(E, Q, l) E > アクティビティ・プランニング(E,Q,l) 0.67
approximation parameter l ΓE, φ− E, φ+ ¯f E ← φ− 近似パラメータ l γe, φ− e, φ+ は φ− である。 0.72
4 for j ∈ J and E ∈ Ψj do 4 は j ∈ j と e ∈ ψj do である。 0.80
E ← Q− ¯gE Ij へえ q-の略。 Ij (複数形 Ijs) 0.34
5 6 ρ, Φ−, Φ+ ← Procedural-Planning( H, ¯f , ¯g, l) 7 return Φ− 5 6 ρ, t−, t−, t+ > Procedural-Planning( H, tf , tg, l) 7 は t− を返す。 0.64
E,Ij (E) E (複数形 Es) 0.51
approximation parameter l Algorithm 5: Compute-UB Input: HC-SSP instance H, partition Q, 1 Γ = {} 2 for E ∈ E in a topological order do 3 4 5 近似パラメータ l アルゴリズム 5: Compute-UB 入力: HC-SSP インスタンス H, partition Q, 1 s = {} 2 for E ∈ E in a topological order do 3 4 5 0.84
ΓE, φ− E, φ+ ¯f E ← φ+ Γ ← Γ ∪ {ΓE} γe, φ− e, φ+ が成立する。 0.46
E ← Activity-Planning(E, Q, l) E > アクティビティ・プランニング(E,Q,l) 0.67
E 6 for j ∈ J and E ∈ Ψj do へえ 6 を j ∈ J とし、E ∈ sj do とする。 0.63
← gE ¯gE Ij ~gE Ij (複数形 Ijs) 0.23
(ΓE) Ij 7 8 ρ, Φ−, Φ+ ← Procedural-Planning( H, ¯f , ¯g, l) 9 if ρ is None then 10 11 else 12 (おえ) Ij ρ が None なら 10 11 以外の 12 なら 7 8 ρ, y , y , y , y , y , y ) 9 である。
訳抜け防止モード: (おえ) Ij 7 8 ρ, ~−, ~+ ~ 手続き的 - 計画的(H, ) ρ が None ならば 10 11 の他の 12 が成り立つ。
0.48
return ∞, None return Φ+, (cid:104)ρ, Γ(cid:105) ∞ を返し、None は >+, (cid:104)ρ, >(cid:105) 0.75
(R2) Let |Q| be the maximum half-length of the sides of Q. Then, as |Q| goes to zero, αk−βk uniformly converges to zero, i.e., for every  > 0, there exist δ > 0 such that α(Q) − β(Q) <  for every Q ⊂ Qinit with |Q| ≤ δ. (R2) Q| を Q の辺の最大半長さとすると、|Q| は 0 に一様収束するので、αk−βk は 0 に一様収束する。
訳抜け防止モード: (R2) Q| を Q の辺の最大半分の長さとする。 Q| が 0 になるとき、αk−βk は一様収束する。 すなわち、すべての δ > 0 に対して α(Q) となる δ > 0 が存在する。 ) − β(Q ) < > |Q| ≤ δ {\displaystyle |Q|\init} である。
0.65
Note that we already showed that (R1) is satisfied in Theorem すでに (R1) が Theorem で満足していることを示していたことに注意。 0.65
2. Now we conclude that Algorithm 1 is convergent under a certain condition by the following theorem. 2. アルゴリズム1は、次の定理により、ある条件下で収束する。
訳抜け防止モード: 2 では、結論を下す。 アルゴリズム1は次の定理によりある条件下で収束する。
0.69
Theorem 3. Suppose we use l = ∞ for Algorithm 定理 3. アルゴリズムに l = ∞ を用いるとする。 0.75
4. Then Algorithm 1 satisfies (R2). 4. アルゴリズム1は(R2)を満たす。 0.80
Proof Sketch. First, recall that there is only a finite number of feasible solutions to a HC-SSP since we only consider deterministic policies. スケッチの証明。 まず、決定論的なポリシーのみを考えるため、HC-SSPに対して可能な解は有限であるということを思い出す。 0.61
Let the budget allocation space Qinit has the dimension of n. 予算割り当て空間 qinit は n の次元を持つ。 0.57
Also, let Y be a set of solutions to a HC-SSP, and Z be a set of budget allocation points in Qinit correspond to Y . また、Y を HC-SSP の解の集合とし、Z を Qinit の Y に対応する予算割り当て点の集合とする。 0.68
Then there exist  > 0 such that B(z, ) is disjoint for every z ∈ Z, where B(x, r) is an open ball at x with radius r, which implies that ||z1 − z2||2 > 2 for every √ n||x − y||∞ ≥ ||x − z1, z2 ∈ Z. Then given the fact that y||2, we know that ||z1 − z2||∞ > 2√ n for every z1, z2 ∈ Z. n for some Q ⊂ Qinit. ここで、b(x, r) は半径 r の x における開球であるので、すべての n||x − y|∞ ≥ ||x − z1, z2 ∈ z に対して ||z1 − z2||∞ > 2 となる。
訳抜け防止モード: すると、すべての z ∈ Z に対して B(z, s ) が非随伴であるような > 0 が存在する。 ここで B(x, r ) は半径 r の x における開球である。 つまり、すべての y n||x − y||∞ ≥ ||x − z1 に対して ||z1 − z2||2 > 2 となる。 そして y||2 の事実を仮定すると、||z1 − z2||∞ > 2 が分かる。 任意の z1, z2 ∈ Z. n に対して、ある Q は Qinit である。
0.74
Then at most a single point in Z is in Q. Suppose z ∈ Q ∩ Z and z corresponds to a feasible solution. すると、Z の少なくとも1つの点が Q に含まれる: z ∈ Q > Z と z は実現可能な解に対応するとする。 0.72
Then the upper bound computed from Algorithm 5 is the value of a feasible solution, which corresponds to z. 次に、アルゴリズム5から計算された上限は、zに対応する実現可能な解の値である。 0.67
Otherwise, i.e., if z corresponds さもなくば z が対応するなら 0.64
Now, suppose |Q| ≤ 2√ さて |Q| ≤ 2 とする。 0.71
to an infeasible solution or Q∩ Z = ∅, then the upper bound is ∞. 実現不可能な解や Q = Z = s に対して、上界は ∞ である。 0.71
For each solution y ∈ Y , let ηy > 0 be the maximum error in any estimate of ¯g that does not affect the feasibility of the solution y. それぞれの解 y ∈ Y に対して、ηy > 0 を解 y の実現可能性に影響を及ぼさない任意の yg の推定における最大誤差とする。 0.75
Then, let η = maxy∈Y ηy. すると、η = maxy~Y ηy とする。 0.52
Now, let δ = n , η} and |Q| ≤ δ for some Q ⊂ Qinit. ここで δ = n , η} および |Q| ≤ δ とする。 0.61
Again, at min{ 2√ most a single point in Z is in Q. Suppose z ∈ Q ∩ Z and z corresponds to a feasible solution. 繰り返しになるが、 min{ 2> において、Z のほとんどの単一点は Q に含まれる。
訳抜け防止モード: 再び、Z の最も単一の点は Q である。 z ∈ Q , Z および z は実現可能な解に対応する。
0.63
Since l = ∞, the lower bounds computed from activity plannings in Algorithm 4 (line 3) are exact, and thus the lower bound is equal to the value of the corresponding feasible solution. l = ∞ であるため、アルゴリズム 4 (ライン3) のアクティビティ計画から計算された下界は完全であり、従って下界は対応する実現可能な解の値と等しい。 0.74
Otherwise, i.e., if z corresponds to an infeasible solution or Q∩ Z = ∅, then the lower bound is ∞. さもなくば、すなわち、z が実現不可能な解あるいは Q = Z = ∞ に対応するなら、下界は ∞ である。 0.74
Therefore, for any Q ⊂ Qinit with |Q| ≤ δ, α(Q) − β(Q) = 0. したがって、|Q| ≤ δ の任意の Q > Qinit に対して α(Q) − β(Q) = 0 となる。 0.85
Note that although l = ∞ is required for the optimality, running the anytime algorithm until its convergence for every iteration can be computationally intractable. 最適性には l = ∞ が必要であるが、全ての反復に対して収束するまでの時間アルゴリズムの実行は計算的に難解である。 0.81
Therefore, in practice, we can use small l to balance the level of approximation. したがって、実際には、近似のバランスをとるために小さな l を用いることができる。 0.66
In Section V, we show that even with l = 0, the algorithm finds near-optimal solutions in most cases. セクション v において、l = 0 であっても、アルゴリズムは大抵の場合、最適に近い解を見つける。 0.67
V. EMPIRICAL EVALUATION We begin this section with details of the evaluation scenario and then we provide the evaluation results to demonstrate the performance of the proposed method. v. 実証的評価 本項目では,評価シナリオの詳細から開始し,提案手法の性能を示す評価結果を提供する。 0.60
A. Evaluation Scenario We test our algorithm with the evacuation problem shown in Fig 2. A. 評価シナリオ 図2に示す避難問題を用いて,本アルゴリズムを検証した。 0.75
In this problem, navigating between adjacent landmarks comprises a set of activities, where landmarks include initial position, exit position, doors and hallways. この問題では、隣接するランドマーク間のナビゲートには、最初の位置、出口位置、ドア、廊下を含む一連の活動が含まれている。 0.55
As mentioned in Section III-A, every hallway is known to be clear, but each door can be locked with a 0.1 probability. 第III節-A節で述べたように、すべての廊下は明確であることが知られているが、それぞれのドアは0.1の確率でロックできる。
訳抜け防止モード: 第3節 - A, すべての廊下は明確であることが知られています それぞれのドアは0.1の確率でロックできます
0.72
Then, each room is modeled as a grid world and each activity is defined over a corresponding room. そして、各部屋をグリッドワールドとしてモデル化し、各アクティビティを対応する部屋上で定義する。 0.71
For each activity, there is one action for each cardinal direction, with a 0.85 probability of correct movement, and a 0.075 probability of +90 or -90 degrees deviation from the intended movement. 各活動には、各基数方向に対して1つの作用があり、正しい動きの確率は 0.85 であり、意図された動きから 0.075 の確率は +90 または -90 度ずれている。
訳抜け防止モード: 各活動には、各基数方向に対して1つの作用がある。 正しい動きの確率は 0.85 で、0.075 の確率は +90 または -90 である。
0.81
The robot stays at the same state if it bumps into walls, which are boundaries of the grid world. ロボットは、グリッドの世界の境界である壁にぶつかっても、同じ状態にとどまります。 0.70
In addition, there are hazardous states which cause the 50 numerical damage to the robot. さらに、ロボットに50の数値的なダメージを与える有害な状態が存在する。 0.76
Then the primary objective is to evacuate as fast as possible while the constraint is to keep the damage level below the given threshold ∆. 次に、主な目的はできるだけ早く避難することであり、一方、制約は与えられた閾値より低いダメージレベルを維持することである。 0.53
More details of the scenario and the source code can be found at https://github.com/s k5050/HCSSP. シナリオとソースコードの詳細はhttps://github.com/s k5050/HCSSPで確認できる。 0.75
B. Evaluation Results We evaluate the proposed method with the state-of-theart MILP-based method [17], [18]. B. 評価結果 提案手法を最先端milp法[17],[18]を用いて評価した。 0.69
The benchmark MILP method first aggregates the rooms in Fig 2, which results in a single grid world with the additional open action next to the doors. ベンチマークmilp法は、最初にfig 2の部屋を集約し、ドアの横に追加のオープンアクションを持つ単一のグリッドワールドを生成する。 0.56
Note that the total number of states in the aggregated problem is 18644. 総合問題における状態の総数は18644である。 0.58
Then the evacuation problem is encoded as a MILP formulation and then solved using Gurobi 9. その後、避難問題はmilpの定式化としてコード化され、gurobi 9で解決される。 0.59
For more details about the encoding, please refer to [17], [18]. エンコーディングの詳細については、[17], [18]を参照してください。 0.76
英語(論文から抽出)日本語訳スコア
The proposed algorithm was implemented in Python 3, and all of the algorithms were executed on an Intel core i57200U with 8GB of RAM. 提案アルゴリズムはPython 3で実装され、全てのアルゴリズムはIntelのコアi57200Uと8GBのRAMで実行された。 0.84
In addition, the approximation parameter l for the algorithm was set as 0 throughout the experiments. さらに、アルゴリズムの近似パラメータ l を実験全体を通して 0 として設定した。 0.87
Finally, we used simple Euclidean distance and 0 for the primary and secondary cost heuristics, respectively, for the anytime algorithm. 最後に, 単純ユークリッド距離を1次および2次コストヒューリスティックスにそれぞれ0, を任意のアルゴリズムに使用した。 0.72
Table I summarizes the evaluation results. 表 i 評価結果を要約します。 0.70
We evaluated both MILP-based and the proposed method for different levels of ∆’s, which is shown in the first column of the table. 表の第1列に示すように,MILP ベースと提案手法の双方を異なるレベルに評価した。
訳抜け防止モード: 実験では,MILP-ベースと提案手法の双方を,異なるレベルで評価した。 表の最初の列に示されています
0.76
For each case, we show the results for both the proposed algorithm and MILP-based baseline method. いずれの場合においても,提案手法とmilpに基づくベースライン法の両方の結果を示す。 0.72
For the baseline method, optimal objective and computation time in seconds are reported. ベースライン法では、最適な目的と計算時間を秒単位で報告する。 0.71
The computation time includes both time for MILP encoding and the Gurobi solving time. 計算時間は、milp符号化の時間と、gurobi解決時間との両方を含む。 0.64
Similarly, for the proposed method, the optimality gap of the solution and the computation time are presented. 同様に,提案手法では解の最適性ギャップと計算時間について述べる。 0.69
To show the anytime history, three different solutions are reported, at the time when 10%, 20% and 50% of the computation time has been spent compared to the computation time spent by the MILP-based method. 計算時間の10%,20%,50%がmilp法で費やされた計算時間と比べ,計算時間の10%,20%,50%が費やされた時点で3つの異なる解が報告されている。 0.59
We left the cell with a hyphen if no feasible solution has been found at the corresponding time bound. 対応する時間帯に実現可能な溶液が見つからなかった場合は, ハイフンで細胞を切除した。 0.66
∆ 0.01 0.1 1 2 5 8 10 ∆ 0.01 0.1 1 2 5 8 10 0.41
MILP Opt obj 145.71 145.64 145.11 144.70 143.48 142.68 142.18 MILPオプト obj 145.71 145.64 145.11 144.70 143.48 142.68 142.18 0.30
time 404.95 203.35 211.27 127.31 143.48 135.75 336.44 time 404.95 203.35 211.27 127.31 143.48 135.75 336.44 0.23
10% gap time 0.00% 25.770.04% 21.88 10% ギャップタイム 0.00% 25.770.04% 21.88 0.48
- Proposed method 20% - 提案方法 20% 0.41
gap time 0.00% 25.77 0.05% 24.27 0.07% 39.20 0.35% 21.95 1.19% 21.85 1.74% 21.56 0.04% 21.88 gap time 0.00% 25.77 0.05% 24.27 0.07% 39.20 0.35% 21.95 1.19% 21.85 1.74% 21.56 0.04% 21.88 0.27
50% gap time 0.00% 25.77 0.05% 24.27 0.07% 39.20 0.35% 38.05 1.19% 21.85 0.45% 27.69 0.04% 21.88 50% gap time 0.00% 25.77 0.05% 24.27 0.07% 39.20 0.35% 38.05 1.19% 21.85 0.45% 27.69 0.04% 21.88 0.35
TABLE I: Evaluation results of the evacuation scenario. TABLE I:避難シナリオの評価結果。 0.58
As shown in the table, the proposed method could obtain a feasible solution within 20% of the computation time compared to the MILP-based method. 表に示すように,提案手法はMILP法と比較して計算時間の20%以内で実現可能な解が得られる。 0.77
This result highlights the value of the proposed method in the practical domains where obtaining a safe policy is extremely important given highly limited planning time. この結果から,安全政策の獲得が極めて重要であり,計画時間が非常に限られている分野において,提案手法の価値が強調された。 0.72
Even further, it is interesting to note that the proposed method could obtain < 1% of the optimality gap with less than half of the computation time compared to the MILP-based method except for one problem instance. さらに,提案手法は1つの問題インスタンスを除くMILP法と比較して計算時間の半分以下で最適性ギャップの1%以下が得られることに注意が必要である。 0.74
In addition, the algorithm could obtain < 0.1% of the optimality gap for 5 out of 7 cases with only up to 20% of the baseline computation time. さらに,本アルゴリズムは,最大20%の計算時間しか持たない7例中5例において,最適性ギャップの0.1%を得ることができた。 0.85
The worst case still only has 1.19% of the optimality gap with 20% of the baseline computation time. 最悪のケースは、まだ1.19%の最適性ギャップしか持たず、ベースライン計算時間の20%しか持たない。 0.65
This result shows that the proposed algorithm is able to not only find a feasible solution faster than the non-hierarchical method, but also obtain nearoptimal solutions even with small approximation parameter l and simple heuristics. この結果から,提案アルゴリズムは非階層的手法よりも高速に実現可能な解を見つけるだけでなく,小さな近似パラメータ l と単純なヒューリスティックスを用いても近似解が得られることがわかった。 0.83
VI. CONCLUSION In this paper, we propose a hierarchical constrained stochastic shortest path problem (HC-SSP) that extends CSSP to a hierarchical structure. VI。 結論 本稿では,CSSPを階層構造に拡張する階層的制約付き確率的最短経路問題(HC-SSP)を提案する。 0.70
Then we present a branchand-bound based algorithm with a notion of cost budget 次に,コスト予算の概念を用いた分岐結合型アルゴリズムを提案する。 0.72
allocation. Although the algorithm is proved to be optimal, the true value of the algorithm is its anytime property with high convergence rate to a near-optimal solution even with high approximation level. 割り当て。 アルゴリズムは最適であることが証明されているが、アルゴリズムの真の価値は、高い近似レベルであっても、その収束率の高い時限性である。 0.70
We demonstrate the advantage of the proposed algorithm compared to a MILP-based method in an evacuation scenario, yielding 2–5 times speed-ups with less than 1.2% of the optimality gaps. 避難シナリオにおけるMILP法と比較して,提案アルゴリズムの利点を実証し,最適性ギャップの1.2%以下で2~5倍の高速化を実現する。 0.77
Future work includes more comprehensive experiments in various problem domains. 今後の研究には、様々な問題領域におけるより包括的な実験が含まれる。 0.41
Another promising future work is allowing a nested hierarchical structure in the problem. もう1つの有望な将来的な仕事は、問題にネストした階層構造を可能にすることである。 0.45
REFERENCES [1] D. Ernst, M. Glavic, and L. Wehenkel, “Power systems stability learning framework,” IEEE transactions on 参考 [1] D. Ernst, M. Glavic, L. Wehenkel, “Power System stability learning framework”, IEEETransaction on
訳抜け防止モード: 参考 [1 ]D.Ernst,M.Glavic,L.W ehenkel 『電力系統安定学習フレームワーク』、IEEEトランザクション
0.50
control: reinforcement power systems, vol. 制御:強化型電力システム、vol.1。 0.72
19, no. 1, pp. 427–435, 2004. 19.1、p.427-435、2004。 0.65
[2] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al , “Mastering the game of go without human knowledge,” nature, vol. [2] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al , “Mastering the go of go without human knowledge”, nature, vol。
訳抜け防止モード: D. Silver, J. Schrittwieser, K. Simonyan, I.Antonoglou, A. Huang, A. Guez, T. Hubert L. Baker, M. Lai, A. Bolton, et al 「人間の知識なしに囲碁をマスターする」 自然、vol。
0.84
550, no. 7676, pp. 354–359, 2017. 550, no. 7676, pp. 354-359, 2017 頁。 0.82
[3] A. R. Cassandra, “A survey of POMDP applications,” in Working notes of AAAI 1998 fall symposium on planning with partially observable Markov decision processes, vol. AAAI 1998 fall symposium on planning with partial observable Markov decision process, vol.[3] A. R. Cassandra, “A survey of POMDP applications”. AAAI 1998 fall symposium on planning with partial observable Markov decision process, 0.42
1724, 1998. 1724, 1998. 0.43
[4] R. S. Sutton, D. Precup, and S. Singh, “Between mdps and semi-mdps: learning,” [4]R.S. Sutton,D. Precup,S. Singh, “Between mdps and semi-mdps: Learning” 0.47
A framework for temporal abstraction in reinforcement Artificial intelligence, vol. 強化型人工知能における時間的抽象化の枠組み, vol. 0.75
112, no. 1-2, pp. 181–211, 1999. 112, No. 1-2, pp. 181-211, 1999。 0.83
[5] G. Theocharous and L. P. Kaelbling, “Approximate planning in information 5] theocharous と l. p. kaelbling 著「情報における概略計画」 0.79
pomdps with macro-actions,” in Advances in neural processing systems, 2004, pp. 775–782. pomdps with macro-actions” in advances in neural processing systems, 2004, pp. 775-782。 0.46
[6] Z. Lim, L. Sun, and D. Hsu, “Monte carlo value iteration with macroactions,” in Advances in Neural Information Processing Systems, 2011, pp. 1287–1295. 6] z. lim, l. sun, d. hsu, “monte carlo value iteration with macroactions” in advances in neural information processing systems, 2011, pp. 1287–1295. (英語)
訳抜け防止モード: [6 ]Z.Lim、L.Sun、D.Hsu ニューラル情報処理システムにおける「マクロアクションによるモンテカルロ値の反復」 2011 , pp . 1287–1295 .
0.70
[7] S. Omidshafiei, A. [7]S. Omidshafiei, A. 0.46
-A. Agha-Mohammadi, C. Amato, S. -A。 Agha-Mohammadi, C. Amato, S。 0.41
-Y. Liu, J. P. How, and J. Vian, “Decentralized control of multi-robot partially observable markov decision processes using belief space macro-actions,” The International Journal of Robotics Research, vol. -y。 Liu, J. P. How, そしてJ. Vianは、“信念空間のマクロアクションを使って、マルチロボットの分散制御を部分的に観測可能なマルコフ決定プロセスで行う”。 0.53
36, no. 2, pp. 231–258, 2017. 36, no. 2, pp. 231–258, 2017 頁。 0.43
[8] C. Amato, G. D. Konidaris, and L. P. Kaelbling, “Planning with macro- C. Amato, G. D. Konidaris, L. P. Kaelbling, “Planning with macro-” 0.40
actions in decentralized pomdps,” 2014. 2014年、「分散pomdpsにおける行動」。 0.43
[9] E. Altman, Constrained Markov decision processes. 9] e・アルトマン マルコフ決定過程の制約です 0.55
CRC Press, 1999, CRCプレス、1999年。 0.86
vol. 7. [10] S. Feyzabadi and S. Carpin, “Hcmdp: a hierarchical solution to constrained markov decision processes,” in 2015 IEEE International Conference on Robotics and Automation (ICRA). vol.1。 7. 10] s. feyzabadi氏とs. carpin氏は2015年のieee international conference on robotics and automation (icra)で,“hcmdp: a hierarchical solution to constraintsed markov decision processes”と題した講演を行った。 0.52
IEEE, 2015, pp. 3971–3978. IEEE, 2015, pp. 3971-3978。 0.42
[11] F. Trevizan, S. Thi´ebaux, P. Santana, and B. Williams, “Heuristic search in dual space for constrained stochastic shortest path problems,” in Twenty-Sixth International Conference on Automated Planning and Scheduling, 2016. 11] f. trevizan, s. thi ́ebaux, p. santana, b. williams, “heuristic search in dual space for constraintsed stochastic shortest path problems” (2016年) 第26回自動計画・スケジューリング国際会議 (international conference on automated planning and scheduling) で発表された。
訳抜け防止モード: F. Trevizan, S. Thi ́ebaux, P. Santana, B. Williamsは曰く、“制約付き確率的最短経路問題の二重空間におけるヒューリスティック検索”。 In Twenty - Sixth International Conference on Automated Planning and Scheduling, 2016
0.83
[12] E. A. Feinberg, “Constrained discounted markov decision processes and hamiltonian cycles,” Mathematics of Operations Research, vol. 12] e. a. feinberg, “constrained discounted markov decision processes and hamiltonian cycles” ^ mathematics of operations research, vol. (英語)
訳抜け防止モード: 12 ] e. a. feinberg, “制約付き割引マルコフ決定過程とハミルトニアンサイクル” オペレーション・リサーチの数学。
0.67
25, no. 1, pp. 130–140, 2000. 25, No. 1, pp. 130–140, 2000。 0.93
[13] S. Hong, S. U. Lee, X. Huang, M. Khonji, R. Alyassi, and B. C. Williams, “An anytime algorithm for chance constrained stochastic shortest path problems and its application to aircraft routing,” in 2021 IEEE International Conference on Robotics and Automation (ICRA). S. Hong, S. U. Lee, X. Huang, M. Khonji, R. Alyassi, and B. C. Williamsは2021年のIEEE International Conference on Robotics and Automation(ICRA)で、“確率制約付き確率的最短経路問題とその航空機のルーティングへの応用のためのアルゴリズム”と評している。 0.80
IEEE, 2021, pp. 475–481. ieee, 2021, pp. 475-481。 0.74
[14] S. Boyd and L. Vandenberghe, Convex optimization. [14] S. Boyd と L. Vandenberghe, Convex Optimization。 0.46
Cambridge university press, 2004. ケンブリッジ 2004年、大学出版。 0.67
[15] V. Balakrishnan, S. Boyd, and S. Balemi, “Branch and bound algorithm for computing the minimum stability degree of parameterdependent linear systems,” International Journal of Robust and Nonlinear Control, vol. international journal of robust and nonlinear control, vol. “[15] v. balakrishnan, s. boyd, s. balemi, “パラメータ依存線形システムの最小安定性度を計算するための分岐および境界アルゴリズム”。 0.87
1, no. 4, pp. 295–317, 1991. 1, no. 4, pp. 295-317, 1991。 0.84
[16] R. Horst and H. Tuy, Global optimization: Deterministic approaches. 16] R. Horst と H. Tuy, Global Optimization: 決定論的アプローチ 0.86
Springer Science & Business Media, 2013. スプリンガー・サイエンス&ビジネス・メディア、2013年。 0.46
[17] D. Dolgov and E. Durfee, “Stationary deterministic policies for constrained MDPs with multiple rewards, costs, and discount factors,” in International Joint Conference on Artificial Intelligence, vol. 17] d. dolgov氏とe. durfee氏は、international joint conference on artificial intelligence, vol.で、“複数の報酬、コスト、割引要因を伴う制約付きmdpの定常的決定主義的政策”について講演した。
訳抜け防止モード: D. Dolgov と E. Durfee は,「複数の報酬,コスト,割引要因を有する制約付き MDP に対する定常決定論的な政策」と評した。 人工知能国際会議に参加して
0.79
19. LAWRENCE ERLBAUM ASSOCIATES LTD, 2005, p. 1326. 19. LAWRENCE ERLBAUM ASSOCIATES LTD, 2005, pp. 1326。 0.43
[18] M. Khonji, A. Jasour, and B. Williams, “Approximability of constanthorizon constrained POMDP,” International Joint Conference on Artificial Intelligence, pp. 5583–5590, 2019. M. Khonji, A. Jasour, and B. Williams, “Approximability of constanthorizon constrained POMDP”. International Joint Conference on Artificial Intelligence, pp. 5583–5590, 2019.
訳抜け防止モード: 18 ] m. khonji, a. jasour, b. williams. 人工知能国際共同会議「コンスタントホリゾン拘束型pomdpの近似可能性」 pp . 5583–5590 , 2019 .
0.68
                 ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。