CSC477: Introduction to Mobile Robotics

Course Overview

This undergraduate course provides an introduction to robotic systems from a computational perspective. A robot is regarded as an intelligent computer that can use sensors and act on the world. We will consider the definitional problems in robotics and look at how they are being solved in practice and by the research community. The emphasis is on algorithms, probabilistic reasoning, optimization, inference mechanisms, and behavior strategies, as opposed to electromechanical systems design. This course aims to help students improve their probabilistic modeling skills and instill the idea that a robot that explicitly accounts for its uncertainty works better than a robot that does not.

Prerequisites

Required: CSC209H5; STA256H5; MAT223H5/MAT240H5; MAT232H5; CSC376
Recommended: MAT224H5; CSC384H5; CSC311H5;

Course Delivery Details

  • Lectures: Wednesdays @ 11am-1pm ET, IB260 + Zoom
  • Tutorials: Wednesdays @ 1pm-2pm ET, MN3110 + Zoom
  • Instructor Office Hours: Wednesdays @ 10am-11am ET, DH3066 + Zoom
  • TA Office Hours: Mondays @ 12pm-1pm ET, Zoom
  • Announcements will be posted on Quercus
  • Discussions will take place on Piazza
  • Anonymous feedback form for suggested improvements

Teaching Staff

Florian Shkurti (Instructor, csc477-instructor@cs.toronto.edu)
S. Mohammad Sheikholeslami (TA, csc477-tas@cs.toronto.edu)

Evaluation and Due Dates

Item Due Date % of Final Grade
Assignment 1 Oct 8 10%
Assignment 2 Oct 29 10%
Assignment 3 Nov 19 10%
Assignment 4 Dec 4 10%
Midterm Test Nov 11 30%
Tutorial / Lab Activities / Quizzes (best 6 / 8) during PRA sessions (*) 10%
Final project Dec 8 20%

(*) Sept 23, Sep 30, Oct 7, Oct 14, Oct 21, Nov 4, Nov 18, Nov 25

Schedule

This page contains an outline of the topics, content, and assignments for the semester. Note that this schedule will be updated as the semester progresses, with all changes documented here.

Week Date Topic Tutorials Lecture Slides Lecture Recordings Optional Exercises Assignments Midterm Test Project Deliverables
1 Sep 9 Introduction 🖥️ 🎥 📋
Sensors and Actuators
2 Sep 16 Kinematics 📖 🖥️ 🎥 📋
Dynamics
3 Sep 23 PID Control 📖 🖥️ 🎥 📋
Artificial Potential Fields and Obstacle Avoidance
4 Sep 30 Planning 📖 🖥️ 🎥 📋
5 Oct 7 Linear Quadratic Regulator (LQR) 🖥️ 🎥 📋 ✍️
6 Oct 14 Map Representations and Map Alignment 🖥️ 🎥 📋
Occupancy Grid Mapping With Known Robot Poses
7 Oct 21 Maximum Likelihood, Least Squares Estimation, Maximum A Posteriori Estimation 🖥️ 🎥 📋
GraphSLAM
8 Oct 28 Reading Week ✍️
9 Nov 4 Kalman Filter 🖥️ 🎥 📋
Bayes’ Filter and Kalman Filter
10 Nov 11 Extended Kalman Filter (EKF) 📖 🖥️ 🎥 📋 ✅
11 Nov 18 Particle Filter 🖥️ 🎥 📋 ✍️
12 Nov 25 Camera Optics and Multi-view Geometry 🖥️ 🎥 📋
13 Dec 2 Visual odometry and Visual SLAM 🖥️ 🎥 📋 ✍️
14 Dec 8 Final project report due. 📂

Week 1

Introduction
Motivation, logistics, rough description of assignments, sense-plan-act paradigm.

Sensors and Actuators
Camera, LiDAR, tactile, IMU, depth, GPS, Hall-effect sensors, encoders, RGBD. Pulse-Width Modulation. Motors.

