\documentclass{report}

\usepackage{amsmath, amsthm, amssymb}
\usepackage{setspace, fancyhdr, extramarks, fullpage, lastpage}
\usepackage{fourier}
\usepackage{graphicx,float,wrapfig, algorithm2e}
\usepackage[all]{xy}
\usepackage{enumerate}
\usepackage{url}
\usepackage{proof}



% Homework Specific Information
\newcommand{\hmwkTitle}{Homework 5}
\newcommand{\hmwkAssignDate}{March 29}
\newcommand{\hmwkDueDate}{April 5}
\newcommand{\hmwkClass}{Graduate Artificial Intelligence 15-780}
\newcommand{\hmwkClassInstructor}{Geoff Gordon \and Tuomas Sandholm}
\newcommand{\hmwkDescr}{Probabilistic Inference}

%\newcommand{\Answer}[1]{\noindent\fbox{\begin{minipage}[c]{0.9\columnwidth}#1\end{minipage}}}
\newcommand{\Answer}[1]
  {}
  
\newenvironment{penumerate}{
\begin{enumerate}
  \setlength{\itemsep}{0pt}
  \setlength{\parsep}{3pt}
  \setlength{\topsep}{-8pt}
  \setlength{\partopsep}{0pt}
  \setlength{\leftmargin}{1.5em}
  \setlength{\labelwidth}{1em}
  \setlength{\labelsep}{0.5em}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{enumerate}}
\newenvironment{pitemize}{
\begin{itemize}
  \setlength{\itemsep}{0pt}
  \setlength{\parsep}{3pt}
  \setlength{\topsep}{-8pt}
  \setlength{\partopsep}{0pt}
  \setlength{\leftmargin}{1.5em}
  \setlength{\labelwidth}{1em}
  \setlength{\labelsep}{0.5em}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{itemize}}


\renewcommand{\labelenumi}{\alph{enumi})}

% In case you need to adjust margins:
\topmargin=-0.45in      %
\evensidemargin=0in     %
\oddsidemargin=0in      %
\textwidth=6.5in        %
\textheight=9.0in       %
\headsep=0.25in         %

% Setup the header and footer
\pagestyle{fancy}                                                       %                                          %
\lhead{\hmwkTitle}  %
\rhead{\hmwkClass }                                                     %                                                     %
\cfoot{}                                                                %
\rfoot{Page\ \thepage\ of\ \protect\pageref{LastPage}}                          %
\renewcommand\headrulewidth{0.4pt}                                      %
\renewcommand\footrulewidth{0.4pt}                                      %

% This is used to trace down (pin point) problems
% in latexing a document:
%\tracingall

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Some tools
\newcommand{\enterProblemHeader}[1]{\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak%
                                    \nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak}%
\newcommand{\exitProblemHeader}[1]{\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak%
                                   \nobreak\extramarks{#1}{}\nobreak}%

\newlength{\labelLength}
\newcommand{\labelAnswer}[2]
  {\settowidth{\labelLength}{#1}%
   \addtolength{\labelLength}{0.25in}%
   \changetext{}{-\labelLength}{}{}{}%
   \noindent\fbox{\begin{minipage}[c]{\columnwidth}#2\end{minipage}}%
   \marginpar{\fbox{#1}}%

   % We put the blank space above in order to make sure this
   % \marginpar gets correctly placed.
   \changetext{}{+\labelLength}{}{}{}}%

\newcommand{\homeworkProblemName}{}%
\newcounter{homeworkProblemCounter}%
\newenvironment{homeworkProblem}[1][Problem \arabic{homeworkProblemCounter}]%
  {\stepcounter{homeworkProblemCounter}%
   \renewcommand{\homeworkProblemName}{#1}%
   \section*{\homeworkProblemName}%
   \enterProblemHeader{\homeworkProblemName}}%
  {\exitProblemHeader{\homeworkProblemName}}%

\newcommand{\problemLAnswer}[1]
  {\labelAnswer{\homeworkProblemName}{#1}}

\newcommand{\homeworkSectionName}{}%
\newlength{\homeworkSectionLabelLength}{}%
\newenvironment{homeworkSection}[1]%
  {% We put this space here to make sure we're not connected to the above.
   % Otherwise the changetext can do funny things to the other margin

   \renewcommand{\homeworkSectionName}{#1}%
   \settowidth{\homeworkSectionLabelLength}{\homeworkSectionName}%
   \addtolength{\homeworkSectionLabelLength}{0.25in}%
   \changetext{}{-\homeworkSectionLabelLength}{}{}{}%
   \subsection*{\homeworkSectionName}%
   \enterProblemHeader{\homeworkProblemName\ [\homeworkSectionName]}}%
  {\enterProblemHeader{\homeworkProblemName}%

   % We put the blank space above in order to make sure this margin
   % change doesn't happen too soon (otherwise \sectionAnswer's can
   % get ugly about their \marginpar placement.
   \changetext{}{+\homeworkSectionLabelLength}{}{}{}}%

\newcommand{\sectionAnswer}[1]
  {% We put this space here to make sure we're disconnected from the previous
   % passage

   \noindent\fbox{\begin{minipage}[c]{\columnwidth}#1\end{minipage}}%
   \enterProblemHeader{\homeworkProblemName}\exitProblemHeader{\homeworkProblemName}%
   \marginpar{\fbox{\homeworkSectionName}}%

   % We put the blank space above in order to make sure this
   % \marginpar gets correctly placed.
   }%

\begin{document}
\begin{spacing}{1.1}

 \begin{titlepage}
   \begin{center}
~

\vspace{2in}
\Large{\textmd{\textbf{\hmwkClass}}}

\vspace{1in}
\Huge{\hmwkTitle: \emph{\hmwkDescr}}

\vspace{1in}

\decofourright

\vspace{1in}

\large{Out\ on\ \hmwkAssignDate}\\
\large{Due\ on\ \hmwkDueDate}
 \end{center}
 \end{titlepage}


\begin{homeworkProblem}[Problem 1:  Broken Sparrow]

\subsection*{The Story So Far...}
Class, the unthinkable has happen.

An unmanned aerial vehicle (UAV) loaded with literally tens of hundreds of dollars worth of atmospheric sensors has gone rogue. Well, technically it malfunctioned. A standard flight started to go wrong at time-step $t=0$. This was the was the last time-step that we received telemetry directly from the UAV. 

Since then we have been tracking it from two far-off radar towers. At $t=0$ the UAV reported a system failure that not only disrupted its communication systems, but also knocked-out its guidance system. 

You, and a special case of the Hidden Markov Model (HMM), are our only hope to find where the UAV is now.

\subsection*{Technical Briefing: Linear Dynamic Systems}

A \emph{Linear Dynamic System} is a special case of the HMM where the latent (unobserved or hidden) state at $t+1$ and the observation at $t$ are both linear functions of the latent state at $t$ with additive Gaussian noise. This special case is extremely attractive mathematically because updating the model in the face of evidence can be written as a series of linear algebra operations.

Formally the system is defined by the following equations:

\begin{align}
z_{t+1} &= A \cdot z_t + w_t\\
x_t &= C \cdot z_t + v_t.
\end{align} 

Here $z_t = \left(d^x_t, d^y_t, v^x_t, v^y_t, a^y_t, a^x_t\right)$ is the latent state and $x_t = \left(a^x_t, a^y_t, b^x_t, b^y_t\right)$ is observed state (the observations of $(x,y)$ from the two towers). $A$ and $C$ are matrices, called the \emph{transition} and \emph{observation} matrices. The noise terms, $w_t$ and $v_t$ are distributed by zero-mean multivariate Gaussians:

\begin{align}
w_t &\sim \mathcal{N}(w_t\;|\;0, \Gamma)\\
v_t &\sim \mathcal{N}(v_t\;|\;0, \Sigma)
\end{align}

The initial state is also a multivariate Gaussian:

\begin{align}
z_0 &\sim \mathcal{N}(z_0\;|\;\mu_{0}, V_{0}).
\end{align}

\subsection*{Filling in the Numbers}

\begin{itemize}
\item \textbf{Dynamics}: 

We can model the transition of the UAV with the following simple 2D dynamics:

\begin{align}
a^x_{t+1} &= a^x_{t}\\
v^x_{t+1} &= v^x_{t} + a^x_{t} \cdot \Delta t\\
d^{x}_{t+1} &= d^x_t + v^x_t \cdot \Delta t + \frac{1}{2} a^x_t \cdot(\Delta t)^2
\end{align}

A similar set of equations could be written for the $y$-dimension. These equations define your transition matrix. We receive observations from the radar towers every second, so $\Delta t = 1$.

The UAV is reasonably aerodynamically stable, but because of its malfunctioning guidance system is is believed to be accelerating randomly. In particular:

\begin{equation}
\Gamma = \begin{pmatrix}0.0001 &&&&&\\&0.0001&&&&\\ && 0.0001&&&\\ &&&0.0001&&\\ &&&&0.1&\\&&&&&0.1\end{pmatrix}
\end{equation}

\item \textbf{Observation}

The two towers both provide unbiased but imprecise estimates of the UAV's $\left(d^x_i,d^y_i\right)$ position every time-step. Luckily, their noise is completely independent of each other. Therefore, the system's observation noise has the following measurement-noise covariance matrix: 

\begin{align}
\Sigma_1 = \Sigma_2 &= \begin{pmatrix}100&10\\10&100\end{pmatrix}\\
\Sigma &= \begin{pmatrix}\Sigma_1&\\&\Sigma_2\end{pmatrix}
\end{align}

\item \textbf{Initial Position}

The UAV was initially at $(0,0)m$ and was traveling at $(6,6)m/s$. It was not accelerating at that time. However the initial telemetry data is also subject to noise; $V_{-1} = \mathbb{I}_6$ (the $6\times6$ identity matrix).
\end{itemize}

\subsection*{Tasks}
Your mission, should you choose to accept it:
\begin{enumerate}
\item Draw the Bayes net for time steps $t-1$, $t$, and $t+1$ for arbitrary time-step $t$. \emph{I.e.} draw all the variables for these three time steps, and all the edges that connect them.
\item Understand how to infer the posterior distribution of latent state at $t$ from the observed data at steps $0, \ldots, t$. This inference in an LDS is performed by a \emph{Kalman Filter}. More information can be found on Wikipedia's excellent \emph{Kalman Filter} page, in \S 15.4 of Russell and Norvig,  and in \S 13.3 of \emph{Pattern Recognition and Machine Learning} by Bishop. 

%The following identities will be helpful for the following questions. If 
%\begin{align}
%p(x) &= \mathcal{N}(x\;|\;\mu, \Lambda^{-1})\\
%p(y|x) &= \mathcal{N}(y\;|\;Ax + b, L^{-1})
%\end{align}
%then
%\begin{align}
%p(y) &= \mathcal{N}(y\;|\;A\mu + b, L^{-1} + A \Lambda^{-1} A^T)\\
%p(x|y) &= \mathcal{N}(x\;|\;\Sigma \left[A^TL(y-b) + \Lambda\mu\right], \Sigma)
%\end{align}
%where
%\[\Sigma = (\Lambda + A^TLA)^{-1}.\]
Comprehension questions for this task:
\begin{enumerate}
\item  Derive the expression for the joint distribution of two successive states and one observation: $P(x_t, z_t, z_{t+1})$.  In this expression, assume that the observations prior to time $t$ lead you to believe that the distribution of the previous state is $z_{t} \sim \mathcal{N}(z_{t}\;|\;\mu_{t}, V_{t})$. Your answer should be the product multivariate Gaussians.
\item Suppose that the distribution of state $z_{t} \sim \mathcal{N}(z_{t}\;|\;\mu_{t}, V_{t})$. The distribution of $P(z_{t+1}|x_{t+1})$ is normal. Please provide expressions for the mean and covariance. You do not have to provide the derivation for this answer, but cite your source if you do not.
\end{enumerate}


\item Plot the sensor data and sequence of posterior distribution means for the $(x,y)$-positions of the UAV. Figure~\ref{fig:ex} is an example of the kind of plot that we are looking for. (The actual data will be entirely different.)
\begin{figure}[htbp]
\begin{center}
\resizebox{0.6\columnwidth}{!}{
\includegraphics{example.png}
}
\end{center}
\caption{The blue line is the expected path, the green paths are the observed path from the two towers given in the files, and the red path is the true trajectory of the UAV. You are not given the data for the red path.}
\label{fig:ex}
\end{figure}
\item Report UAV's posterior position distribution at $t=100$. This is a multivariate Gaussian, and can be reported as its mean and $6 \times 6$ covariance matrix. 
\end{enumerate}

\textbf{Note:} please pick an appropriate language to do this question in. Your language should be able to easily support linear algebra. If you want to build a test simulator, you also need to pick a language that allows sampling from multivariate Gaussians. MATLAB and Python/Numpy are both good choices. 

\end{homeworkProblem}

\end{spacing}
\end{document}