Geometric Computation for Motion Planning
CS 6370 and ME EN 6225

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.
Texts: 
Principles of Robot Motion: Theory, Algorithms, and Implementations
by Howie Choset, et al. (note: the U bookstore is not carrying this text, so please order online)
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 (6) 60%
 Final Project Paper and Talk 15%
 Discussion and Paper Critiques 5%
 Mid-term and Final Exam 20%

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

22     Syllabus Overview/Introduction to Motion Planning
            - For a Matlab refresher, look at MatlabIntro.m and DrawingExamples.m.
24     Graphs/Graph Representation in MatLab/Terrain Graphs/Breadth-first Graph Search
            - Read Appendix H 
            - Read Wikipedia on Graphs
            - You can look at some Matlab implementations by downloading graphIntro.zip and trying out testGraph.m and testBreadth.m. 
26     Graph Search - Developing Breadth-first search

29     Graph Search - Dijkstra/Best-first/A*/Costmaps      
            - Assignment 1: Graph Search
31     C-space
            - Read p. 477, Chap. 3
 

September

2      Distance metrics (p. 479-480)/Simple primitives		 
            - Read my notes on distance     

5      Labor Day  - no class
7      Distance computations/Distance to Primitives
9      Grid Decomposition (p 162-168)
            - Assignment 1 due
            - Assignment 2:C-space Grid Decompositon

12     Minkowski Difference
14     Visibility Algorithms (pages 110-116)                    
16     Paper critique 
            - "An Algorithm for Planning Collision-Free Paths Among
	      Polyhedral Obstacles" by Tomas Lozano-Perez and Michael
	      Wesley, 1979. 
            - See how to do a critique

19     Potential Field Methods	(section 2.1, chap. 4)                    
21     Numerical Integration                                          
23     More on Potential Field Planners
            - Assignment 2 due
            - Assignment 3: Potential Field Planner

26     Probabilistic Roadmaps
28     Probabilistic Roadmap Sampling
30     PRM Sampling/PRM Demo


October

3      Midterm
5      Paper critique 
           -  LINK paper  
7      More PRM                                                  
           - Assignment 3 due
           - Assignment 4: PRM

10
12    Fall Break
14

17     Convex Polyhedra Collision - GJK
19     Polygonal Model Collision Detection
           - Here is a summary of PCA
21     Polygonal Model Distance

24     RRT     
26     RRT2
28     RRT3
           - Assignment 4 due
           - Assignment 5: RRT


31    Sensor-based planning - Bug1, Bug2

November

2     Gaussians, Estimation, Probability
4     Kalman Filtering

7     Kalman Filtering 2
9     Grid Localization
11    Particle Localization - paper critique

14    Active Localization
           - Assignment 5 due
16    Final Project Planning  - Guidelines   
           - Assignment 6: Localization
18    SLAM



21    Final Project pitches
23    Deformable robots
25    Thanksgiving Break

28    Multiple robots, flocks, swarms 
           - Assignment 6 due
           - paper critique on Flocking paper             
30    Pursuer-evader    

December

2     Project consult   

5     Current Directions of the Field
7     Review
9     Mini-final

Final Exam Period - December 15 1-3 P.M. Final Project Presentations