SUNY at Buffalo

CSE Department

Spring 2012

New time: The final exam will be posted here at 10am on 5/8/2012. It will be due in the TA's departmental mail box or via email to the TA at noon on 5/9/2012. NO LATE EXAMS WILL BE ACCEPTED!

As I have mentioned several times in class, I will drop the lowest grade of the five homework assignments assigned. Therefore, only the best four assignments will count toward your final grade.

Many of the big challenges in robotics research today are algorithmic. Given today's robot hardware, how can robots be programmed to do useful tasks and chores? This course will introduce the student to a few key problems and algorithms in robotics. The student will apply the algorithms to simulated robotics problems in Matlab. We will cover: 1) topics in optimal control including: the Bellman equation, value iteration, reinforcement learning, linear quadratic regulation; 2) topics in planning including: trajectory optimization, randomized planners; 3) topics in estimation including: Kalman filtering/smoothing, particle filters, mapping, object localization; 4) topics in optimization including: non-linear optimization, convex optimization, polynomial optimization. There will be approximately five homework or Matlab assignments and a final exam. Prerequisites: linear algebra, familiarity with Matlab.

Timeslot: MWF 10:00 -- 10:50

Room: Clemens 322

Instructor: Robert Platt

ubit: robplatt

Office: 330 Davis Hall

Office Hours: MW 11--12

Textbook: None. Readings assigned on syllabus below.

TA: Zihe Chen

TA email: zihechen@buffalo.edu

- One exam: 25%
- 5 Homeworks/Labs: 75%. Out of the five homework assignments, I will drop the lowest grade.
- In order to get credit for cse510, you must complete a small additional projct. Project topic should be pre-approved by me.

- Homeworks and labs are to be completed by individual students unless otherwise specified. You may study with other students or ask other students to explain general concepts. However, the solution that is turned in must be completely your own.
- Late homeworks will be docked 5% per day late. Please put late homeworks in my mailbox in the main office.
- All assignments are to be submitted in class.

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

- Markov Decision Processes
- The Bellman equation
- Value iteration
- Reinforcement learning
- Linear quadratic regulation
- Model predictive control

- Non-linear model predictive control
- Iterative LQR, Shooting, collocation methods
- Optimization algorithms
- Configuration space, representation of rotation
- Dynamic Programming methods in planning
- Randomized planning methods

- Extended Kalman filtering, Kalman smoothing
- Particle filtering
- Linear Quadratic Gaussian control
- Sensor models, scan matching
- Mapping

- Standard convex optimization problems, approximate complexity
- Semi-definite relaxations in control
- Polynomial optimization via sums of squares
- Lypanunov functions and stability certificates

Date | Topic | Lecture | Readings | Homework | Optional/Additional Readings |

1/18/2012 | Introduction | ||||

1/20/2012 | Markov Decision Processes | Blackboard | SB Chapter 3 | Bert Vol 1, Ch 1 | |

1/23/2012 | Value Iteration | Blackboard | SB Chapter 4 | Check out the value iteration Applet by David Poole at UBC | |

1/25/2012 | Value Iteration | Blackboard | SB Chapter 6 | ||

1/27/2012 | Value function contractions, q-learning | Blackboard | SB Chapter 6 | Check out gridworld q-learning Applet by David Poole at UBC. Also, check out actor critic RL for the inverted pendulum Applet by Takashi Kanamaru at Kagokuin U. | |

1/30/2012 | SARSA, Fn Approx | Blackboard | SB Chapter 8 | ||

2/1/2012 | LSTD | Backboard | Section 2 of this and LSTD Section of this. | ||

2/3/2012 | Policy gradient | Backboard | Policy gradient sources: Peters' scholarpedia page. | Overview paper. | |

2/6/2012 | Linear systems | Backboard | Steven Boyd's DT LQR slides. | Also, see Emo Todorov's chapter on optimal control Section 4. | |

2/8/2012 | DT LQR | Backboard | Steven Boyd's DT LQR slides. | Also, see Emo Todorov's chapter on optimal control Section 4. | |

2/10/2012 | LQR, TVLQR | Backboard | Video of LQR being used to control an inverted pendulum about the upright. | ||

2/13/2012 | TVLQR | Homework 1 | |||

2/15/2012 | TVLQR, iLQR | ||||

