CSE 410/510: Robotics Algorithms

Robert Platt
SUNY at Buffalo
CSE Department
Spring 2013

Announcements:

The final exam will be an in-class exam on 4/25 between 12:30 and 1:50pm in the normal classroom.

I just posted Homeworks 4 and 5.

The final project has a progress report due on 4/22/2013. See the project description for details.

I just posted instructions for the final project. You only need to complete a project if you are in the 500 version of the class.

Course Description

This course will study key algorithms relevant to programming intelligent robots with a focus on the following questions. How might one program a robot to estimate the state of the world based on multiple sources of information? How might a robot create plans or control policies for performing tasks? How might a robot learn a control policy directly from experience? The course will cover topics in estimation, control, and planning with applications to robotics including: reinforcement learning, linear optimal control, randomized motion planning, trajectory optimization, Kalman filtering, particle filtering, and selected topics in optimization.

Course Information:

Timeslot: T/TH 12:30 -- 1:50
Room: 220 NSC
Instructor: Robert Platt
ubit: robplatt
Office: 330 Davis Hall
Office Hours: Tuesday 2:00 -- 3:00pm in 106 Davis Hall
Textbook: None. This course does not require the purchase of a textbook. All course reading material will be taken from sources freely available on the Internet as assigned on syllabus below.

TA: Suchismit Mahapatra
TA email: suchismi@buffalo.edu
TA office hours: Monday and Friday, 2:30 -- 3:30pm in 106 Davis Hall

Grading:

One exam: 25%
5 Homeworks/Labs: 75%. I will only count your four best homeworks toward your grade. This means that you don't need to complete the fifth homework assignment if you feel that you have already done well on the first four assignments.
In order to get credit for cse510, you must complete a small additional projct. Project topic should be pre-approved by me. We will begin projects in the middle of the semester.

Course Policies:

Homeworks are to be completed by individual students. NO CHEATING ON HOMEWORK ASSIGNMENTS WILL BE ALLOWED. This means that the code you turn in for your homework must be your own. We will run all submitted code through a plagarism detector that detects common code segments. If we find two assignments that share common code or are otherwise similar, then BOTH students will be penalized. You may ask other students to explain general concepts. However, the submitted work must be your own.
Late homeworks will be docked 10% per day late.
All assignments are to be submitted to the TA via email or via the TA's mailbox.

Course Goals:

Gain an understanding of the basic problems in robotics.
Understand a few key robotics algorithms in detail.
Learn mathematical/algorithmic tools that can be applied elsewhere. Improve your analysis skills.

Topics to be covered:

1. Control

Markov Decision Processes
Reinforcement learning (Q-learning, SARSA)
The Bellman equation, value iteration
Linear optimal control (LQR, TVLQR)
Basic manipulator kinematics (Jacobians, representation of orientation)
Cartesian end-effector control

2. Planning

Introduction to convex optimization
Linear model predictive control, iterative LQR
Trajectory optimization, Newton's method, Sequential Quadratic Programming
Randomized planning methods (RRT, PRM)
Search, A^*

3. Localization and mapping

Sequential Bayesian estimation, Histogram filter
Particle filter
Kalman filter, EKF, Kalman smoothing
Linear Quadratic Gaussian control
Sensor models, scan matching, ICP, RANSAC
Occupancy grids
Loop closure

4. Convex Optimization

Semi-definite programming
Semi-definite relaxations in control
Polynomial optimization via sums of squares
Lypanunov functions and stability certificates

Syllabus

