16-311 - Spring 2022

Introduction to Robotics




Key Information

Mondays, Wednesdays, Thursdays (Lab), 11:30am - 12:45pm, Room CMB 2147

Dr. Eduardo Feo-Flushing

12.0

35% Weekly Homework, 10% Labs, 17% Final Project, 20% Final exam, 18% Midterm exam

Most of the material will be provided by the instructor, additional info can be found in:

  • P. Corke, Robotics, Vision and Control, Springer, 2017
  • K. Lynch and F. Park, Modern Robotics, Cambridge University Press, 2017
  • N. Correll, B. Hayes, C. Heckman, A. Roncone, Introduction to Autonomous Robots: Mechanisms, Sensors, Actuators, and Algorithms, MIT Press, 2021
  • S. Thrun, W. Burgard, D. Fox, Probabilistic Robotics, MIT Press, 2006
  • R. Siegvart, I. Nourbakhsh, D. Scaramuzza, Autonomous Mobile Robots, 2011
  • J. Lentin, Mastering ROS for Robotics Programming, Packt Publishing, 2015

Overview

The course will provide a general overview of robotics. The fundamental concepts, mathematical models, and actuation/sensing devices that are necessary to design and control a robotic system will be studied, including:

  • Forward and Inverse Kinematics
  • Proprio- and Exteroceptive Sensing
  • State Estimation with Gaussian and Bayesian Filters
  • Feedback-based Control
  • Machine learning approaches to Robot Control
  • Paradigms and Architectures for Robot Control
  • Localization and Mapping
  • Motion Planning
  • Robot Navigation

Both autonomous mobile robots (wheeled robots) and robotic arms will be studied. Robot programming and control will be based on ROS, while Gazebo will be used for simulation studies.

The robots that will be used for practice during the course are shown in the figure below, they include the following: TurtleBot 2 and 3 (Waffle), PhantomX Reactor AX-12 Robot Arm, Erle Rover, Anki Cozmo.


Students who successfully complete the course will acquire:

  • Core knowledge, both theoretical and practical, of modeling, programming, and control for mobile (wheeled) and arm robots;
  • Working knowledge of ROS and Gazebo for real and simulated robots;
  • Familiarity with fundamental issues and potentialities of autonomous and industrial robotic applications;

Moreover, the students will be exposed to a number of formal notions whose importance and application goes well beyond robotics, including: topology, control theory, statistical estimation and filtering.


Course Layout

The course includes theory classes, interactive laboratory classes, homework, and project. Students will learn how to use ROS (Robot Operating System) and the (multi-robot) simulator Gazebo, and will apply the learned concepts through the programming of a number of robots, both in simulation and with real robots.

The first two lectures of each week will be theory lectures, that will focus on mathematical and algorithmic aspects.

The third lecture of the week will be an interactive lab / recitation that will emphasize the pragmatic facets of implementing and controlling robotic and mechatronic devices, and will consist of a mix of theory and hands-on robots and simulation.

At the end of the lab, the students will have to submit their answers (which will be graded) to questions about topics addressed in the lab.

There will be homework assignments, which will consist of:

  • Weekly homework, that will include both questions to be answered and programming assignments (in simulation and/or with real robots). Possibly, a total of 10 homework will be assigned.
    The programming / robot implementation part of each homework will have to be practically demonstrated by the student in a live demo.
  • One final project, that will consider a real-world scenario and will require to employ and coordinate all the major results achieved in previous homework plus the topics addressed during the last weeks of the course. The project will have to be completed during the last four weeks of the course.
    The students will have to submit a written report describing their work and make a live demo with the robots.
    Project will be done in teams (from 1 up to 3 students).


Prerequisites

Formal prerequisites: 21-240 (Matrix Algebra) Min. grade C, or 21-241 (Matrices and Linear Transformations) Min. grade C, or 18-202 (Mathematical Foundations of Electrical Engineering) Min. Grade C, or 21-260 (Differential Equations) Min. grade C, or 24-311 (Numerical Methods) Min. grade C.

Practical prerequisites: Since the course will cover a number of different topics, students should also have: experience with Linux systems, previous programming experience (programming assignments will be given in Python), a solid general CS background, basic notions of calculus, and basics of probability theory.

Please talk to the instructor if you are unsure whether your background is suitable or not for the course.

Grading

