Jump to: navigation, search
EE-562/CS-5610: Robot Motion Planning


Dr Abubakr Muhammad, Assistant Professor of Electrical Engineering

Email: abubakr [at]

Office: Room 9-351A, Right Wing, 3rd Floor, SSE Bldg

Office Hours:

Teaching assistant.

Course Details

Year: 2013-14

Semester: Spring

Category: Grad

Credits: 3

Elective course for electrical engineering, computer engineering and computer science majors

Course Website:

Course Description

Motion planning is the study of models and algorithms that reason about the movement of physical bodies such as humans, robots, and animals. This course focuses on motion planning for industrial manipulators and autonomous mobile robots such as unmanned aerial and ground vehicles. Topics include representations of state and movement, potential functions, roadmaps, cell decomposition, sampling based probabilistic planners, robot dynamics, sensor limitations and environmental mapping. Students will implement motion planning algorithms in open-source robotics frameworks such as ROS and OMPL, read recent literature in the field and complete a project that draws on the course material. The course bridges the gap between low-level regulatory control and higher-level AI in robots.


  • Introduce fundamental principles in robot motion planning.
  • Use of geometric and dynamical models acquired from sensory data.
  • Using sensor-based information to determine robot’s own state and of the world
  • Setting up and running planning algorithms on robotic platforms
  • Control theoretic issues in trajectory planning and sensory feedback.

This course is NOT about

  • Mechatronics or robot building.
  • Higher-level perception and AI.

Learning Outcomes

Students will be able to:

  • To model and simulate robotic mechanisms and vehicles.
  • To analyze limitations of motion and sensing in motion planning.
  • To integrate control, planning and reasoning problems in autonomous systems.
  • To implement motion planning methods in complex uncertain environment.


Courses. EE-361. Feedback control systems OR CS-310. Algorithms OR By permission of instructor.

Topics/Skills. Programming proficiency in C or MATLAB; multi-variable calculus, linear algebra, probability

Text book

The course will be taught from a combination of the following textbooks.

Primary Texts

Secondary Texts

Grading Scheme

  • Home Works ( 5 x 4% ) : 20%
  • Midterm Examination: 25%
  • Final Examination: 30 %
  • Group Project: 25 %

Course Delivery Method

Lectures. Mon, Wed: 9:30am-10:45am.


Week 1. Jan 13 Lec 1. Introduction; what is a robot?; course objectives;

Lec 2. workspaces; configuration spaces; planning algorithms; bug algorithms; Bug0 and Bug1 algorithms;

Choset Chapter 1,2;

Introductory Slides.

Bug algorithms. Errata.

Week 2. Jan 20 Lec 3. Completeness of Bug1; upper bounds on Bug1; Bug2 algorithm; performance comparison; range sensors and mathematical description.

Lec 4. Tangent Bug algorithm; implementation issues; wall-following behavior with range sensors;

Homework 1

Textbook Slides - Bug Algos;

Choset CH 2;

LaValle 12.3.3. Planning in Unknown Environments;

LaValle 12.3.4. Competitive Ratios

Week 3. Jan 27 Lec 5. The idea of a configuration spaces; Config. Spaces of mechanical linkages and mobile robots; Obstacles; A bug algorithm for a 2-link robotic arm;

Lec 6. Mappings between configuration spaces and workspaces; geometric primitives; star algorithms for polygonal robots and obstacles;

Homework 2

Textbook Slides - CSpaces;

Choset Chapter 3;

Week 4. Feb 3 Lec 7. Rigid body configuration spaces; SO(3); SE(3); parameterization of SO(3); kinematics of rigid bodies; Textbook Slides;

Choset Chapter 3;

Week 5. Feb 10 Lec 8. Rigid bodies (contd.); kinematics Vs. dynamics; constraints (holonomic Vs. non-holonomic); Velocity kinematics;

Lec 9. Velocity kinematics (contd.); Games and puzzles as Planning algorithms; Multi-agent configuration spaces; continuity in configuration spaces;

Homework 3

Textbook Slides - CSpaces;

Slides on Discrete Planning

Choset Chapter 3;

Week 6. Feb 17 Lec 10. Discrete configuration spaces; generalized view of state-spaces; state transition functions on discrete configuration spaces; finite state machines and discrete planning;

Lec 11. Graph searches as planning algorihtms;

Slides on Discrete Planning

Textbook Slides - A*

LaValle Chapter 2. Discrete Planning; Choset Appendix H;

Week 7. Feb 24 Lec 12. Use of heuristics in cost functions or rewards; H-star algorithm; Dijkstra's algorithm revisited; a formal analysis of discrete planning; value iteration in forward and backward search; Bellmann's principle of optimality;

Lec 13. Artificial potential functions; primitives for attractive and repulsive potentials;

