CSCI-4290/6290: Robot Motion Planning
Fall 2003

New Announcements!
Lectures
Homeworks
Exams

Course Information

Instructor: Srinivas Akella
Office: Amos Eaton 112, x8770, sakella@cs.rpi.edu
Office Hours: Tuesday 2:30-3:30pm, or after class

Credits: 3 (graduate students) / 4 (undergraduates)
Time: Tuesday and Friday, 12:00pm - 1:50pm (NOTE: This time differs from that in the printed Class Hour Schedule)
Classroom: Amos Eaton 214
Prerequisites: Data structures and algorithms (CSCI-2300) and Multivariable calculus and matrix algebra (MATH-2010), or permission of instructor

Undergrad TA: Mayur Patel , patelm4@cs.rpi.edu
Office hours: Tuesday, Friday 3-4pm, AE 211

Motion Planning

Have you ever wondered:

How to move a large couch into your dorm room with the least effort?
How characters in computer games can plan their paths so they don't run into obstacles or each other?
How to get a car-like robot to parallel park itself? A tractor-trailer?
How to plan the sequence of assembly motions to assemble a Walkman or a VCR?

All of these geometric motion planning problems can be solved using the techniques discussed in this course.

Description

This course is an introduction to algorithmic techniques for robot motion planning. Topics will include configuration space representations, roadmap methods, cell decomposition and potential field techniques, randomized path planning, collision detection, multiple robot coordination, nonholonomic motion planning, and manipulation planning. These techniques will be motivated by applications of motion planning to mobile robots and robot manipulators, assembly planning, computer-aided design, computer graphics, and molecular modeling.

Prerequisites are CSCI-2300 (Data Structures and Algorithms) and Multivariable Calculus and Matrix Algebra (MATH-2010), or permission of the instructor. Course grading will be on the basis of homework assignments (some involving programming), exams, and a course project. Undergraduate students and graduate students will be graded separately.

Syllabus .

Check out the course web page from Fall 2001, the last time the course was taught.

Textbooks

Readings will primarily be from two new textbooks-in-progress:

Robotic Motion Planning: Foundation and Implementation by H. Choset, K. M. Lynch, L. Kavraki, W. Burgard, S. A. Hutchinson, G. Kantor, and S. Thrun.
Planning Algorithms by Steven M. LaValle.

The optional textbook is: Robot Motion Planning by J.-C. Latombe, Kluwer, 1991.
Textbook readings will be supplemented by handouts and recent papers.

Reference Books

Robot Motion Planning and Control , J.-P. Laumond (Editor), Lecture Notes in Control and Information Sciences, Vol. 229, Springer Verlag, 1998.
Introduction to Robotics: Mechanics and Control, second edition, by John J. Craig, Addison Wesley, 1989.
Mechanics of Robotic Manipulation by Matthew T. Mason, MIT Press, 2001.
A Mathematical Introduction to Robotic Manipulation, by Richard M. Murray, Zexiang Li, and S. Shankar Sastry, CRC Press, Boca Raton, FL, 1994.
Robot Dynamics and Control, by Mark W. Spong and M. Vidyasagar, John Wiley, 1989.
Computational Geometry: Algorithms and Applications , second edition, M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer, 2000.
Computational Geometry in C, second edition, Joseph O'Rourke, Cambridge University Press, New York, 1998.
Introduction to Algorithms, by T. H. Cormen, C. E. Leiserson, and R. L. Rivest, MIT Press, 1990.
Or the more recent Introduction to Algorithms, second edition, by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, MIT Press, 2001.

Lectures

