CSCE 452/752: Review Sheet for Test 2

This review sheet is intended as a guide to help you prepare for Test 2.

Format

The test will occur at a scheduled time on March 25. You will have an opportunity in the week before the exam to share time preferences and constraints — watch for a request in your email!
The test will be proctored via Zoom.
- Zoom links will be shared by email on the day of the exam.
- You must participate in the Zoom session by video, and the proctor must be able to see you for the length of the exam.
- Log in to zoom using your TAMU NetID.
- The zoom session will use a waiting room. The proctor will let you into the room after the beginning of the time slot, but before the exam starts.
The test will be distributed in PDF format as an activity in Canvas.
Because the answers may not be entirely textual —for example, you might be asked to draw a diagram, annotate a figure, write an equation, etc.— it is recommended to print the exam, complete it on paper, and then scan and submit. Scanning can be done, for example, using the Google Drive app on an Android Device, or the Notes app on an iOS device, or even an old school flatbed scanner. If you do not have access to a printer, you may write your answers on blank paper, as long as the question numbers are clearly marked.
The test will cover material up to and including March 23.
The test will be designed to be completed in 75 minutes. The exam time slot includes a short buffer to account for set up and submission.
No notes, external reference material, nor calculators are permitted. No electronic devices or apps other than what is needed to submit your answers.
Questions will be structured so that computations typically requiring a calculator will not be required.

Some types of questions to expect:

Questions similar in spirit to the homework assignments.
Questions in a similar format to the homework assignments, but covering different topics.
Questions that probe your understanding of specific terms introduced in the lectures.
Questions that probe your understanding of ROS concepts from the projects.
Questions that probe your understanding of important diagrams or figures from the lectures.
Questions that ask you explain why a statement is correct or incorrect.

Question formats will include both multiple choice ("Choose A, B, C, or D") and short answer questions ("Solve", "Draw", "Explain", etc.).

Remember that the homework assignments are graded on the basis of making a reasonable good-faith attempt to solve the problem. That is, receiving full credit on the homework is not a sign that your answers were correct.

9. Navigation: Potential fields

When are potential fields applicable? Intuitive explanation of how potential fields work.
Domain and range of the potential function. Robot follows the negative gradient of the potential function.
Definition of typical potential function as sum of attractive and repulsive forces. Details for attractive and repulsive components.
Notation: $x$, $U(x)$, $\zeta$, $\eta$, $Q_i^*$, $d_i$
Local minima. What are they? Why do they cause problems for potential fields? Possible solutions.

10. PID Control

What is control theory about?
Notation: $X$, $U$, $x(t)$, $u(t)$, $\dot{x}$, $f(x,u)$.
Set point. Error.
Open loop (no feedback) vs. closed loop (with feedback). Why is feedback useful?
PID control: Gains. Purpose of each term. Discrete time approximation.

11. Localization 1: Dudek-Romanik-Whitesides Localization

What is localization? Types of localization problems. Active versus passive. Global versus local.
Dudek-Romanik-Whitesides localization. It's active and global. What information does the robot have access to? No sensor noise. Visibility polygons. Be able to explain the importance of the robot's compass. What's the robot's goal?
Hypothesis generation. General idea, purpose. intuition of algorithm. How many hypotheses can there be? What does the set of possible states look like after the robot takes its first sensor reading?
Decision trees. What information is stored at internal nodes? Leaves? Edges? How to “execute” the strategy described by a decision tree.
Hypothesis elimination. How to compute visibility cell decomposition. Why is this decomposition useful? How and why to “overlay” multiple copies of the visibility cell decomposition. How to generate a decision tree (possibly many levels) from these overlays.

12. Localization 2: The Kalman Filter