No Tutorials

Readings
- Dudek & Jenkin 3.1.1,4, 3.2-3, 4.1-8, 4.10, 5.1.1

Things to know
- Camera projection models: pinhole and thin-lens
- How RGB-D cameras work
- LiDAR sensors
- IMU sensors and what they measure
- Encoders and Hall effect sensors
- PWM

Week 2

Kinematics
Frames of reference. Rotation representations. Homogeneous coordinates and transformations. Rigid body motion.

Dynamics
Dynamical systems and control. Examples: Dubins car, differential drive car, unicycle, pendulum, cartpole, quadcopter. Holonomic vs. non-holonomic systems.

Readings
- Paul Furgale: robot pose
- Lavalle 13.1
- Dudek & Jenkin 3.1.5,6

Things to know
- Euler angles, quaternions, rotation matrices, and axis-angle representations
- How to convert points from one frame to another
- How to convert vectors from one frame to another
- How to find the rotation that converts one vector into another
- How to update the current rotation based on an angular velocity measurement
- What is an inertial frame?
- Dubins vehicle
- What is forward and backward kinematics?
- Rotation representations, in more detail than covered in lecture

Week 3

PID Control
Tuning, cascading PID, advantages and drawbacks.

Artificial Potential Fields and Obstacle Avoidance
Implementation issues, navigation functions. Vector-field histogram (VFH), dynamic window approach (DWA).

Readings
- Optional: Astrom and Hagglund, Ch. 2
- Lavalle Ch. 8.4
- Dudek & Jenkin 6.3.4
- Optional: Howie Choset’s notes

Things to know
- How to implement and tune a PID controller
- When is PID insufficient
- How to formulate a potential field for goal-based navigation
- Disadvantages of potential fields
- Vector Field Histogram

Week 4

Planning
Dijkstra, A*, Rapidly-exploring Random Trees (RRT), Probabilistic RoadMaps (PRM)

Readings
- Blog post on A*
- Udacity Lesson 4
- Lavalle 5.5, 5.6

Things to know
- Dynamic programming
- Sense plan act vs subsumption architecture
- Dijkstra and its use of cost-to-come as the new node visitation order
- A* and its use of cost-to-come + underestimate of cost-to-go as the new node visitation order
- Configuration space planning
- Problems with state discretization in high dimensions
- RRT, and its 5 properties
- PRM

Week 5

Linear Quadratic Regulator (LQR)
Computing optimal actions for linear dynamical systems with quadratic cost-to-go functions.

Readings
- Optional: Stephen Boyd’s LQR notes and examples

Things to know
- The derivations for 1 step of LQR
- What are the requirements on the cost function for LQR to be applied
- What are the requirements on the dynamics for LQR to be applied
- How to convert a continuous-time dynamical system to a discrete-time dynamical system for use in LQR

Week 6

Map Representations and Map Alignment
Occupancy grids, Octrees, Voronoi Graph, Homotopy Classes. Map alignment with known or unknown correspondences. Iterative Closest Point (ICP).

Occupancy Grid Mapping With Known Robot Poses
Log-odds ratio, Probabilistic dynamics and measurement models, Bayesian estimation.

Readings
- Pieter Abbeel’s notes
- Pieter Abbeel’s notes
- Probabilistic Robotics Ch. 2 and Ch. 9

Things to know
- The difference between metric, topological, and topometric maps
- Advantages and disadvantages of quadtrees and octrees
- Signed distance functions
- Homotopy classes
- Scan matching with unknown correspondences & the Iterative Closest Point (ICP) algorithm
- The proof of the occupancy grid mapping algorithm

Week 7

Maximum Likelihood, Least Squares Estimation, Maximum A Posteriori Estimation
Least squares as a special case of maximum likelihood estimation on Gaussian models.

GraphSLAM
Expectation and Covariance. Geometric interpretation of the covariance matrix. Nonlinear Least Squares formulation of the Simultaneous Localization And Mapping (SLAM) problem.

