\ie \cf

$\newcommand{\norm}[1]{\\|#1\\|} \newcommand{\tr}{\text{tr}} \newcommand{\mor}{\text{Mor}} \newcommand{\hom}{\text{Hom}} \newcommand{\id}{\text{id}} \newcommand{\obj}{\text{obj}} \newcommand{\pr}{\text{pr}} \newcommand{\ker}{\text{ker}} \newcommand{\coker}{\text{coker}} \newcommand{\im}{\text{im}} \newcommand{\vol}{\text{vol}} \newcommand{\bbA}{\mathbb A} \newcommand{\bbB}{\mathbb B} \newcommand{\bbC}{\mathbb C} \newcommand{\bbD}{\mathbb D} \newcommand{\bbE}{\mathbb E} \newcommand{\bbF}{\mathbb F} \newcommand{\bbG}{\mathbb G} \newcommand{\bbH}{\mathbb H} \newcommand{\bbI}{\mathbb I} \newcommand{\bbJ}{\mathbb J} \newcommand{\bbK}{\mathbb K} \newcommand{\bbL}{\mathbb L} \newcommand{\bbM}{\mathbb M} \newcommand{\bbN}{\mathbb N} \newcommand{\bbO}{\mathbb O} \newcommand{\bbP}{\mathbb P} \newcommand{\bbQ}{\mathbb Q} \newcommand{\bbR}{\mathbb R} \newcommand{\bbS}{\mathbb S} \newcommand{\bbT}{\mathbb T} \newcommand{\bbU}{\mathbb U} \newcommand{\bbV}{\mathbb V} \newcommand{\bbW}{\mathbb W} \newcommand{\bbX}{\mathbb X} \newcommand{\bbY}{\mathbb Y} \newcommand{\bbZ}{\mathbb Z} \newcommand{\cA}{\mathcal A} \newcommand{\cB}{\mathcal B} \newcommand{\cC}{\mathcal C} \newcommand{\cD}{\mathcal D} \newcommand{\cE}{\mathcal E} \newcommand{\cF}{\mathcal F} \newcommand{\cG}{\mathcal G} \newcommand{\cH}{\mathcal H} \newcommand{\cI}{\mathcal I} \newcommand{\cJ}{\mathcal J} \newcommand{\cK}{\mathcal K} \newcommand{\cL}{\mathcal L} \newcommand{\cM}{\mathcal M} \newcommand{\cN}{\mathcal N} \newcommand{\cO}{\mathcal O} \newcommand{\cP}{\mathcal P} \newcommand{\cQ}{\mathcal Q} \newcommand{\cR}{\mathcal R} \newcommand{\cS}{\mathcal S} \newcommand{\cT}{\mathcal T} \newcommand{\cU}{\mathcal U} \newcommand{\cV}{\mathcal V} \newcommand{\cW}{\mathcal W} \newcommand{\cX}{\mathcal X} \newcommand{\cY}{\mathcal Y} \newcommand{\cZ}{\mathcal Z} \newcommand{\rmA}{\mathfrak A} \newcommand{\rmB}{\mathfrak B} \newcommand{\rmC}{\mathfrak C} \newcommand{\rmD}{\mathfrak D} \newcommand{\rmE}{\mathfrak E} \newcommand{\rmF}{\mathfrak F} \newcommand{\rmG}{\mathfrak G} \newcommand{\rmH}{\mathfrak H} \newcommand{\rmI}{\mathfrak I} \newcommand{\rmJ}{\mathfrak J} \newcommand{\rmK}{\mathfrak K} \newcommand{\rmL}{\mathfrak L} \newcommand{\rmM}{\mathfrak M} \newcommand{\rmN}{\mathfrak N} \newcommand{\rmO}{\mathfrak O} \newcommand{\rmP}{\mathfrak P} \newcommand{\rmQ}{\mathfrak Q} \newcommand{\rmR}{\mathfrak R} \newcommand{\rmS}{\mathfrak S} \newcommand{\rmT}{\mathfrak T} \newcommand{\rmU}{\mathfrak U} \newcommand{\rmV}{\mathfrak V} \newcommand{\rmW}{\mathfrak W} \newcommand{\rmX}{\mathfrak X} \newcommand{\rmY}{\mathfrak Y} \newcommand{\rmZ}{\mathfrak Z} \newcommand{\paren}[1]{( #1 )} \newcommand{\Paren}[1]{\left( #1 \right)} \newcommand{\bigparen}[1]{\bigl( #1 \bigr)} \newcommand{\Bigparen}[1]{\Bigl( #1 \Bigr)} \newcommand{\biggparen}[1]{\biggl( #1 \biggr)} \newcommand{\Biggparen}[1]{\Biggl( #1 \Biggr)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\Abs}[1]{\left\lvert #1 \right\rvert} \newcommand{\bigabs}[1]{\bigl\lvert #1 \bigr\rvert} \newcommand{\Bigabs}[1]{\Bigl\lvert #1 \Bigr\rvert} \newcommand{\biggabs}[1]{\biggl\lvert #1 \biggr\rvert} \newcommand{\Biggabs}[1]{\Biggl\lvert #1 \Biggr\rvert} \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\Card}[1]{\left\lvert #1 \right\rvert} \newcommand{\bigcard}[1]{\bigl\lvert #1 \bigr\rvert} \newcommand{\Bigcard}[1]{\Bigl\lvert #1 \Bigr\rvert} \newcommand{\biggcard}[1]{\biggl\lvert #1 \biggr\rvert} \newcommand{\Biggcard}[1]{\Biggl\lvert #1 \Biggr\rvert} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\Norm}[1]{\left\lVert #1 \right\rVert} \newcommand{\bignorm}[1]{\bigl\lVert #1 \bigr\rVert} \newcommand{\Bignorm}[1]{\Bigl\lVert #1 \Bigr\rVert} \newcommand{\biggnorm}[1]{\biggl\lVert #1 \biggr\rVert} \newcommand{\Biggnorm}[1]{\Biggl\lVert #1 \Biggr\rVert} \newcommand{\iprod}[1]{\langle #1 \rangle} \newcommand{\Iprod}[1]{\left\langle #1 \right\rangle} \newcommand{\bigiprod}[1]{\bigl\langle #1 \bigr\rangle} \newcommand{\Bigiprod}[1]{\Bigl\langle #1 \Bigr\rangle} \newcommand{\biggiprod}[1]{\biggl\langle #1 \biggr\rangle} \newcommand{\Biggiprod}[1]{\Biggl\langle #1 \Biggr\rangle} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\Set}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bigset}[1]{\bigl\lbrace #1 \bigr\rbrace} \newcommand{\Bigset}[1]{\Bigl\lbrace #1 \Bigr\rbrace} \newcommand{\biggset}[1]{\biggl\lbrace #1 \biggr\rbrace} \newcommand{\Biggset}[1]{\Biggl\lbrace #1 \Biggr\rbrace} \newcommand{\bracket}[1]{\lbrack #1 \rbrack} \newcommand{\Bracket}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\bigbracket}[1]{\bigl\lbrack #1 \bigr\rbrack} \newcommand{\Bigbracket}[1]{\Bigl\lbrack #1 \Bigr\rbrack} \newcommand{\biggbracket}[1]{\biggl\lbrack #1 \biggr\rbrack} \newcommand{\Biggbracket}[1]{\Biggl\lbrack #1 \Biggr\rbrack} \newcommand{\ucorner}[1]{\ulcorner #1 \urcorner} \newcommand{\Ucorner}[1]{\left\ulcorner #1 \right\urcorner} \newcommand{\bigucorner}[1]{\bigl\ulcorner #1 \bigr\urcorner} \newcommand{\Bigucorner}[1]{\Bigl\ulcorner #1 \Bigr\urcorner} \newcommand{\biggucorner}[1]{\biggl\ulcorner #1 \biggr\urcorner} \newcommand{\Biggucorner}[1]{\Biggl\ulcorner #1 \Biggr\urcorner} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\Ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\bigceil}[1]{\bigl\lceil #1 \bigr\rceil} \newcommand{\Bigceil}[1]{\Bigl\lceil #1 \Bigr\rceil} \newcommand{\biggceil}[1]{\biggl\lceil #1 \biggr\rceil} \newcommand{\Biggceil}[1]{\Biggl\lceil #1 \Biggr\rceil} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\bigfloor}[1]{\bigl\lfloor #1 \bigr\rfloor} \newcommand{\Bigfloor}[1]{\Bigl\lfloor #1 \Bigr\rfloor} \newcommand{\biggfloor}[1]{\biggl\lfloor #1 \biggr\rfloor} \newcommand{\Biggfloor}[1]{\Biggl\lfloor #1 \Biggr\rfloor} \newcommand{\lcorner}[1]{\llcorner #1 \lrcorner} \newcommand{\Lcorner}[1]{\left\llcorner #1 \right\lrcorner} \newcommand{\biglcorner}[1]{\bigl\llcorner #1 \bigr\lrcorner} \newcommand{\Biglcorner}[1]{\Bigl\llcorner #1 \Bigr\lrcorner} \newcommand{\bigglcorner}[1]{\biggl\llcorner #1 \biggr\lrcorner} \newcommand{\Bigglcorner}[1]{\Biggl\llcorner #1 \Biggr\lrcorner} \newcommand{\Rnn}{\R_{\ge 0}} \DeclareMathOperator{\Tr}{Tr} \DeclareMathOperator{\min}{min} \DeclareMathOperator{\max}{max} \DeclareMathOperator{\argmax}{arg\,max} \DeclareMathOperator{\argmin}{arg\,min} \DeclareMathOperator{\E}{\mathbb E} \DeclareMathOperator{\pE}{\tilde{\mathbb E}} \DeclareMathOperator{\Pr}{\mathbb P} \DeclareMathOperator{\Det}{\textbf{Det}} \DeclareMathOperator{\Perm}{\textbf{Perm}} \DeclareMathOperator{\Sym}{\textbf{Sym}} \DeclareMathOperator{\Pow}{\textbf{Pow}} \DeclareMathOperator{\Gal}{\textbf{Gal}} \DeclareMathOperator{\Aut}{\textbf{Aut}} \notag$

$\newcommand{\1}{\ensuremath{\mathrm{1}}} \notag$

$\newcommand{\transpose}[1]{\ensuremath{#1{}^{\mkern-2mu\intercal}}} \newcommand{\dyad}[1]{\ensuremath{#1#1{}^{\mkern-2mu\intercal}}} \newcommand{\nchoose}[1]{\ensuremath} \newcommand{\generated}[1]{\ensuremath{\langle #1 \rangle}} \notag$

\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}  \newcommand{\R} % real numbers  \newcommand{\N}} % natural numbers  \newcommand{\Z} % integers  \newcommand{\F} % a field  \newcommand{\Q} % the rationals  \newcommand{\C}{\mathbb{C}} % the complexes  \newcommand{\poly}}  \newcommand{\polylog}}  \newcommand{\loglog}}}  \newcommand{\zo}{\{0,1\}}  \newcommand{\suchthat}  \newcommand{\pr}[1]{\Pr\left[#1\right]}  \newcommand{\deffont}{\em}  \newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}}  \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation  \newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance  \newcommand{\xor}{\oplus}  \newcommand{\GF}{\mathrm{GF}}  \newcommand{\eps}{\varepsilon}  \notag

$\newcommand{\eps}{\varepsilon} \notag$

$\newcommand{\MIP}{\class{MIP}}$

\no

$\newcommand{\textprob}[1]{\text{#1}} \newcommand{\mathprob}[1]{\textbf{#1}} \newcommand{\Satisfiability}{\textprob{Satisfiability}} \newcommand{\Mor}{\textprob{Mor}} \newcommand{\Hom}{\textprob{Hom}} \newcommand{\cok}{\textprob{cok }} \newcommand{\ker}{\textprob{ker }} \newcommand{\im}{\textprob{im }} \newcommand{\coim}{\textprob{coim }} \newcommand{\id}{\textprob{id}}$

Next |

| Previous

Reformulations of Basic Problems

100%

Time Delays
Correlated Disturbances
Forecasts
Simplifying Uncontrollable Components

Last time, we briefly mentioned the issues with state augmentation to deal with reformulations to the basic problem. In this post, we'll go into a bit more detail about how to deal with such reformulations

As a general rule of thumb, when we augment state, we want to include at time $k$ all the information known to the DDS at the time into the state variable at time $k$.

Time Delays

Consider the situation in which the DDS is no longer Markovian, i.e., $x_{k+1}$ depends on $x_0,\ldots,x_k$ and $u_0,\ldots,u_k$. This is essentially impossible to handle in an open loop basic problem without sacrificing the dynamic programming algorithm, but we can use state augmentation to reformulate the basic problem in the closed case. Let

$$\tilde{x_k}=(x_0,\ldots,x_k,u_0,\ldots,u_{k-1})$$

Thus, we've reformulated the problem into a standard closed loop basic problem over states $\tilde{x_k}$. This of course didn't come without a steep cost. The state space has increased from $S$ to at most $S^{2k}$.

For this reason, we often consider partially Markovian models, i.e., models in which $x_{k+1}$ depends on $x_{k-i},\ldots,x_k$, $u_{k-i},\ldots,u_k$ for some manageable $i$, so that the state space increases to at most $S^{2i}$ instead. We call this a time delay of $i$

Correlated Disturbances

Consider the modification to the DDS model in which $w_k$ now can depend on previous $w_i$, i.e., the disturbances are correlated. There is no good way to handle this situation in general, but if we make the assumption that each $w_k$ can be written as follows (with $\lambda$ a constant and $\eta_k$ independent random variables)$$w_k=\lambda w_{k-1}+\eta_k$$

We can modify the problem into a basic problem. In fact, it's as simple as letting $\tilde x_k=(x_k,w_k)$. See if you can figure out all of the details involved in converting this setup into a basic problem. This can even be generalized to multiple dimensions with matrix coefficients.

Besides the state space growth (which in this case isn't too bad), the main issue with this approach is the assumption of perfect state knowledge. To be able to run our algorithm, we need to be able to perfectly measure the randomness and previous $x_k$ state of the DDS in generating the state $x_{k+1}$. But often, we can't do either, since $w_k$ is generally an uncertainty on our measurement of $x_k$. To deal with these sorts of situations, we'll have to wait until Chapter 4.

Forecasts

Suppose that we no longer are given the probability distribution $P_k$, but rather are told that we now have a set of probability distributions $Q_k$ (a finite set), and there exists a probability distribution $\zeta_k$ on $Q$ representing the likelihood of a particular distribution in $Q$ being the one that determines the disturbance.

We call $\zeta$ the forecast, since we are informed of its output before making the decision $\mu$. (For simplicity, let $\zeta_k^i$ refer to the probability of the $i$th element of $Q$ being selected at time $k$).

As a real world example, $\zeta_k$ could be a forecast of the demand for a product on year $k$: small, medium or large. How do we convert this into a basic problem?

It's quite simple: let $\tilde{x_k}=(x_k,\zeta_k)$ and the stochastic term be $\tilde{w_k}=(w_k,\zeta_k)$. Can you see how to finish the setup?

Simplifying Uncontrollable Components

In the three examples above, we've seen how to take complications in the setup of the basic problem, and via state augmentation, rewrite the complications as part of the basic problem. Of course, this adds to the size of the state space, which can very easily become unmanageable.

In general, there is no good way to deal with this expansion, other than heuristics. However, there is a special case that comes up relatively often.

Suppose we've augmented our space to have state $\tilde{x_k}=(x_k,y_k)$, where $x_k$ is the original state variable ($x_{k+1}=f(\tilde{x_k},u_k,P(\cdot\mid\tilde{x_k},y_k))$) and $y_k$ is dependent on $x_k$ stochastically. However, the controller observes the value of $y_k$ prior to picking $u_k$ (unlike $w_k$). Define$$\tilde{V_k}(x_k)=E_{y_k}\set{V_k(\tilde{x_k}\mid x_k)}$$

Via basic arithmetic, we have $$\tilde{V_k}(x_k)=E_{y_k}\Set{\min\limits_{u_k\in C_k(\tilde{x_k})}E_{w_k}\Set{g_k(\tilde{x_k},u_k,w_k)+\tilde{V_k}(f_k(\tilde{x_k},u_k,w_k))}\mid x_k}$$

We now can use the same approach as the Dynamic Programming Algorithm. The advantage is the size of the state space. If we just used the state augmentation approach, the state space size would be $n\cdot m$, with $n$ the state space size of $x_k$ and $m$ the state space size of $y_k$. But, this approach leaves us with a state space of size $n$.

Can you see how to directly simplify the augmentation of forecasts?

Top