Date	Topic	Lecture	Readings	Homework	Optional Readings / Videos
1/15/2012	Introduction	pdf
1/17/2012	Markov Decision Processes	Blackboard	SB Chapter 3		Bert Vol 1, Ch 1. Also, check out this video of reinforcement learning operating on a gridworld environment.
1/22/2012	Reinforcement Learning	Blackboard	SB Chapter 6		Bert Vol 1, Ch 1. Here is a Java applet that illustrates q-learning in a very simple gridworld environment. This one illustrates reinforcement learning applied to the inverted pendulum task. This one illustrates value iteration.
1/24/2012	Linear Algebra Review (TA)				I'll be out of town this day. The TA will review linear algebra and answer questions as needed. This class is optional.
1/29/2012	Value Iteration	Blackboard	SB Chapter 4		Bert Vol 1, Ch 1. Here is a Java applet that illustrates q-learning in a very simple gridworld environment. This one illustrates reinforcement learning applied to the inverted pendulum task. This one illustrates value iteration.
1/31/2012	Value Iteration	Blackboard	SB Chapter 4		Bert Vol 1, Ch 1. Here is a Java applet that illustrates q-learning in a very simple gridworld environment. This one illustrates reinforcement learning applied to the inverted pendulum task. This one illustrates value iteration.
2/5/2012	Reinforcement Learning	Blackboard	SB Chapter 4
2/7/2012	Reinforcement Learning	Blackboard	SB Chapter 4
2/11/2012				Homework 1
2/12/2012	LQR	Blackboard	Intro to LQR. Also, see the wikipedia page on the pseudoinverse.
2/14/2012	LQR	Blackboard	Intro to LQR		This video illustrates the application of LQR to the cart pole balancing problem.
2/19/2012	LQR	Blackboard	Intro to LQR		This video illustrates the application of LQR to the cart pole balancing problem.
2/19/2012	LQR	Blackboard	Intro to LQR		I wrote a short matlab program to illustrate LQR for the two-dimensional infinite horizon double-integrator system with parameters: m=1, b=0.1. Here is the trajectory followed (position coordinates only) when Q=1eye(4), B=1eye(2). Here is the trajectory followed when Q=0.1eye(4), B=1eye(2). Here is the trajectory followed when Q=10eye(4), B=1eye(2).
2/21/2012	More LQR!	Blackboard	Intro to LQR		Here's a video of a glider perching on a power line. The glider is cotnrolled using TVLQR (time varying LQR).
3/5/2013	PRM, RRT	Blackboard	Lavalle paper, Wikipedia article.		Here's a video of RRT doing it's thing. Here is a robot arm trajectory generated by RRT.
3/7/2013	PRM, RRT	Blackboard	Lavalle paper, Wikipedia article.		Here's a video of RRT doing it's thing. Here is a robot arm trajectory generated by RRT. For more detail, see sections 5.5 and 5.6 of LaValle's comprehensive book.
3/11/2012				Homework 2
3/12/2012	Spring Break!
3/14/2012	Spring Break!
3/19/2012	SLAM, ICP	Guest Lecture, Julian Ryde	Julian's Slides
3/21/2012	RRT	Blackboard			For more detail, see sections 5.5 and 5.6 of LaValle's comprehensive book.
3/26/2012	Search	Blackboard	Wikipedia page on A-Star		For more detail, see section 2.2 of LaValle's comprehensive book.
3/28/2012	Sequential Bayes Filtering	Blackboard
4/2/2012	Sequential Bayes Filtering	Blackboard	See the wikipedia article.		Illustration of particle filtering (with narration by Sebastian Thrun).
4/5/2012				Homework 3
4/9/2012	Particle Filtering	Blackboard	See the wikipedia article.		I thought that this tutorial did a good job covering the more technical aspects of particle filtering (see Sect 4 for the SIR version of partcile filtering on which we have focused in class).
4/11/2012	Particle Filtering	Blackboard	See the wikipedia article.		I thought that this tutorial did a good job covering the more technical aspects of particle filtering (see Sect 4 for the SIR version of partcile filtering on which we have focused in class).
4/16/2012	Kalman Filtering	Blackboard	See the wikipedia article.		This article does a good job introducting the more technical aspects of Kalman filtering. Simple KF example here. Application of Kalman filtering to IMU tracking and color tracking. Thrun's SEIF paper. EKF slam image.
4/18/2012	Kalman Filtering, EKF-SLAM	Blackboard	See the wikipedia article.		Thrun's SEIF paper. EKF slam image.
4/22/2012				Homework 4
4/25/2012	Final Exam				This will be an in-class exam held in the normal classroom and the normal time.
5/2/2012				Homework 5

Instructions for the final course project are given here. The project is due on the last day of exam period.

Our TA, Suchismit Mahapatra, has put together helpful instructions on how to access the UB file system here.

This course has a discussion forum on Piazza here.

Homeworks are due on the date where they appear in the syllabus.

Matlab Access: Our TA, Suchismit Mahapatra, has put together some helpful instructions here on how to access Matlab over the UB campus network.

Key to Readings:
SB --> Sutton and Barto, "Reinforcement Learning", MIT Press
Bert --> Bertsekas, "Dynamic Programming and Optimal Control", Athena

Somewhat related courses elsewhere:

Standford EECS, Advanced Robotics
RPI CS, Robotics II