General Information

Course Description

This course will cover a broad spectrum of planning algorithms, including motion planning, discrete planning, planning under uncertainty, and decision-theoretic planning The course will be relevant to researcher in robotics, AI, algorithms, computational geometry and computer graphics

Course Outline

• Introduction. Overview. Goals.
• Discrete planning
  • State-space search. STRIPS planning.
  • Plan-space search. Partial-order planning.
  • Planning as satisfiability.
  • Heuristic planning.
• Motion planning.
  • Geometric representations and transformations.
  • Configuration space.
  • Sampling-based motion planning.
  • Combinatorial motion planning. Algebraic cell decomposition. Voronoi diagrams.
• Decision-theoretic planning
  • Utility theory. Decision theory.
  • Sequential decision theory. Markov Decision Processes. Reinforcement learning.
  • Sensors and information spaces. Discrete, parametric and sample-based information spaces.
  • Planning under sensor uncertainty. Partially observable Markov decision processes.

Recommended Textbook

• Steven M. Lavalle. Planning Algorithms. Cambridge University Press. 2006.
  Available online at http://planning.cs.uiuc.edu/.


• The course will require reading of scientific papers. The list will be posted on the class schedule. All of these are available through the web, and students are encouraged to track them down. Please contact the T.A. if you have difficulty finding a paper.

Class Format

• Four assignments (50%).
  The assignments will contain a mix of theory, analysis, programming, and reading/summarizing exercises.
  
• One oral presentation (10%).
  This will require oral presentation of an assigned paper.
  
• One final project (30%).
  This will require choosing a topic (the instructor can offer suggestions if necessary), writing a short proposal, completing the work, writing a report, and giving an oral presentation.
  
• In class participation (10%)
  This is a key component of the course and should be taken seriously. It includes reading the assigned papers prior to class, and actively participating in their discussion.

Grading Policy

All assignments and projects are individual. You are encouraged to consult your colleagues to discuss class material and papers, but assignments will be prepared and submitted individually. You are expected to properly acknowledge all sources (including online resources).

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offenses under the Code of Student Conduct and Disciplinary Procedures (see www.mcgill.ca/integrity for more information).