Homework 4

Choset Appendix H, Chapter 4;

Textbook Slides - A*

Textbook Slides - Potentials

LaValle 2.3. Discrete Optimal Planning

Week 8. March 3 Lec 14. Artificial potential functions (contd.); Bush-fire algorithm; local minima; Wave-front planners; Lifts of forces and torques from workspace to configuration spaces;

Lec 15. Artificial potentials in non-Euclidean spaces; navigation functions on sphere-worlds;

Choset Chapter 4;

Textbook Slides - Potentials

Week 9. 17 March Lec 16. Navigation functions (contd.); navigation functions on star worlds; convexity and star-property; diffeomorphisms between star worlds and sphere worlds; invariance of navigation function properties under morphisms; topology and obstacles;

Lec 17. Cell decomposition; Trapezoidal cell decompositions; Morse decomposition; Reeb graphs; CSpaces for dynamic obstacles; practical issues; coverage problems in robotics;

Homework 5

Choset Chapter 4, 6;

Textbook Slides - Potentials

Textbook Slides - Cell decomposition

Week 10. March 24 Midterm. Exam Problems

Lec 18. Introduction to roadmaps in configuration spaces; visibility maps; visibility graph construction; convexity revisited; Voronoi partitions; Generalized voronoi diagrams; GVD roadmaps;

Choset Chapter 5;

Textbook Slides - Roadmaps

Navigation Functions on Product Spaces

Week 11. March 31 Lec 19. Deterministic Vs. Probabilistic methods of roadmap construction; Sampling based planners; Probabilistic roadmaps; PRM algorithm introduction; construction phase; Algorithmic and analytical challenges in roadmap construction using sampling; Distances in non-Euclidean CSpaces; Formal introduction to Metric spaces;

Lec 20. Configuration spaces as metric spaces (contd.); distance metrics on S^1, SO(2), SE(2), T^n; composition of metrics on product spaces; Quaternion algebra; topology of SO(3) as RP^3; distance metrics on SO(3), SE(3) using quaternions; generating random elements of R^n, S^1, SO(2), SE(3); Lebesgue and Haar measures; A reciep to generate random rigid body orientations using quaternion algebra;

Project Task 1

Choset Chapter 7;

LaValle 4.2.2 Quaternions

LaValle 5.1. Metric Spaces

Textbook Slides - Sampling Based Algorithms

Week 12. April 7 Lec 21. Learning phase in PRM algorithm; recall of construction; kd-trees for fast comparison; local planner; heuristics for expansion; OBPRM algorithm; Gaussian sampling; Jacobian matrix and manipulability in robotic manipulators; manipulability based sampling; query phase;

Lec 22. Analysis of sampling based algorithms; comparing sampling methods; coverings of CSpace; discrepancy of random sequences; dispersion of sample sets; Sukharev's sampling bound; deterministic completeness Vs. probabilistic completeness; completeness of PRM algorithm; sketch of proof;

Lab Session. Hands-on introduction to sampling based planners via Open Motion Planning Library (OMPL)

Choset Chapter 7;

Textbook Slides - Sampling Based Algorithms


Week 13. April 14 Lec 23. Introduction to Simultaneous Localization and Mapping; motivation for SLAM problems; inadequacy of odometry; SLAM as a chicken-and-the-egg problem; uncertainty in models and sensors; SLAM as a hard problem; data association problems; a probabilistic framework for solving SLAM problems; Probabilistic Graphical Models (PGM) for SLAM; role of statistics and prior information;

Lec 24. Uncertainty in motion models; odometry models in mobile robots; empirically tuning probabilistic odometry models; sensors in mobile robotics; sources of uncertainty in range finders; modeling ultrasound and laser data; empirically tuning probabilistic sensor models;

Slides on SLAM

Thrun Ch 1, 2

Week 14. April 21 Lec 25. Review of uncertain motion models and noisy sensors; Baye's rule; prior, posterior and conditional density functions; state estimation as Bayesian inference; diagnostic models vs causal models; inverting sensor models to estimate state; inverting motion models to estimate state; prelude to Bayes filter; a 1D robot localization example to explain Bayesian filtering;

Lec 26. Guest lecture by Dr Ahmad Kamal Nasir on SLAM

Slides on SLAM;

Guest lecture on SLAM;

Thrun Ch 1, 2; Choset Ch 8, 9

Week 14. April 28 Lec 27. Guest lecture by Dr Ahmad Kamal Nasir on SLAM (contd.)

Lec 28. Bayes filter derivation; implementation issues in Bayes filter; Final look at localization, mapping and SLAM; Course Wrap up

Slides on SLAM;

Guest lecture on SLAM;

Thrun Ch 1, 2; Choset Ch 8, 9

Personal tools