\documentclass[11pt]{article}

% -------------------------------------------------
% Packages
% -------------------------------------------------
\usepackage[margin=1in]{geometry}          % Page geometry
\usepackage{xcolor}                        % Color definitions

% Math & Fonts
\usepackage{amsmath,amssymb,amsthm}        % AMS math
\usepackage{fontawesome5}                  % Icons
\usepackage{minted}                        % Code listings

% Graphics
\usepackage{graphicx}                      % Include graphics

% Lists and boxes
\usepackage{enumitem}
% TODO lists
\newlist{todolist}{itemize}{2}
\setlist[todolist]{label=$\square$}       
\usepackage[most]{tcolorbox}               % Colored boxes

% Header / footer
\usepackage{fancyhdr}                      % Fancy header

% Hyperlinks (keep last)
\usepackage{hyperref}                      % Hyperlinks

% -------------------------------------------------
% Macros & Styles
% -------------------------------------------------

% Course‑specific info
\newcommand{\course}{ECE 531/COS 531: Robot Planning Meets Machine Learning}
\newcommand{\semester}{Fall 2025}
\newcommand{\hwNum}{2}
\newcommand{\dueDate}{September~23,~2025 at 11:59pm}

% Common icons
\newcommand{\WritingIcon}{\faEdit}
\newcommand{\CodeIcon}{\faLaptopCode}
\newcommand{\WarningIcon}{\faExclamationTriangle}


% tcolorbox base style
\tcbset{
  base/.style={
    before skip=2em,
    after skip=2em,
    colback=purple!5!white,
    colframe=purple!25!white,
    fonttitle=\bfseries,
    coltitle=black,
    boxrule=0.8pt,
    arc=4pt,
    left=6pt,right=6pt,top=6pt,bottom=6pt
  }
}

