Motion Planning

CS26N: Motion Planning for Robots,
Digital Actors, and Other Moving Objects
Winter 2012

actor1 geex protein1 sony-robots

image-unc arlrobot loopg2full

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

humansecond010

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