presentation.tex

%% LaTeX-Beamer template for KIT design
%% by Erik Burger, Christian Hammer
%% title picture by Klaus Krogmann
%%
%% version 2.0
%%
%% mostly compatible to KIT corporate design v2.0
%% http://intranet.kit.edu/gestaltungsrichtlinien.php
%%
%% Problems, bugs and comments to
%% burger@kit.edu
\documentclass[18pt]{beamer}
\usetheme{kit}

\titleimage{titleImage}
\titlelogo{logos}

% the presentation starts here

\title[MDP Pfadplanung]{Markov-Entscheidungsprozesse für die Roboterpfadplanung}
\subtitle{Entscheidungsprobleme unter Unsicherheit} %TODO nötig?
\author{Matthias Holoch}

\institute{Proseminar Anthropomatik: Von der Theorie zur Anwendung}

\setbeamertemplate{bibliography item}[text] %Creates numbers in the bibliography at the end of the presentation
\usepackage{multicol}

\begin{document}

\selectlanguage{ngerman}

%title page
\begin{frame}
	\titlepage
\end{frame}


\section{Einleitung}
\subsection{Motivation}
\begin{frame}
	\frametitle{Motivation}
	Medizinische Diagnose und Therapie
	\begin{itemize}
		\visible<2->{
		\item genauer Patientenzustand unbekannt
		}
		\visible<3->{
		\item Beobachtungen als Hinweis auf den Patientenzustand
		}		
		\visible<4->{
		\item Menge an Therapiemöglichkeiten
		}
		\visible<5->{
		\item Abwägen des Nutzens
		}
		\vspace{0.5cm}
		\begin{columns}
			\column[t]{0.2\textwidth}
			\visible<2->{%
				\includegraphics[width=\textwidth]{images/patient.png}\\ \cite{flickrniklas}
				}%
			\column[t]{0.2\textwidth}
			\visible<3->{%
				\includegraphics[width=\textwidth]{images/doctor_observe.png}\\ \cite{flickrammar}
				}%
			\visible<4->{%
			\column[t]{0.2\textwidth}
				\includegraphics[width=\textwidth]{images/therapy2.jpg}\\ \cite{flickrrodrigo}
			\column[t]{0.2\textwidth}
				\includegraphics[width=\textwidth]{images/therapy1.jpg}\\ \cite{flickrpanama}
				}%
		\end{columns}
	\end{itemize}
\end{frame}
\subsection{Problemstellung}
\begin{frame}
	\frametitle{Problemstellung}
	Lösen von Entscheidungsproblemen unter Einbezug von\\Unsicherheiten\\
	\vspace{0.5cm}
	\visible<2->{
		\textbf{Im Folgenden: Roboterpfadplanung}
		\begin{columns}
		\column{0.8\textwidth}
			\begin{figure}
				\includegraphics[scale=0.8]{images/autnmRobot_basicSituation.png}
			\end{figure}
		\column{0.2\textwidth}
		\vspace{3.2cm}\\
			\cite{thrun2005probabilistic}
		\end{columns}
	}
\end{frame}


\section{Pfadplanung unter Unsicherheit}
\subsection{Pfadplanung klassisch}
\begin{frame}
	\frametitle{Klassische Pfadplanung}
	\vspace{-0.5cm}
	\begin{columns}
	\column{0.8\textwidth}
		\only<1>{
			\includegraphics[scale=0.8]{images/autnmRobot_basicSituation.png}
		}
		\only<2->{
			\includegraphics[scale=0.8]{images/autnmRobot_directPath.png}
		}
	\column{0.2\textwidth}
		\vspace{2.3cm}\\
			\cite{thrun2005probabilistic}
	\end{columns}
	\vspace{0.5cm}
	\begin{columns}
		\column[t]{0.5\textwidth}
			Annahmen
			\begin{itemize}
				\item genauer Zustand bekannt
				\item Aktionsausführung fehlerfrei
			\end{itemize}
		\column[t]{0.5\textwidth}
			\visible<3->{
				Realität
				\begin{itemize}
					\item verrauschte Sensordaten
					\item Fehler im Bewegungsmodell
					\item exogene Störungen
				\end{itemize}
			}
	\end{columns}
	\visible<4>{
		\vspace{0.5cm}
		Einbezug von Unsicherheiten nötig\\
		\textbf{$\Rightarrow$ Einzelne Aktionsfolge reicht nicht aus}
	}
\end{frame}

