CSCI-4290/6290: Robot Motion Planning
Fall 2005

Course Information

Credits: 3 (graduate students) / 4 (undergraduates)
Time: Tuesday and Friday, 10:00am - 11:50am
Classroom: CII 3116 (Low 3116) , near the Playhouse
Prerequisites: Data structures and algorithms (CSCI-2300) and Multivariable calculus and matrix algebra (MATH-2010), or permission of instructor

TA: Kartik Babu , babuk@cs.rpi.edu
Office hours: Thursday 2-3pm, Amos Eaton 217

Motion Planning

• 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

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 2003, the last time the course was taught.

Textbooks

• Principles of Robot Motion: Theory, Algorithms, and Implementation by H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun, MIT Press, 2005.

• Planning Algorithms by Steven M. LaValle.

Reference Books

• Robot Motion Planning by J.-C. Latombe, Kluwer, 1991.
  
• 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, second edition, by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, MIT Press, 2001.
  

Lectures

• Lecture 1 (August 30) outline: pdf .
  
• Lecture 2 (September 2) outline: pdf .
  
• Lecture 3 (September 6) outline: pdf .
  
• Lecture 4 (September 9) outline: pdf .
  
• Lecture 5 (September 13) outline: pdf .
  
• Lecture 6 (September 16) outline: pdf .
  
• Lecture 7 (September 20) outline: pdf .
  
• Lecture 8 (September 23) outline: pdf .
  
• Lecture 9 (September 27) outline: pdf .
  
• Lecture 10 (September 30) outline: pdf .
  
• Lecture 11 (October 4) outline: pdf .
  
• Lecture 12 (October 7) outline: pdf .
  
• Lecture 13 (October 14) outline: pdf .
  
• Lecture 14 (October 18) outline: pdf .
• Lecture 15 (October 21): Midterm exam!
• Lecture 16 (October 25) outline: pdf
  
• Lecture 17 (October 28) outline: pdf
  
• Lecture 18 (November 1) outline: pdf
  
• Lecture 19 (November 4) outline: pdf
  
• Lecture 20 (November 8) outline: pdf
  
• Lecture 21 (November 11) outline: pdf
  
• Lecture 22 (November 15) outline: pdf
  
• Lecture 23 (November 18) outline: pdf
  
• Lecture 24 (November 22) outline: pdf
  
• Lecture 25 (November 29) outline: pdf
  
• Lecture 26 (December 2) outline: pdf
  
• Lecture 27 (December 6) outline: pdf
  

Assignments

• Assignment 1, Qns 1-4 due September 9, Qns 5-6 due September 16. pdf file.
• Assignment 2 , revised due date October 3. pdf file.
• Assignment 3, due Friday, October 14. pdf file.
• Assignment 4, due October 28. pdf file.
  Sampling paper (pdf) ,
  Visibility PRM paper (pdf) , Visibility PRM paper (ps) .
  Good advice from Prof. Wes Huang on how to read a research paper and how to write a reading report.
• Assignment 5, due November 7. pdf file, Submission page .

Exams

• October 21 (Friday): Midterm (in class, 10:00am-11:50am)
  
• 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 14 (October 18).
• Please bring a pencil, eraser, and a ruler (straight edge) to the exam.
• Here is a list of formulas that will be provided to you: cribsheet .

Schedule

• September 9/16 (Fri): Assignment 1 due
  
• October 3 (Mon): Assignment 2 due
  
• October 14 (Fri): Assignment 3 due
  
• October 21 (Fri): Midterm (in class)
  
• October 28 (Fri): Assignment 4 due
  
• November 7 (Mon): Assignment 5 due
  
• November 11 (Fri): Final Project proposal due: pdf file.
  
• December 7 (Wed): Final Course Project due (revised due date)
  

The presentation of papers by graduate students will be in November. Here is a preliminary and rather incomplete list of papers to choose from.
Here is the schedule of paper presentations.

Project

• November 11 (Fri): Final Project proposal due: pdf file.
  
• December 7 (Wed): Final Course Project due (revised due date)
  
• Project submission page .

Announcements

• You should have received an email from me listing your scores for assignments and exams. Please let me know by Tuesday (Dec 6) if any of those scores are incorrect.

  I have placed graded Assignment 4 outside my office. You should receive Assignment 5 grades from Kartik.

• For the latest project info, please see the Final Course Project page .
• Here is the Project submission page .
• Here is the Assignment 5 submission page .
• You should have access to Amos Eaton during the day over the weekend. If it is locked, please call public safety to remind them.
• I have not yet been able to get the lecture notes for Lectures 16 and 17 scanned in. That will be done by Monday. Please read the relevant textbook chapters meanwhile.
• Please bring a pencil, eraser, and a ruler (straight edge) to the exam. Here is a list of formulas that will be provided to you: cribsheet .
• Midterm exam is on Friday, October 21, (in class, 10:00am-11:50am). There will be no makeup exam. Please contact me in advance if you have a legitimate reason for not being able to attend the exam.
  
• Graded Assignment 1 is in the box outside my office. Remember to pick up both parts of your assignment.
• The DARPA Grand Challenge autonomous robot race is on Saturday, Oct 8.
• Owing to the various issues with dolt that some of you have encountered, the Assignment 2 due date is changed to 11:59pm on Monday, October 3 . Please regularly check the Assignment 2 FAQ for any further clarifications.
• If you need a CS ID (for Assignment 2), please send me email before 5pm on Tuesday, September 20.
• Please see the Assignment 2 web page for sample files and additional information.
• Lecture 4 notes are now visible on webct. (We forgot to update the student view. My apologies for the delay.)
• There was a question in class today regarding Qn 1 of Assignment 1, and my response was inaccurate. Note that the polygon P is not convex and hence the polygon must be represented as a union of halfplane intersections.
• Homework assignment 1 has been handed out. See link above. It is due at the beginning of class on the due date.
• The scanned-in lecture notes are now available on WebCT. Follow the Lecture Notes link off the Course Menu. (If you do not find it, send me email.)
• The Choset book is now available at the Bookstore. Follow link above for the LaValle book.