ECE 780 Topic 8 - Motion Coordination and Planning
Calendar Description
This course will cover aspects of path planning, dynamic vehicle routing, and coordination for mobile robots. Topics include: 1) Path planning: graph search methods; traveling salesman problems 2) Multi-robot coordination: the consensus and rendezvous problems; sensor coverage; workspace partitioning/load balancing. 3) Dynamic vehicle routing: overview of Poisson processes and birth- death processes; path planning for tasks arriving in real-time; relation to automated material handling, mobility-on-demand.
Instructor
Professor
Stephen
L.
Smith
(stephen.smith@uwaterloo.ca)
Office:
E5
5112
Office hours will be announced at the beginning of the term.
Course Outline
The main topics covered in this course are as follows:
- Introduction to robot path planning: Graph decompositions, shortest paths
- Vehicle routing problems: Traveling salesman problems, patrolling problems, monitoring problems. Solution techniques: reductions, exact algorithms and search heuristics
- Dynamic vehicle routing problems: background in stochastic processes, single and multiple robot policies. Pickup and delivery problems.
- Multi-robot coordination: Sensor coverage and environment partitioning for multi-robot operation
Project
Two types of projects are possible in this course.
- Solution to a research problem in the student’s area of research through the application of techniques presented in this course.
- Independent study of a topic not covered in class through reading research papers or book chapters. A list of possible topics will be given a few weeks into the term.
Each project will consist of a written report along with an in-class presentation.
Grading
The course will consist of four homeworks, a class project, and a final exam. The grading scheme is
- Homework: 25%
- Project: 25%
- Final Exam: 50%
Late Turn-in Policy
Homework will be due in class on Wednesday. Homework received by the Friday of the same week will be accepted with a 20% late penalty. Homework will not be accepted after the Friday.
Recommended Background
There are no formal prerequisites for the course. A familiarity with graphs, probability, and some experience with mathematical proofs and reasoning would be helpful.
Textbook
There is no required textbook. Course notes will be available and will contain all material. The following two texts will be used for parts of the course.
- Steven M. LaValle, Planning Algorithms, Cambridge University Press, 2006.
- Francesco Bullo, Jorge Cortés, and Sonia Martínez, Distributed Control of Robotic Networks, Princeton University Press, 2009.
Both books are freely available online. The first text will be used in single robot path planning, and the second text will be used for multi-robot coordination.