Geometric Computation for Motion Planning
CS 6370 and ME EN 6960-03

Schedule: MWF 12:55 - 1:45
Location: MEB 3105
Instructor: David Johnson
Email: dejohnso@cs.utah.edu
Office: 2875 WEB (ph) 585-1726
Hours: I am generally available and through appointment. The best hours for drop-in meetings are in the morning and late afternoon.
Texts: 
Principles of Robot Motion: Theory, Algorithms, and Implementations
by Howie Choset, et al.
MatLab student edition
(you need MatLab availablility, either through purchase or use in the labs)

Objectives

Robot motion planning formulates safe motion through a modeled environment. This problem can be formulated in a high dimensional space, known as a configuration space, and various approaches to a solution use this abstraction in creative ways. Underlying these approaches are fundamental geometric computations, such as model-model intersection and minimum distance, with broader application in computer animation, simulation, computer-aided design, haptics, and virtual reality. Topics to be covered in this course are spatial subdivision and model hierarchies, model intersection, distance queries and distance fields, medial axis computations, configuration spaces, geometric constraint solving, and motion planning. Classical geometric planning algorithms will be covered as well as current randomized approaches and topics on localizations and SLAM. The course will rely on lectures, readings, and projects to provide understanding of current practices in the field.

Students should finish the course with:

Grading

Your course grade will depend on the following factors:
 Programming Assignments (5) 60%
 Final Project Paper and Talk 25%
 Discussion and Paper Critiques 5%
 Final Exam 10%

Policies

Late Policy: Zero credit is given for late work, please just submit what you have for partial credit if unfinished. However, you can have three late days to use at your discretion (not for the final project). You must notify me of your intent to use this privilege by the original due date. Also, additional leeway can be given for officially sanctioned University activities.

Cheating and Plagiarism: Students are encouraged to discuss approaches with one another and to help one another with computer infrastructure questions, but not to share or view another person’s code.

This is a graduate level course. As such, students are expected to behave in a professional manner.

Accommodations: The University of Utah seeks to provide equal access to its programs, services and activities for people with disabilities. If you will need accommodations in the class, reasonable prior notice needs to be given to the Center for Disability Services, 162 Union Building, 581-5020 (V/TDD). CDS will work with you and the instructor to make arrangements for accommodations.

Lecture Materials

Lecture materials are kept off of the main web page

www.cs.utah.edu/classes/cs6370/Lectures

Schedule (to be adjusted as needed)

August

25     Syllabus Overview/Introduction to Motion Planning
27     Graphs/Terrain Graphs/Graph Representation in MatLab 
                  (Read Appendix H) (Read Wikipedia on Graphs)
29     Graph Search/Costmaps


September

1 - Labor Day
3      A* graph search                                           Assignment 1: Graph Search                
5      Distance metrics (p. 479-480)				 Read my notes on distance

8      Simple primitives
10     Convex Objects/Minkowski Sum/C-space (p. 477, Chap. 3)                      
12     Visibility Algorithms (pages 110-116)                     Assignment 1 due/Assignment 2: Visibility Graphs

15     Cell Decomposition/Trapezoidal Decomposition (p. 162-168)
17     Hierarchical Cell Decomposition
19     Potential Field Methods	(section 2.1, chap. 4)                                 

22     Numerical Integration                                     Assignment 2 due/
24     More on Potential Field Planners				 Assignment 3: Potential Field Planner
26     Roadmaps/Voronoi Diagrams

29     Generalized Voronoi Diagrams


October

1      Probabilistic Roadmaps
3      Probabilistic Roadmap Sampling                            Collision paper critique due next Wednesday.

6      PRM Sampling/PRM Demo                                     Assignment 3 due
8      the LINK function  (collision paper critique)             Assignment 4: PRM
10     More PRM sampling

13 - Fall Break
15 - Fall Break
17 - Fall Break

20     Polygonal Model Collision Detection
22     Polygonal Model Distance
24     RRT

27     Multiple robots, flocks, swarms
29     Final Project Planning                                    Assignment 4 due
31     Gaussians, Estimation, Probability


November

3      Kalman Filtering
5      Final Project pitches
7      Grid Localization

10     Particle Localization                                     Assignment 5: Particle Localization
12     SLAM
14     Guarding and Pursuit-Evader

17     Grasp and assembly
19     Manipulation                                              Assignment 5 due
21     Trajectory planning/Reed and Shepp's paths

24     Splines
26     Project consult
28 - Thanksgiving


December

1      Splines for non-holonomic vehicles
3      DARPA Urban Challenge talk
5      Protein folding applications

8      Surgical Applications
10     Review
12     Mini-final

Final Exam Period - Monday, December 15 1-3PM - Final Project Presentations