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.
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].
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.
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.
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.
In this paper, we propose a hierarchical constrained stochastic shortest path problem (HCSSP) 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.
提案手法を避難シナリオで実証し,最先端の数学的プログラミング手法よりも優れていることを示す。
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.
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.
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.
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.
In this paper, we propose a new framework, hierarchical constrained stochastic shortest path problem (HC-SSP), that extends C-SSP to hierarchical problem structure.
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.
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.
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:
− ∆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.
(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(λ∗, π).
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.
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.
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.
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.
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.”
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.
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.
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.
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.
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.
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.
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.
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.
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.
(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.
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.
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).
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.
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
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)
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.
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 ].
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.
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.
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
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.
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.
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.
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.
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.
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).
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.
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).
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.
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| ≤ δ.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 .