\documentclass{beamer}
\usepackage[czech]{babel}      % česky psaná práce
\usepackage[T1]{fontenc}
\usepackage[cp1250]{inputenc}  % vstupní znaková sada: Windows 1250

\usepackage{amsmath} % balíček pro pokročilou matem. sazbu
\usepackage{algorithm}
\usepackage{algorithmic}
\DeclareMathOperator*{\E}{E}
\DeclareMathOperator*{\cov}{Cov}
\DeclareMathOperator*{\tr}{tr}

\usetheme{Berlin}
\title{Stochastické iterativní aproximace dynamického programování (SIDP)}
\author{Miroslav Zima}
\institute{FJFI ČVUT}
\date{1. září 2010}

\begin{document}

\begin{frame}
\titlepage
\end{frame}



\begin{frame}
\frametitle{Obsah}
\tableofcontents
\end{frame}


\section{Úloha řízení za neurčitosti}
\begin{frame}{Systém}
\begin{itemize}[<+->]

\item Systém, jeho odezva na vstup $u_t$ při realizaci šumu $v_{t+1}$
\begin{equation}
y_{t+1}=h_t(I_t,u_t,v_{t+1},\theta), \qquad t=0,\ldots,N-1,
\end{equation}
kde $I_t=(y_{t:0},u_{t-1:0})$ a $\theta$ je neznámý parametr. Známe $I_0$, rozdělení šumu $v_t$ a apriorní informaci $f(\theta|T_0)$.

\item Bayesovské učení k získání aposteriorní hustoty $f(\theta|T_{t+1})$
\begin{equation}
f(\theta|T_{t+1}) = \frac{f(y_{t+1} | \theta, I_t,u_t) f(\theta| T_t)}
{\int f(y_{t+1} | \theta, I_t,u_t) f(\theta| T_t)\mathrm{d}\theta}.
\end{equation}

\item Hyperstav $H_t=(I_t,T_t)$ platí
\begin{equation}
H_{t+1}=f_t(H_t,u_t,y_{t+1}), \qquad  t=0,\ldots,N-1.
\end{equation} 

\end{itemize}
\end{frame}

\begin{frame}{Formulace úlohy}
\begin{itemize}[<+->]


\item Ztrátová funkce (určuje kvalitu řízení)
\begin{equation}
g(y_{1:N},u_{0:N-1})=\sum_{t=0}^{N-1}g_t(y_{t+1},u_t).
\end{equation}

\item Řídící strategie
\begin{equation}
\mu_t(H_t)=u_t, \qquad t=0,1,\ldots,N-1.
\end{equation}

\item Hledáme $\pi=\mu_{0:N-1}$ minimalizující očekávanou ztrátu
\begin{equation}
J_\pi=\E_{\theta_0,v_{0:N-1}}\left\{\sum_{t=0}^{N-1}g_t(y_{t+1},\mu_t(H_t))\right\},
\end{equation}
\end{itemize}
\end{frame}

\begin{frame}{Použití dynamického programování při řešení úlohy řízení s aditivní ztrátou}

\begin{itemize}[<+->]

\item Princip optimality $\implies$ postupně od konce řídícího horizontu minimalizujeme dílčí očekávané ztráty 
\begin{gather}
J_N(H_N)=0,\\
J_t(H_t)=\min_{u_t \in U_t}\E_{y_{t+1}}\left\{g_t(y_{t+1},u_t)+J_{t+1}(H_{t+1})|H_t,u_t\right\},
\end{gather}
podmínky: $y_{t+1}=h_t(I_t,u_t,v_{t+1},\theta)$ a $H_{t+1}=f_t(H_t,u_t,y_{t+1})$  

\item Problémy v řešení
\begin{itemize}
\item výpočet střední hodnoty
\item minimalizace vzhledem k $u_t$
\item Analytické řešení obvykle nejde nalézt  $\implies$ aproximační metody.
\end{itemize}
\end{itemize}
\end{frame}

\section{Suboptimální přístup k řešení pomocí SIDP}
\begin{frame}{SIDP}

\begin{itemize}[<+->]
\item Iterativní dynamické programování
\begin{itemize}
\item {Namísto přímého nalezení $\pi$ konstruujeme $\pi_n \to \pi$}
\end{itemize}

\item Stochastická aproximace $=$ Metoda Monte Carlo
\begin{itemize}
\item Očekávaná ztráta se aproximuje průměrem z $n$ realizací ztráty
\item Generování realizace ztráty pro konkrétní bod $H_t$ 
\begin{enumerate}
\item \label{po} generujeme $v_t$ a $\theta$ (použijeme $f(\theta,T_t)$)
\item aplikací řídícího zásahu získáme $y_{t+1}=h_t(I_t,u_t,v_{t+1},\theta)$ 
\item k dosavadní ztrátě přičteme $g_t(y_{t+1},u_t)$
\item dopočítáme $H_{t+1}=f_t(H_t,u_t,y_{t+1})$
\item interpolací/extrapolací $\pi_n$ určíme optimální zásah pro $H_{t+1}$
\item pokud $t<N-1 \implies$ \ref{po}.
\end{enumerate}
\end{itemize}
\end{itemize}
\end{frame}

\section{Srovnání SIDP s jinými metodami} 
\begin{frame}{Integrátor s neznámým ziskem}
\begin{itemize}[<+->]

