# COMP-417 Introduction to Robotics and Intelligent Systems

### 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**In particular, we consider how can robots move and interact, what various body designs look like. Robotic sensors. Kinematics and inverse kinematics. Sensor data interpretation and sensor fusion. Path planning. Configuration spaces. Position estimation. Intelligent systems. Spatial mapping. Multi-agent systems. Applications.**

*a robot that explicitly accounts for its uncertainty works better than a robot that does not.*### Teaching Staff

### Course Description

This course will broadly cover the following areas:- State space representations of the robot and it's environment.
- Path planning. How to get from one place to another using deterministic and probabilistic methods, in low and high dimensional spaces.
- 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?
- Intro to 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 Learning for robots: how can we learn the parameters of a robot controller? How can we directly map sensor data to actions?

### Syllabus

Lecture | Date | Topics | Tutorial | References | Slides |
---|---|---|---|---|---|

Sept 5 | IntroductionMotivation, logistics, scope of the field and the course, sense-plan-act paradigm. Quiz 0 (Introduction, Background, Expectations) |
Dudek & Jenkin Ch. 1 Aggressive UAV flight |
Slides: Intro (part 1 of 2) [history] (part 2 of 2) |
||

Sept 7 | Intro to PlanningProperties, definitions, configuration space, deterministic methods. |
Lavalle Ch. 4 Dudek & Jenkin Ch. 6 |
Planning part 1 and Probabilistic planning and RRT | ||

Sept 12 | Deterministic planning methods. | Lavalle Ch. 8.4 Dudek & Jenkin 6.3.4 Optional: Howie Choset's notes |
Planning part 1 (continued)</a | ||

Sept 14 | PlanningImplementation issues, navigation functions. Rapidly-exploring Random Trees (RRT), Probabilistic RoadMaps (PRM) Artificial Potential Fields and Obstacle Avoidance |
Lavalle 5.5, 5.6 | |||

Sept 19 | MDP and Reinforcement Learning 1 (Lecture given by Sandeep Manjanna)Markov Decision Process, Introduction to Reinforcement Learning, Value Function, and Q-Value Function. |
Optional: Pieter Abbeel's MDP lectures | MDP and RL part 1 | ||

Sept 21 | MDP and Reinforcement Learning 2 (Lecture given by Sandeep Manjanna)Value Iteration, Policy Iteration, TD-learning, and Q-learning. |
Optional: Pieter Abbeel's MDP lectures Pieter Abbeel's RL lectures |
MDP and RL part 2 | ||

Sept 26 (guest lecture) | Vehcile design, Kinematics and cooridate systems (Guest Lecture by Dr. Jose Ruiz Ascencio)Frames of reference. Rotation representations. Homogeneous coordinates and transformations. Rigid body motion. Special topics: emerging research guest presentations. |
Intro to ROS | Paul Furgale: robot pose | PID part 1 | |

Sept 28 (guest lecture) | Into to dynamics (Guest Lecture by: Dr. Jose Ruiz Ascencio)Dynamical systems and control. Examples: Dubins car, differential drive car, unicycle, pendulum, cartpole, quadcopter. Holonomic vs. non-holonomic systems. Special topics: emerging research guest presentations. |
Lavalle 13.1 Dudek & Jenkin 3.1.5,6 Kumar TED talk (again!) |
PID slides | ||

Introduction to ControlTuning, PID, advantages and drawbacks. |
Linear algebra refresher | Optional: Astrom and Hagglund, Ch. 2 | PID_Control-recap.key.pdf and ROS-briefing.key.pdf and Kinematics and dynamics | ||

Oct 10 | Sensors and ActuatorsObservation models for the following sensors: cameras, lasers, tactile, IMU, depth, GPS, Hall-effect, encoders, RGBD. Pulse-Width Modulation. |
Dudek & Jenkin C 3.1.1,4, 3.2-3, 4.1-8, 4.10, 5.1.1 Optional: Mike Langer's notes |
Sensors | ||

SLAM: mapping and location estimation. SLAM. GraphSLAM. Expectation and Covariance. Geometric interpretation of the covariance matrix. Nonlinear Least Squares formulation of the Simultaneous Localization And Mapping (SLAM) problem. Quiz 2 (Potential fields, maps and sensor types) |
Udacity Lesson 6 Probabilistic Robotics Ch. 11 |
SLAM | |||

The Bayes probabilistic FilterBayes' rule on Gaussian distributions. |
Udacity Lesson 2 Kalman Filter, Illustrated |
Bayes' Filter | |||

Oct 12 | State estimationHow to compute one's position. Worst-case analysis, practical methods, mtulti-sensor methods. Learning-based methods. (Conclusion of sensors survey) |
Pieter Abbeel's notes | |||

Oct 17 | Map Representations and Map AlignmentOccupancy grids, Octrees, Voronoi Graph, Homotopy Classes. Map alignment with known or unknown correspondences. Iterative Closest Point (ICP). Extended assignment due date (10am) Quiz 1 (Planning and PID) |
Dudek and Jenkin, Chapter 9 | Map Representations and Map Alignment | ||

