EE562
From CYPHYNETS
(→Schedule (2014)) 
(→Schedule (2014)) 

Line 123:  Line 123:  
 align ="left"  [http://www.cs.cmu.edu/~motionplanning/lecture/Chap3ConfigSpace_howie.pdf Textbook Slides  CSpaces];   align ="left"  [http://www.cs.cmu.edu/~motionplanning/lecture/Chap3ConfigSpace_howie.pdf Textbook Slides  CSpaces];  
  Choset Chapter  +  Choset Chapter 3; 
Line 131:  Line 131:  
 align ="left"  [http://www.cs.cmu.edu/~motionplanning/lecture/Chap3ConfigSpace_howie.pdf Textbook Slides];   align ="left"  [http://www.cs.cmu.edu/~motionplanning/lecture/Chap3ConfigSpace_howie.pdf Textbook Slides];  
  Choset Chapter  +  Choset Chapter 3; 
    
Line 145:  Line 145:  
[[Media:EE562discreteplanningslides.pdfSlides on Discrete Planning]]  [[Media:EE562discreteplanningslides.pdfSlides on Discrete Planning]]  
  Choset Chapter  +  Choset Chapter 3; 
    
Line 158:  Line 158:  
[http://www.cs.cmu.edu/~motionplanning/lecture/AppHastardstar_howie.pdf Textbook Slides  A*]  [http://www.cs.cmu.edu/~motionplanning/lecture/AppHastardstar_howie.pdf Textbook Slides  A*]  
  [http://planning.cs.uiuc.edu/node35.html LaValle Chapter 2]  +  [http://planning.cs.uiuc.edu/node35.html LaValle Chapter 2]; Choset Appendix H; 
  +  
    
 align ="left"  Week 7. Feb 24   align ="left"  Week 7. Feb 24  
Line 168:  Line 167:  
[[Media:EE562Hw3.pdfHomework 4]]  [[Media:EE562Hw3.pdfHomework 4]]  
   align ="left"  Choset Appendix H  +   align ="left"  Choset Appendix H, Chapter 4; 
[http://www.cs.cmu.edu/~motionplanning/lecture/AppHastardstar_howie.pdf Textbook Slides  A*]  [http://www.cs.cmu.edu/~motionplanning/lecture/AppHastardstar_howie.pdf Textbook Slides  A*]  
Line 180:  Line 179:  
 align ="left"  '''Lec 14'''. Artificial potential functions (contd.); Bushfire algorithm; local minima; Wavefront planners; Lifts of forces and torques from workspace to configuration spaces;   align ="left"  '''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 starworlds;  +  '''Lec 15.''' Artificial potentials in nonEuclidean spaces; navigation functions on sphereworlds; 
+  
+   align ="left"  Choset Chapter 4;  
+  
+  [http://www.cs.cmu.edu/~motionplanning/lecture/Chap4PotentialField_howie.pdf Textbook Slides  Potentials]  
+  
+    
+   align ="left"  Week 9. 17 March  
+   align ="left"  '''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;  
 align ="left"  Choset Chapter 4;   align ="left"  Choset Chapter 4;  
Line 186:  Line 195:  
[http://www.cs.cmu.edu/~motionplanning/lecture/Chap4PotentialField_howie.pdf Textbook Slides  Potentials]  [http://www.cs.cmu.edu/~motionplanning/lecture/Chap4PotentialField_howie.pdf Textbook Slides  Potentials]  
+  [http://www.cs.cmu.edu/~./motionplanning/lecture/Chap6CellDecomp_howie.pdf Textbook Slides  Cell decomposition]  
    
}  } 
Revision as of 07:52, 22 March 2014
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 (2014)
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; 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; 
Schedule (2010)
WEEK  SCHOOL CALENDAR  TOPICS  READINGS/REFERENCES 

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; 
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; wallfollowing behavior with range sensors;  Choset CH 2; LaValle SEC 12.3.3; 
Week 3. September 6  Sept 914. EidulFitr 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; 
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. 
Week 7. October 4  Lec 12. 2D and 3D rigid bodies revisited; rotations and translations of points and bodies; types of joints; kinematic chains; DHparameters;
Lec 13. Introduction to roadmaps; deterministic/combinatorial methods for roadmap construction; general properties; visibility graphs; linesweep algorithm;  LaValle SEC3.3; Choset CH5.  
Week 8. October 11  Lec 14. Voronoi diagrams; generalized Voronoi diagrams (GVD); bushfire 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 bushfire algorithm;  Choset CH4;  
Week 9. October 18  Midterm exams  Lec 16. Introduction to navigation functions; navigation functions for the sphereshaped world; compositions of potentials; analytical switches; empirical tuning of navigation functions;
Lec 17. Starshaped 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 roadmaps algorithm (PRM); query phase of PRM; Tutorial. Using the MATLAB robotics toolbox. (Oct 29)  Choset SEC3.8, SEC4.7, CH 7;  
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 nonEuclidean spaces; metric spaces and Lpnorms 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; discretetime linear models from equations of motion; examples; process noise and sensor noise; Objectives of Kalman filtering;  Choset CH7, CH8; 
Week 14. November 15  EidulAzha holidays. Nov 1719.  
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 nonGaussian 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; nonlinear models of sensing and robot motion; Extended Kalman filtering; Lec 26. Nonlinear transformations of random variables; generation of nonGaussian noise via nonlinear transforms; modeling sensor noise; ultrasound, laser models and other nonGaussian 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 915. Final Exams 
Lec 27. Wrapup. Future directions. Take home Exam. Due December 7th.
 
Week 18. December 13  Dec 1617. Ashura Holidays;
Dec 27. Final grades submission; Dec 20Jan 21 Semester break.  Project Presentations/Viva/Demo 1. Dec 14th
Project Presentations/Viva/Demo 2. Dec 15th