Recall from before: notation for modeling motion ($X$, $x$, $U$, $u$, $\Theta$, $\theta$, $f$) sensing ($Y$, $y$, $\Psi$, $\psi$, $h$) with errors.
What is a Linear-Gaussian system? Linear transitions, linear sensing, Gaussian noise. Know the notation for describing an LG system: $A$, $B$, $C$, $G$, $H$, $\Sigma_\theta$, $\Sigma_\psi$. Why are LG systems special?
Kalman filter: What are its inputs? What are its outputs?
Kalman filter updates. Know how to use the update equations.
What's the difference between the Kalman filter and the EKF? When does the EKF apply? Main idea behind EKF.

13. Localization 3: Histogram filters and particle filters

Why do we need more algorithms beyond the KF and EKF?
In the figure titled “Basic idea of probabilistic localization,” why does the final distribution have 5 peaks? Why do these peaks have different shapes? What history does each peak correspond to?
Transition models and observation models. What is each describing?
Histogram filter: How does it work? What tradeoffs occur from the choice of cell size?
Particle filter: Represent the distribution indirectly by a set of samples. How to initialize? How to update when an action occurs? How to update when an observation occurs? What is forward projection? Where do the weights come from? How does the resampling step work? Why is resampling important?

14. Simultaneous Localization and Mapping

Definition. What's the goal? Why is SLAM harder than either localization or mapping alone?
Mapping without worrying about localization. How is the map represented? Understand the role of each part of the update equation for occupancy grid probabilities. Observation models. Prior probabilities.
SLAM algorithm. Treat as a huge localization problem in a much bigger state space. Disadvantage to this viewpoint. What is Rao-Blackwellization? What kinds of particles does the algorithm maintain? How are the particles updated? How does this algorithm use the “mapping without worrying about localization” algorithm?

Provided equations

These equations will appear, without any explanation, on the cover sheet:

$ \newcommand{\goal}{_{\rm goal}} \newcommand{\obst}{_{\rm obst}} U(x) = U\goal(x) + \sum_i U^{(i)}\obst(x) $ $ U\goal(x) = \frac{1}{2} \zeta \left[d(x, x\goal) \right]^2 $ $ U^{(i)}\obst(x) = \begin{cases} \frac{1}{2} \eta \left( \frac{1}{d_i(x)} - \frac{1}{Q_i^*} \right)^2 & \text{if } d_i(x) \le Q_i^* \\ 0 & \text{if } d_i(x) > Q_i^* \\ \end{cases} $ $ u(t) = K_p e(t) + K_i {\Large\int}_0^{\,t} e(\tau) \mathrm{d}\tau + K_d \frac{\mathrm{d}e}{\mathrm{d}t} $ $ u_k = K_p e_k + K_i \left(\Delta t \sum_{i=1}^k e_i \right) + K_d \left(\frac{e_k - e_{k-1}}{\Delta t} \right) $ $x_{k+1} = Ax_k + Bu_k + G\theta_k$ $y_{k} = Cx_k + H\psi_k$ $ \Sigma^\prime_{k+1} = A \Sigma_k A^\top + G \Sigma_\theta G^\top $ $ L_{k+1} = \Sigma^\prime_{k+1}C^\top ( C \Sigma^\prime_{k+1} C^\top + H \Sigma_\psi H )^{-1} $ $ \mu_{k+1} = A \mu_k + B u_k + L_{k+1}( y_k - C(A \mu_k + B u_k) ) $ $\Sigma_{k+1} = (I - L_{k+1}C)\Sigma^\prime_{k+1} $ \begin{multline*} P(x_k | u_1, \ldots, u_{k-1}, y_1, \ldots, y_k) \\ = \alpha_k P(y_k \mid x_k) \sum_{x_{k-1} \in X} \left[ P(x_k | x_{k-1}, u_{k-1}) P(x_{k-1} \mid u_1,\ldots,u_{k-2},y_1,\ldots,y_{k-1}) \right] \end{multline*} $ P_{\ell,k} = \left[ 1 + \left(\frac{P(m_\ell = 0 \mid x_k, y_k)}{P(m_\ell = 1 \mid x_k, y_k)} \right) \left(\frac{1 - P_{\ell,k-1}}{P_{\ell,k-1}} \right) \right]^{-1} $