Readings
- Udacity Lesson 6
- Probabilistic Robotics Ch. 11

Things to know
- The difference between maximum likelihood and maximum a posteriori estimation
- Least squares as a special case of maximum likelihood estimation
- Smoothing vs filtering
- Cost functions in GraphSLAM

Week 8

Reading Week

No lectures or tutorials this week.

Week 9

Kalman Filter
Bayes’ rule on Gaussian distributions. Example of 1D Kalman Filter.

Bayes’ Filter and Kalman Filter
Kalman Filter as a special case of Bayes’ Filter. Examples of 2D and 4D Kalman Filter. General prediction and update equations.

Readings
- Udacity Lesson 2
- Kalman Filter, Illustrated,
- Probabilistic Robotics Ch. 2,3

Things to know
- The difference between smoothing and filtering
- The assumptions of the Bayes’ filters and Kalman filter
- How to derive the Bayes’ filter
- How to derive the 1D Kalman filter
- Whether the uncertainty grows or shrinks after the prediction step and update step
- How to derive the 2D Kalman filter
- Is the Kalman filter an optimal estimator for linear systems?

Week 10

Extended Kalman Filter (EKF)
Bayes’ Filter and nonlinear transformations. Monte Carlo sampling vs. Linearization. EKF prediction and update equations. Examples: EKF Localization and EKF SLAM.

Readings
- Cyrill Stachniss’ intro to EKF
- Cyrill Stachniss’ intro to EKF-SLAM
- Probabilistic Robotics Ch. 2,3

Things to know
- What’s the pdf of the random variable Y=aX+b when X ~ N(x; mu, sigma^2)
- Is the pdf of the random variable Y = g(X) normally distributed when X ~ N(x; mu, sigma^2)?
- Taylor approximation for multi-dimensional functions and inputs
- What are the assumptions of the Extended Kalman Filter?
- Whether the uncertainty grows or shrinks after the prediction step and update step
- How to locally linearize the dynamics model and the observation model in EKF
- Is the EKF an optimal estimator for nonlinear systems?
- How to use the EKF for localization
- The disadvantages of EKF-SLAM

Week 11

Particle Filter
Representing multimodal distributions. Particle propagation and resampling. Pathologies of particle filter. Importance Sampling. Examples: Markov localization in a known map. FastSLAM.

Readings
- Udacity Lesson 3
- Optional: Thrun’s paper on PF

Things to know
- Differences between KF, EKF, Particle Filter
- How to update particle weights after receiving an observation from the sensor
- Particle resampling and its pathologies
- How to address particle deprivation
- Monte Carlo localization in a known map

Week 12

Camera Optics and Multi-view Geometry
Pinhole cameras, lenses, perspective projection. Aperture, focal length, exposure time, depth-of-field. Structure from Motion.

Readings
- Optional: James Tompkin’s notes.
- Sanja Fidler’s notes on depth from stereo

Things to know
- Differences between projective geometry and Euclidean geometry
- Pinhole camera model vs thin-lens camera model
- Aperture, exposure time, focal length, field of view, depth of field
- Pinhole camera observation model
- Lens distortion model in the thin-lens camera model
- Camera calibration
- Multiview geometry problem definitions: estimating structure, motion, optical flow, and stereo

Week 13

Visual odometry and Visual SLAM
Epipolar constraints. Depth from stereo disparity for parallel cameras. Triangulation as a least-squares problem. Scale issues in visual odometry with a single camera. Visual SLAM vs. structure from motion.

Readings
- Optional: James Tompkin’s notes on stereo and SfM.
- Sanja Fidler’s notes on depth from stereo

Things to know
- Setting up 3D triangulation as a least squares problem
- Depth from disparity for parallel and calibrated stereo cameras
- Scale ambiguity in single-camera visual odometry and visual SLAM
- Structure from motion as a least squares problem

Week 14