EE562
From CYPHYNETS
EE562/CS5610: Robot Motion Planning 

Instructor
Dr Abubakr Muhammad, Assistant Professor of Electrical Engineering
Email: abubakr [at] lums.edu.pk
Office: Room 9351A, Right Wing, 3rd Floor, SSE Bldg
Office Hours:
Teaching assistant.
Course Details
Year: 201314
Semester: Spring
Category: Grad
Credits: 3
Elective course for electrical engineering, computer engineering and computer science majors
Course Website: http://cyphynets.lums.edu.pk/index.php/EE562
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 opensource 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 lowlevel regulatory control and higherlevel AI in robots.
Objectives
 Introduce fundamental principles in robot motion planning.
 Use of geometric and dynamical models acquired from sensory data.
 Using sensorbased 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.
 Higherlevel 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.
Prerequisites
Courses. EE361. Feedback control systems OR CS310. Algorithms OR By permission of instructor.
Topics/Skills. Programming proficiency in C or MATLAB; multivariable calculus, linear algebra, probability
Text book
The course will be taught from a combination of the following textbooks.
Primary Texts
 Principles of Robot Motion by Choset et al. [available as low priced edition]
 Planning Algorithms by Steve Lavalle. [available as a free legal download]
Secondary Texts
 Probabilistic Robotics by Thrun et al.
 Research papers.
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:30am10:45am.
Schedule
WEEK  TOPICS  READINGS/REFERENCES 

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; 
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; wallfollowing behavior with range sensors;  Textbook Slides  Bug Algos;
Choset CH 2; 
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 2link robotic arm;
Lec 6. Mappings between configuration spaces and workspaces; geometric primitives; star algorithms for polygonal robots and obstacles;  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. nonholonomic); Velocity kinematics;
Lec 9. Velocity kinematics (contd.); Games and puzzles as Planning algorithms; Multiagent configuration spaces; continuity in configuration spaces;  Textbook Slides  CSpaces;
Choset Chapter 3; 
Week 6. Feb 17  Lec 10. Discrete configuration spaces; generalized view of statespaces; state transition functions on discrete configuration spaces; finite state machines and discrete planning;
Lec 11. Graph searches as planning algorihtms;
 Slides on Discrete Planning
LaValle Chapter 2. Discrete Planning; Choset Appendix H; 
Week 7. Feb 24  Lec 12. Use of heuristics in cost functions or rewards; Hstar 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;  Choset Appendix H, Chapter 4; 
Week 8. March 3  Lec 14. Artificial potential functions (contd.); Bushfire algorithm; local minima; Wavefront planners; Lifts of forces and torques from workspace to configuration spaces;
Lec 15. Artificial potentials in nonEuclidean spaces; navigation functions on sphereworlds;  Choset Chapter 4; 
Week 9. 17 March  Lec 16. Navigation functions (contd.); navigation functions on star worlds; convexity and starproperty; 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;  Choset Chapter 4, 6; 
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; 
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 nonEuclidean 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;  Choset Chapter 7; 
Week 12. April 7  Lec 21. Learning phase in PRM algorithm; recall of construction; kdtrees 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;  Choset Chapter 7; 