CSCE 452/752: Review Sheet for Test 1

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

Format

The test will be conducted in person, on paper.
The test will cover material up to and including September 22.
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.

1. Introduction

What is a robot? Defining characteristics. Mount Fuji illustration.
Why is robotics hard? The fundamental problem.
Why can't we focus strictly on computing issues?
Four fundamental problem types. What does each problem type ask the robot to do?

2. Robot hardware

Actuators: motors (simple DC and gearhead), stepper, servo, linear actuator.
Sensing: encoder, infrared sensor, camera, RGBD sensor, sonar, lidar, IMU, compass, GPS, inclinometer
Modes of locomotion
Proprioception and exteroception
Evaluating sensors: Active vs passive. What is the difference? Which sensor types are active? Which are passive? Proprioception vs. exteroception. Criteria for evaluating sensors.

3. A Quick Tour of ROS

What is ROS? Why is software like ROS necessary? Distributed computation. Code reuse. Seamless simulations.
Meanings and relationships between various ROS objects: packages, nodes, topics, publishers, subscribers, messages
What is the ROS graph?
What ROS concepts are used for one-way many-to-many communication? Two-way one-to-one communication?
No specific questions about the details of Project 1, but the main ROS concepts explored by that project may appear on the test.

4. Basic models for robot motion and perception

States and actions What are they? $x$, $X$, $u$, $U$.
Models of time. Discrete, continuous. Explicit, implicit. $t$, $k$.
Transitions. Discrete vs. continuous time. With errors and without. $f$, $\theta$
Observations. Observation functions, with errors and without. $y$, $Y$, $h$, $\psi$
Plans. Different types of plans: sequence, trajectory, state-feedback, information-feedback.

5. Differential drive locomotion

Drive vs. steered vs. passive wheels.
Using the differential drive ICC equations. Special cases for differential drive movement. Updating the state for a diff drive.
Navigate with a differential drive to a given target.

6. Other wheeled systems

What is an ICC? How to find ICC? What assumptions is this analysis based on? What happens if no ICC exists?
How to find the ICC.
ICC analysis for bicycle, synchro, tricycle, and Ackerman drive.
Alternatives to simple wheels for terrestrial navigation.

7. Navigation: Bug algorithms

Basic model. How does the robot move? What can it sense? Be able to tell if the Bug algorithms are applicable in a given situation.
Why doesn't the naive optimistic algorithm ('Bug0') work?
Online vs. offline algorithms. Planning and execution interleaved vs. forming a complete plan before moving. Be able to apply these concepts to all of the navigation algorithms we've learned.
Hit points and Leave points
Bug1. Be able to execute the algorithm. Be able to state and explain an upper bound on path length. What if the goal cannot be reached?
Bug2. Be able to execute the algorithm. Be able to state and explain an upper bound on path length. What if the goal cannot be reached?
Comparison between Bug1 and Bug2. Be able to explain when Bug1 is better. Be able to explain when Bug2 is better.

8. Navigation: Visibility graphs

Applicability: Under what conditions can the visibility graph method be used?
Definition: What are the nodes? What are the edges? Be able to draw the visibility graph for a given set of obstacles.
How do we know that the shortest path must be along the visibility graph?
Difference between visibility graph and reduced visibility graph. Be able to identify edges that are in the visibility graph but not in the reduced visibility graph.

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$