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