CS26N: Motion
Planning for Robots,
Digital Actors, and Other Moving Objects
Winter 2012
Class time and location: Mon-Wed 9:30-10:45am, Gates, 200
Instructor:
Jean-Claude Latombe, 135, Gates Building,
Email: latombe@cs.stanford.edu
URL: 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 1/25,
2/8, 2/22, and 2/29, 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, automatically
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 (including 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.
Mon 1/9: Introduction:
What is motion planning? What are the applications?
2.
Wed 1/11: Guest
lecture by Professor Oussama Khatib:
Humanoid robots and human-robot interaction. Meeting with Honda ASIMO robot. (Exceptionally, this lecture will be given
in the central area of the Artificial Intelligence Lab, on the first floor of
Gates.)
3.
Mon 1/16: MLK Day: no
class
4.
Wed 1/18: How to plan
the motion of a point robot among obstacles in a plane? Bug algorithms
5.
Mon 1/23: How to plan
the motion of a point robot among obstacles in a plane? Grid searching
6.
Wed 1/25: How to plan
the motion of a point robot among obstacles in a plane? Cell decomposition,
Visibility graph, Voronoi diagram. Graphic animation of a
digital actor
7.
Mon 1/30: How to plan
the motion of a complex articulated robot? Probabilistic roadmap planners
8.
Wed 2/1: Sampling and
connection strategies to speed up probabilistic roadmap planners
9.
Mon 2/6: Guest lecture
by Michael Vitus (PhD candidate in the Aeronautics
and Astronautics Department): Sensing, planning and control for autonomous quadrotor vehicles (STARMAC project)
10.
Wed 2/8: Dealing with
uncertainty on two examples (Exceptionally,
this lecture will be given in Gates 300.)
11.
Mon 2/13: How to
efficiently detect collisions among objects with computer models?
12.
Wed 2/15: How to plan
the disassembly (and re-assembly) of a mechanical assembly made of many parts?
13.
Mon 2/20: Presidents’
Day: no class
14.
Wed 2/22: How to plan
the motions of a car, including back-up maneuvers, like parallel parking?
15.
Mon 2/27: Motion
planning to find a moving target
16.
Wed 2/29: Motion
planning for legged robots and climbing robots on irregular terrain
17.
Mon 3/5: Application
of motion planning to radiosurgery: the Cyberknife robotic system
18.
Wed 3/7: Application
of motion planning algorithms to the study of protein motion
19.
Mon 3/12: Student
presentations of position papers
20.Wed 3/14: Student presentations of position papers
Material posted throughout the quarter (homework assignments and
slides):
Slides
of Class #1
Slides
of Class #4
Slides
of Classes #5 and #6
Slides
of Class #6
Slides
of Class #7
Slides
for Class #8
Slides
for Class #10
Slides
for Class #11
Slides
for Class #12
Slides
for Class #14
Slides
for Class #15
Slides
for Class #16
Slides
for Class #17
Slides
for Class #18