CS26N: Motion
Planning for Robots, Digital Actors, and Other Moving Objects
Spring 2010
Class time and location: Mon-Wed 9:30-10:45am, Gates, 100
Instructor: Jean-Claude Latombe, S244,
Clark Center,
latombe@cs.stanford.edu , ai.stanford.edu/~latombe/
Office hours: Tuesday
11am-noon (+ by arrangement when needed)
Goal of the course: It will introduce a fun domain (motion
planning) that has many applications: mobile robots, manipulation robots,
humanoid robots, product design and manufacturing, graphic animation, video
games, computer-generated movies, surgical planning, architectural design,
navigation in complex virtual worlds, molecular simulation, etc... Throughout
their applications to motion planning, the course will describe several
modeling and computational tools that have broad usage across engineering and
sciences, e.g., concepts in geometry, kinematics and dynamics, and algorithms
(search, linear programming), as well as more specific tools (e.g.,
approximating the connectivity of a complex space using random sampling
techniques).
Assignments and exams:
1. Most lectures will be scribed by one or two
students. Each student will get 1 point to scribe a lecture alone and 0.5 point
to scribe a lecture with another student. Each student must eventually get at
least 2 points.
2. There will be 4 homework assignments, in
the form of small problems or questions. A new assignment will be emailed on
Wednesday 4/7,
4/21, 5/5, and 5/19, to be
returned on the following Wednesday at the end of the class.
3. Each student will have to return a position
paper at the end of the quarter. This paper will describe how the student would
apply motion planning methods to a specific problem, e.g., planning the
trajectories of cranes on a construction site, generating a user′s manual to assemble a product, designing a
video game that could make substantial use of motion planning methods, etc...
All positions position papers will be presented at a special session in front
of the class at the end of the quarter.
4. There will be no midterm or final exam.
Grading: 30% for lecture scribing, 10% for each HW
assignment, 30% for position paper (and its presentation).
Scribing a class: I do not ask you to just repeat what has
been said in class. Your scribing report should summarize and stress the main
issue(s) addressed in the class, why they are important, and how they can be
addressed. You should try to illustrate your report with examples different
from those used in class. Personal ideas and suggestions not covered in class
are welcome.
Collaboration policy for HW
assignments: Each
student should complete the assignments alone. However, you may, and actually
are encouraged to discuss the assignments with other students in the class, but
without taking any written or electronic notes.
Tentative schedule (to be
updated during quarter):
1.
3/29: Introduction:
What is motion planning? What are the applications?
2. 3/31: How to plan the motion of a point
robot among obstacles in a plane? Bug algorithms
3.
4/5: How to plan the
motion of a point robot among obstacles in a plane? Grid searching
4. 4/7: How to plan the motion of a point
robot among obstacles in a plane? Cell decomposition, Visibility graph, Voronoi
diagram
5. 4/12: Graphic animation of a
digital actor
6. 4/14: Configuration space of a moving rigid
object
7. 4/19: How to plan the motions
of a car, including back-up maneuvers, like parallel parking?
8. 4/21: How to plan the motions
of a car, including back-up maneuvers, like parallel parking?
9. 4/26: How to plan the disassembly (and
re-assembly) of a mechanical assembly made of many parts?
10. 4/28: How to plan the motion
of a complex articulated robot? Probabilistic roadmap planners
11. 5/3: Sampling and connection strategies to
speed up probabilistic roadmap planners
12. 5/8: Sampling and connection strategies to
speed up probabilistic roadmap planners
13. 5/10: How to detect collisions with
computer models?
14. 5/12: Hansen Medical′s robotized
catheter (guest lecture by Federico Barbagli)
15. 5/17: How to detect collisions with
computer models? (Computation of BHV models)
16. 5/19: Initial student presentations of
position papers
17. 5/24: Application of motion planning to
radiosurgery: the Cyberknife robotic system
18. 5/26: Motion planning for legged robots on
irregular terrain
19. 6/2: Final student presentations of
position papers (the class will start at 9am
instead of 9:30am)
Material posted during the
course (homeworks and slides):
Slides
of Class #1
Slides
of Class #2
Slides
of Class #3 and Class #4
Slides
of Class #5
Slides
of Class #6
Slides
of Classes #7 and #8
Slides
of Class #9
Slides
of Class #10
Slides
of Classes #11 and #12
Slides
of Classes #13 and #15
Slides
of Class #17
Slides
of Class #18