In addition to the above mentioned Weekly Homework, review questions at the Labs, and Final Project, the class also includes one Midterm exam and one Final exam. Both will be written assignments with multiple questions to answers and problems to solve.

Grading will be assigned based on the following weighting:

  • 35% Weekly Homework
  • 10% Labs
  • 17% Final Project
  • 20% Final exam
  • 18% Midterm exam


Readings

There is no required textbook for this class. The students should be able to learn everything from lecture handouts, homework, and the additional material provided by the instructor. However, the following books will cover good parts of the course:

  • P. Corke, Robotics, Vision and Control, Springer, 2017
  • K. Lynch and F. Park, Modern Robotics, Cambridge University Press, 2017
  • S. Thrun, W. Burgard, D. Fox, Probabilistic Robotics, MIT Press, 2006
  • R. Siegvart, I. Nourbakhsh, D. Scaramuzza, Autonomous Mobile Robots, 2011
  • N. Correll, B. Hayes, C. Heckman, A. Roncone, Introduction to Autonomous Robots: Mechanisms, Sensors, Actuators, and Algorithms, MIT Press, 2021
  • J. Lentin, Mastering ROS for Robotics Programming, Packt Publishing, 2015

Schedule

Date Topics Handouts References
1/10 Introduction, Road map: Characterization of a robotic mechanism; components of a robotic system: links and joints, effectors and actuators, goals, autonomy, open and closed loop control, sensing and perception; general architecture and information flows; robotics as an interdisciplinary field of study; road map of the course: the robots, ROS, topics; educational goals; course organization and logistics. pdf P. Corke, Robotics, Vision and Control: Chapter 1
1/12 Robot pose, Coordinates, Configuration space, Constraints, DOF: Reference frame and coordinate systems; examples of coordinate systems; pose: concepts and importance; rigid body assumption and point abstraction; robot configuration and generalized coordinates; configuration space, C-space; basic notions on rotation groups and manifolds; holonomic constraints; degrees of freedom (DOF). pdf pdfK. Lynch, Modern robotics: Chapter 2
1/13 DOFs, Workspace, Task space, C-space & Topological spaces: Examples of calculation of DOF for single body and multi-link robots; DOF of a joint; open chaain vs. closed chain mechanisms; Grubler's formula; DOF and control; workspace and task space, examples with robot arms and mobile single body robots; C-space of a mobile robot and point reduction.

Lab - Introduction to ROS and Gazebo: Basic concepts about ROS, a first example, installation.
pdf (theory)

pdf (intro to ROS)

Lab practice
K. Lynch, Modern robotics: Chapter 2
Start with ROS
1/17 Pose representation, transformation, and composition 1: Pose representation and relative poses; properties of poses as an additive group; representing spatial relations and compting with relative poses; poses in 2D and matrix representation; derivation of rotation matrix; homogeneous transformation matrix, 2D and 3D; SE(2), SE(3) group properties; no commutatitivity; intro to relative poses in 3D and homogeneous matrix in 3D. pdf P. Corke, Robotics, Vision and Control: Chapter 2
1/19 Pose representation, transformation, and composition 2: Poses and relative poses in 3D using homogeneous matrix; redundant / implicit vs. explicit representations non-commutativity; orientation and right/left-hand rules for coordinate axes; Euler's theorem; elemental rotations; RPY sequences, calculations; atan2(y,x) function for deriving the angle; notions about the ROS tf package for dealing with frame transformations; ROS frames, odometry frame; quaternions are implicit representation of orientations in 3D; basic properties and rules to transformation from/to rotation matrices/angles. pdf P. Corke, Robotics, Vision and Control: Chapter 2