\subsection{Pfadplanung mit MDPs}
\begin{frame}
	\frametitle{Pfadplanung mit Markov- Entscheidungsprozessen (MDPs)}
	\begin{columns}
	\column{0.8\textwidth}
		\only<1,2>{
			\includegraphics[scale=0.8]{images/autnmRobot_basicSituation.png}
		}
		\only<3>{
			\includegraphics[scale=0.8]{images/autnmRobot_detActionMDP.png}
		}
		\only<4>{
			\includegraphics[scale=0.8]{images/autnmRobot_ndetActionMDP.png}
		}
	\column{0.2\textwidth}
		\vspace{2cm}\\
		\cite{thrun2005probabilistic}
	\end{columns}
	\begin{columns}
	\column[t]{0.7\textwidth}
	\\Annahme: Genauer Zustand bekannt\\
	\vspace{0.5cm}
	\visible<2->{
		Vorberechnete Aktionsverhalten
		\begin{itemize}
			\item Antizipation des Fehlverhaltens
			\item optimales Verfahren
		\end{itemize}
	}
	\column[t]{0.3\textwidth}
	\only<3>{
	\textcolor{blue}{deterministische Aktionseffekte}
	}%
	\only<4>{
	\textcolor{blue}{nichtdeterministische Aktionseffekte}
	}%
	\end{columns}
\end{frame}


\section{MDP}
\subsection{Definition}
\begin{frame}
	\frametitle{MDP}
	Ein MDP ist ein 4-Tupel
	\begin{equation}
		(S, A, T, r)
	\end{equation}
	mit
	\begin{itemize}
		\visible<1->{
			\item diskreter, endlicher Zustandsmenge $S$
		}
		\visible<2->{
			\item diskreter, endlicher Aktionsmenge $A$
		}		
		\visible<3->{
			\item Zustandsübergangsmodell des Systems $T$
				\begin{equation}
					T(s, a, s') = \mathbf{p}(s'|s, a)\text{, mit } s,s' \in S, a \in A
				\end{equation}
		}
		\visible<4->{
			\item Funktion
				\begin{equation}
					r: S \times A \rightarrow \mathbb{R}\ .
				\end{equation}
		}
	\end{itemize}
\end{frame}

\subsection{Beispiel}
\begin{frame}
	\frametitle{MDP Beispiel}
	\only<1>{
		\includegraphics[scale=0.2]{images/MDP_example_part2.png}
	}
	\only<2>{
		\includegraphics[scale=0.2]{images/MDP_example_part1.png}
	}
	\only<3>{
		\includegraphics[scale=0.2]{images/MDP_example_part0.png}
	}
	\only<4>{
		\includegraphics[scale=0.2]{images/MDP_example.png}
	}
	\begin{itemize}
	\visible<1->{
		\item $S = \{s_0, s_1, s_2\}$
	}
	\visible<2->{
		\item $A = \{a_0, a_1\}$
	}
	\visible<3->{
		\item $T(s_0, a_0, s_0) = 0.2,\ T(s_0, a_0, s_2) = 0.8,\ ...$
	}
	\visible<4->{
		\item $r(s_0, a_1) = 1,\ r(s_2, a_0) = 10,\ r(s_1, a_1) = -5$
	}
	\end{itemize}
\end{frame}

\section{Strategien}
\subsection{Optimale Strategien}
\begin{frame}
	\frametitle{Strategien}
	\begin{columns}
	\column{0.8\textwidth}
		\only<1>{
			\includegraphics[scale=0.8]{images/autnmRobot_directPath.png}\\
		}
		\only<2->{
			\includegraphics[scale=0.8]{images/autnmRobot_detActionMDP.png}\\
		}
	\column{0.2\textwidth}
		\vspace{2.3cm}\\
			\cite{thrun2005probabilistic}
	\end{columns}
	\visible<3->{
	\vspace{1cm}
		Strategie ist Funktion
		\begin{equation}
			\pi: S \rightarrow A
		\end{equation}
	}%
	\visible<4->{%
		Gesucht: Optimale Strategie\\
		Was bedeutet optimal?
	}
