CS26N:
Motion Planning for Robots, Digital Actors, and Other Moving
Objects
Class time and location: Mon-Wed 9:30-10:45am, Gates, 100
Instructor: Jean-Claude Latombe, S244,
Office hours: Tuesday
11am-noon (+ by arrangement when needed)
TA: Ankur
Dhanik, S245
Clark Center, ankurd@stanford.edu
Office hours:
Thursday 2-4pm
You may also send
emails to both of us at cs26n-aut0708-staff@lists.stanford.edu
and to all students registered in the class at cs26n-aut0708-students@lists.stanford.edu
Goal of the course: Introduce a fun domain (motion planning)
that has many applications: robotics, product design and manufacturing, graphic
animation, video games, surgical planning, architectural design, navigation in
complex virtual worlds, molecular simulation, etc… Throughout their
applications to motion planning, introduce a number of 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).
Assignments and exams:
- Lectures will be
scribed by 2 or 3 students. Each student will scribe 2 lectures
- There will be 6
homework assignments, in the form of small problems or questions. A new
assignment will be emailed on Wednesday 10/3, 10/10, 10/17, 10/31, 11/7, and
11/14, to be returned on the following Wednesday (at the end of the class).
- The students who
wish to do so can do a programming project, instead of homework assignments.
Click here
for more information on the project (timetable, topic examples)
- There will be no
midterm and final exams.
Tentative schedule (to be
updated during quarter):
9/24: Introduction
9/26: How to plan the
motion of a point robot among obstacles? Bug algorithms
10/1: How to plan the
motion of a point robot among obstacles? Grid searching
10/3: Visit to Junior, Stanford’s robotic car that will
compete in the Darpa Urban Challenge
10/8: Graphic animation of a digital actor + How to shrink a
moving rigid object to a moving point for the purpose of motion planning?
10/10: How to perform maneuvers (e.g., parallel parking) with
a car?
10/15: Guest
lecture by Chuck Han (Stanford) “Application of Motion Planning to
Architectural Design”
10/17: Interaction with
sensors: How to build a map of a new environment? How to find a target and
track it with visual sensors?
10/22: Configuration space of an articulated robot
10/24: Guest
lecture by Tsai-Yen Li (
10/29: Motion planning for articulated robots: Probabilistic
roadmaps
10/31: Collision detection on computer models
11/5: Guest
lecture of Yotto Koga (Haiku Media) “Animation of Digital Actors”
11/7: Probabilistic sampling strategies
11/12: Humanoid
and climbing robots
11/14: Guest lecture by Federico Barbagli (Hansen
Medical) “Robotic Catheters”
11/26: Guest
lecture by Peggy Yao (Stanford) “Computational Tools to Study Protein
Motion”
11/28: Surgical planning
11/3: Open (presentation of programming projects)
Slides:
- Introduction
- Motion
Planning for Point Robot
- Configuration
space of a moving rigid object
- Car-like
robot: How to park a car?
- Target
finding and map building
- Application
to architectural design
- Configuration
space of an articulated robot. Basics of Probabilistic Roadmaps
- Application of motion
planning to human-computer interaction
- Haptic interaction
with virtual worlds
- Multi-limbed
robots on irregular terrain
- Computational
tools to study protein motion
Some movies used in the slides can be found here
Scribe
notes (scribe
schedule):
Class 2 (Motion
planning for point robot, Bug algorithms)
Class 3 (Motion
planning for point robot, grid searching)
Class 5
(Animation of a digital actor + configuration space of a rigid object)
Class 7 (Application
to architectural design)
Class 8
(Target finding)
Class 9 (Map
building + Configuration space of articulated object)
Class 10 (Application
of motion planning to human-computer interaction)
Class 11 (Basics
of Probabilistic Roadmaps)
Class 12 (Collision
detection and distance computation)
Class 13 (From
Subways, Cars, Rock Falcon to BeatStep)
Homeworks: