%\documentclass[11pt,letterpaper]{article}
\documentclass[11pt,letterpaper,addpoints]{exam}
\usepackage[top=.6in,left=1.2in,right=1.2in,bottom=.75in]{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{nopageno}
\usepackage{listings}
\usepackage{ulem}
\usepackage[pdftex]{graphicx}
\usepackage{enumerate}
\usepackage{array}
\usepackage[parfill]{parskip}
\usepackage{hyperref}
\usepackage{pbox}
    \usepackage[bottom]{footmisc}

\lstdefinestyle{basic}{
    basicstyle=\small\ttfamily,%
    frame=single,
    showstringspaces=false,%
}
\lstset{
    language=python,
    basicstyle=\tt\small,
    keepspaces=true,
    showstringspaces=false,
    frame=single,
    emphstyle=\textit,
    emph={val1,val2,val3,val4,val5},
    numbers=left, stepnumber=1
}




%-----------------------------------
\begin{document}
%-----------------------------------
\vspace*{-.5in}

\hspace*{-.1in}Name: \vspace{.2in}\underline{ \hspace{2in} }

\hspace*{-.1in}With help from: \vspace{.2in}\underline{ \hspace{2in} }
\vspace{.25in}
\begin{center}
{\Large HW \#2} 
\end{center}

\subsection*{Useful Formulas}
\bgroup
\footnotesize
\def\arraystretch{2}%
\begin{tabular}{|l|l|}
  \hline
  Definition of conditional probability & $ \displaystyle P(A \mid B) =  \frac{P(A \cap B)}{P(B)}$ \\
  \hline
  Chain rule & $ \displaystyle P(A \cap B) =  P(B \mid A)P(A) = P(A \mid B)P(B)$ \\
  \hline
   Bayes' rule & $ \displaystyle P(A \mid B) = \frac{P(B \mid A) P(A)}{P(B)}$ \\
  \hline
   Total probability theorem & $ \displaystyle P(Z) = \sum_i^N P(Z \mid X=x_i) P(X=x_i)$ \\
  \hline
  Recursive state estimation formula & \pbox{20cm}{ $ \displaystyle Bel^-(X_t) =  \sum_{x_{t-1}\in X} P(X_t \mid x_{t-1} ) Bel(x_{t-1})$ \\
    $ \displaystyle Bel(X_t) =  \alpha P(Z_t \mid X_t) Bel^-(X_t)$} \\
  \hline
\end{tabular}
\egroup

\begin{questions}

\question \textbf{Bayes' Rule and Probability Notation}\footnote{Question is based on question 5 from Appendix A of
\emph{Computational Principles of Mobile Robotics.}}

A common technique for the localization of robots in industrial
settings is to augment the local environment with specific landmarks
(often visual) that can be sensed by the robot. Suppose we have such a
landmark scheme. We are interested in two Boolean random variables: $D$
- the robot has detected a landmark and $L$ - there is actually a
landmark present. Express each of the following in probability
notation using these variables:

\begin{parts}

\part    When a landmark is present, the system correctly identifies it with probability .9. In other words, there is a .9 probability that the detector will activate \emph{given} the presence of a landmine.

\begin{solution}[.5in]
\end{solution}


\part    Landmarks are identified falsely (i.e. when no landmark is present) with probability .01.

\begin{solution}[.5in]
\end{solution}



\part    The probability of a landmark being present is .05.

\begin{solution}[.5in]
\end{solution}

\end{parts}

\newpage
Answer the following questions by writing the desired quantity in
probability notation, then determining the solution.
\begin{parts}
\setcounter{partno}{3}
\part    What is the missed detection probability (probability of missing a landmark even though one is present)?


\begin{solution}[.75in]
\end{solution}


\part What is the probability that a target is present given that one is detected? (\textbf{Hint:} use Bayes' rule.)

\begin{solution}[.75in]
\end{solution}

\part Complete the following table with the full joint distribution over detections and landmark presence. (\textbf{Hint:} use the chain rule.)

\begin{tabular}{c|c|c}
$D$ & $L$ & $P(D,L)$\\
\hline
T & T &  \\
T & F &  \\
F & T &  \\
F & F &  \\
\end{tabular}

\end{parts}

\pagebreak


\question \textbf{Bayes' Rule and Localization}

Consider the robot localization scenario described in
\href{https://w3.cs.jmu.edu/spragunr/CS354/lectures/probabilitity/bayes.pdf}{these
  slides}. What is the final probability distribution over room
locations given the following series of sensor readings?

\begin{verbatim}
b (done for you in the slides)
a
b
\end{verbatim}

Assume that the initial distribution is

\begin{tabular}{|c|c|c|c|}
\hline
.4	&.4	&.1	&.1 \\
\hline
\end{tabular}

that the robot is not moving, and that sensor readings are independent
given the robot's position. (I.e. one incorrect sensor reading does
not increase the probability of seeing the same incorrect sensor
reading in the future.)

You should treat the distribution calculated after each sensor reading
as the prior distribution for the next sensor reading.


\pagebreak







\question \textbf{Grid-Based Localization and Tracking}


 We've discussed the application of grid-based localization to the
 problem of tracking a robot moving in a circular four-room maze. For
 this question we will track the same robot.  The robot may choose to
 move left or right, and we know that the actions succeed 50\% of the
 time.  When an action does not succeed, the robot remains in the same
 location.  Our sensor model tells us that there is an 80\% chance
 that his room sensor will output the true location, and a 20\% that
 it will indicate one of the rooms to the immediate left or right of
 the true location.
\vspace{.2in}  

Initially, the robot is 75\% likely to be in room ``a'' and 25\%
likely to be in room ``b'':
\begin{center}
$Bel(X_0) = $
\begin{tabular}{|c|c|c|c|}
\hline
 a & b& c& d\\
\hline
 .75 & .25   & 0   & 0 \\
\hline
\end{tabular}
\end{center}
 The robot's first action is ``right'' and the first sensor output  is ``b''.


\begin{parts}


  \part
  What will the belief distribution be after one step of prediction
  (before the sensor update)?  Show your work.

\begin{center}
\vspace{1.8in}
$Bel^-(X_1) = $
\begin{tabular}{|c|c|c|c|}
\hline
 a & b& c& d\\
\hline
  &    &    &  \\
\hline
\end{tabular}
\vspace{.2in}
\end{center}

\part
What will the belief distribution be after the sensor update? Show
your work.

\vspace{1.8in}
\begin{center}
$Bel(X_0) = $
\begin{tabular}{|c|c|c|c|}
\hline
 a & b& c& d\\
\hline
 &    &   &  \\
\hline
\end{tabular}
\end{center}
\vspace{.2in}



\end{parts}





\pagebreak
\question \textbf{Multivariate Normal Distribution}

\begin{parts}
  \part
  Recall that the multivariate normal distribution is parameterized by
  a mean vector $\mu$ and a covariance matrix $\Sigma$.  Cross out any
  of the following parameter values that do \textit{not} correspond to
  a valid normal distribution.

\hspace*{-2em}
\begin{tabular}{|p{2in}|p{2in}|p{2in}|}
\hline 
&&\\[5pt] 
$\mu_A = \begin{bmatrix}
3\\
3
\end{bmatrix}, \Sigma_A = \begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}$ &
$\mu_B = \begin{bmatrix}
3\\
4
\end{bmatrix}, \Sigma_B = \begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}$ &
$\mu_C = \begin{bmatrix}
3\\
3
\end{bmatrix}, \Sigma_C = \begin{bmatrix}
2 & -.5\\
.5 & 1
\end{bmatrix}$ \\[20pt]
\hline
&&\\[5pt] 
$\mu_D = \begin{bmatrix}
3\\
3
\end{bmatrix}, \Sigma_D = \begin{bmatrix}
1 & 0\\
0 & .2
\end{bmatrix}$ &
$\mu_E = \begin{bmatrix}
3\\
3
\end{bmatrix}, \Sigma_E = \begin{bmatrix}
1 & -.3\\
-.3 & 1
\end{bmatrix}$ &
$\mu_F = \begin{bmatrix}
3\\
3
\end{bmatrix}, \Sigma_F = \begin{bmatrix}
0 & .8 \\
.8 & 0
\end{bmatrix}$ \\[20pt]
\hline
\end{tabular}

\vspace{.5in}
\part Each of the following figures illustrates one of the  probability density functions parameterized above. Label each figure with the matching parameterization (A-F).   

\begin{center}
\includegraphics[width=1.5in]{tilt.pdf} \hspace{1em}
\includegraphics[width=1.5in]{eye.pdf} \hspace{1em}
\includegraphics[width=1.5in]{big_x.pdf}
\end{center}

\end{parts}


\pagebreak

\question \textbf{The Kalman Filter}

Recall that the Kalman filter requires both a linear system model and
a linear measurement model.  The system model (without control) can be
expressed as

 $\mathbf{x}_t = F \mathbf{x}_{t-1}  + \mathbf{w}_{t-1}$,

where $\textbf{x}_t$ represents the system state, $F$ expresses the
state dynamics, and $\textbf{w}_t$ is a noise term. The measurement
model can be expressed as

 $\mathbf{z}_t = H \mathbf{x}_t + \mathbf{v}_t$,

where $\textbf{z}_t$ is a measurement value, $H$ expresses how sensor values
are related to the system state, and $\textbf{v}_t$ is sensor noise. 

For this question assume that we want to use a Kalman filter to track
an object moving in one dimension with a fixed acceleration.

The following difference equations describe the system dynamics:
\begin{align*}
x_{t} &= x_{t-1} + \dot{x}_{t-1} \Delta t\\
\dot{x}_{t} &= \dot{x}_{t-1} + \ddot{x}_{t-1} \Delta t\\
\ddot{x}_{t} &= \ddot{x}_{t-1}
\end{align*}
Where $x_t$ is the object position, $\dot{x}_t$ is the velocity and
$\ddot{x}_t$ is acceleration and $\Delta t$ is the size of the time
step.


\begin{parts} 
  \part
  Assuming that the state of the system is encoded as: 
$\textbf{x}_t = \begin{bmatrix}
x_t\\
\dot{x}_t\\
\ddot{x}_t\\
  \end{bmatrix}$,
  what $F$ matrix corresponds to the difference equations
  above?  \vspace{2in}

\part
What should the $H$ matrix be to represent the fact that we have a
one-dimensional sensor that provides an estimate of the object
position, but no information about velocity or acceleration?




\end{parts}


\end{questions}

%-------------------------
\end{document}
%-------------------------







