Overview

This 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.

Teaching Staff

Instructor
Florian Shkurti
florian@X
Office: McConnell 403
Office Hours: Thu 10:30-11:30am
Teaching Assistant
Arnold Kalmbach
akalmbach@X
Office: McConnell 403
Office Hours: Wed 3-4pm
Teaching Assistant
Martin Gerdzhev
martin.gerdzhev@Y
Office: McConnell 111
Office Hours: Mon 1-2pm
X = cim.mcgill.ca, Y = mail.mcgill.ca

Course Description

This course will broadly cover the following areas:

  • Kinematics and Dynamics: how can we model robotic systems using approximate physical models that enable us to make predictions about how robots move in response to given commands?
  • Feedback Control and Planning: how can we compute the state-(in)dependent commands that can bring a robotic system from its current state to a desired state?
  • Mapping: how can we combine noisy measurements from sensors with the robot’s pose to build a map of the environment?
  • State Estimation: the state of the robot is not always directly measurable/observable. How can we determine the relative weighs of multiple sensor measurements in order to form an accurate estimate of the (hidden) state?
  • The Geometry of Computer Vision: how can modeling pixel projections on an RGB camera help us infer the 3D structure of the world? How can we triangulate points seen from two cameras? How can we estimate the camera’s pose (and therefore the robot’s) while it is moving in the environment?
  • (Intro to) Reinforcement Learning: how can we learn the parameters of a state-dependent controller without having a prior physical model of the robot’s dynamics? This is an enormous research field, with many exciting results. In this course we will only have time to see two algorithms.

Schedule

Lecture Date Topics Tutorial Slides Readings
1 Jan 5 Introduction
Motivation, logistics, rough description of assignments, sense-plan-act paradigm.
Syllabus, Quiz 0 (Introduction, Background, Expectations)
2 Jan 10 Dynamics (lecture given by Martin Gerdzhev)
Dynamical systems and control. Examples: Dubins car, differential drive car, unicycle, pendulum, cartpole, quadcopter. Holonomic vs. non-holonomic systems.
pdf, pptx Lavalle 13.1
Dudek & Jenkin 3.1.5,6
3 Jan 12 Kinematics (lecture given by Martin Gerdzhev)
Frames of reference. Rotation representations. Homogeneous coordinates and transformations. Rigid body motion.
Intro to ROS pdf, pptx Paul Furgale: robot pose
4 Jan 17 Sensors and Actuators
Observation models for the following sensors: cameras, lasers, tactile, IMU, depth, GPS, Hall-effect, encoders, RGBD. Pulse-Width Modulation.
pdf, pptx Dudek & Jenkin 3.1.1,4, 3.2-3, 4.1-8, 4.10, 5.1.1
Optional: Mike Langer's notes
5 Jan 19 PID Control
Tuning, cascading PID, advantages and drawbacks.
Linear algebra refresher pdf, pptx Optional: Astrom and Hagglund, Ch. 2
6 Jan 24 Artificial Potential Fields and Obstacle Avoidance
Implementation issues, navigation functions. Vector-field histogram (VFH), dynamic window approach (DWA).
pdf, pptx Lavalle Ch. 8.4
Dudek & Jenkin 6.3.4
Optional: Howie Choset's notes
7 Jan 26 Linear Quadratic Regulator (LQR)
Computing optimal actions for linear dynamical systems with quadratic cost-to-go functions.
Quiz 1 (Transformations and PID)
Probability refresher pdf, pptx, code Optional: Stephen Boyd's LQR notes and examples.
8 Jan 31 Planning
Dijkstra, A*
pdf, pptx Blog post on A*
Udacity Lesson 4
9 Feb 2 Planning
Rapidly-exploring Random Trees (RRT), Probabilistic RoadMaps (PRM)
pdf, pptx Lavalle 5.5, 5.6
10 Feb 7 Map Representations and Map Alignment
Occupancy grids, Octrees, Voronoi Graph, Homotopy Classes. Map alignment with known or unknown correspondences. Iterative Closest Point (ICP).
Quiz 2 (Potential fields and LQR)
pdf, pptx Pieter Abbeel's notes
11 Feb 9 Occupancy Grid Mapping With Known Robot Poses
Log-odds ratio, Probabilistic dynamics and measurement models, Bayesian estimation.
Intro to numpy pdf, pptx Pieter Abbeel's notes
Probabilistic Robotics Ch. 2 and Ch. 9
12 Feb 14 Maximum Likelihood, Least Squares Estimation, Maximum A Posteriori Estimation
Least squares as a special case of maximum likelihood estimation on Gaussian models.
pdf, pptx Optional: Simon Prince Ch.2 and Ch. 4
13 Feb 16 GraphSLAM
Expectation and Covariance. Geometric interpretation of the covariance matrix. Nonlinear Least Squares formulation of the Simultaneous Localization And Mapping (SLAM) problem.
Quiz 3 (Map representations and Bayes' rule)
pdf, pptx Udacity Lesson 6
Probabilistic Robotics Ch. 11
14 Feb 21 Midterm
Midterm review session
15 Feb 23 Kalman Filter
Bayes' rule on Gaussian distributions. Example of 1D Kalman Filter.
pdf, pptx Udacity Lesson 2
Kalman Filter, Illustrated
Feb 28 Reading week
Mar 2 Reading week
16 Mar 7 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.
pdf, pptx Probabilistic Robotics Ch. 2,3
17 Mar 9 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.
Quiz 4 (GraphSLAM and Gaussians)
Basic Kalman Filter implementation pdf, pptx Cyrill Stachniss' intro to EKF
Cyrill Stachniss' intro to EKF-SLAM
Probabilistic Robotics Ch. 2,3
18 Mar 14 Particle Filter
Representing multimodal distributions. Particle propagation and resampling. Pathologies of particle filter.
pdf, pptx Udacity Lesson 3
19 Mar 16 Particle Filter
Importance Sampling. Examples: Markov localization in a known map. FastSLAM.
pdf, pptx Optional: Thrun's paper on PF
20 Mar 21 Camera Optics and Multi-view Geometry
Pinhole cameras, lenses, perspective projection. Aperture, focal length, exposure time, depth-of-field. Structure from Motion.
pdf, pptx Optional: James Tompkin's notes
21 Mar 23 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.
Quiz 5 (KF/EKF)
pdf, pptx Optional: James Tompkin's notes on stereo and SfM.
Sanja Fidler's notes on depth from stereo
22 Mar 28 Function Approximation
Intro to Reinforcement Learning
Research highlights (non-examinable material). Model-free RL: policy gradient estimation and the cross-entropy method.
Markov Localization pdf, pptx
pdf, pptx
Optional: Pieter Abbeel's policy optimization notes
23 Mar 31 Intro to Reinforcement Learning (invited talk by Juan Camilo Gamboa Higuera)
Research highlights (non-examinable material). Model-based reinforcement learning. Learning to swim on the Aqua robot.
pdf, pptx
24 Apr 4 Intro to Human-Robot Interaction (invited talk by Anqi Xu)
Research highlights (non-examinable material). Modeling human trust, and trust-aware control.
Assignment 4 Discussion pdf, pptx
25 Apr 6 Review session for final exam

Assignments

Marking scheme

Recommended, but optional, textbooks

Related courses