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 be conducted in person, on paper.
The test will cover material up to and including November 3.
The test will be designed to be completed in 75 minutes.
No notes nor electronic devices are permitted. 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:

$ x_{k+1} = f(x_k,u_k) $ $ \dot{x} = f(x,u) $ $ y_k = h(x_k) $ $ y(t) = h(x(t)) $ $ R = \left(\frac{l}{2}\right) \frac{v_r + v_l}{v_r - v_l} $ $ \omega = \frac{v_r - v_l}{l} $ $ \left[ \begin{matrix} x_{k+1} \\ y_{k+1} \\ \theta_{k+1} \end{matrix} \right] = \left[\begin{matrix} \cos (\omega \Delta t) & -\sin(\omega \Delta t) & 0 \\ \sin (\omega \Delta t) & \cos(\omega \Delta t) & 0 \\ 0 & 0 & 1 \end{matrix}\right] \left[\begin{matrix} x - c_x \\ y - c_y \\ \theta \end{matrix}\right] + \left[\begin{matrix} c_x \\ c_y \\ \omega \Delta t \end{matrix}\right] $ $D + \frac{3}{2} \sum_{i=1}^M p_i$ $D + \frac{1}{2} \sum_{i=1}^M n_i p_i$ $ \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} $