Lecture 1 (August 25) outline: pdf .
Lecture 2 (August 29) outline: pdf .
Lecture 3 (September 2) outline: pdf .
Lecture 4 (September 5) outline: pdf .
Lecture 5 (September 9) outline: pdf .
Lecture 6 (September 12) outline: pdf .
Lecture 7 (September 16) outline: pdf .
Lecture 8 (September 19) outline: pdf .
Lecture 9 (September 23) outline: pdf .
Lecture 10 (September 26) outline: pdf .
Lecture 11 (September 30) outline: pdf .
Lecture 12 (October 3) outline: pdf .
Lecture 13 (October 7) outline: pdf .
Lecture 14 (October 10) outline: pdf . Links to Lazy PRM , Visibility PRM animations
Lecture 15 (October 17) outline: pdf . Link to MSL
Lecture 16 (October 21) outline: pdf
Lecture 17 (October 24) outline: pdf
Midterm (October 28).
No lecture (October 31).
Lecture 18 (November 4) outline: pdf
Lecture 19 (November 7) outline: pdf
Lecture 20 (November 11) outline: pdf
Lecture 21 (November 14) outline: pdf
Lecture 22 (November 18) outline: pdf
Lecture 23 (November 21) outline: pdf
Lecture 24 (November 25) outline: pdf
Lecture 25 (December 2) outline: pdf
Lecture 26 (December 5) outline: pdf

The scanned-in lecture slides are available online through the library's electronic class reserves. Type in the course name (Robot Motion Planning) or instructor name (Akella).
The presentations by graduate students are available here here .

Homework Assignments

Assignment 1, due September 9. postscript file, pdf file.
Assignment 2 , due October 1. pdf file.
Assignment 3, due October 10. postscript file, pdf file.
Assignment 4, due October 21. pdf file.
PRM paper (pdf) ,
Visibility PRM paper (pdf) , Visibility PRM paper (ps) .
Assignment 5 , due November 4. pdf file.
Final Project proposal, due November 7 (Fri): pdf file.

Exams

Here is the exam schedule:

October 28 (Tue): Midterm (in class, 12:00noon-1:50pm)
There will be no programming questions on the midterm. Of course, questions about motion planning algorithms we have discussed are considered reasonable.
The midterm covers all material discussed in class through Lecture 15 (October 17).

There will be no final exam for the course. There will be a course project instead.

Schedule

Here is the assignment and exam schedule:

September 9 (Tue): Assignment 1 due
October 1 (Wed): Assignment 2 due
October 10 (Fri): Assignment 3 due
October 21 (Tue): Assignment 4 due
October 28 (Tue): Midterm (in class)
November 4 (Tue): Assignment 5 due
November 7 (Fri): Final Project proposal due: pdf file.
December 3 (Wed): Final Course Project due
December 4 (Thu) and 5 (Fri): Final Course Project demos

There will be no final exam for the course.

The presentation of papers by graduate students will be in November. Choose from this preliminary list of papers .

Announcements

Please check these announcements frequently. Last updated Thursday, December 11 at 7:10pm.

All grades have been posted on SIS. Have a good winter break!
If you have any midterm grading concerns, please drop off your midterm in my office by noon on Monday (Nov 24). On the first page, please list the questions that you have grading questions about. If I am not in, slip your midterm under my office door (AE 112).
All graded HWs, exams, project proposals that were not picked up are in the box outside my office.
There will be no class on Friday, October 31. Please use the time to work on Assignment 5 . Happy Halloween!
Graded HW 3 is either with the TA Mayur or outside my office (AE 112).
Here is the Assignment 5 web page.
The test files used to grade your Assignment 2 programs are available on the Assignment 2 page .
Here are links to Lazy PRM and Visibility PRM animations
I will not be able to hold office hours today (Oct 7) from 2:30 to 3:30pm. Please send me email if you would like to meet later today instead (probably after 5pm).
Assignment 3 is due October 10. postscript file, pdf file.
The Office hours for the Undergrad TA: Mayur Patel , patelm4@cs.rpi.edu are Tuesday and Friday 3-4pm, AE 211.
Assignment 2 code has been posted.
HW Assignment 1: Since we have not yet covered DH parameters and quaternions in class, Qns 5 and 6 are due on Friday, Sept 12. The first four questions are due on Tuesday, Sept 9 as originally scheduled.
The class time is: Tuesday and Friday, 12:00pm - 1:50pm. (NOTE: This time differs from that in the printed Class Hour Schedule).

Srinivas Akella
Department of Computer Science
Rensselaer Polytechnic Institute
110 8th Street
Troy, NY 12180
Email: sakella@cs.rpi.edu

CSCI-4290/6290: Robot Motion Planning Fall 2003