#LyX 1.6.5 created this file. For more info see http://www.lyx.org/ \lyxformat 345 \begin_document \begin_header \textclass scrreprt \use_default_options true \language czech \inputencoding auto \font_roman default \font_sans default \font_typewriter default \font_default_family default \font_sc false \font_osf false \font_sf_scale 100 \font_tt_scale 100 \graphics default \paperfontsize default \spacing single \use_hyperref false \papersize a4paper \use_geometry false \use_amsmath 1 \use_esint 1 \cite_engine basic \use_bibtopic false \paperorientation portrait \secnumdepth 2 \tocdepth 2 \paragraph_separation indent \defskip medskip \quotes_language german \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \author "" \author "" \end_header \begin_body \begin_layout Standard \align left \begin_inset ERT status open \begin_layout Plain Layout \backslash thispagestyle{empty} \end_layout \end_inset \end_layout \begin_layout Standard \align center \size large České vysoké učení technické v Praze \end_layout \begin_layout Standard \align center \size large Fakulta jaderná a fyzikálně inženýrská \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Standard \align center Katedra matematiky \end_layout \begin_layout Standard \align center Obor: Inženýrská informatika \end_layout \begin_layout Standard \align center Zaměření: Softwarové inženýrství \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Standard \align center \begin_inset Graphics filename logo_cvut.eps lyxscale 20 scale 20 \end_inset \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Standard \align center \size larger \color black Iterativní lokální dynamické programování pro návrh duálního řízení \end_layout \begin_layout Standard \begin_inset VSpace smallskip \end_inset \end_layout \begin_layout Standard \align center \size larger \color black Iterative local dynamic programming for dual control \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Standard \align center \size largest \color black BAKALÁŘSKÁ \size larger \size largest PRÁCE \end_layout \begin_layout Standard \begin_inset VSpace vfill \end_inset \end_layout \begin_layout Standard \align center Vypracoval: Michal Vahala \end_layout \begin_layout Standard \align center Vedoucí práce: Ing. Václav Šmídl, Ph.D. \end_layout \begin_layout Standard \align center Rok: 2010 \end_layout \begin_layout Standard \begin_inset Newpage newpage \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash thispagestyle{empty} \end_layout \end_inset \end_layout \begin_layout Standard zadání práce \end_layout \begin_layout Standard \begin_inset Newpage newpage \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash thispagestyle{empty}~ \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset VSpace vfill \end_inset \end_layout \begin_layout Subsubsection* Prohlášení \end_layout \begin_layout Standard Prohlašuji, že jsem svou bakalářskou práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Standard \noindent \align left V Praze dne \SpecialChar \ldots{} \SpecialChar \ldots{} \SpecialChar \ldots{} \SpecialChar \ldots{} \SpecialChar \ldots{} \begin_inset space \hfill{} \end_inset \SpecialChar \ldots{} \SpecialChar \ldots{} \SpecialChar \ldots{} \SpecialChar \ldots{} \SpecialChar \ldots{} \SpecialChar \ldots{} \end_layout \begin_layout Standard \noindent \align block \begin_inset space \hfill{} \end_inset Michal Vahala \begin_inset ERT status open \begin_layout Plain Layout ~~ \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset Newpage newpage \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash thispagestyle{empty}~ \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset VSpace vfill \end_inset \end_layout \begin_layout Subsubsection* Poděkování \end_layout \begin_layout Standard Děkuji \SpecialChar \ldots{} za \SpecialChar \ldots{} \end_layout \begin_layout Standard \begin_inset VSpace defskip \end_inset \end_layout \begin_layout Standard \begin_inset space \hfill{} \end_inset Michal Vahala \end_layout \begin_layout Standard \begin_inset Newpage newpage \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash thispagestyle{empty} \end_layout \end_inset \end_layout \begin_layout Description \emph on Název \begin_inset space \space{} \end_inset práce: \emph default \color black \begin_inset ERT status open \begin_layout Plain Layout ~ \end_layout \end_inset \begin_inset Newline newline \end_inset Iterativní lokální dynamické programování pro návrh duálního řízení \end_layout \begin_layout Description \begin_inset VSpace defskip \end_inset \end_layout \begin_layout Description \emph on Autor: \emph default Michal Vahala \end_layout \begin_layout Description \emph on Obor: \emph default Inženýrská informatika \end_layout \begin_layout Description \emph on Druh \begin_inset space \space{} \end_inset práce: \emph default Bakalářská práce \end_layout \begin_layout Description \emph on Vedoucí \begin_inset space \space{} \end_inset práce: \emph default Ing. Václav Šmídl, Ph.D. \end_layout \begin_layout Description \emph on Konzultant: \emph default --- \end_layout \begin_layout Description \emph on Abstrakt: \emph default abstrakt \end_layout \begin_layout Description \emph on Klíčová \begin_inset space \space{} \end_inset slova: \emph default klíčová slova \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Description \emph on Title: \emph default \color black \begin_inset ERT status open \begin_layout Plain Layout ~ \end_layout \end_inset \begin_inset Newline newline \end_inset Iterative local dynamic programming for dual control \end_layout \begin_layout Description \begin_inset VSpace defskip \end_inset \end_layout \begin_layout Description \emph on Author: \emph default Michal Vahala \end_layout \begin_layout Description \emph on Abstract: \emph default abstrakt \end_layout \begin_layout Description \emph on Key \begin_inset space \space{} \end_inset words: \emph default klíčová slova \end_layout \begin_layout Standard \begin_inset Newpage newpage \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash thispagestyle{empty} \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset CommandInset toc LatexCommand tableofcontents \end_inset \end_layout \begin_layout Standard \begin_inset Newpage newpage \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash thispagestyle{empty} \end_layout \end_inset \end_layout \begin_layout Chapter* Seznam použitého označení \end_layout \begin_layout Labeling \labelwidthstring 00.00.0000 iLDP iterativní lokální dynamické programování \end_layout \begin_layout Labeling \labelwidthstring 00.00.0000 LQG lineáně kvadraticky gaussovské řízení (Linear-Quadratic-Gaussian) \end_layout \begin_layout Labeling \labelwidthstring 00.00.0000 iLQG iterativní LQG \end_layout \begin_layout Labeling \labelwidthstring 00.00.0000 \color red DDP \color inherit diferenciální dynamické programování \end_layout \begin_layout Standard \begin_inset Newpage newpage \end_inset \end_layout \begin_layout Addchap Úvod \end_layout \begin_layout Standard Skutečný svět se nikdy nechová přesně podle matematických rovnic, protože ty jsou vždy jen jakýmsi zjednodušením nebo přiblížením. V reálném světě se vyskytuje mnoho neznámých veličin, poruch, nepředvídatelných vlivů a ani naše měřící přístroje nejsou přesné. Chceme-li efektivně řídit nějaký systém, musíme si být těchto vlivů vědomi a zahrnout je do našich uvažování. Situace se však ještě může zkomplikovat, když jeden nebo více parametrů neznáme. To může nastat z různých důvodů, například příšlušné čidlo nebo měřící přístroj nemůžeme nebo nechceme (například z důvodů vysoké ceny) instalovat a tedy o velikosti příslušné hodnoty můžeme jen usuzovat ze známých dat. Ještě složitější situace nastane, když uvažujeme neznámý parametr proměnný. \end_layout \begin_layout Standard \color black Máme tedy dva cíle, musíme systém co nejlépe řídit a současně se snažit o co nejpřesnější určení neznámých parametrů. Tyto dva postupy jsou však obecně v rozporu, protože parametry se nejlépe určují, když je systém vybuzen a nechová se optimálně. Právě tento rozpor a nalezení kompromisu, který povede k jeho řešení, je podstatou duálního řízení. \end_layout \begin_layout Standard \color black Pro přiblížení ilustrujme problém na jednoduchém příkladě: Uvažujme elektromotor s možností řídit napětí na vstupu motoru a měřit příslušné proudy. Jedná se tedy o systém se dvěma vstupy a dvěma výstupy. Cílem našeho řízení je dosažení požadovaných otáček rotoru. Ovšem otáčky a ani polohu hřídele měřit nemůžeme. Máme o nich však znalost v podobě středních hodnot a variancí. Naší snahou je co nejpřesněji určit hodnotu otáček a polohy hřídele a současně systém řídit tak, abychom dosáhly požadované hodnoty otáček. Tyto dvě snahy jsou ale v rozporu, protože nejvíce informací o neznámých parametrech získáme, když je motor vybuzen. Tedy například se prudce rozjíždí, brzdí, rychle mění rychlost nebo kmitá, což se projevuje v proudech, které máme možnost měřit. Ale právě vybuzení motoru je v rozporu se snahou o dobré řízení, protože chyba, které se dopustíme je většinou nepřijatelná. Naopak, když se systém snažíme řídit, bez dostatečné znalosti jeho parametrů, s velkou pravděpodobností selžeme. \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Standard Námětem této bakalářské práce je algoritmus \emph on iterativního lokálního dynamického programování \emph default (iLDP) jako jedna z metod pro řešení problému duálního řízení. Algoritmus byl navržen a popsán v článku \color black \begin_inset CommandInset citation LatexCommand cite key "TodorovTassaILDP" \end_inset \color inherit . Jak už prozrazuje název algoritmu, jedná se o iterační metodu. Tedy stručně řečeno, algoritmus vyjde od nějakého počátečního řízení, které je ovšem nutno dodat jako apriorní informaci a v cyklech (iteracích) tuto řídící strategii vylepšuje, za účelem získání řízení optimálního. Dále se jedná o metodu lokální, což v můžeme jednoduše chápat tak, že kandidáti na \begin_inset Quotes gld \end_inset vylepšení \begin_inset Quotes grd \end_inset řízení jsou vybírání z jistého, zatím blíže nespecifikovaného, okolí původní řídící strategie. Nakonec algoritmus využívá obecné schéma dynamického programování, které bude blíže popsáno v dalším textu. \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Standard Cílem této práce bylo seznámit se s obecnou tématikou duálního řízení a detailněji s konkrétním algoritmem - iterativním lokálním dynamickým programová ním. Následně tento algoritmus implementovat a aplikovat na jednoduchý systém. Otestovat jeho funkčnost a schopnost řídit a to i v porovnání s jinými metodami a algoritmy. \emph on \color blue Dále implementovat algoritmus iLDP pro složitější systém blíže praktické aplikaci, konkrétně se jedná o synchronní motor s permanentními magnety. Opět otestovat funkčnost a případně srovnat s dostupnými výsledky jiných řídících strategii. \emph default \color inherit Na základě získaných výsledků posoudit výhody a nevýhody algoritmu a jeho použitelnost na další úlohy. \end_layout \begin_layout Standard Hlavním přínosem práce je otestování vlastností algoritmu iLDP na jiných problémech, než pro které byla vyvinuta autory. Objevení kladů a záporů algoritmu a dále díky srovnání s jinými algoritmy získání přehledu, pro které praktické aplikace je vhodnější respektive méně vhodný než srovnávané metody. Prvotní očekávání pro srovnání algoritmu iLDP a \emph on \color blue principu separace \emph default \color inherit jsou, že iLDP bude rychlejší co do výpočetního času, avšak přesnost získaných výsledků bude nižší. Dále je očekávána nezanedbatelná závislost výsledného řízení na volbě použitých aproximací a apriorní řídící strategie. \end_layout \begin_layout Standard \begin_inset Newpage newpage \end_inset \end_layout \begin_layout Chapter Teorie duálního řízení \end_layout \begin_layout Section Základní pojmy \end_layout \begin_layout Subsection Systém a řízení \end_layout \begin_layout Subsubsection Systém \end_layout \begin_layout Standard Základním pojmem, se kterým budeme v textu pracovat je \emph on systém \emph default . Obdobně jako základní pojmy zejména v matematických vědách (bod, množina, algoritmus,\SpecialChar \ldots{} ), nelze tento pojem exaktně definovat. Systém si můžeme představit jako jistý \begin_inset Quotes gld \end_inset objekt \begin_inset Quotes grd \end_inset , často bude reprezentovat objekt skutečného světa. Hlavní vlastností systému je, že má zpravidla jeden nebo více vstupů, pomocí kterých mu můžeme předávat informaci -- řízení a jeden nebo více výstupu, což jsou hodnyty, které pozorujeme. Co se odehrává uvnitř systému však obecně nevíme. Řízení, které budeme dodávat systému na vstup bude v textu značeno písmenem \emph on \begin_inset Formula $u$ \end_inset \emph default . Analogicky bude písmenem \emph on \begin_inset Formula $y$ \end_inset \emph default označena pozorovaná hodnota na výstupu. \end_layout \begin_layout Standard Chování systému, to je jakým výstupem reaguje na vstup, popisujeme dle \begin_inset CommandInset citation LatexCommand cite key "MelicharLS" \end_inset obecně diferenciální rovnicí respektive soustavou diferenciálních rovnic vyšších řádů. Jedná se o takzvaný \color black vnější popis \color inherit . Tento druh popisu, pohlíží na systém \begin_inset Quotes gld \end_inset zvenku \begin_inset Quotes grd \end_inset bez skutečné znalosti, co se odehrává uvnitř systému a jaká je jeho podstata. Vnější popis obvykle obdržíme při odvození modelu systému z fyzikálních rovnic. Omezení, která z něj plynou, se snažíme odstranit zavedením \color black vnitřního (stavového) popisu \color inherit , kdy (soustavu) diferenciálních rovnic vyššího řádu, převedeme vhodnou volbou nových proměnných \emph on \begin_inset Formula $x$ \end_inset \series bold \series default \emph default na soustavu diferenciálních rovnic prvního řádu. Proměnné \emph on \begin_inset Formula $x$ \end_inset \series bold \series default \emph default označujeme jako \color black stavové proměnné \color inherit . \end_layout \begin_layout Subsubsection Řízení \end_layout \begin_layout Standard Naším úkolem je pro zadaný systém nalézt regulátor, tedy obecně řízení \emph on \begin_inset Formula $u$ \end_inset \emph default takové, které dodané na vstup způsobí, že systém se bude \begin_inset Quotes gld \end_inset chovat podle našich požadavků \begin_inset Quotes grd \end_inset . To zpravidla znamená, že hodnoty výstupní veličiny \series bold \emph on \begin_inset Formula $y$ \end_inset \series default \emph default dosáhnou (nebo se přiblíží s danou přesností) požadované hodnotě v podobě referenčního signálu, který regulátor dostavá z vnějšku a současně dodrží předem stanovená omezení. Práce je ovšem zaměřena na řízení složitějších systémů, u kterých jeden nebo více parametrů neznáme přesně. Tedy některý (více) z koeficientů v rovnicích popisujících systém není znám. Máme však o něm jistou statistickou informaci v podob \color black ě jeho \color inherit očekávané hodnoty a variance. Dále je-li systém nelineární, jsou výsledné rovnice příliš složité a tedy analyticky neřešitelné. Pro numerické řešení, jsou rovnice systému zpravidla převáděny do diskrétního tvaru. \end_layout \begin_layout Standard Řízení obecně dělíme podle \begin_inset CommandInset citation LatexCommand cite key "MelicharLS" \end_inset na dva typy: \emph on Přímovazební řízení \emph default užíváme v případě, kde je k dispozici přesný matematický model systému a je vyloučen výskyt neurčitostí. Toto řízení nevyužívá žádné zpětné informace od systému a regulátor pracuje pouze s referenčním signálem. Naproti tomu \emph on zpětnovazební řízení \emph default využívá i informace o skutečném výstupu systému a snaží se tak eliminovat chyby v důsledku neurčitostí a chyb způsobenych nepřesností modelu. \end_layout \begin_layout Subsubsection Duální řízení \end_layout \begin_layout Standard Chceme navrhnout regulátor pro zadaný systém s neznámými parametry. Úkoly jsou tedy dva: 1. \emph on opatrnost \emph default - efektivně systém řídit a 2. \emph on testování \emph default - určit neznáme parametry. Tyto dva přístupy jsou ale obecně v rozporu. Abychom mohli systém dobře řídit, potřebujeme znát parametry co nejpřesněji. Nejvíce informací o parametrech však získáme, když je systém vybuzen a nechová optimálně. Tyto pojmy není snadné kvantifikovat, ale velmi často se projevují v konkrétníc h řídících schématech. Naším úkolem je pokusit nalézt nějaký kompromis mezi oběma úkoly. Právě tento přístup je označován jako \emph on duální řízení \emph default \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset . \end_layout \begin_layout Subsection Formulace problému \end_layout \begin_layout Standard V textu budeme pracovat zpravidla s diskrétním systémem, ve smyslu systému s diskrétním časem, protože výpočty jsou prováděny ve většině případů problemat iky duálního řízení numericky. Rovnice popisující systém jsou však zpravidla ve spojitém tvaru, (model často vychází ze skutečnosti, popřípadě fyzikálních zákonů). V tomto případě provádíme diskretizaci. \end_layout \begin_layout Standard Základní problém je formulován podle \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset následovně: \end_layout \begin_layout Standard \begin_inset VSpace defskip \end_inset \end_layout \begin_layout Standard Uvažujme stavový popis diskrétního dynamického systému \begin_inset Formula \begin{equation} \begin{array}{cc} x_{k+1}=f_{k}(x_{k},u_{k},w_{k}), & k=0,\ldots,N-1\end{array},\label{eq:zakladniproblem}\end{equation} \end_inset kde \begin_inset Formula $x_{k}$ \end_inset je stavová proměná z prostoru \begin_inset Formula $S_{k}$ \end_inset , \begin_inset Formula $u_{k}$ \end_inset řízení z prostoru \begin_inset Formula $C_{k}$ \end_inset a \begin_inset Formula $w_{k}$ \end_inset náhodná porucha z prostoru \begin_inset Formula $D_{k}$ \end_inset , vše v čase \begin_inset Formula $k$ \end_inset při celkovém časovém horizontu \begin_inset Formula $N$ \end_inset . Na řízení \begin_inset Formula $u_{k}$ \end_inset klademe omezení, že může nabývat pouze hodnot z neprázdné podmonožiny \begin_inset Formula $U_{k}(x_{k})\subset C_{k}$ \end_inset závislé na stavu \begin_inset Formula $x_{k}$ \end_inset . Náhodná porucha \begin_inset Formula $w_{k}$ \end_inset je charakterizována rozdělením pravděpodobnosti \begin_inset Formula $P_{k}$ \end_inset , které může explicitně záviset na \begin_inset Formula $x_{k}$ \end_inset a \begin_inset Formula $u_{k}$ \end_inset , ne však na předchozích poruchách \begin_inset Formula $w_{k-1},\ldots,w_{0}$ \end_inset . \end_layout \begin_layout Standard Dále uvažujme množinu řízení, jedná se o posloupnost funkcí \begin_inset Formula \[ \pi=\{\mu_{0},\ldots,\mu_{N-1}\},\] \end_inset kde \begin_inset Formula $\mu_{k}$ \end_inset přiřazuje stavu \begin_inset Formula $x_{k}$ \end_inset přípustné řízení \begin_inset Formula $u_{k}=\mu_{k}(x_{k})$ \end_inset , to je takové, že \begin_inset Formula $\mu_{k}(x_{k})\in U_{k}(x_{k})$ \end_inset , množinu přípustných řešení označme \begin_inset Formula $\Pi$ \end_inset . Máme-li dány počáteční stav \begin_inset Formula $x_{0}$ \end_inset a přípustné řešení \begin_inset Formula $\pi$ \end_inset můžeme stavy \begin_inset Formula $x_{k}$ \end_inset a poruchy \begin_inset Formula $w_{k}$ \end_inset považovat za náhodné veličiny s rozdělemím definovaným systémem rovnic \begin_inset CommandInset ref LatexCommand ref reference "eq:zakladniproblem" \end_inset , kde za řízení \begin_inset Formula $u_{k}$ \end_inset dosadíme hodnotu funkce \begin_inset Formula $\mu_{k}$ \end_inset v \begin_inset Formula $x_{k}$ \end_inset . \end_layout \begin_layout Standard Pro dané ztráty v jednotlivých časech -- funkce \begin_inset Formula $g_{k}$ \end_inset , pak definujeme očekávanou ztrátu \begin_inset Formula $\pi$ \end_inset v \begin_inset Formula $x_{0}$ \end_inset jako \begin_inset Formula \[ J_{\pi}(x_{0})=\mathbf{E}\left\{ g_{N}(x_{N})+\sum_{k=0}^{N-1}g_{k}\left(x_{k},\mu_{k}(x_{k}),w_{k}\right)\right\} \] \end_inset kde je očekávaná hodnota počítána přes náhodné veličiny \begin_inset Formula $w_{k}$ \end_inset a \begin_inset Formula $x_{k}$ \end_inset . Optimální řízení \begin_inset Formula $\pi^{*}$ \end_inset je právě to, které minimalizuje ztrátu \begin_inset Formula \[ J_{\pi^{*}}(x_{0})=\min_{\pi\in\Pi}J_{\pi}(x_{0}).\] \end_inset Optimální ztrátu označme \begin_inset Formula $J^{*}(x_{0})$ \end_inset . \end_layout \begin_layout Subsection Dynamické programování \end_layout \begin_layout Standard Dynamické programovní dle \begin_inset CommandInset citation LatexCommand cite key "ViriusZA" \end_inset je jedním ze způsobů návrhu algoritmů pro řešení jistých typu optimalizačních problémů. Konkrétně se uplatňuje v případě, že jde o diskrétní optimalizační úlohu, na řešení daného problému můžeme nahlížet jako na konečnou posloupnost rozhodnutí a platí \emph on princip optimality \emph default . \end_layout \begin_layout Subsubsection Princip optimality \end_layout \begin_layout Standard říká, že optimální posloupnost rozhodnutí musí mít následující vlastnost: \emph on Jestliže jsme už udělali \emph default k \emph on rozhodnutí, musí být všechna následující rozhodnutí optimální vzhledem k výsledkům rozhodnutí předchozích, jinak nemůžeme dostat optimální řešení \emph default \begin_inset CommandInset citation LatexCommand cite key "ViriusZA" \end_inset \emph on . \end_layout \begin_layout Subsubsection Princip optimality v teorii řízení \end_layout \begin_layout Standard Nechť \begin_inset Formula $\pi^{*}=\left\{ \mu_{0}^{*},\mu_{1}^{*},\ldots,\mu_{N-1}^{*}\right\} $ \end_inset je optimální řídící strategie pro \color black základní \color inherit problém a předpokládejme, že když aplikujeme řízení \begin_inset Formula $\pi^{*}$ \end_inset , daný stav \begin_inset Formula $x_{i}$ \end_inset se vyskytne v čase \begin_inset Formula $i$ \end_inset s pozitivní pravděpodobností. Uvažujme podproblém, kdy ve stavu \begin_inset Formula $x_{i}$ \end_inset a čase \begin_inset Formula $i$ \end_inset chceme minimalizovat \emph on náklady na pokračování \emph default (v anglické literatuře označováno jako \color black \begin_inset Quotes gld \end_inset cost-to-go \color inherit \begin_inset Quotes grd \end_inset ) od času \begin_inset Formula $i$ \end_inset do \begin_inset Formula $N$ \end_inset \begin_inset Formula \[ \mathbf{E}\left\{ g_{N}(x_{N})+\sum_{k=i}^{N-1}g_{k}(x_{k},\mu_{k}(x_{k}),w_{k})\right\} \] \end_inset Potom úsek strategie \family roman \series medium \shape up \size normal \emph off \bar no \noun off \color none \begin_inset Formula $\left\{ \mu_{i}^{*},\mu_{i+1}^{*},\ldots,\mu_{N-1}^{*}\right\} $ \end_inset je optimální pro tento podproblém. \begin_inset VSpace medskip \end_inset \end_layout \begin_layout Standard Intuitivně je princip optimality velmi jednoduchý. Jestliže úsek strategie \begin_inset Formula $\left\{ \mu_{i}^{*},\mu_{i+1}^{*},\ldots,\mu_{N-1}^{*}\right\} $ \end_inset nebude optimální, budeme schopni dále zredukovat cenu přechodem k optimální strategii pro podproblém. \end_layout \begin_layout Standard Princip optimality umožňuje optimální strategii konstruovat postupně. Nejdříve nalezneme optimální strategii pro koncový podproblém zahrnující poslední krok. Poté rozšiřujeme podproblém od konce přidáním předposledního kroku a tak dále. Takto může být vytvořena optimální strategie pro celý problém. \end_layout \begin_layout Standard Algoritmus dynamického programování je tedy založen na následující myšlence: Algoritmus pracuje iterativně a řeší \color black koncové \color inherit podproblémy pro daný časový úsek, při tom využívá řešení předchozích \color black koncových \color inherit podproblémů pro kratší časové úseky. Převzato z \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset . \end_layout \begin_layout Subsubsection Formulace algoritmu dynamického programování \end_layout \begin_layout Standard Podle \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset , pro každý počáteční stav \begin_inset Formula $x_{0}$ \end_inset , je optimální cena \begin_inset Formula $J^{*}(x_{0})$ \end_inset základního problému rovna \begin_inset Formula $J_{0}(x_{0})$ \end_inset , získané z posledního kroku následujícího algoritmu, který prochází zpět časy od \begin_inset Formula $N-1$ \end_inset do \begin_inset Formula $0$ \end_inset : \begin_inset Formula \[ J_{N}(x_{N})=g_{N}(x_{N})\] \end_inset \end_layout \begin_layout Standard \begin_inset Formula \begin{equation} J_{k}(x_{k})=\min_{u_{k}\in U_{k}(x_{k})w_{k}}\mathbf{E}\left\{ g_{k}(x_{k},u_{k},w_{k})+J_{k+1}(f_{k}(x_{k},u_{k},w_{k}))\right\} \label{eq:Jkeqmin}\end{equation} \end_inset \begin_inset Formula \[ k=0,1,\ldots,N-1\] \end_inset \end_layout \begin_layout Standard kde je očekávaná hodnota počítána podle náhodné veličiny \begin_inset Formula $w_{k}$ \end_inset , která obecně závisí na \begin_inset Formula $x_{k}$ \end_inset a \begin_inset Formula $u_{k}$ \end_inset . Dále, když \begin_inset Formula $u_{k}^{*}=\mu_{k}^{*}(x_{k})$ \end_inset minimalizuje pravou stranu rovnice \begin_inset CommandInset ref LatexCommand eqref reference "eq:Jkeqmin" \end_inset pro každé \begin_inset Formula $x_{k}$ \end_inset a \begin_inset Formula $k$ \end_inset , stretegie \begin_inset Formula $\pi*=\left\{ \mu_{1}^{*},\ldots,\mu_{N-1}^{*}\right\} $ \end_inset je optimální. \begin_inset VSpace medskip \end_inset \end_layout \begin_layout Standard Hodnotu \begin_inset Formula $J_{k}(x_{k})$ \end_inset je možno interpretovat jako optimální cenu pro \emph on \begin_inset Formula $(N-k)$ \end_inset \emph default -tý krok problému začínajícího ve stavu \begin_inset Formula $x_{k}$ \end_inset a čase \begin_inset Formula $k$ \end_inset , a končícího v čase \begin_inset Formula $N$ \end_inset . Následně označujeme \begin_inset Formula $J_{k}(x_{k})$ \end_inset náklady na pokračování ( \color black \begin_inset Quotes gld \end_inset cost-to-go \color inherit \begin_inset Quotes grd \end_inset ) ve stavu \begin_inset Formula $x_{k}$ \end_inset a čase \begin_inset Formula $k$ \end_inset , a \begin_inset Formula $J_{k}$ \end_inset označujeme jako funkci nákladů na pokračování ( \color black \begin_inset Quotes gld \end_inset cost-to-go \color inherit function \begin_inset Quotes grd \end_inset ) v čase \begin_inset Formula $k$ \end_inset . \end_layout \begin_layout Standard Ideálně bychom chtěli využít algoritmus dynamického programování k získání \begin_inset Formula $J_{k}$ \end_inset vyjádřené v uzavřeném tvaru nebo k získání optimální strategie. Existuje mnoho případů, kdy je daná úloha řešitelná analyticky, obzvláště za zjednodušujících předpokladů. To je velmi užitečné zejména pro lepší náhled do problematiky a jako vodítko pro složitější modely. Avšak ve většíně případů není analytické řešení možné, pak je třeba použít numerické řešení pomocí algoritmu dynamického programování. Tento přístup může být časově velmi náročný, zejména minimalizaci v rovnici \begin_inset CommandInset ref LatexCommand eqref reference "eq:Jkeqmin" \end_inset je třeba provést pro každou hodnotu \begin_inset Formula $x_{k}$ \end_inset . Stavový prostor musí být diskretizován, nejedná-li se o konečnou množinu a výpočetní nároky pak narůstají proporcionálně k počtu možných hodnot \begin_inset Formula $x_{k}$ \end_inset . Nicméně dynamické programování je pouze obecný přístup pro iterativní optimaliz aci při uvažování nejistoty v systému. \end_layout \begin_layout Subsection Úplná a neúplná stavová informace \end_layout \begin_layout Standard V optimálním případě by bylo možno měřit všechny stavové veličiny systému a na jejich základě libovolným způsobem upravovat jeho dynamické vlastnosti. Ve skutečnosti ale zpravidla není možné všechny stavy změřit a musíme se rozhodovat pouze na základě informací, které máme k dispozici, pak mluvíme o \emph on neúplné informaci o stavu systému \emph default \begin_inset CommandInset citation LatexCommand cite key "StechaTDS,BertsekasDPOC" \end_inset . Může to být způsobeno například nedostupností hodnot některých stavů, použité měřící přístroje mohou být nepřesné nebo náklady na získání přesné hodnoty stavu mohou být příliš omezující. Případy tohoto typu modelujeme zpravidla tak, že v každém kroku regulátor obdrží jisté pozorování skutečné hodnoty stavu, které ovšem může být ovlivněno a narušeno stochastickou nejistotou. Teoreticky se však problém s neúplnou informací o stavu neodlišuje od úloh s úplnou stavovou informací, protože existují způsoby, jak převést (redukovat) systém s neúplnou informací na systém s úplnou. Tyto postupy obecně vedou na algoritmy využívající dynamické programování, ale jsou výpočetně mnohem náročnější, než v případě úplné informace. Dva možné postupy redukce převzaté z \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset budou následovat po formulaci problému: \end_layout \begin_layout Subsubsection Formulace problému s neúplnou informací o stavu \end_layout \begin_layout Standard Nejdříve formulujme základní problém s neúplnou stavovou informací, který následně redukujeme na systém s informací úplnou. Uvažujme rozšíření základního problému \begin_inset CommandInset ref LatexCommand ref reference "eq:zakladniproblem" \end_inset , kde ale regulátor, namísto přístupu ke stavu systému, získává pouze pozorování \begin_inset Formula $z_{k}$ \end_inset ve tvaru \begin_inset Formula \begin{equation} z_{0}=h_{0}(x_{0},v_{0}),\quad z_{k}=h_{k}(x_{k},u_{k-1},v_{k}),\quad k=1,2,\ldots,N-1,\label{eq:zaklprobneuplnystav}\end{equation} \end_inset kde \begin_inset Formula $v_{k}$ \end_inset reprezentuje náhodnou poruchu pozorování charakterizovanou rozdělením pravděpod obnosti \begin_inset Formula $P_{v_{k}}$ \end_inset , která závisí na současném stavu a všech předchozích stavech, řízeních a poruchách. Dále také počáteční stav \begin_inset Formula $x_{0}$ \end_inset považujeme za náhodnou veličinu s rozdělením \begin_inset Formula $P_{x_{0}}$ \end_inset . \end_layout \begin_layout Standard Soubor informací dostupných regulátoru v čase \begin_inset Formula $k$ \end_inset označme \begin_inset Formula $I_{k}$ \end_inset informačním vektorem. Tedy \begin_inset Formula \begin{eqnarray*} I_{k} & = & (z_{0},\ldots,z_{k},u_{0},\ldots,u_{k-1}),\quad k=1,\ldots,N-1,\\ I_{0} & = & z_{0}.\end{eqnarray*} \end_inset Uvažujme množinu přípustných řízení jako posloupnost funkcí \begin_inset Formula $\pi=\{\mu_{0},\ldots,\mu_{N-1}\}$ \end_inset , kde každá funkce \begin_inset Formula $\mu_{k}$ \end_inset přiřazuje informačnímu vektoru \begin_inset Formula $I_{k}$ \end_inset řízení \begin_inset Formula $\mu_{k}(I_{k})\in U_{k}$ \end_inset , pro všechna \begin_inset Formula $I_{k}$ \end_inset , kde \begin_inset Formula $k=0,\ldots,N-1$ \end_inset . Chceme najít přípustnou řídící strategii, to jest posloupnost \begin_inset Formula $\pi$ \end_inset , která minimalizuje očekávanou ztrátu \begin_inset Formula \[ J_{\pi}=\mathbf{E}\left\{ g_{N}(x_{N})+\sum_{k=0}^{N-1}g_{k}\left(x_{k},\mu_{k}(I_{k}),w_{k}\right)\right\} ,\] \end_inset kde je očekávaná hodnota počítána přes náhodné veličiny \begin_inset Formula $x_{0}$ \end_inset a \begin_inset Formula $w_{k},v_{k}$ \end_inset pro \begin_inset Formula $k=0,\ldots,N-1$ \end_inset . Veličiny \begin_inset Formula $x_{k}$ \end_inset a \begin_inset Formula $z_{k}$ \end_inset se vypočítají z rovnic \begin_inset CommandInset ref LatexCommand ref reference "eq:zakladniproblem" \end_inset respektive \begin_inset CommandInset ref LatexCommand ref reference "eq:zaklprobneuplnystav" \end_inset , přičemž v nich položíme \begin_inset Formula $u_{k}=\mu_{k}(I_{k})$ \end_inset . \end_layout \begin_layout Subsubsection Redukce na systém s úplnou stavovou informací \end_layout \begin_layout Standard Tento postup je založen na myšlence definovat nový systém, jehož stav v čase \begin_inset Formula $k$ \end_inset je množina všech hodnot, kterých může využít regulátor při tvorbě řízení. Jako stav nového systému tedy volíme informační vektor \begin_inset Formula $I_{k}$ \end_inset a získáme systém \begin_inset Formula \begin{equation} I_{k+1}=(I_{k,}z_{k+1},u_{k}),\quad I_{0}=z_{0},\quad k=0,\ldots,N-2.\label{eq:rednewsystem}\end{equation} \end_inset Na tento systém povahy základního problému s úplnou informací můžeme pohlížet tak, že \begin_inset Formula $I_{k}$ \end_inset je stav. Řízení \begin_inset Formula $u_{k}$ \end_inset a pozorování \begin_inset Formula $z_{k}$ \end_inset lze pak chápat jako náhodné poruchy. Dále rozdělení pravděpodobnosti \begin_inset Formula $z_{k+1}$ \end_inset závisí explicitně pouze na stavu \begin_inset Formula $I_{k}$ \end_inset a řízení \begin_inset Formula $u_{k}$ \end_inset . Ztrátovou funkci vyjádřenou pro nový systém je možno zapsat jako \begin_inset Formula \[ \mathbf{E}\left\{ g_{k}\left(x_{k},u_{k},w_{k}\right)\right\} =\mathbf{E}\left\{ \mathbf{E}_{x_{k},w_{k}}\left\{ g_{k}\left(x_{k},u_{k},w_{k}\right)\mid I_{k},u_{k}\right\} \right\} .\] \end_inset Tedy ztráta během jednoho kroku vyjádřená jako funkce nového stavu \begin_inset Formula $I_{k}$ \end_inset a řízení \begin_inset Formula $u_{k}$ \end_inset je \begin_inset Formula \begin{equation} \tilde{g}_{k}(I_{k,}u_{k})=\mathbf{E}_{x_{k},w_{k}}\left\{ g_{k}\left(x_{k},u_{k},w_{k}\right)\mid I_{k},u_{k}\right\} .\label{eq:rednewztrata}\end{equation} \end_inset Původní základní problém s neúplnou stavovou informací byl tedy převeden na úlohu s úplnou stavovou informací s rovnicí popisující systém \begin_inset CommandInset ref LatexCommand ref reference "eq:rednewsystem" \end_inset a ztrátou během jednoho kroku \begin_inset CommandInset ref LatexCommand ref reference "eq:rednewztrata" \end_inset . Nyní je pro něj možno napsat algoritmus dynamického programování. \color blue (možná sem dát i rovnice DP) \end_layout \begin_layout Subsubsection Postačující statistika \end_layout \begin_layout Standard Při užití algoritmu dynamického programování za neúplné stavové informace je hlavní problém v jeho vyhodnocování ve stavovém prostoru, jehož dimenze neustále roste. S každým dalším měřením dimenze stavu a tedy informační vektor \begin_inset Formula $I_{k}$ \end_inset narůstá, proto se snažíme redukovat množství dat skutečně potřebných pro účely řízení. Hledáme tedy popis známý jako \emph on postačující statistika \emph default , který bude mít menší dimenzi než \begin_inset Formula $I_{k}$ \end_inset ale současně zahrne veškerý důležitý obsah \begin_inset Formula $I_{k}$ \end_inset potřebný pro řízení. Jako postačující statistiku označme funkci \begin_inset Formula $S_{k}$ \end_inset informačního vektoru \begin_inset Formula $I_{k}$ \end_inset , tedy \begin_inset Formula $S_{k}(I_{k})$ \end_inset takovou, že minimalizuje ztrátu v algoritmu dynamického programování přes všechna přípustná řízení. Což můžeme zapsat pro vhodnou funkci \begin_inset Formula $H_{k}$ \end_inset jako \begin_inset Formula \begin{eqnarray*} J_{k}(I_{k}) & = & \min_{u_{k}\in U_{k}}H_{k}(S_{k}(I_{k}),u_{k}).\end{eqnarray*} \end_inset Po funkci \begin_inset Formula $S_{k}$ \end_inset samozřejmě chceme, aby byla charakterizována menší množinou čísel, než informační vektor \begin_inset Formula $I_{k}$ \end_inset , abychom získaly výhody z jejího použití. Obecně existuje mnoho funkcí, které mohou sloužit jako postačující statistika. Triviálním příkladem může být identita \begin_inset Formula $S_{k}(I_{k})=I_{k}$ \end_inset . \end_layout \begin_layout Standard Závisí-li rozdělení pravděpodobnosti poruchy pozorování \begin_inset Formula $v_{k}$ \end_inset explicitně pouze na bezprostředně předcházejícím stavu, řízení a poruše systému, tedy na \begin_inset Formula $x_{k},u_{k},w_{k}$ \end_inset a nezávisí na předchozích hodnotách \begin_inset Formula $x_{k-1},\ldots,x_{0},u_{k-1},\ldots,u_{0},w_{k-1},\ldots,w_{0},v_{k-1},\ldots,v_{0}$ \end_inset můžeme za postačující statistiku volit podmíněné rozdělení pravděpodobnosti \begin_inset Formula $P_{x_{k}|I_{k}}$ \end_inset , o kterém lze ukázat (viz \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset ), že \begin_inset Formula \[ J_{k}(I_{k})=\min_{u_{k}\in U_{k}}H_{k}(P_{x_{k}|I_{k}},u_{k})=\overline{J}_{k}(P_{x_{k}|I_{k}}),\] \end_inset kde \begin_inset Formula $H_{k}$ \end_inset a \begin_inset Formula $\overline{J}_{k}$ \end_inset jsou vhodné funkce. Optimální řízení pak získáme ve tvaru funkcí podmíněného rozdělení pravděpodobn osti \begin_inset Formula $\mu_{k}(I_{k})=\overline{\mu}_{k}(P_{x_{k}|I_{k}})$ \end_inset pro \begin_inset Formula $k=0,\ldots,N-1$ \end_inset . Tato reprezentace může být velmi užitečná, protože nám umožňuje rozložit optimální řízení na dvě nezávislé časti: \end_layout \begin_layout Enumerate \emph on pozorovatel \emph default (estimátor), který v čase \begin_inset Formula $k$ \end_inset použije měření \begin_inset Formula $z_{k}$ \end_inset a řízení \begin_inset Formula $u_{k-1}$ \end_inset k vygenerování rozdělení pravděpodobnosti \begin_inset Formula $P_{x_{k}|I_{k}}$ \end_inset \end_layout \begin_layout Enumerate \emph on ovladač \emph default (regulátor), který generuje vstupy (řízení) pro systém jako funkci rozdělení pravděpodobnosti \begin_inset Formula $P_{x_{k}|I_{k}}$ \end_inset \end_layout \begin_layout Standard Tento rozklad pak umožňuje navrhovat každou z částí samostatně podle charakteru konkrétní úlohy. \end_layout \begin_layout Subsection Kalmanův filtr \end_layout \begin_layout Standard Chceme řešit následující problém, viz \begin_inset CommandInset citation LatexCommand cite key "StechaTDS" \end_inset : Máme lineární systém s neúplnou stavovou informací a snažíme se odhadnout (rekonstruovat, estimovat) stav systému z měřitelných vstupních a výstupních veličin. Dále předpokládejme, že měření výstupu a popřípadě i vstupu je zatíženo chybou měření. Tyto nepřesnosti měření můžeme modelovat jako aditivní šum. Odhadování (rekonstrukci, estimaci) potom navrhujeme pomocí stochastických metod. Řešení vede na takzvaný \emph on Kalmanův filtr \emph default . \end_layout \begin_layout Standard \begin_inset VSpace medskip \end_inset \end_layout \begin_layout Standard Následující formulace problému a popis algoritmu Kalmanova filtru je převzat z \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset , kde lze také nalézt odvození příslušných rovnic: Máme dva náhodné vektory \begin_inset Formula $x$ \end_inset a \begin_inset Formula $y$ \end_inset , které jsou svázány \color red společným rozdělením pravděpodobnosti \color inherit ( \begin_inset Quotes gld \end_inset joint probability distribution \begin_inset Quotes grd \end_inset ) tak, že hodnota jednoho poskytuje informaci o hodnotě druhého. Známe hodnotu \begin_inset Formula $y$ \end_inset a chceme určit (odhadnout) hodnotu \begin_inset Formula $x$ \end_inset tak, aby střední kvadratická odchylka mezi \begin_inset Formula $x$ \end_inset a jeho odhadem byla minimální. \end_layout \begin_layout Standard Takový odhad můžeme zístat v nejjednodušším případě metodou nejmenších čtverců, ale pro tento způsob je třeba velkého počtu měření. Jako lepší způsob se ale jeví využít sekvenční struktury problému a iterativně použít Kalmanův filtr, kdy odhad v čase \begin_inset Formula $k+1$ \end_inset získáme na základě jednoduchých rovnic pouze z předchozího odhadu a nového měření v čase \begin_inset Formula $k$ \end_inset , žádná předchozí měření nejsou explicitně zahrnuta. \end_layout \begin_layout Standard V dalším textu označme \begin_inset Formula $\hat{x}_{k|k-1}$ \end_inset apriorní odhad stavu, tedy odhad stavu v čase \begin_inset Formula $k$ \end_inset na základě informací až do času \begin_inset Formula $k-1$ \end_inset . Analogicky \begin_inset Formula $\Sigma_{k|k-1}$ \end_inset označuje apriorní kovarianční matici. Aposteriorní odhad stavu označme \begin_inset Formula $\hat{x}_{k|k}$ \end_inset , to jest odhad v čase \begin_inset Formula $k$ \end_inset na základě informačí až do času \begin_inset Formula $k$ \end_inset . Aposteriorní kovarianční matice je pak označena \begin_inset Formula $\Sigma_{k|k}$ \end_inset . \end_layout \begin_layout Standard \begin_inset VSpace bigskip \end_inset \end_layout \begin_layout Subsubsection System \end_layout \begin_layout Standard Uvažujme lineární dynamický systém bez řízení ( \begin_inset Formula $u_{k}\equiv0$ \end_inset ) ve tvaru \begin_inset Formula \[ x_{k+1}=A_{k}x_{k}+w_{k},\; k=0,1,\ldots,N-1,\] \end_inset kde \begin_inset Formula $x_{k}$ \end_inset je vektor stavu, \begin_inset Formula $w_{k}$ \end_inset vektor náhodné poruchy a matice \begin_inset Formula $A_{k}$ \end_inset předpokládáme známé. Dále rovnice měření je \begin_inset Formula \[ z_{k}=C_{k}x_{k}+v_{k},\; k=0,1,\ldots,N-1,\] \end_inset kde \begin_inset Formula $z_{k}$ \end_inset je vektor pozorování (měřených veličin) a \begin_inset Formula $v_{k}$ \end_inset vektor šumu. Nechť \begin_inset Formula $x_{0},w_{0},\ldots,w_{N-1},v_{0},\ldots,v_{N-1}$ \end_inset jsou vektory nezávislých náhodných veličin s daným rozdělením pravděpodobnosti, takovým, že \begin_inset Formula \[ \mathrm{E}\{w_{k}\}=\mathrm{E}\{v_{k}\}=0,\; k=0,1,\ldots,N-1.\] \end_inset Označme \begin_inset Formula \[ S=\mathrm{E}\left\{ \left(x_{0}-\mathrm{E}\{x_{0}\}\right)\left(x_{0}-\mathrm{E}\{x_{0}\}\right)^{T}\right\} ,\; M_{k}=\mathrm{E}\{w_{k}w_{k}^{T}\},\; N_{k}=\mathrm{E}\{v_{k}v_{k}^{T}\},\] \end_inset a nechť matice \begin_inset Formula $N_{k}$ \end_inset pozitivně definitní pro všechny časy \begin_inset Formula $k$ \end_inset . \end_layout \begin_layout Subsubsection Algoritmus Kalmanova filtru \end_layout \begin_layout Standard Předpokládejme, že máme spočítaný odhad \begin_inset Formula $\hat{x}_{k|k-1}$ \end_inset společně s kovarianční maticí \begin_inset Formula $\Sigma_{k|k-1}=\mathrm{E}\left\{ \left(x_{k}-\hat{x}_{k|k-1}\right)\left(x_{k}-\hat{x}_{k|k-1}\right)^{T}\right\} $ \end_inset . V čase \begin_inset Formula $k$ \end_inset získáme další měření \begin_inset Formula $z_{k}=C_{k}x_{k}+v_{k}$ \end_inset . Nyní můžeme získat aposteriorní odhad stavu \begin_inset Formula $\hat{x}_{k|k}$ \end_inset v čase \begin_inset Formula $k$ \end_inset jako \begin_inset Formula \begin{equation} \hat{x}_{k|k}=\hat{x}_{k|k-1}+\Sigma_{k|k-1}C_{k}^{T}\left(C_{k}\Sigma_{k|k-1}C_{k}^{T}+N_{k}\right)^{-1}\left(z_{k}-C_{k}\hat{x}_{k|k-1}\right),\label{eq:kalmanaposkk}\end{equation} \end_inset dále pak apriorní odhad stavu \begin_inset Formula $\hat{x}_{k+1|k}$ \end_inset v čase \begin_inset Formula $k+1,$ \end_inset tedy \begin_inset Formula $\hat{x}_{k+1|k}=A_{k}\hat{x}_{k|k}$ \end_inset . Apriorní kovarianční matici v čase \begin_inset Formula $k+1$ \end_inset vypočítáme z \begin_inset Formula \[ \Sigma_{k+1|k}=A_{k}\Sigma_{k|k}A_{k}^{T}+M_{k},\] \end_inset kde aposteriorní kovarianční matici \begin_inset Formula $\Sigma_{k|k}=\mathrm{E}\left\{ \left(x_{k}-\hat{x}_{k|k}\right)\left(x_{k}-\hat{x}_{k|k}\right)^{T}\right\} $ \end_inset můžeme získat z rovnice \begin_inset Formula \[ \Sigma_{k|k}=\Sigma_{k|k-1}-\Sigma_{k|k-1}C_{k}^{T}\left(C_{k}\Sigma_{k|k-1}C_{k}^{T}+N_{k}\right)^{-1}C_{k}\Sigma_{k|k-1}.\] \end_inset Přidáním počátečních podmínek \begin_inset Formula $\hat{x}_{0|-1}=\mathrm{E}\{x_{0}\}$ \end_inset a \begin_inset Formula $\Sigma_{0|-1}=S$ \end_inset získáme \emph on algoritmus Kalmanova filtru \emph default , který ve své podstatě rekurzivně generuje posloupnost lineárních odhadů založených na metodě nejmenších čtverců. \end_layout \begin_layout Standard Dále je možno vyjádřit rovnici \begin_inset CommandInset ref LatexCommand ref reference "eq:kalmanaposkk" \end_inset ve tvaru \begin_inset Formula \[ \hat{x}_{k|k}=A_{k-1}\hat{x}_{k-1|k-1}+\Sigma_{k|k}C_{k}^{T}N_{k}^{-1}\left(z_{k}-C_{k}A_{k-1}\hat{x}_{k-1|k-1}\right),\] \end_inset který při uvažování systému se vstupem \begin_inset Formula \[ x_{k+1}=A_{k}x_{k}+B_{k}u_{k}+w_{k},\; k=0,1,\ldots,N-1,\] \end_inset umožňuje vypočítat rekurzivně aposteriorní odhady stavů \begin_inset Formula $\hat{x}_{k|k}$ \end_inset v časech \begin_inset Formula $k$ \end_inset z rovnice \begin_inset Formula \[ \hat{x}_{k|k}=A_{k-1}\hat{x}_{k-1|k-1}+B_{k-1}u_{k-1}+\Sigma_{k|k}C_{k}^{T}N_{k}^{-1}\left(z_{k}-C_{k}A_{k-1}\hat{x}_{k-1|k-1}\right),\] \end_inset přičemž rovnice pro výpočet aposteriorní kovarianční matice \begin_inset Formula $\Sigma_{k|k}$ \end_inset zůstávají nezměněny. \end_layout \begin_layout Subsection Deterministické systémy se spojitým časem \end_layout \begin_layout Standard I když zpravidla pracujeme s diskrétními systémy, zejména z důvodů výpočtů na počítači, teorie optimálního řízení spojitých systémů může být velmi užitečná. Poskytuje totiž důležité principy, které jsou velmi často používány při návrhu algoritmů pro duální řízení. Konkrétně se jedná o Hamilton-Jacobi-Bellmanovu rovnost a Pontryaginův princip minima. \end_layout \begin_layout Subsubsection Spojitý systém \end_layout \begin_layout Standard Dynamický systém se spojitým časem uvažujeme dle \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset ve tvaru \begin_inset Formula \begin{eqnarray} \dot{x}(t) & = & f(x(t),u(t)),\;0\leq t\leq T,\label{eq:spojsystemHJBP}\\ x(0) & = & x_{0},\nonumber \end{eqnarray} \end_inset kde \begin_inset Formula $x(t)$ \end_inset je stavový vektor v čase \begin_inset Formula $t$ \end_inset , \begin_inset Formula $\dot{x}(t)$ \end_inset je vektor prvních derivací podle času v čase \begin_inset Formula $t$ \end_inset , \begin_inset Formula $u(t)\in U$ \end_inset je řídící vektor v čase \begin_inset Formula $t$ \end_inset , \begin_inset Formula $U$ \end_inset je množina omezení řízení a \begin_inset Formula $T$ \end_inset je časový horizont. O funkci \begin_inset Formula $f$ \end_inset předpokládáme, že je spojitě diferencovatelná vzhledem k \begin_inset Formula $x$ \end_inset a spojitá vzhledem k \begin_inset Formula $u$ \end_inset . Rovnice \begin_inset CommandInset ref LatexCommand ref reference "eq:spojsystemHJBP" \end_inset představuje soustavu \begin_inset Formula $n$ \end_inset diferenciálních rovnic prvního řádu. Naším cílem je nalézení přípustné řídící trajektorie \begin_inset Formula $\left\{ u(t)\mid t\in[0,T]\right\} $ \end_inset a odpovídající stavové trajektorie \family roman \series medium \shape up \size normal \emph off \bar no \noun off \color none \begin_inset Formula $\left\{ x(t)\mid t\in[0,T]\right\} $ \end_inset takové, že minimalizují ztrátovou funkci ve tvaru \begin_inset Formula \[ h(x(T))+\int_{0}^{T}g\left(x(t),u(t)\right)dt,\] \end_inset o funkcích \begin_inset Formula $g$ \end_inset a \begin_inset Formula $h$ \end_inset předpokládáme, že jsou spojitě diferencovatelné vzhledem k \begin_inset Formula $x$ \end_inset a \begin_inset Formula $g$ \end_inset je spojitá vzhledem k \begin_inset Formula $u$ \end_inset . \end_layout \begin_layout Subsubsection Hamilton-Jacobi-Bellmanova rovnost \end_layout \begin_layout Standard Hamilton-Jacobi-Bellmanova rovnost je parciální diferenciální rovnicí, která je splněna optimální funkcí nákladů na pokračování \begin_inset Formula $J^{*}(t,x)$ \end_inset . Tato rovnice je analogií algoritmu dynamického programování ve spojitém čase. Rovnici lze psát podle \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset ve tvaru \begin_inset Formula \begin{eqnarray} 0 & = & \min_{u\in U}\left[g(x,u)+\nabla_{t}J^{*}(t,x)+\nabla_{x}J^{*}(t,x)^{T}f(x,u)\right],\quad\forall t,x,\label{eq:hjbrovnostJ}\\ J^{*}(T,x) & = & h(x).\nonumber \end{eqnarray} \end_inset Jedná se tedy o parciální diferenciální rovnici s okrajovou podmínkou. O funkci \begin_inset Formula $J^{*}(t,x)$ \end_inset jsme předpokládali diferencovatelnost, apriorně ale její diferencovatelnost neznáme a tedy nevíme, jestli \begin_inset Formula $J^{*}(t,x)$ \end_inset řeší rovnici \begin_inset CommandInset ref LatexCommand ref reference "eq:hjbrovnostJ" \end_inset . Můžeme však použít následující tvrzení, jehož formulaci i důkaz lze nalézt v \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset : \end_layout \begin_layout Description Věta \begin_inset space \space{} \end_inset o \begin_inset space \space{} \end_inset dostatečnosti: \begin_inset ERT status open \begin_layout Plain Layout ~ \end_layout \end_inset \begin_inset Newline newline \end_inset Nechť je funkce \begin_inset Formula $V(t,x)$ \end_inset spojitě diferencovatelná vzhledem k \begin_inset Formula $t$ \end_inset a \begin_inset Formula $x$ \end_inset a nechť je řešením Hamilton-Jacobi-Bellmanovy rovnosti: \begin_inset Formula \begin{eqnarray} 0 & = & \min_{u\in U}\left[g(x,u)+\nabla_{t}V(t,x)+\nabla_{x}V(t,x)^{T}f(x,u)\right],\quad\forall t,x,\label{eq:hjbrovnostV}\\ V(T,x) & = & h(x),\quad\forall x.\nonumber \end{eqnarray} \end_inset Předpokládejme dále, že \begin_inset Formula $\mu^{*}(t,x)$ \end_inset dosáhne minima v rovnosti \begin_inset CommandInset ref LatexCommand ref reference "eq:hjbrovnostV" \end_inset pro všechna \begin_inset Formula $t$ \end_inset a \begin_inset Formula $x$ \end_inset . Nechť \family roman \series medium \shape up \size normal \emph off \bar no \noun off \color none \begin_inset Formula $\left\{ x^{*}(t)\mid t\in[0,T]\right\} $ \end_inset označuje stavovou trajektorii získanou při dané počáteční podmínce \begin_inset Formula $x^{*}(0)=x_{0}$ \end_inset a řídící trajektorii \family default \series default \shape default \size default \emph default \bar default \noun default \color inherit \begin_inset Formula $u^{*}(t)=\mu^{*}(t,x^{*}(t)),\; t\in[0,T]$ \end_inset . Pak \begin_inset Formula $V$ \end_inset je rovno optimální funkci nákladů na pokračování, tedy \begin_inset Formula \[ V(t,x)=J^{*}(t,x),\quad\forall t,x.\] \end_inset Navíc řídící trajektorie \begin_inset Formula $\left\{ u^{*}(t)\mid t\in[0,T]\right\} $ \end_inset je optimální. \end_layout \begin_layout Subsubsection Pontryaginův princip minima \end_layout \begin_layout Standard Pontryaginův princip minima je důležitým teorémem optimálního řízení. Poskytuje nutnou (ne však postačující) podmínku pro optimální trajektorii, je úzce spřízněn s Hamilton-Jacobi-Bellmanovou rovností a lze ho z ní podle \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset také odvodit. Princip minima je výhodné formulovat pomocí Hamiltoniánu. Označme \begin_inset Formula $p$ \end_inset gradient optimální funkce nákladů na pokračování pro optimální stavovou trajektorii \begin_inset Formula $p(t)=\nabla_{x}J^{*}\left(t,x^{*}(t)\right)$ \end_inset a definujme Hamiltonián jako funkci zobrazující trojice vektorů \begin_inset Formula $(x,u,p)$ \end_inset do reálných čísel \begin_inset Formula \[ H(x,u,p)=g(x,u)+p^{T}f(x,u).\] \end_inset Rovnice pro systém pak může být zapsána v kompaktním tvaru \begin_inset Formula \[ \dot{x}^{*}(t)=\nabla_{p}H\left(x^{*}(t),u^{*}(t),p(t)\right).\] \end_inset Obdobně může být zapsána pro \begin_inset Formula $p$ \end_inset takzvaná \emph on adjungovaná rovnice \emph default \begin_inset Formula \[ \dot{p}(t)=-\nabla_{x}H\left(x^{*}(t),u^{*}(t),p(t)\right).\] \end_inset Pontryaginův princip minima je podle \begin_inset CommandInset citation LatexCommand cite key "BertsekasDPOC" \end_inset formulován následovně: \end_layout \begin_layout Description Princip \begin_inset space \space{} \end_inset minima: \begin_inset ERT status open \begin_layout Plain Layout ~ \end_layout \end_inset \begin_inset Newline newline \end_inset Nechť \family roman \series medium \shape up \size normal \emph off \bar no \noun off \color none \begin_inset Formula $\left\{ u^{*}(t)\mid t\in[0,T]\right\} $ \end_inset je optimální řídící trajektorie a nechť \begin_inset Formula $\left\{ x^{*}(t)\mid t\in[0,T]\right\} $ \end_inset je odpovídající stavová trajektorie, to jest \begin_inset Formula \[ \dot{x}^{*}(t)=f\left(x^{*}(t),u^{*}(t)\right),\quad x^{*}(0)=x_{0}.\] \end_inset Nechť dále \begin_inset Formula $p(t)$ \end_inset je řešením adjungované rovnice \begin_inset Formula \[ \dot{p}(t)=-\nabla_{x}H\left(x^{*}(t),u^{*}(t),p(t)\right),\] \end_inset s okrajovou podmínkou \begin_inset Formula $p(T)=\nabla h\left(x^{*}(T)\right)$ \end_inset . Pak pro všechna \begin_inset Formula $t\in[0,T]$ \end_inset \begin_inset Formula \[ u^{*}(t)=\arg\min_{u\in U}H\left(x^{*}(t),u,p(t)\right).\] \end_inset Navíc existuje konstanta \begin_inset Formula $C$ \end_inset taková, že \begin_inset Formula \[ H\left(x^{*}(t),u^{*}(t),p(t)\right)=C,\quad\forall t\in[0,T].\] \end_inset \end_layout \begin_layout Subsection Algoritmy pro duální řízení \end_layout \begin_layout Standard Metody pro nalezení optimálního řízení lze obecně rozdělit do dvou základních kategorií na \emph on globální \emph default a \emph on lokální \emph default viz \begin_inset CommandInset citation LatexCommand cite key "TodorovWeiweiILQG,TodorovTassaILDP" \end_inset \emph on . \emph default \end_layout \begin_layout Standard Globální metody, používané zejména v posilovaném učení \color black ( \begin_inset Quotes gld \end_inset Reinforcement Learning \color inherit \begin_inset Quotes grd \end_inset ), jsou založeny na na \color black Bellmanově principu optimality, Hamilton-Jacobi-Bellmanově rovnosti \color inherit a dynamickém programování. Tyto algoritmy hledají globálně optimální zpětnovazební řízení pro všechny stavy obecného stochastického systému a proto podléhají nebezpečí \begin_inset Quotes gld \end_inset problému dimenzionality \begin_inset Quotes grd \end_inset nebo také rozměrnosti (z anglického \begin_inset Quotes eld \end_inset curse of dimensionality \begin_inset Quotes erd \end_inset doslovně - \emph on kletba rozměrnosti \emph default ). Jednoduše můžeme tento problém chápat tak, že při numerickém řešení úlohy jsou počítačem procházeny všechny body diskretizovaného stavového a řídícího prostoru jejichž počet s rostoucím počtem dimenzí extrémně (exponenciálně) rychle roste. Výpočet pro mnohadimenzionální úlohy se pak stává co do paměťových nároků, ale hlavně z hlediska výpočetního času prakticky nerealizovatelným. \end_layout \begin_layout Standard Lokální metody, častěji studované v teorii řízení, souvisí s \color black Pontryaginovým principem maxima \color inherit . Jejich podstatou je nalezení řízení, které je pouze lokálně optimální v okolí nějaké \begin_inset Quotes gld \end_inset extremalní \begin_inset Quotes grd \end_inset trajektorie. Většinou je užito deterministických prostředků jako řešení soustavy obyčejných diferenciálních rovnic (střelbou, relaxací, \color red uspořádáním - collocation \color inherit nebo \color red spádem gradientu - gradient descent \color inherit ). Tento přístup ale vede na přímovazební \color red \color black řízení \color red \color inherit a nezle užít pro stochastické úlohy, vyhýbá se ale problému dimenzionality, což umožňuje řešit i komplexnější problémy. \end_layout \begin_layout Standard V poslední době je snaha vyvíjet nové algoritmy, které kombinují výhody obou výše zmíněných přístupů. Příkladem může být \emph on diferenciální dynamické programování \emph default (DDP). Tento algoritmus zůstává lokální metodou ve smyslu, že uchovává pouzve jedinou trajektorii, která je lokálně vylepšována. Vylepšení však není založeno na řešení soustavy obyčejných diferenciálních rovnic, ale na dynamickém programování aplikovaném na okolí - \begin_inset Quotes eld \end_inset trubici \begin_inset Quotes erd \end_inset podél současné trajektorie. Jedná se o algoritmus s konvergencí druhého řádu. Ještě efektivnější je metoda podobná DDP, \emph on iterativní LQG \emph default (iLQG). Tento algoritmus je založen na linearizaci nelineární úlohy v každém bodě reprezentativní trajektorie a následném řešení modifikované Riccatiho rovnice. Výhodou DDP i iLQG je, že jejich výsledkem je zpětnovazební řízení. Obě metody jsou ale stále deterministické a nedokáží se vypořádat s nekvadratic kými ztrátovými funkcemi a požadavky na omezené řízení. \end_layout \begin_layout Standard S výše zmíněnými problémy se snaží vypořádat modifikovaná iLQG, která bude \color red možná \color inherit použita pro srovnání s ústřední metodou této práce iLDP. Dále pak do kategorie smíšených metod spadá právě i metoda iLDP, která bude podrobně popsána dále. \end_layout \begin_layout Section Výběr konkrétních algoritmů pro srovnání \end_layout \begin_layout Subsection LQG \end_layout \begin_layout Standard \color blue (iLQG) \end_layout \begin_layout Subsection Princip separace \end_layout \begin_layout Section Algoritmus iterativního lokálního dynamického programování \end_layout \begin_layout Standard Algoritmus iLDP byl vytvořen pro účely nalezení stochastického optimálního řízení v mnohadimenzionálních stavových a řídících prostorech. Tento případ je častý zejména při řízení biologických pohybů. Metoda je popsána autory v článku \begin_inset CommandInset citation LatexCommand cite key "TodorovTassaILDP" \end_inset \emph on \emph default a z tohoto zdroje je také převzata \emph on . \end_layout \begin_layout Standard Základní popis algoritmu, tak jak ho autoři podali, je však pouze šablonou a mnoho detailů a dílčích částí je ponecháno na vyřešení při konkrétní realizaci. To se týká zejména použitých aproximací pro jednotlivé funkce, zejména aproximace Bellmanovy funkce a aproximace hledaného regulátoru. Dále, protože algoritmus využívá hledání minima, není v základním popisu algoritmu vyřešen konkrétní typ minimalizace. Použitý minimalizační algoritmus se samozřejmě liší podle konkrétního problému, zejména jedná-li se o minimalizaci omezenou nebo neomezenou. Ještě je třeba zmínil, že pro algoritmus je nutno zvolit parametr \begin_inset Quotes gld \end_inset velikosti \begin_inset Quotes grd \end_inset okolí, protože se jedná o lokální metodu. \end_layout \begin_layout Standard \begin_inset VSpace defskip \end_inset \end_layout \begin_layout Subsection Formulace problému \end_layout \begin_layout Standard Naším úkolem je nalézt řízení \begin_inset Formula $\mathbf{u}=\pi(t,\mathbf{\, x})$ \end_inset , které minimalizuje očekávanou ztrátu \end_layout \begin_layout Standard \align center \begin_inset Formula \[ J(\pi)=E_{\omega}\left(h(\mathbf{x},\pi(t,\mathbf{x}))+\int_{0}^{T}l(\mathbf{x},\pi(t,\mathbf{x}))dt\right)\] \end_inset \end_layout \begin_layout Standard obecně pro spojitý systém: \end_layout \begin_layout Standard \begin_inset Formula \begin{eqnarray} d\mathbf{x} & = & \mathbf{f}(\mathbf{x},\mathbf{u})dt+F(\mathbf{x},\mathbf{u})d\omega\nonumber \\ \mathbf{x}(0) & = & \mathbf{x}_{0}\label{eq:systemSpoj}\\ t & \in & [0,T]\nonumber \end{eqnarray} \end_inset \end_layout \begin_layout Standard v diskrétním tvaru: \end_layout \begin_layout Standard \begin_inset Formula \begin{eqnarray} \mathbf{x}_{k+1}-\mathbf{x}_{k} & = & \mathbf{f}(\mathbf{x},\mathbf{u})\cdot\Delta k+F(\mathbf{x},\mathbf{u})e_{k}\nonumber \\ \mathbf{x}_{(k=0)} & = & \mathbf{x}_{0}\label{eq:systemDis}\\ k & \in & \{0,1,\ldots,N\}\nonumber \\ \Delta k & = & (k+1)-(k)\nonumber \end{eqnarray} \end_inset \end_layout \begin_layout Standard kde hledáme řízení \begin_inset Formula $\mathbf{u}=\pi(k,\mathbf{\, x})$ \end_inset , které minimalizuje očekávanou ztrátu \series bold \emph on \color red asi \end_layout \begin_layout Standard \begin_inset Formula \[ J(\pi)=E\left(h(\mathbf{x},\pi(N,\mathbf{x}))+\sum_{k=0}^{N-1}l_{k}(\mathbf{x},\pi(k,\mathbf{x}))\Delta k\right)\] \end_inset \end_layout \begin_layout Subsection Osnova algoritmu \end_layout \begin_layout Standard Algoritmus pracuje iteračně, každá iterace začne s řízením \begin_inset Formula $\pi$ \end_inset a vytvoří zlepšení \begin_inset Formula $\pi'$ \end_inset . Přičemž prvotní řešení \begin_inset Formula $\pi_{0}$ \end_inset musíme algoritmu dodat jako apriorní informaci. Pro zajištění globální konvergence je možno nové řešení hledat jako konvexní kombinaci starého a algoritmem nalezeného řešení \begin_inset Formula \[ \pi^{nové}=\alpha\pi'+(1-\alpha)\pi;\;0<\alpha\leq1;\; J(\pi^{nové})