% Individual box styles
\newtcolorbox{instructionsbox}[1][]{base,title=Instructions,#1}
\newtcolorbox{ponderbox}[1][]{base,title=Pause to Ponder (No Points \& No Submission Required),#1}
\newtcolorbox{warningbox}[1][]{base,title=\WarningIcon\ Important Note,#1}

% Answer box macro
\newcommand{\AnswerBox}[1]{\framebox[\textwidth][c]{\rule{0pt}{#1}}}

% Spacing
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}

% Header / footer
\pagestyle{fancy}
\fancyhf{}
\lhead{\course}
\rhead{\semester}
\cfoot{\thepage}

% Hyperref colors
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    urlcolor=blue,
    citecolor=blue,
}

% Title
\title{\vspace{-3em}\textbf{Homework \hwNum}\vspace{-2em}}
\date{\vspace{-1em}Due: \dueDate\vspace{-2em}}

% -------------------------------------------------
\begin{document}
\maketitle
\thispagestyle{fancy}

\begin{instructionsbox}
\begin{itemize}
    \item See \url{https://rpmml.github.io/homework_instructions/} for instructions on accessing the accompanying code and submitting homework via GradeScope.
    \item See \url{https://rpmml.github.io/policies} for additional policies regarding collaboration, LLMs, and late submissions.
    \item Use Piazza or attend office hours to ask questions about the homework.
\end{itemize}
\end{instructionsbox}

\section*{Part 1: Written Exercises}

\subsection*{\WritingIcon\ Practice with State Estimation (15 points)}

\begin{figure}[h]
    \centering
    \includegraphics[width=\linewidth]{figures/catch-frog.pdf}
    \caption{Illustration for state estimation question.}
    \label{fig:catch-frog}
\end{figure}

A frog is hopping between 5 locations that are hidden behind tall grass (Figure~\ref{fig:catch-frog}).
The frog makes a noise when in each location, but the noise is muffled:
\begin{itemize}
    \item If the frog is at Location 1, a noise is heard at Location 1 with probability 0.75 and heard at Location 2 with probability 0.25.
    \item If the frog is at Location 5, a noise is heard at Location 5 with probability 0.75 and heard at Location 4 with probability 0.25.
    \item If the frog is at Location $x$, for $1 < x < 5$, a noise is heard at Location $x$ with probability 0.5, Location $x-1$ with probability 0.25, and Location $x+1$ with probability 0.25.
\end{itemize}
After making a noise, the frog may hop to an adjacent location:
\begin{itemize}
    \item If at Location 1, it hops to Location 2 with probability 0.5 and stays in place otherwise.
    \item If at Location 5, it hops to Location 4 with probability 0.5 and stays in place otherwise.
    \item If at Location $x$, for $1 < x < 5$, it hops to location $x-1$ with probability 0.25, to location $x+1$ with probability 0.25, and stays in place otherwise.
\end{itemize}

You hear a noise at Location 1 at $t=0$, Location 2 at $t=1$, and Location 5 at $t=2$.
Calculate and report your belief about the frog's true location after each of the noises are heard.
Do filtering only, not smoothing; i.e., when calculating your belief about $t=0$, consider only the noise at Location 1, not the future noises.
Show your work.

\begin{ponderbox}
Under what circumstances, if any, can you be absolutely certain about the frog's location?
\end{ponderbox}

\subsection*{\WritingIcon\ Practice with POMDP Formulation (10 points)}

On Monday morning, you see a painting at a local store that is selling for \$100.
You have a keen eye for art and you believe there is a small chance this painting is the original work of a famous artist, which would make it worth \$10,000.
If the painting is not original, then it is only worth \$10.
At this moment, you think there is a 20\% chance that the painting is original and an 80\% chance that it is not.
You also happen to be friends with an art expert who could tell you with absolute certainty whether the painting is original.
Unfortunately, your friend is on vacation, and the earliest that they could assist you is first thing Wednesday morning.
With each passing day, there is a 10\% chance that someone else will buy the painting.
Formulate a POMDP that captures this decision-making problem.

\subsection*{\WritingIcon\ Practice with POMDP Expectimax Search (20 points)}

Draw a complete expectimax search tree for the POMDP you formulated in the previous question.\footnote{There are multiple ways to formulate the POMDP. Feel free to revise your answer to the first question if it makes this second question easier.}
Make sure that all values are shown in the tree.
Annotate the optimal actions at each node. You can hand-draw the figure or use any software to produce it.

\begin{ponderbox}
Why might losing money on unoriginal painting ``feel worse'' than gaining money on an original one, even if the amounts lost and gained were the same?
\end{ponderbox}

\section*{Part 2: Coding Exercises}

\subsection*{\CodeIcon\ Policy Trees (10 points)}

In this question, you will implement a data structure for a policy tree, and then use that data structure to create three specific policy trees for a Tiger POMDP.
There are no requirements for your data structure other than that the unit tests must pass.
Examine the unit tests in \mintinline{python}{test_policy_tree.py} to make sure you understand the question.
No written answer required.

\begin{ponderbox}
How would you change our implementation of expectimax search to extract a policy tree?
\end{ponderbox}

\subsection*{\CodeIcon\ Conformant Planning (20 points)}

A \emph{conformant plan} is a sequence of actions that is guaranteed to achieve some performance regardless of which initial state and transitions are sampled from a POMDP.
For example, if you are in a dark room but you know that there is a light switch somewhere on a wall, then sweeping your hand along the wall is a conformant plan---eventually you will touch the switch, regardless of where you start.
In this question, you will implement two conformant planners: a ``good'' conformant planner that is guaranteed to find a plan that attains total rewards $1.0$ or greater; and a ``bad'' conformant planner that is guaranteed to find a plan that attains total rewards $-1.0$ or less.
Both planners must report if no conformant plan is possible.
Examine the unit tests in \mintinline{python}{test_conformant_planning.py} to make sure you understand the question.
Note that your program must return the shortest plan that meets these guarantees.
Suggested approach: For these unit tests, it is computationally feasible to explore every possible path. This means for every plan length, enumerating all possible combinations of actions; then for every action plan, explore the tree to find the worst and best case scenarios. We have provided helper functions (that you must implement) which may be useful on the way.
No written answer required.

\begin{ponderbox}
Our approach here was fairly ``brute force.'' Can you think of any tricks to speed this up?
\end{ponderbox}

\subsection*{\CodeIcon\ Most Likely State Estimation (10 points)}

Implement \mintinline{python}{MostLikelyStateEstimator} in \mintinline{python}{most_likely_state.py}.
This estimator should update the belief state to be a distribution with just a single state that has 1.0 probability.
In addition, implement \mintinline{python}{CustomPOMDP} in such a way that using this most likely state estimator leads to suboptimal performance.
Examine the unit tests in \mintinline{python}{test_most_likely_state.py} to make sure you understand the question.
No written answer required.

\begin{ponderbox}
Is it ever possible to perform information-gathering when using the most likely state estimator?
\end{ponderbox}

% \subsection*{\CodeIcon\ QMDP (15 points)}

% TODO (implement MLS and QMDP, then a POMDP where QMDP is better than MLS)

% \begin{ponderbox}
% TODO
% \end{ponderbox}

\section*{Part 3: Your Turn to Teach}

\subsection*{\WritingIcon\ Create a Question (10-15 points)}

Create a new question of any kind (writing, coding, etc.) that pertains to the material covered in this problem set.
To receive full credit, you only need to write the question.
To receive up to 5 points of extra credit, you should also provide a solution.
Extra credit points will also be awarded based on creativity and effort.
Please indicate in your answer (1) whether your question can be used (with modifications) in future versions of this course; and (2) whether you would like to be credited by name if your question is used.

\section*{Part 4: Feedback}

\subsection*{\WritingIcon\ General Course Feedback (5 points)}

How can we improve the course in future years? Any and all feedback is welcome. Please comment on this problem set, lectures, and anything else.
Some feedback is required for full credit.
If you prefer to additionally submit anonymous feedback, please do so through the course website.

% \AnswerBox{6cm}

\end{document}
