(Difference between revisions)
Jump to: navigation, search
Line 4: Line 4:
|- style="background:#e0e0ff; color:black; font-size:18px; -moz-border-radius:8px;"
|- style="background:#e0e0ff; color:black; font-size:18px; -moz-border-radius:8px;"
! width="75%" colspan="2" | Spring 2014 [UNDER CONSTRUCTION.]
! width="75%" colspan="2" | Spring 2014  

Revision as of 17:20, 31 December 2013

EE-562/CS-5311: Robot Motion Planning
Spring 2014


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 %
    • Proposal. 3%
    • Code / demo. 8%
    • Presentation. 4%
    • Paper. 7%
    • Team work balance. 3%

Course Delivery Method

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

Schedule (in last offering)

Week 1. August 23 Aug 23. Classes begin. Lec 1. Introduction; robotics and autonomous systems;

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

Choset CH 1,2;

Stanley, the robot that won the DARPA Grand Challenge

Bug algorithms. Errata from author's website.

Week 2. August 30 Aug 30. Add/drop with full refund 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

MATLAB code solutions

Choset CH 2; LaValle SEC 12.3.3;
Week 3. September 6 Sept 9-14. Eid-ul-Fitr holiday Lec 5. Introduction to discrete planning; state space models and examples; discrete feasible planning; graph search algorithms; general forward search;

Lec 6. Breadth first search; depth first search; Dijkstra's algorithm; A*; systematic searches; configuration spaces revisited; mechanical linkages; forward and inverse kinematics; toroidal configuration spaces;

LaValle CH2;


Dijkstra's algorithm Demo

Week 4. September 13 Sept 15. Second payment deadline Lec 7. Mapping workspace obstacles into configuration space obstacles; visualizing high dimensional configuration spaces; a first look at obstacles in SE(2); polygonal robots and obstacles; Choset CH3, Appendix F
Week 5. September 20 Lec 8. representing polygonal objects via linear inequalities; computing configuration space obstacle polygons from workspace descriptions; star algorithm; Minkowski sums and differences of sets;

Lec 9. Holonomic constraints; degrees of freedom in a configuration space; rigid body CSpace in 2D; rigid bodies in 3D; SO(3) matrix group; Euler parameterization;

Lavalle SEC4.3.2, SEC3.2;

Choset CH3, Appendex F, E.

Week 6. September 27 October 1. Semester Drop with fee Penalty Lec 10. SO(2) revisited via complex numbers; generalization to SO(3); quaternion algebra; topology of SO(3);

Lec 11. Gimbal lock problem; parameterization problems and topology of configuration spaces; topology of S^1 x S^1 vs S^2; S^3; SO(3); RP^3; quaternions as a double cover of SO(3);

Lavalle SEC3.2 ,SEC4.2; Choset CH3, Appendix E;

Gimbal lock problem in Euler Angles. Video.

Quaternions and the topology of SO(3).

Week 7. October 4 Lec 12. 2D and 3D rigid bodies revisited; rotations and translations of points and bodies; types of joints; kinematic chains; DH-parameters;

Lec 13. Introduction to roadmaps; deterministic/combinatorial methods for roadmap construction; general properties; visibility graphs; line-sweep algorithm;

Homework 2

MATLAB code solutions

LaValle SEC3.3; Choset CH5.
Week 8. October 11 Lec 14. Voronoi diagrams; generalized Voronoi diagrams (GVD); bush-fire algorithm; wavefront algorithm;

Lec 15. Potential field methods; vector fields and gradients; critical points and Hessian matrix; attractive and repulsive potential fields; gradient descent algorithm; local minima and other practical implementation issues; another look at bush-fire algorithm;

Choset CH4;
Week 9. October 18 Midterm exams Lec 16. Introduction to navigation functions; navigation functions for the sphere-shaped world; compositions of potentials; analytical switches; empirical tuning of navigation functions;

Lec 17. Star-shaped worlds; diffeomorphisms; mapping stars to spheres; analytical switches revisited; navigation functions for star worlds;

Choset CH4;
Week 10. October 25 Lec 17. Inverse and forward kinematics; lifting velocities and forces between coordinate changes; modified potential field method for direct workspace control;

Lec 18. Introduction to sampling based planning; problem history and motivation; computational complexity of planning algorithms; introduction to probabilistic road-maps algorithm (PRM); query phase of PRM;

Tutorial. Using the MATLAB robotics toolbox. (Oct 29)

Choset SEC3.8, SEC4.7, CH 7;

MATLAB Robotics Toolbox Tutorials.

Week 12. November 1 Project Proposal Presentations. (Session 1)

Project Proposal Presentations. (Session 2)

Week 13. November 8 Nov 9. Iqbal day; Lec 20. PRMs continued. Refinements in PRM construction; sampling difficulties and narrow passages; distance functions for non-Euclidean spaces; metric spaces and Lp-norms for complex configuration spaces; Cartesian products; metrics for S^1, SO(3) using complex numbers and quaternions; generating a random configuration in S^1, SO(3);