Tutorial on Quaternions (Ch. 4)
1/20 Lab - ROS hands-on: Pose representation and transformation, TF, Rviz Python for pose handling:
PDF
Notebook
Lab practice
Video: tf broadcastener-listener demo
1/24 Kinematics 1: Kinematics vs. Dynamics; Forward and Inverse kinematics and their use; forward kinematics equations for a simple robot arm; notions and challenges of inverse kinematics; forward kinematics as a homogeneous transform; forward differential kinematics: equations and formalism; calculus: partial derivatives, gradients, composite functions, chain rule; matrix form of differential kinematics using Jacobian matrix. pdf C. Correll et al., Introduction to autonomous robots: Chapter 3
1/26 Kinematics 2: Forward kinematics of manipulator vs. mobile robots: holonomic vs. non-holonomic robots; closed-loop paths in joint space and (non) holonomicity; properties of wheeled mobile robots; properties and arrangement of wheels, DoF; assumptions on wheels, pure rolling, no lateral motion; differential steering robots; computing pose for a differential robot and non-holonomic constaints; need for differential kinematics; unicycle model; pose velocity expressed in different forms and in inertial and robot frame; use of rotation matrix; robot's configuration variables and configuration velocities; summary of expressions of differential forward kinematics equations; relationship to Jacobian; integration of equations for pose prediction. pdf C. Correll et al., Introduction to autonomous robots: Chapter 3
1/27 Lab + Kinematics 3 (in practice):First hands-on Turtlebot3 in the Lab; Summary of kinematic equations; practice computing a pose velocity; integration of kinematic equations and special / easy cases; practice computing a pose by integration; simplified inverse kinematics; dead reckoning / odometry for estimating a pose in practice; brief introduction to numerical integration of kinematic equations. pdf Recording of the lab session (Instructions for ROS) PWD: 6.pRsg^9
1/31 Break, no class
2/2 Kinematics 4: Inverse kinematics and plath planning, use of motion primitives to implement a plan; Center rotation and Instantaneous Center of Rotation (ICR) for a rigid body, multi-link robot, mobile robot; relationship between ICR and placement and type of wheels on a robot chassis; ICR and maneuverability; time equations of the ICR, use for forward kinematics of differential drive ad car-like robots; robot pose differential evolution as time function of ICR and derivation of exact kinematic equations; dead reckoning / odometry for estimating pose by online numeric integration of kinematic equations; Euler, Runge-Kutta, Exact methods for numeric inetgration. pdf
2/3 Lab: from simulation to real robots Writeup
Lab practice
Guide to use LiPo batteries
Sample code for making a square
2/7 Feedback control 1: General scheme of closed-loop control; types of robot goals and of controllers; dynamical system and control, general equations; bang-bang controller: control based on direction of error, two-state system, hyesteresis; control based on magnitude of error: proportinal control; notion of gain; intergral controller for as a form of adaptive control; PI controller; derivative control to capture onset of error; PID controller. pdf
2/9 Feedback control 2: PID concepts via a wall-following task example; wall-follwoing and reference signal tracking tasks; PID controls for car-like robot: move to a point, follow a line, follow a path, move to a pose; limitations of PID controllers; PID's response figures vs. gains; heuristics for gain tuning: ascent methods, Ziegler-Nichols (open-loop and closed-loop tuning). pdf P. Corke, Robotics, Vision and Control: Chapter 4
2/10 Lab - Move to a goal, pose-reaching, and path-following in closed-loop; tune a controller pdf Code skeleton