2/17/2012 | Affine LQR, stochastic LQR, MPC | My notes on affine LQR here | |||

2/20/2012 | Intro to nonlinear MPC | Manoj Srinivasan's tutorial on trajectory optimization here | MIT perching glider video. Also, see Diehl paper. | ||

2/22/2012 | Intro to convex optimizaion | Stephen Boyd's lecture notes on convex functions. | |||

2/24/2012 | !!!!NO CLASS!!!! | ||||

2/27/2012 | Newton's Method, Sequential Quadratic Programming, Single shooting | Wikipedia page on Newton's method in optimization. Manoj Srinivasan's tutorial on trajectory optimization here | Homework 2 | See Diehl paper. | |

2/29/2012 | Newton's Method | Wikipedia page on Newton's method in optimization. | See Diehl paper. | ||

3/2/2012 | Single shooting | Manoj Srinivasan's tutorial on trajectory optimization here | See Diehl paper. RRT growing example here. Robot executing trajectory found using RRT here. | ||

3/5/2012 | Multiple shooting, Sequential quadratic programming | Manoj Srinivasan's tutorial on trajectory optimization here | See Diehl paper. RRT growing example here. Robot executing trajectory found using RRT here. | ||

3/7/2012 | Sequential quadratic programming | ||||

3/9/2012 | Motion Planning | Pieter Abbeel's notes on sample based motion planning here. | For more detail, see sections 5.5 and 5.6 of LaValle's comprehensive book. RRT growing example here. Robot executing trajectory found using RRT here. | ||

3/19/2012 | PRMs, RRTs | Pieter Abbeel's notes on sample based motion planning here. | For more detail, see sections 5.5 and 5.6 of LaValle's comprehensive book. RRT growing example here. Robot executing trajectory found using RRT here. | ||

3/21/2012 | RRTs | ||||

3/23/2012 | PRMs, Search, and A* | Pieter Abbeel's notes on search here. | For more detail, see section 2.2 of LaValle's comprehensive book. | ||

3/26/2012 | Search, A*, Sequential Bayesian Estimation | Pieter Abbeel's notes on search here. | Homework 3 | My Bayes filtering video here. | |

3/28/2012 | Sequential Bayesian Estimation | Pieter Abbeel's notes on Bayes filters here. Sebastian Thrun's notes here | My Bayes filtering video here. | ||

3/30/2012 | Sequential Bayesian Estimation, particle filtering | ||||

4/2/2012 | Histogram filter, particle filter | Pieter Abbeel's notes on particle filters here | Dieter Fox's particle filtering videos here. | ||

4/4/2012 | Histogram filter, particle filter | Pieter Abbeel's notes on particle filters here | Dieter Fox's particle filtering videos here. | ||

4/6/2012 | Particle filter, kalman filter | Pieter Abbeel's notes on kalman filters here | |||

4/9/2012 | Particle filter, kalman filter | Pieter Abbeel's notes on kalman filters here | |||

4/11/2012 | Kalman filter | Pieter Abbeel's notes on kalman filters here | |||

4/13/2012 | Kalman filter, SLAM | Homework 4 | Thrun's SEIF paper. EKF slam image. | ||

4/16/2012 | CLASS CANCELLED! | ||||

4/18/2012 | SLAM 1 (Dr. Julian Ryde) | Dr. Ryde's notes on SLAM here | |||

4/20/2012 | SLAM 2 (Dr. Julian Ryde) | Dr. Ryde's notes on SLAM here | |||

4/23/2012 | SLAM 3: EKF-SLAM | Wikipedia page on RANSAC. Pieter Abbeel's notes on ICP here. Thrun's EKF slam slides here. | |||

4/24/2012 | Homework 5 | ||||

4/25/2012 | SLAM 3: Rao-Blackwellized particle filter (RBPF) SLAM | RBPF SLAM tutorial. | Youtube video of rbpf-slam. | ||

4/25/2012 | SLAM 4: FAST-SLAM, ICP, RANSAC | Wikipedia article on RANSAC. | ICP video. |

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

Key to Readings:SB --> Sutton and Barto, "Reinforcement Learning", MIT Press

Bert --> Bertsekas, "Dynamic Programming and Optimal Control", Athena

Standford EECS, Advanced Robotics

RPI CS, Robotics II