CSCI-4965/6963: Robot Motion Planning
Fall 2001

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: Monday and Thursday, 2:00pm - 3:50pm
Classroom: Sage 2715

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, randomized path planning, multiple robot coordination, collision detection, manipulation, and nonholonomic motion planning. We will motivate these techniques by applications of motion planning to mobile robots and robot manipulators, assembly planning, computer aided design, and computer graphics. Prerequisites are CSCI-2300 (Data Structures and Algorithms) and familiarity with Calculus and Linear 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. Please see the syllabus for details.

Syllabus. postscript file, pdf file.

Textbook

Robot Motion Planning by J.-C. Latombe, Kluwer, 1991.
The textbook will be supplemented by handouts and recent papers.
Note: There is a copy of the textbook on reserve in the Folsom library.

Chapter 2, Motion Strategy: Algorithms and Applications by Steven LaValle postscript file, pdf file.
Chapter 3, Motion Strategy: Algorithms and Applications by Steven LaValle postscript file, pdf file.
Chapter 4, Motion Strategy: Algorithms and Applications by Steven LaValle postscript file, pdf file.
Chapter 7, Motion Strategy: Algorithms and Applications by Steven LaValle postscript file, pdf file.
Chapter 8, Motion Strategy: Algorithms and Applications by Steven LaValle postscript file, pdf file.
Chapter 9, Motion Strategy: Algorithms and Applications by Steven LaValle postscript file, pdf file.

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.
Computational Geometry: Algorithms and Applications , second edition, M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer, 2000.
Introduction to Algorithms, by T. H. Cormen, C. E. Leiserson, and R. L. Rivest, MIT Press, 1990. Or the recently released second edition.

Lectures

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

The scanned-in lecture slides are available online through the library's electronic class reserves.
Here are the slides of class presentations by graduate students.

Assignments

Assignment 1, due September 17. postscript file, pdf file.
Assignment 2, due October 1. postscript file, pdf file. Go here for more information.
Assignment 3, due October 11. postscript file, pdf file.
Assignment 4, due October 22. postscript file, pdf file.
Assignment 5, due November 8. postscript file, pdf file.

Check here for recent announcements .

Schedule

Here is the tentative assignment and exam schedule:

September 17 (Mon): Assignment 1 due
October 1 (Mon): Assignment 2 due
October 11 (Thu): Assignment 3 due
October 15 (Mon): Midterm (in class)
October 22 (Mon): Assignment 4 due
November 5 (Mon): Project proposal due
November 12 (Mon): Assignment 5 due
November 29 (Thu): Course project due

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 .

Project

Project proposal, due November 5 (Monday) ps , pdf
Course Project, due November 29 (Thursday). New due date: 11:59pm, Tuesday, December 4 !
Please submit your code and related files using the submission script, and email me a pointer to your project web page.
The project report should clearly describe what your motion planner can do (type of robot, obstacles, number of dimensions, motion model, collision checking, algorithm used), how you implemented it (especially modifications to the algorithm), a few snapshots of examples, the advantages and disadvantages of your implemented approach, any bugs or limitations of your implementation, identify libraries or code written by others that you are using, etc. If there are particularly interesting things in your implementation or things that you noticed in running your planner on examples, point those out as well.
Here is the project demo schedule .
Please submit your code and related files using the submission script, and email me a pointer to your project web page before 11:59pm, December 4.
Here are the project web pages .

Announcements

Please check these announcements frequently. Last updated Tuesday, December 4 at 5:30pm.

Please submit your code and related files using the submission script, and email me a pointer to your project web page before 11:59pm, December 4.
Here is the project demo schedule .
The new due date for the final course project is now 11:59pm, Tuesday, December 4.
Assignment 5: For the part that asks you to compare the different planners on the example data, you can limit yourself to the RRT-based and PRM planners if you like. I would like you to study the problem (holonomic, nonholonomic, likelihood of narrow passages, etc) and use that information to guide you in identifying a good planner for the problem. While a comprehensive comparison of the different planners on the examples would be great, that is not necessary. Justifying your choice of planner for each example is recommended.
The Sun labs in Amos Eaton 117 and 217 will be open on Sunday (Nov 11) from 9am to 5pm. It is possible that Amos Eaton 117 will be open on Saturday (Nov 10) from 9am to 5pm. If either lab is locked and there is someone inside, you can ask them to let you in. If you find the doors to Amos Eaton locked, call campus security to let you in.
I have written comments on your project proposals to provide feedback. You can pick them up from me on Wednesday, or I will bring them to class on Thursday.
The due date for Assignment 5 is now Monday, November 12.
Here is a link to the MSL home page. You may find Chapters 7, 8, 9 of Motion Strategy: Algorithms and Applications by Steven LaValle (available in the Textbook section above) helpful in understanding the MSL.
Graded midterms are available if you would like to pick them up before class on Thursday.
Class presentations by graduate students: Here is a list of assigned presentations .
The assigned readings include Chapter 3.1 of LaValle, which contains helpful mathematical background material. However you will not have topology questions on the midterm.
There will be no programming questions on the midterm. Of course, questions about motion planning algorithms are fair game.
The midterm covers all material discussed in class through October 11. Since class on October 11 focused on solutions to assignments, there are no lecture notes for October 11.
Class presentations: Here is a preliminary list of papers for graduate students (taking CSCI-6963) to select from.
Assignment 3, Question 6: You may find it helpful to look at Chapter 8.3.1 of Latombe.
Assignment 3: For question 2, indicate the status of the sweep line between events. For the status, you should indicate the edges in order, but do not have to show a corresponding binary tree representation.
Since Tuesday, October 9 is on a Monday schedule, I will have office hours after class from 4:00 to 5:00pm instead of 2:30-3:30pm.
Assignment 3 is here: postscript , pdf.
Assignment 2: Go to the Assignment 2 page for the latest information.
Assignment 2: Here is obstacles.txt , an example file with convex polygonal obstacles. Note that you cannot assume a fixed limit on the number of edges of a polygonal obstacle.
Assignment 1: For problem 3, assume the center of the semi-circular arcs lies on the right edge of the vertical bar of the D. So the right edge of the vertical bar lies on the y axis.
Assignment 1: For problem 4(b), the center of the gripper is the point C in the figure.

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

CSCI-4965/6963: Robot Motion Planning Fall 2001