\end{frame}
\begin{frame}
	\frametitle{Optimale Strategien}
	\begin{center}
		\visible<2->{$\pi^*$}\visible<4->{$ = \underset{\pi}{argmax}\ \mathrm{E}\left[\visible<8->{\sum\limits_{t=1}^{n} \gamma^t r(s_t, a_t) \ \vert\ \pi}\right]$}
	\end{center}
	\visible<3->{
	\begin{itemize}
		\item Planungshorizont $n$
		\begin{itemize}
			\item endlicher Planungshorizont
			\item unendlicher Planungshorizont
		\end{itemize}
		}
		\visible<4->{
		\item Maximierung einer erwarteten Güte aller Aktionsfolgen \\
			  $\left[(s_1, a_1), (s_2, a_2), ..., (s_n, a_n)\right]$
		\begin{itemize}
			\visible<5->{
				\item additive Güte
				\begin{equation}
					\sum\limits_{t=1}^n r(s_t, a_t)
				\end{equation}
			}
			\visible<6->{
				\item reduzierte Güte
				\begin{equation}
					\sum\limits_{t=1}^n \gamma^t r(s_t, a_t),\ \text{mit }\gamma \in [0,1]
				\end{equation}
			}
			\visible<7->{
				\item durchschnittliche Güte pro Zeitschritt
			}
		\end{itemize}
	\end{itemize}
	}
\end{frame}

\subsection{Algorithmus}
\begin{frame}
	\frametitle{Lösen von MDPs - Vorüberlegung}
	\begin{itemize}
		\only<2,3>{
			\item $n=1$:
				\begin{equation}
					\begin{split}
						\pi_1^*(s)= \underset{a}{argmax}\ r(s, a) \\
						V_1(s) = \gamma\ \underset{a}{max}\ r(s, a)
					\end{split}
				\end{equation}
		}
		\visible<3->{
			\item $n=2$:
				\begin{equation}
					\begin{split}
						\pi_2^*(s) = \underset{a}{argmax} \left[ r(s,a) + \sum_{s' \in S} V_1(s')\ T(s, a, s') \right] \\
						V_2(s) = \gamma\ \underset{a}{max} \left[ r(s,a) + \sum_{s' \in S} V_1(s')\ T(s, a, s') \right]
					\end{split}
				\end{equation}
		}
		\only<4->{
			\item $\forall n > 1$:
				\begin{equation}
					\begin{split}
						\pi_n^*(s) = \underset{a}{argmax} \left[ r(s,a) + \sum_{s' \in S} V_{n-1}(s')\ T(s, a, s') \right] \\
						V_n(s) = \gamma\ \underset{a}{max} \left[ r(s,a) + \sum_{s' \in S} V_{n-1}(s')\ T(s, a, s') \right]
					\end{split}
				\end{equation}
		}
	\end{itemize}
\end{frame}
\begin{frame}
	\frametitle{Lösen von MDPs - dynamische Programmierung}
	\begin{itemize}
		\visible<2->{
			\item Initialisierung
				\begin{equation}
					\hat{V}(s) \leftarrow 0
				\end{equation}
		}
		\visible<3->{
			\item pro Iteration
				\begin{equation}
					\hat{V}(s) \leftarrow \gamma\ \underset{a}{max} \left[ r(s,a) + \sum_{s' \in S} \hat{V}(s')\ T(s, a, s') \right]
				\end{equation}
		}
		\visible<4->{
			\item bis $\hat{V}$ konvergiert
		}
	\end{itemize}
		\visible<5->{
			$\hat{V}$ induziert nun
				\begin{equation}
					\pi(s)^* = \underset{a}{argmax} \left[ r(s,a) + \sum_{s' \in S} \hat{V}(s')\ T(s, a, s') \right]
				\end{equation}
		}
\end{frame}


\section{Ausblick}
\subsection{Ausblick}
\begin{frame}
	\frametitle{Ausblick}
	Mit dem MDP
	\begin{itemize}
		\item Unsicherheiten in Aktionen modellieren
		\item optimale Strategie berechnen
	\end{itemize}
	\visible<2->{
		\textbf{Aber}
		\begin{itemize}
			\item Annahme: Genauer Zustand erkennbar
			\item Entspricht \emph{nicht} der Realität
		\end{itemize}
	}
	\visible<3->{
		Ausblick: POMDP
		\begin{itemize}
			\item erlaubt Unsicherheiten in dem Zustand
			\item Wahrscheinlichkeitsverteilung über alle Zustände
		\end{itemize}
	}
\end{frame}

\subsection{Quellen}
\begin{frame}{~}
\begin{center}
\vspace{1.5cm}%
	\textbf{{\LARGE Vielen Dank für Ihre Aufmerksamkeit}}%
\end{center}%
	\begin{multicols}{2}%
		\bibliographystyle{plain}%
		\bibliography{literatur}%
	\end{multicols}%
\end{frame}

\end{document}