Format
- The test will be conducted in person, on paper.
- The test will cover material up to and including December 8.
- The test will be designed to be completed in 75 minutes, but you may take up to 120 minutes if needed.
- No notes nor electronic devices are permitted. Questions will be structured so that computations typically requiring a calculator will not be required.
- 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.
15. Motion planning
- What is a configuration space? Why is it important?
- Example C-spaces: Translating disk in the plane, translating and rotating polygon in the plane, robot arm with revolute joints. Be able to determine the configuration space for similar kinds of systems.
- Common C-spaces: $SO(2)$, $SE(2)$, $SO(3)$, $SE(3)$ What do these represent? How many dimensions does each have?
- Obstacle configurations. Relationships between configuration space, obstacle space, and free space. Difference between configuration space and work space.
- Collision detection. Checks for points or for short segments in C-space. How does this differ from explicit construction of C-space obstacles?
- Motion planning problems. What are the inputs? What are the outputs? Hardness of Combinatorial approaches.
- Basic idea of sampling-based algorithms: Avoid representing the obstacle boundaries explicitly.
- Probabilistic roadmaps (PRM).
- Rapidly-exploring random trees (RRT). Voronoi bias. What does this term mean? How does it describe the growth of the tree? Which vertices can possibly have new children added? Which vertices are most likely to have new children added?
- What does “completeness” mean? Is PRM complete? Is RRT complete? Probabilistic completeness: What does it mean? What algorithms have this property?
- When is motion planning hard?
- Comparison between PRM and RRT. Single query vs. multiple query.
16. Asymptotically Optimal Motion Planning
- What problem with standard motion planning do AO algorithms solve? Why does path smoothing fail to solve this problem?
- RRT$^*$: How does it differ from the standard RRT? What information is maintained for each node? Choosing the parent for new nodes. Rewiring the tree.
- Asymptotic optimality. What does it mean? How is it different from probabilistic completeness?
17. Pursuit and Evasion
- Problem definition. What can the pursuer see? What can the evaders do? What is the goal? What input does the algorithm receive? What output does the algorithm produce?
- Gaps: What is a gap? Clear and contaminated labels. Initial labels? Goal labels? How can gaps change? Appear, disappear, split, merge. How do the labels change for each of these events?
- Algorithm: What is a conservative region? How to divide the environment into conservative regions. Information graph nodes. Information graph edges. Where do we start in the information graph? What's the goal in this graph? How to reconstruct a path in the environment from a path in the graph. Recontaminations.
Provided equations
These equations will appear, without any explanation, on the exam paper:
$ 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}
$
$ \lim_{n \to \infty} P(\text{failure}) = 0 $
$ \lim_{n \to \infty} E[c(P)] = c^* $