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 occur at a scheduled time on February 16. 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 the week of February 9.
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.

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. $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 Systems

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}{\ell} $ $ \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$