Show path
Lab practice
2/14 Sensors 1: Sensors for a mobile robot; sensor types, taxonomy; properties and profiling of a sensor; sensors for dead reckoning; compasses; inclinometers; accelerometers; gyroscopes; IMUs and inertial navigation systems; map-based sensors; global positioning systems (GPS, differential GPS, RTK) pdf
2/16 Sensors 2: Range-finder sensors; ultrasonic range sensors; contact sensors; proximity sensors; laser range sensors; 2D and 3D laser scanners; TOF cameras; structured light camera pdf
2/17 Lab - Use range sensors for closed-loop motion
2/21 Maps, Navigation in presence of Obstacles 1: Behaviors for motion in presence of obstacles: Bug 1 and 2 algorithms; obstacle avoidance and local/global maps; general properties and taxonomy of maps; map indexing; local maps and occupancy grids; use of sensor models and Bayes rule for probabilistic updating; case study of range / ultrasonic sensors; sequential Bayes for information fusion and continual updating of posteriors pdf
2/23 Maps, Navigation in presence of Obstacles 2: Obstacle avoidance and local motion planning; taxonomy of obstacle avoidance algorithms; selecting directions: vector field histogram; selecting velocities: dynamic window adaptation (DWA); set of velocities and objective function; DWA in practice; issues with narrow passages and dependence on dynamic window. pdf DWA reference paper
Tuning DWA in ROS
2/24 Lab - Sensor-assisted robot navigation Lab practice
2/28 Spring break
3/2 Spring break
3/3 Spring break
3/7 State estimation I: data fusion and localization with Kalman filters Adding a noise component to kinematic equations; stochastic discrete-time dynamical system for robot's pose; Detour on probability theory: univariate case (mean, variance, probability distributions), multivariate case, multivariate normal, equation and covariance, notion of covariance and covariance matrix, special cases of covariance matrix, level sets of Gaussians; robot's pose, mean and covariance of the estimator; assumption of Gaussian white noise; need for linearization of the dynamical system; linearization + normality as fundamental assumptions of Kalman filter. pdf Multivariate Gaussians 1
Multivariate Gaussians 2
3/9 State estimation II: data fusion and localization with Kalman filters General scenario for map-based localization using proprioceptive and exteroceptive measures; structure and equations of Kalman filter: process model and observation model; system equations, parameters to set and initial conditions; update scheme of KF; properties of KF; KF equations and probability posteriors; scalar example: filtering sensor measures; impact of parameter choices. pdf KF explained
3/10 State estimation III: data fusion and localization with Kalman filters Analysis of the equations for the scalar filtering problem; KF as information fusion and maximum-likelihood estimation; belied evolution and robot localization in one dimension; KF as low-pass filter, adaptive exponentially weighted average; impact of parameters for an accelerometer use case; filtering and fusion problems: n range and bearing sensors; multi-vaiable scenarios; Extended Kalman Filter (EKF) for robot pose estimation; Taylor series and function approximation; gradients and Jacobians for linearization of kinematics equations; equations and Jacobians of the robot's EKF; effect of linearization on accuracy of estimates; growth of process covariance. pdf
3/14 State estimation IV: Extended Kalman filters, Bayesian filters: Linearization of both motion and observation equations; Jacobians; map-based observations of landmarks; range and bearing measures using visual tags; quantification of innovation; EKF example using landmarks and using visual beacons; summary view of KF and EKF; limitations of Kalman filters; need for non-parametric filters; filters as recursive probabilistic inference. pdf P. Corke, Robotics, Vision and Control: Chapter 6.1-6.2
3/16 State estimation V: Bayesian filters, Particle filters, Monte Carlo localization: State estimation and probabilistic inference; sequential probabilistic inference in controlled systems; Markov assumption; definition of a general form recursive Bayesian filter; prediction and correction steps; motion and observation models; parametric vs. non-parametric Bayes filter; estimation of arbritrary distributions; sampling and importance sampling; particle filter; particles and resampling; particle filter for localization: Monte Carlo Localization (MCL); examples of MCL at work, illustration of the concepts. pdf S. Thrun et al., Probabilistic Robotics: Chapter 2 (Bayes filters)
Chapter 4.2 (Particle filter)
Chapter 8.3 (MCL)
P. Corke, Robotics, Vision and Control: Chapter 6.7-6.8
3/17 Lab - Localization for planar mobile robots Lab practice
3/21 SLAM 1: Bayes filters and role of observation model: scan measurements and occupancy grid, visual markers and landmark map; scenarios for robot localization and mapping using Bayes filters / EKF; road map to SLAM; EKF for estimating landmark positions: known pose and number of landmarks; EKF for estimating landmark positions: known pose and unknown number of landmarks. pdf P. Corke, Robotics, Vision and Control: Chapter 6.3
3/23 SLAM 2: SLAM problem: definition, general properties, challenges; EKF for SLAM from previous EKFs: model equations, Jacobians, filter equations; covariances and correlations; loop closure; uncertainty and computational issues; examples in indoor and outdoor scenarios. pdf P. Corke, Robotics, Vision and Control: Chapter 6.4
3/24 Lab - Landmark-based SLAM in a 2D environment Lab practice
3/28 SLAM 3, Project presentation: Data association; maximum likelihood criterion for data association; innovation and Mahalanobis distance; properties of Mahalanobis distance; use for data/landmark association; validation gates; settings for validation gates. pdf Project assignment
3/30 Break, no class
3/31 Break, no class
4/4 Motion planning I: Planning for goal-oriented agents; robot control architectures: deliberative, reactive, hybrid; motion planning and its characterizations; general propeties and design choices; configuration space and state evolution; definition of C_free and C_obs; path planning for point robot in configuration space; definition of basic path planning (piano mover's problem): parametric continuos path in C_free; derivation of velocity controls from geometric path; defintion of trajectory planning; objectives and metrics; construction of C_free in the topological configuration space; intractability of general case and approximation with distance measurement algorithms, coverage by convex shapes (spheres); summary of challenges of motion planning. pdf K. Lynch, Modern robotics: Chapter 10.1 - 10.2.2
S. LaValle, Planning algorithms: Chapters 1,4
4/6 Motion planning II: Approaches to discretization of C-space; roadmaps: definitions and properties; semi-free space and optimal paths in polygonal world; from optimal paths to visibility graphs as roadmaps; reduced visibility graphs, construction complexity; generalized Voronois graphs as roadmaps; construction and properties of Voronoi diagrams; planning in Voronoi maps; discretization and roadmaps by spatial decomposition; cell shapes and reference points, navigation; exact vs. approximate cell decomposition. pdf
4/7 Feedback on project proposals
4/11 Motion planning III: Discretization and roadmaps by spatial decomposition (continued); uniform grids vs. iterative cell decomposition, quad/oct-trees; wavefront propagation for path finding in spatial grids; navigation functions and flood-fill of cost-to-go values; path improvements by shortcuts; exact spatial decomposition with polygonal and cylindrical objects; from combinatorial planning to sampling-based planning; general scheme of sampling-based approaches: iterative sampling, collision-detection, local planner. pdf K. Lynch, Modern robotics: Chapter 10.3 - 10.4
4/13 Motion planning IV: Sampling-based planning: core concepts and motivations; probabilistic road maps (PRMs),: construction, properties, probabilistic completeness, neighbor selection, connecting start and goal, strategies for importance sampling; properties and examples of local planners for different robots; Rapidly-exploring random trees (RRTs): construction, impact of strategic parameters, properties; RRT* and its variants for asympotic optimality; bidirectional search and RRT; limitations and difficult case scenarios; continuous motion planning with potential fields (optional). pdf K. Lynch, Modern robotics: Chapter 10.5 - 10.6
4/14 Review and practice of topics covered during the course
4/18 Review and practice of topics covered during the course
4/20 (Midterm) Exam
4/21 Checkpoint on Final Projects
4/28 Final Exam (Room 2147)

Homework Assignments

Topic Files Due Dates
Homework 1 - Basic use of ROS and Gazebo - 1/20
Homework 2 - Pose transformation, dead reckoning, numeric integration of kinematic equations - 1/27
Homework 3 - Forward and inverse kinematics for mobile robots - 2/3
Homework 4 - Forward and inverse kinematics for arm robots - 2/10
Homework 5 - Feedback-based control - 2/17
Homework 6 - Use of proprioceptive and exteroceptive sensors - 2/24
Homework 7 - Map-building and road navigation using range finders and vision sensors - 3/10
Homework 8 - Gaussian filters for state estimation and data fusion - 3/17
Homework 9 - Localization with Bayesian filters - 3/24
Homework 10 - Landmark-based SLAM for mobile robots - 4/7
Final Project - Full scenario: SLAM -> Planning -> Navigation (+ Localization + Closed-loop control) - 4/21

Homework policies

  • Weekly Homework and the Final Project are due by the posted deadlines. Lab answers must be handed out by the end of the lab session.

  • If a weekly homework is not submitted by the due date, it can still be submitted within one week time, but the score will decreased by 30%. No submission will be allowed over one week past the original due date.

  • For homework and labs, you can discuss the exercises with your classmates, but you should write up your own solutions. If you find a solution in any source other than the material provided on the course website, you must mention the source.

  • In general, for all assignments and exams, CMU's directives for academic integrity apply and must be duly followed. Students are required to refer to CMU's general policies on cheating and plagiarism: https://www.cmu.edu/policies/student-and-student-life/academic-integrity.html

Exam dates and policies

The midterm exam is set for March 28. The students can consult the slides and bring 1-page cheatsheet.

The final exam will be held after the end of the course, during the allowed days for exams between April 24 and April 28. During the exam students are allowed to consult 1-page cheatsheet (written in any desired format).

Students with special needs or disabilities are kindly asked to talk about it to the teacher at the beginning of the semester and make use of the assistance procedures provided by CMU https://scotty.qatar.cmu.edu/qword/student-affairs/office-of-health-and-wellness/assistance-for-individuals-with-disabilities/

Office Hours

Name Email Hours Location
Gianni Di Caro gdicaro@cmu.edu Thursdays 1:30-2:30pm + Drop in at my office any time I'm there ... M 1007