\item Výstup systému
\begin{equation}
y_{t+1}=y_t+\theta u_t+v_{t+1},	\qquad t=0,\ldots,N-1,
\end{equation}
kde $\theta\neq0$ neznáme,  šum $v_{t+1}\sim N(0,0.1)$ a $y_0=1$.

\item Ztrátová funkce je kvadratická
\begin{equation}
g(y_{1:N},u_{0:N-1})=\sum_{t=0}^{N-1}y_{t+1}^2.
\end{equation}

\item Předpoklad $\cov(v_{t+1},\theta_t)=0$ a $T_0=(\hat{\theta}_0,P_0)$ $\implies$ lze získat konkrétní tvar rce $H_{t+1}=f_t(H_t,u_t,y_{t+1})$. 
\item Hyperstav systému $H_t$ tvoří vektor $(y_t,\hat{\theta}_t,P_t)$ (lze ho vhodnou transformaci redukovat na dim=2).
\end{itemize}
\end{frame}

\begin{frame}{Konkurenční metody}
\begin{itemize}[<+->]

\item Certainty equivalence (CEC)
\begin{itemize}

\item pro návrh řídícího zásahu je brán bodový odhad $\hat{\theta}$
\item je možné získat analytické vyjádření pro optimální řídící zásah
\end{itemize}

\item Cautious control (CC)
\begin{itemize}

\item hledá se optimální řízení na horizontu délky $N=1$
\item je možné získat analytické vyjádření pro optimální řídící zásah
\end{itemize}

\item Klasický numerický přístup k  dynamickému programování (DP)
\begin{itemize}
\item Pro výpočet střední hodnoty je použita Simpsonova metoda
\item K minimalizaci ztráty slouží jednoduchá interpolační metoda.
\end{itemize}

\end{itemize}
\end{frame}

\begin{frame}{Kvantitativní srovnání}
\begin{itemize}

\item Dosažená ztráta - průměr přes 1000 simulací
\item $\theta$ = první nenulová realizace veličiny s rozdělením $N(\hat{\theta}_0,P_0)$
\end{itemize}

\begin{figure}
\centering
\begin{minipage}[c]{0.49\textwidth}
\centering
\includegraphics[width=\textwidth]{N=10,P=10}
\end{minipage}
\begin{minipage}[c]{0.49\textwidth}
\begin{itemize}
\item Metoda CEC neposkytuje použitelné řízení 
\item Metoda CC funguje pouze při $\hat{\theta}_0 \neq 0$. Tehdy dosahuje nejnižší ztráty.
\item SIDP a DP dobře řídí vždy. Při lepší počáteční identifikaci má SIDP horší výsledky (diskretizace).
\end{itemize}
\end{minipage}
\end{figure}
\end{frame}


\begin{frame}{Kvalitativní srovnání SIDP a DP}
\begin{itemize}
\item Četnost konkrétních realizací ztráty - 1000 simulací. 
\end{itemize}

\begin{figure}
\centering
\begin{minipage}[c]{0.49\textwidth}
\centering
\includegraphics[width=\textwidth]{SIDP4}
\end{minipage}
\begin{minipage}[c]{0.49\textwidth}
\centering
\includegraphics[width=\textwidth]{DP4}
\end{minipage}
\end{figure}

\begin{itemize}

\item SIDP se vyhýbá výrazně špatnému řízení ($>10$)
\item DP častěji nabývá nižší celkové ztráty ($<1$)
\item SIDP navrhuje opatrnější zásahy $\implies$ pomalejší identifikace $\theta$
\end{itemize}
\end{frame}

\begin{frame}{Test robustnosti}
\begin{itemize}

\item Dosažená ztráta vhledem k apriorní informaci - 1000 simulací. 
\item $\theta$ = první nenulová realizace náhodné veličiny s rozdělením $N(1,10)$, různá apriorní informace na $\hat{\theta}_0$, rozptyl $P_0=10$.
\end{itemize}

\begin{figure}
\centering
\begin{minipage}[c]{0.49\textwidth}
\centering
\includegraphics[width=\textwidth]{rob}
\end{minipage}
\begin{minipage}[c]{0.49\textwidth}
\begin{itemize}
\item Vyšší odolnost metody SIDP vůči špatné apriorní informaci
\item SIDP poskytuje dobré řízení i pro $\hat{\theta}_0=-10$, přitom skutečné $\theta=1$
\end{itemize}
\end{minipage}
\end{figure}
\end{frame}


\begin{frame}{Závěr}
\begin{itemize}[<+->]

\item Předměty BP
\begin{itemize}
\item Úloha řízení za neurčitosti - teoretické řešení pomocí dynamického programování
\item Algoritmus SIDP jako možná aproximační metoda
\item Implementace SIDP pro řízení jednoduchého systému, porovnání s dalšími metodami
\end{itemize}
\item Možná další práce
\begin{itemize}
\item Navrhnout algoritmus, který by byl méně výpočetně náročný a stále poskytoval dobré řízení
\item např. $u_t=u^{(1)}_t+u^{(2)}_t$, kde $u^{(1)}_t$ minimalizuje ztrátu (například CC) a $u^{(2)}_t$ budí systém za účelem jeho lepší identifikace (použití SIDP).
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\huge{Děkuji za pozornost}
\end{frame}

\end{document}