Lec 21. Introduction to probabilistic robotics; modeling sensor noise; basic probability and statistics; linear transformations of Gaussian random variables; interpreting and visualizing the covariance matrix; state and measurement;

Lec 22. Linear systems; discrete-time linear models from equations of motion; examples; process noise and sensor noise; Objectives of Kalman filtering;

Choset CH7, CH8;

Lp Norms and Metrics.

Week 14. November 15 Eid-ul-Azha holidays. Nov 17-19.
Week 15. November 22

Lec 23. Basic laws of probability and Bayes rule; belief about state; derivation of the Bayesian filter; prediction and update; dealing with beliefs and distributions for nonlinear non-Gaussian systems; Kalman Filtering as a special case;

Lec 24. Derivation of the Kalman filter; combining estimates from two scalar Gaussians; innovation and Kalman gain; estimation in the absence of process and sensor noise; state and covariance prediction; combining measurement and prediction in the presence of process noise;

Thrun CH 2; Choset CH8

Week 16. Novemeber 29

Lec 25. Completion of proof of KF; basic SLAM using Kalman filtering; non-linear models of sensing and robot motion; Extended Kalman filtering;

Lec 26. Nonlinear transformations of random variables; generation of non-Gaussian noise via nonlinear transforms; modeling sensor noise; ultrasound, laser models and other non-Gaussian sources; data association problem;

Lec 27. Probabilistic localization using Bayesian filtering; data association problem revisited; histogram Bayes filter; introduction to particle filtering; computational issues in sampling arbitrary distributions; practical demonstration of Kalman filtering.

Thrun CH 2,3,4; Choset CH8
Week 17. December 6 Dec 8. Last day of classes; Dec 9-15. Final Exams

Lec 27. Wrap-up. Future directions.

Take home Exam. Due December 7th.

Week 18. December 13 Dec 16-17. Ashura Holidays;

Dec 27. Final grades submission; Dec 20-Jan 21 Semester break.

Project Presentations/Viva/Demo 1. Dec 14th

Project Presentations/Viva/Demo 2. Dec 15th

Project Ideas (Last Offering)

Feedback control methods / robot dynamics

  • LQR-Trees: Feedback Motion Planning on Randomized Trees. Paper..
  • LQG-MP: Optimized Path Planning for Robots with Motion Uncertainty and Imperfect State Information Paper. Hasan Arshad Nasir, 10060010.
  • Integrated Planning and Control for Convex-bodied Nonholonomic systems using Local Feedback Control Policies Paper.
  • Gait Regulation and Feedback on a Robotic Climbing Hexapod Paper.

SLAM/Probabilistic robotics

  • Unified Inverse Depth Parametrization for Monocular SLAM Paper.
  • Monte-Carlo Localization for Mobile Robots with Stereo Vision Paper.
  • Probabilistic Terrain Analysis For High-Speed Desert Driving Paper.
  • A Bayesian Approach to Nonlinear Parameter Identification for Rigid Body Dynamics Paper.
  • The Iterated Sigma Point Kalman Filter with Applications to Long Range Stereo Paper. Ateeq ur Rehman Shaheen, 09060002.
  • Gaussian Processes for Signal Strength-Based Location Estimation Paper. Abdul Rehman Aslam, 09060014.
  • Map-Based Precision Vehicle Localization in Urban Environments Paper. Muhammad Salman, 09060016.
  • Detection of Principal Directions in Unknown Environments for Autonomous Navigation Paper. Amer Zaheer, 04030068.
  • Improving Localization Robustness in Monocular SLAM Using a High-Speed Camera Paper.
  • Mapping Large Loops with a Single Hand-Held Camera Paper. Rehmat Ullah Khattak, 08060009.
  • Model Based Vehicle Tracking for Autonomous Driving in Urban Environments Paper. Mazher Ahmad, 10060014.
  • Large Scale Graph-based SLAM using Aerial Images as Prior Information Paper. Syed Muhammad Abbas, 10030019.

Sampling based methods / Roadmaps

  • Incremental Sampling-based Algorithms for Optimal Motion Planning Paper. Ibrahim Tariq, 10060016.
  • Roadmap Based Pursuit-Evasion and Collision Avoidance Paper. Mudassir Khan, 10060013.
  • Elastic Roadmaps: Globally Task-Consistent Motion for Autonomous Mobile Manipulation in Dynamic Environments Paper. Mhequb Hayat, 09060019.
  • Structural Improvement Filtering Strategy for PRM Paper.


  • Single-Cluster Spectral Graph Partitioning for Robotics Applications Paper.
  • Dynamic Maps for Long-Term Operation of Mobile Service Robots Paper.
  • Distributed Coverage Control with Sensory Feedback for Networked Robots Paper. Muhammad Irfan Riaz, 09060005.
  • Dubins Traveling Salesperson Problems: novel approximation algorithms Paper.
  • Composition of Vector Fields for Multi-Robot Manipulation via Caging Paper. Nauman Shahid, 10060025.
Personal tools