Computational Complexity of global localizationPositional ambiguity, visibility cells, decision trees, competitive ratio |
Dudek and Jenkin Chapter 8.6 | Occupancy Grid Mapping With Known Robot Poses | |||

Occupancy Grid Mapping With Known Robot PosesLog-odds ratio, Probabilistic dynamics and measurement models, Bayesian estimation. |
Intro to numpy | Pieter Abbeel's notes Probabilistic Robotics Ch. 2 and Ch. 9 |
Occupancy Grid Mapping With Known Robot Poses | ||

The Kalman Filterpart 1. Kalman Filter as a special case of Bayes' Filter. Examples of 2D Kalman Filter. General prediction and update equations. |
Dudek and Jenkin Sec 8.3. Probabilistic Robotics Ch. 2 | Kalman filter | |||

Midterm |
|||||

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. |
Cyrill Stachniss' intro to EKF Cyrill Stachniss' intro to EKF-SLAM |
Extended_Kalman_Filter.pdf | |||

Particle FilterRepresenting multimodal distributions. Particle propagation and resampling. Pathologies of particle filter. Quiz 2 |
Udacity Lesson 3 | Particle_Filter.pdf | |||

Particle FilterImportance Sampling. Examples: Markov localization in a known map. FastSLAM. |
Optional: Thrun's paper on PF | Nov_7_Particle_Filter.pdf | |||

Camera Optics and Multi-view GeometryPinhole cameras, lenses, perspective projection. Aperture, focal length, exposure time, depth-of-field. Structure from Motion. |
Optional: James Tompkin's notes | Camera_Geometry.key.pdf and PCA | |||

Learning-based actionUsing learned perceptual models to expore or collect data. |
|||||

Visual odometry and Visual SLAMEpipolar 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 (KF Particle filtering ) |
Optional: James Tompkin's notes on stereo and SfM. Sanja Fidler's notes on depth from stereo |
Visual_SLAM_and_Visual_Odometry | |||

Learning robot controllersFunction Approximation. Intro to Reinforcement Learning Model-free RL: policy gradient estimation and the cross-entropy method. |
Markov Localization | Optional: Pieter Abbeel's policy optimization notes | |||

Human-Robot InteractionModeling human trust, and trust-aware control. |
Assignment 4 Discussion | , | |||

Summarization and emerging applications |
unsupervised_LDA_curious_exploration_from_UCSC14 and Loose_ends_and_course_review | ||||

Review session for final exam |

### Assignments

- Wall following and intro to ROS with starter code here. Due Oct 17.
- Probabilistic planning using RRT's with starter code here. Due Oct 31st 12:00 pm.
- Localization (Particle Filter) with starter code here. Due
~~Nov 17th~~**Nov 20th 12:00 pm**.

As a couple of students requested a sample video from the Assignment 3 solution. I am posting one here. - Assignment 4 is quite open ended, but is meant NOT to take to long. It's in 417-asst4-2017.pdf

### Marking scheme

- 4 assignments worth 10% each = 40%
- 4 quizzes worth 1.25% each = 5%
- 1 midterm exam worth 15%
- 1 final exam worth 40%
- The final exam grade can replace the midterm grade if it improves the student's final mark.

### Textbook

Computational Principles of Mobile Robotics, by Dudek and Jenkin. Cambridge University Press, 2010.

Selected readings from the research literature, to be distributed in class.

### Supplementary reference material

- Jorge Angeles, Fundamentals of robotic mechanical systems: theory, methods, and algorithms New York, Springer, 2003.
- Lung-Wen Tsai, Robot analysis: the mechanics of serial and parallel manipulators, New York, Wiley, 1999.
- J.P. Merlet, Parallel robots, Boston, MA : Kluwer Academic Publishers, 2000.
- Probabilistic Robotics, by Thrun, Fox, and Burgard, The MIT Press, 2005.
- Planning Algorithms, by Steven Lavalle, Cambridge University Press, 2006.
- Robotics, Vision, and Control, by Corke
- Introduction to Autonomous Mobile Robots, by Siegwart, Nourbakhsh, Scaramuzza
- (Chapters 2 and 4 from) Computer Vision: Models, Learning, and Inference, by Prince

**Evaluation**

The details of the course evaluation scheme and format of some classes will depend of the enrollment and hence will not be fixed until after the first lecture (based on attendance and student mix in the first lecture). Evaluation will be based on three types of activity: class participation, independent work (homework/project), and a possible in-class formal presentation. Based on substantial enrollment in 2017, the in-class presentations may not be possible.

The evaluation for the course is to be based on a combination of assignment, exam, midterm and other elements as discussed in class and as posted.

## Technicalities to note

Senate on January 29, 2003 approved the following resolution on academic integrity, which requires that a reminder to students be printed on every course outline:

Whereas, McGill University values academic integrity; Whereas, every term, there are new students who register for the first time at McGill and who need to be informed about academic integrity; Whereas, it is beneficial to remind returning students about academic integrity;

Be it resolved that instructors include the following statement on all course outlines:

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see www.mcgill.ca/integrity for more information).

Be it further resolved that failure by an instructor to include a statement about academic integrity on a course outline shall not constitute an excuse by a student for violating the Code of Student Conduct and Disciplinary Procedures.

*dudek@cim.mcgill.ca*