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) 50%
 Final Project Paper and Talk 25%
 Discussion and Paper Critiques 10%
 Final Exam 15%

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

24     Syllabus Overview/Introduction to Motion Planning
26     Graphs/Terrain Graphs/Graph Representation in MatLab/Costmaps 
                  (Read Appendix H) (Read Wikipedia on Graphs)
28     Graph Search - Depth First/Breadth First

31      - David out


September


2      Heuristic Search/A*                                       Assignment 1: Graph Search                
                                                                 
4      Distance metrics (p. 479-480)/Simple primitives		 Read my notes on distance


7      Labor Day  - no class
9      Distance computations/Distance to Primitives
11     C-space (p. 477, Chap. 3)                      


14     Minkowski Sum/Grid Decomposition (p 162-168)  Assignment 1 due
                                                                 Assignment 2: C-space     
16     Visibility Algorithms (pages 110-116)                    
18     Potential Field Methods	(section 2.1, chap. 4)                                 

21     Numerical Integration                                     
23     More on Potential Field Planners				 
25     Roadmaps/Voronoi Diagrams                                 

28     Generalized Voronoi Diagrams                              Assignment 2 due/Assignment 3: Potential Field Planner
30     Probabilistic Roadmaps


October

2      Probabilistic Roadmap Sampling                            LINK paper and How to do a critique Sept 7      

5      PRM Sampling/PRM Demo
7      Class discussion
9      More PRM                                                  Assignment 3 due
	                                                         Assignment 4: PRM

12
14    Fall Break
16

19     Polygonal Model Collision Detection                      Here is a summary of PCA
21     Polygonal Model Collision     
23     Polygonal Model Distance (critique?)

26     RRT     
28     RRT2
30     Sensor-based planning - Bug1, Bug2                       Assignment 4 due


November


2     Final Project Planning
4     Gaussians, Estimation, Probability
6     Kalman Filtering

9      Final Project pitches
11     Grid Localization
13     Particle Localization                                     Assignment 5: Localization

16     SLAM
18     Multiple robots, flocks, swarms - paper critique          Read Flocking paper             
20     Pursuer-evader    

23     Trajectory planning/Reed and Shepp's paths                Assignment 5 due
25     Splines
27     Thanksgiving

30     Project consult 


December


2     DARPA Urban Challenge talk
4     Grasp and assembly


7     Deformable models 
9     Review
11    Mini-final

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