CMPE633
From CYPHYNETS
Current revision (15:36, 30 March 2012) (view source) 

(112 intermediate revisions not shown.)  
Line 1:  Line 1:  
{ cellspacing=5 cellpadding=5 border=0 width=100%  { cellspacing=5 cellpadding=5 border=0 width=100%  
 style="background:#e0e0ff; color:black; fontsize:18px; mozborderradius:8px;"   style="background:#e0e0ff; color:black; fontsize:18px; mozborderradius:8px;"  
  ! width="75%" colspan="2"  CMPE  +  ! width="75%" colspan="2"  CMPE633A/CS633: Robot Motion Planning 
+    
+   style="background:#e0e0ff; color:black; fontsize:18px; mozborderradius:8px;"  
+  ! width="75%" colspan="2"  Fall 2010  
+    
}  }  
__NOTOC__  __NOTOC__  
  
== Instructor ==  == Instructor ==  
  [[Image:  +  [[Image:choset_book.jpgright200px]] 
+  [[Image:lavalle_book.jpgright200px]]  
+  [[Image:thurn_book.jpgright200px]]  
Dr [[Abubakr Muhammad]], Assistant Professor of Electrical Engineering  Dr [[Abubakr Muhammad]], Assistant Professor of Electrical Engineering  
Line 13:  Line 18:  
Email: abubakr [at] lums.edu.pk  Email: abubakr [at] lums.edu.pk  
  Office: Room  +  Office: Room 9309A, 3rd Floor, SSE Bldg 
  Office Hours: Mon, Wed:  +  Office Hours: Mon, Wed: 12151300; Tue, Thurs: 11301300 or by appointment. 
+  
+  '''Teaching assistant.''' Talha Manzoor. Room 9309. talha.manzoor [at] lums.edu.pk  
== Course Details ==  == Course Details ==  
Line 27:  Line 34:  
Credits: 3  Credits: 3  
  Elective course for electrical  +  Elective course for electrical engineering, computer engineering and computer science majors 
Course Website: http://cyphynets.lums.edu.pk/index.php/CMPE633  Course Website: http://cyphynets.lums.edu.pk/index.php/CMPE633  
===Course Description===  ===Course Description===  
+  A researchmethods based course to study advanced topics in robotics and control system design with emphasis on field robotics, unmanned aerial and ground vehicles, planning algorithms, autonomous systems, telerobotics, Human Robot Interaction (HRI) and other related areas. The course prepares students to do independent work at the frontiers of robotics and control research.  
+  ===Objectives (this year!)===  
+  * 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  
+  * Control theoretic issues in trajectory planning and sensory feedback.  
+  * Introduce practical applications  
+  
+  This course is NOT about  
+  * Mechatronics or robot building.  
+  * Higherlevel perception and AI.  
===Prerequisites===  ===Prerequisites===  
+  '''Courses'''. CMPE432. Feedback control systems OR CMPE435. Robotics OR By permission of instructor.  
+  
+  '''Corequisites'''. CMPE501. Applied probability 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''' 
+  * [http://www.cs.cmu.edu/~biorobotics/book/ Principles of Robot Motion] by Choset et al. [available as low priced edition]  
+  * [http://planning.cs.uiuc.edu/ Planning Algorithms] by Steve Lavalle. [available as a free legal download]  
+  '''Secondary Texts'''  
+  * [http://robots.stanford.edu/probabilisticrobotics/ Probabilistic Robotics] by Thrun et al.  
+  * Research papers.  
+  ===Grading Scheme===  
+  *Class Participation: 15%  
+  *Assignments: 15%  
+  *Final Exam: 20%  
+  *Project: 50%  
+  ** Proposal. 10%  
+  ** Report. 20%  
+  ** Presentation. 20%  
+  ** Code. 50%  
  ===  +  ===Course Delivery Method=== 
+  '''Lectures.''' Mon, Wed: 10:30am11:30am. 10402. SSE Bldg.  
  +  == Schedule ==  
+  {border="1"  
+  ! WEEK !! SCHOOL CALENDAR !! TOPICS !! READINGS/REFERENCES  
+    
+   align ="left"  Week 1. August 23  
+   align ="left"  Aug 23. Classes begin.  
+   align ="left"  '''Lec 1.''' Introduction; robotics and autonomous systems;  
+  '''Lec 2.''' workspaces; configuration spaces; planning algorithms; bug algorithms; Bug0 and Bug1 algorithms;  
+   align ="left"  Choset CH 1,2;  
  +  [http://robots.stanford.edu/papers/thrun.stanley05.html Stanley, the robot that won the DARPA Grand Challenge]  
  +  [[Media:bugalgos_errata.pdfBug algorithms. Errata from author's website.]]  
  +    
+   align ="left"  Week 2. August 30  
+   align ="left"  Aug 30. Add/drop with full refund  
+   align ="left"  '''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;  
  +  [[Media:cmpe633Hw1.pdfHomework 1]]  
  +  [[Media:cmpe633Hw1solcode.rarMATLAB code solutions]]  
  ===  +   align ="left"  Choset CH 2; [http://planning.cs.uiuc.edu/node618.html LaValle SEC 12.3.3]; 
+    
+   align ="left"  Week 3. September 6  
+   align ="left"  Sept 914. EidulFitr holiday  
+   align ="left"  '''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;  
  *  +  
  +  
  +  
  +  
  +  
  +  
  +  
+   align ="left"  LaValle [http://planning.cs.uiuc.edu/node35.html CH2];  
  +  [[Media:cmpe633_Lec5slides.pdfSlides]]  
  '''  +  [http://optlabserver.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html Dijkstra's algorithm Demo] 
+    
+   align ="left"  Week 4. September 13  
+   align ="left"  Sept 15. Second payment deadline  
+   align ="left"  '''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;  
+   align ="left"  Choset CH3, Appendix F  
+    
+   align ="left"  Week 5. September 20  
+   align ="left"   
+   align ="left"  '''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; 
+  
+  
+   align ="left"  Lavalle [http://planning.cs.uiuc.edu/node161.html SEC4.3.2], [http://planning.cs.uiuc.edu/node91.html SEC3.2];  
+  
+  Choset CH3, Appendex F, E.  
+    
+   align ="left"  Week 6. September 27  
+   align ="left"  October 1. Semester Drop with fee Penalty  
+   align ="left"  '''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);  
+  
+   align ="left"  Lavalle [http://planning.cs.uiuc.edu/node91.html SEC3.2] ,[http://planning.cs.uiuc.edu/node144.html SEC4.2]; Choset CH3, Appendix E;  
+  
+  Gimbal lock problem in Euler Angles. [http://www.youtube.com/watch?v=rrUCBOlJdt4 Video.]  
+  
+  [[Media:quaternions_topology.pdfQuaternions and the topology of SO(3).]]  
+    
+   align ="left"  Week 7. October 4  
+   align ="left"   
+   align ="left"  '''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;  
+  
+  [[Media:cmpe633Hw2.pdfHomework 2]]  
+  
+  [[Media:cmpe633Hw2solcode.rarMATLAB code solutions]]  
+  
+   align ="left"  LaValle [http://planning.cs.uiuc.edu/node105.html SEC3.3]; Choset CH5.  
+    
+   align ="left"  Week 8. October 11  
+   align ="left"   
+   align ="left"  '''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;  
+  
+   align ="left"  Choset CH4;  
+    
+   align ="left"  Week 9. October 18  
+   align ="left"  Midterm exams  
+   align ="left"  '''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;  
+  
+   align ="left"  Choset CH4;  
+    
+   align ="left"  Week 10. October 25  
+   align ="left"   
+   align ="left"  '''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)  
+   align ="left"  Choset SEC3.8, SEC4.7, CH 7;  
+  
+  [[Media:cmpe633roboticstoolbox.zipMATLAB Robotics Toolbox Tutorials]].  
+  
+    
+   align ="left"  Week 12. November 1  
+   align ="left"   
+   align ="left"  Project Proposal Presentations. (Session 1)  
+  
+  Project Proposal Presentations. (Session 2)  
+  
+   align ="left"   
+    
+   align ="left"  Week 13. November 8  
+   align ="left"  Nov 9. Iqbal day;  
+   align ="left"  '''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;  
+  
+   align ="left"  Choset CH7, CH8;  
+  
+  [http://en.wikipedia.org/wiki/Lp_space Lp Norms and Metrics].  
+  
+    
+   align ="left"  Week 14. November 15  
+   align ="left"  EidulAzha holidays. Nov 1719.  
+   align ="left"   
+   align ="left"   
+    
+   align ="left"  Week 15. November 22  
+   align ="left"   
+   align ="left"   
+  '''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;  
+  
+   align ="left"  Thrun CH 2; Choset CH8  
+  
+  
+    
+   align ="left"  Week 16. Novemeber 29  
+   align ="left"   
+   align ="left"   
+  '''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.  
+  
+   align ="left"  Thrun CH 2,3,4; Choset CH8  
+    
+   align ="left"  Week 17. December 6  
+   align ="left"  Dec 8. Last day of classes; Dec 915. Final Exams  
+   align ="left"   
+  '''Lec 27'''. Wrapup. Future directions.  
+  
+  '''Take home Exam.''' Due December 7th.  
+  
+  
+   align ="left"   
+    
+   align ="left"  Week 18. December 13  
+   align ="left"  Dec 1617. Ashura Holidays;  
+  Dec 27. Final grades submission;  
+  Dec 20Jan 21 Semester break.  
+   align ="left"  '''Project Presentations/Viva/Demo 1'''. Dec 14th  
+  '''Project Presentations/Viva/Demo 2'''. Dec 15th  
+  
+  
+  
+   align ="left"   
+    
+  }  
+  
+  ==Project Ideas==  
+  
+  ===Feedback control methods / robot dynamics===  
+  
+  * LQRTrees: Feedback Motion Planning on Randomized Trees. [http://www.roboticsproceedings.org/rss05/p3.pdf Paper.].  
+  
+  * LQGMP: Optimized Path Planning for Robots with Motion Uncertainty and Imperfect State Information [http://www.roboticsproceedings.org/rss06/p17.pdf Paper.] '''Hasan Arshad Nasir, 10060010'''.  
+  
+  * Integrated Planning and Control for Convexbodied Nonholonomic systems using Local Feedback Control Policies [http://www.roboticsproceedings.org/rss02/p08.pdf Paper.]  
+  
+  * Gait Regulation and Feedback on a Robotic Climbing Hexapod [http://www.roboticsproceedings.org/rss02/p13.pdf Paper.]  
+  
+  ===SLAM/Probabilistic robotics===  
+  
+  * Unified Inverse Depth Parametrization for Monocular SLAM [http://www.roboticsproceedings.org/rss02/p11.pdf Paper.]  
+  
+  * MonteCarlo Localization for Mobile Robots with Stereo Vision [http://www.roboticsproceedings.org/rss01/p49.pdf Paper.]  
+  
+  * Probabilistic Terrain Analysis For HighSpeed Desert Driving [http://www.roboticsproceedings.org/rss02/p21.pdf Paper.]  
+  
+  * A Bayesian Approach to Nonlinear Parameter Identification for Rigid Body Dynamics [http://www.roboticsproceedings.org/rss02/p32.pdf Paper.]  
+  
+  * The Iterated Sigma Point Kalman Filter with Applications to Long Range Stereo [http://www.roboticsproceedings.org/rss02/p34.pdf Paper.] '''Ateeq ur Rehman Shaheen, 09060002.'''  
+  
+  * Gaussian Processes for Signal StrengthBased Location Estimation [http://www.roboticsproceedings.org/rss02/p39.pdf Paper.] '''Abdul Rehman Aslam, 09060014.'''  
+  
+  * MapBased Precision Vehicle Localization in Urban Environments [http://www.roboticsproceedings.org/rss03/p16.pdf Paper.] '''Muhammad Salman, 09060016.'''  
+  
+  * Detection of Principal Directions in Unknown Environments for Autonomous Navigation [http://www.roboticsproceedings.org/rss04/p10.pdf Paper.] '''Amer Zaheer, 04030068.'''  
+  
+  * Improving Localization Robustness in Monocular SLAM Using a HighSpeed Camera [http://www.roboticsproceedings.org/rss04/p24.pdf Paper.]  
+  
+  * Mapping Large Loops with a Single HandHeld Camera [http://www.roboticsproceedings.org/rss03/p38.pdf Paper.] '''Rehmat Ullah Khattak, 08060009.'''  
+  
+  * Model Based Vehicle Tracking for Autonomous Driving in Urban Environments [http://www.roboticsproceedings.org/rss04/p23.pdf Paper.] '''Mazher Ahmad, 10060014'''.  
+  
+  * Large Scale Graphbased SLAM using Aerial Images as Prior Information [http://www.roboticsproceedings.org/rss05/p38.pdf Paper.] '''Syed Muhammad Abbas, 10030019.'''  
+  
+  ===Sampling based methods / Roadmaps===  
+  
+  * Incremental Samplingbased Algorithms for Optimal Motion Planning [http://www.roboticsproceedings.org/rss06/p34.pdf Paper.] '''Ibrahim Tariq, 10060016.'''  
+  
+  * Roadmap Based PursuitEvasion and Collision Avoidance [http://www.roboticsproceedings.org/rss01/p34.pdf Paper.] '''Mudassir Khan, 10060013'''.  
+  
+  * Elastic Roadmaps: Globally TaskConsistent Motion for Autonomous Mobile Manipulation in Dynamic Environments [http://www.roboticsproceedings.org/rss02/p36.pdf Paper.] '''Mhequb Hayat, 09060019.'''  
+  
+  * Structural Improvement Filtering Strategy for PRM [http://www.roboticsproceedings.org/rss04/p22.pdf Paper.]  
+  
+  ===Miscellaneous===  
+  
+  * SingleCluster Spectral Graph Partitioning for Robotics Applications [http://www.roboticsproceedings.org/rss01/p35.pdf Paper.]  
+  
+  * Dynamic Maps for LongTerm Operation of Mobile Service Robots [http://www.roboticsproceedings.org/rss01/p03.pdf Paper.]  
+  
+  * Distributed Coverage Control with Sensory Feedback for Networked Robots [http://www.roboticsproceedings.org/rss02/p07.pdf Paper.] '''Muhammad Irfan Riaz, 09060005.'''  
+  
+  * Dubins Traveling Salesperson Problems: novel approximation algorithms [http://www.roboticsproceedings.org/rss02/p38.pdf Paper.]  
+  
+  * Composition of Vector Fields for MultiRobot Manipulation via Caging [http://www.roboticsproceedings.org/rss03/p04.pdf Paper.] '''Nauman Shahid, 10060025.'''  
+  
+  ==Robotics Technology Trends==  
+  [An evolving compilation!]  
+  
+  ===Predictions/Overviews===  
+  * [http://www.scientificamerican.com/article.cfm?id=arobotineveryhome A robot in every home] by Bill Gates (Scientific American Magazine, 2007).  
+  
+  * [http://news.nationalgeographic.com/news/2006/09/060906robots.html A Robot in Every Home by 2020, South Korea Says] (National Geographic Magazine, 2006)  
+  
+  ===Industry Successes===  
+  * Kiva Systems [http://www.kivasystems.com/ Link.]  
+  
+  * iRobot [http://www.irobot.com/ Link.]  
+  
+  * Boston Dynamics [http://www.bostondynamics.com/ Link.]  
+  
+  * KUKA [http://www.kuka.com/ Link.]  
+  
+  * Willow Garage [http://www.willowgarage.com/ Link.]  
+  
+  * Robotics at Honda [Link.]  
+  
+  * Robotics at Kawasaki [Link.]  
+  
+  * Robotics at Seiko Epson [Link.]  
+  
+  * Robotics at Sony [Link.]  
+  
+  * Robotics at TOSY [Link.]  
+  
+  ===New Issues of Ethics and Law in Robotics===  
+  
+  * International Committee for Robot Arms Control [http://www.icrac.co.cc/index.html Link.]  
+  
+  * Isaac Asimov's [http://en.wikipedia.org/wiki/Three_Laws_of_Robotics Three Laws of Robotics].  
+  
+  * Human Robot Interaction [http://www.cs.cmu.edu/~illah/ri899.html HRI]  
+  ===Military Robotics===  
+  
+  * United States Air Force Unmanned Aircraft Systems Flight Plan 20092047 [http://www.govexec.com/pdfs/072309kp1.pdf Report.]  
+  
+  * Unmanned Systems Roadmap 20072032 [http://www.icrac.co.cc/Unmanned%20Systems%20Roadmap.20072032.pdf Report.]  
+  
+  * Report to US Congress: Development and Utilization of Robotics and Unmanned Ground Vehicles [http://www.icrac.co.cc/UGV%2520Congressional%2520Report%20to%20US%20Congress%20%28October%202006%29.pdf Report.]  
+  
+  * Autonomous Vehicles in Support of Naval Operations [http://www.nap.edu/openbook.php?isbn=0309096766 Report.]  
+  
+  ===Videos===  
+  
+  <youtube v="cNZPRsrwumQ" /> 
Current revision
CMPE633A/CS633: Robot Motion Planning  

Fall 2010 
Instructor
Dr Abubakr Muhammad, Assistant Professor of Electrical Engineering
Email: abubakr [at] lums.edu.pk
Office: Room 9309A, 3rd Floor, SSE Bldg
Office Hours: Mon, Wed: 12151300; Tue, Thurs: 11301300 or by appointment.
Teaching assistant. Talha Manzoor. Room 9309. talha.manzoor [at] lums.edu.pk
Course Details
Year: 201011
Semester: Fall
Category: Grad
Credits: 3
Elective course for electrical engineering, computer engineering and computer science majors
Course Website: http://cyphynets.lums.edu.pk/index.php/CMPE633
Course Description
A researchmethods based course to study advanced topics in robotics and control system design with emphasis on field robotics, unmanned aerial and ground vehicles, planning algorithms, autonomous systems, telerobotics, Human Robot Interaction (HRI) and other related areas. The course prepares students to do independent work at the frontiers of robotics and control research.
Objectives (this year!)
 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
 Control theoretic issues in trajectory planning and sensory feedback.
 Introduce practical applications
This course is NOT about
 Mechatronics or robot building.
 Higherlevel perception and AI.
Prerequisites
Courses. CMPE432. Feedback control systems OR CMPE435. Robotics OR By permission of instructor.
Corequisites. CMPE501. Applied probability 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
 Class Participation: 15%
 Assignments: 15%
 Final Exam: 20%
 Project: 50%
 Proposal. 10%
 Report. 20%
 Presentation. 20%
 Code. 50%
Course Delivery Method
Lectures. Mon, Wed: 10:30am11:30am. 10402. SSE Bldg.
Schedule
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

Project Ideas
Feedback control methods / robot dynamics
 LQRTrees: Feedback Motion Planning on Randomized Trees. Paper..
 LQGMP: Optimized Path Planning for Robots with Motion Uncertainty and Imperfect State Information Paper. Hasan Arshad Nasir, 10060010.
 Integrated Planning and Control for Convexbodied 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.
 MonteCarlo Localization for Mobile Robots with Stereo Vision Paper.
 Probabilistic Terrain Analysis For HighSpeed 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 StrengthBased Location Estimation Paper. Abdul Rehman Aslam, 09060014.
 MapBased 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 HighSpeed Camera Paper.
 Mapping Large Loops with a Single HandHeld Camera Paper. Rehmat Ullah Khattak, 08060009.
 Model Based Vehicle Tracking for Autonomous Driving in Urban Environments Paper. Mazher Ahmad, 10060014.
 Large Scale Graphbased SLAM using Aerial Images as Prior Information Paper. Syed Muhammad Abbas, 10030019.
Sampling based methods / Roadmaps
 Incremental Samplingbased Algorithms for Optimal Motion Planning Paper. Ibrahim Tariq, 10060016.
 Roadmap Based PursuitEvasion and Collision Avoidance Paper. Mudassir Khan, 10060013.
 Elastic Roadmaps: Globally TaskConsistent Motion for Autonomous Mobile Manipulation in Dynamic Environments Paper. Mhequb Hayat, 09060019.
 Structural Improvement Filtering Strategy for PRM Paper.
Miscellaneous
 SingleCluster Spectral Graph Partitioning for Robotics Applications Paper.
 Dynamic Maps for LongTerm 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 MultiRobot Manipulation via Caging Paper. Nauman Shahid, 10060025.
Robotics Technology Trends
[An evolving compilation!]
Predictions/Overviews
 A robot in every home by Bill Gates (Scientific American Magazine, 2007).
 A Robot in Every Home by 2020, South Korea Says (National Geographic Magazine, 2006)
Industry Successes
 Kiva Systems Link.
 iRobot Link.
 Boston Dynamics Link.
 KUKA Link.
 Willow Garage Link.
 Robotics at Honda [Link.]
 Robotics at Kawasaki [Link.]
 Robotics at Seiko Epson [Link.]
 Robotics at Sony [Link.]
 Robotics at TOSY [Link.]
New Issues of Ethics and Law in Robotics
 International Committee for Robot Arms Control Link.
 Isaac Asimov's Three Laws of Robotics.
 Human Robot Interaction HRI
Military Robotics
 United States Air Force Unmanned Aircraft Systems Flight Plan 20092047 Report.
 Unmanned Systems Roadmap 20072032 Report.
 Report to US Congress: Development and Utilization of Robotics and Unmanned Ground Vehicles Report.
 Autonomous Vehicles in Support of Naval Operations Report.