ECE 550
Advanced Robotic Planning    

      University of Illinois at Urbana-Champaign


Reading assignments should be completed before the lecture for which they are assigned.
References are abbreviated as listed on the Resources Page for the course.

Date Topic Reading Assignment  
Jan. 19 General course overview  
  • [Choset] Chapter 1
Jan. 21 Configuration space and configuration space obstacles; Methods for polygonal robots that translate in the plane: visibility graph, cell decomposition, generalized Voronoi diagram.
  • The concept of configuration spaces is introduced in Chapter 3 of [Choset], Chapter 2 of [Latombe], Chapter 4 of [LaValle]. The level of mathematical treatment, and the number of examples, varies considerably among these references.
  • Visibility graphs are introduced in Section 5.1 of [Choset], Section 4.1 of [Latombe], and Section 6.2.4 of [LaValle].
  • The generalized Voronoi diagrams is introduced in Section 5.2 of [Choset], Section 4.2 of [Latombe], and Section 6.2.3 of [LaValle].
  • Cell decomposition for polygonal configuration spaces (i.e., trapezoidal decomposition) is introduced in Section 6.1 of [Choset], Section 5.1 of [Latombe], and Section 6.3 of [LaValle].
Jan. 26 Rigid motions, SO(n), SE(n)  
  • This material is covered in Chap. 3 of [Choset].
  • An introductory-level presentation is given in Chap. 2 of [SHV].
  • A treatment of SO(n) as a manifold is given in Chap. 2 of [Latombe].
  • A general treatment, including exponential coordinates for rotation, is given in Chap. 2 of [MLS].
  • An introduction to SO(2) and SO(3), along with some nice examples, is given in Chapter 3 of [LaValle].
Jan. 28 Basic concepts in topology and differentiable manifolds I: metrics, open sets, induced topology, homeomorphism, diffeomorphism, manifolds, the implicit function theorem.
  • This material is covered in Chapter 3 of [Choset], Chapter 3 of [Latombe], and Sections 4.1 and 4.2 of [LaValle], which is thorough and accessible, wish several general examples.
Feb. 2 Basic concepts in topology and differentiable manifolds II: SO(2) revisited, charts and atlases, differentiable manifolds, charts and atlases for SO(n).
  • This material is covered in Chapter 3 of [Choset], Chapter 3 of [Latombe], and Sections 4.1 and 4.2 of [LaValle], which is thorough and accessible, wish several general examples.
Feb. 4 Similarity transformations, angle-axis parameterization of rotations, quaternions
  • In addition to the readings for previous lectures, Appendix E of [Choset] covers this material.
  • A derivation of the axis-angle parameterization using similarity transformations is given in Chap. 2 of [SHV].
Feb. 9 Path planning using potential functions: Euclidean spaces
  • This material is covered in Secs. 4.1-4.4 of [Choset], Secs. 5.1-5.3 of [SHV], and Sec. 7.1 of [Latombe].
Feb. 11 Open Lab for ROS debugging, ECEB 3071  
Feb. 16 Path planning using potential functions: Navigation Functions
  • This material is covered in Sec. 4.6 of [Choset].
Feb. 18 CSL Student Conference, No Class  
Feb. 23 Numerical navigation functions
  • This material is covered Sections 4.3 and 4.5 in [Choset] and Section 4.2 of [Latombe].
Feb. 25 Path planning using potential functions: Non-Euclidean spaces
  • This material is covered in Sec. 4.7 of [Choset], Secs. 5.1-5.3 of [SHV], and Sec. 7.2 of [Latombe].
Mar. 1 Randomized Path Planner (RPP), Introduction to PRMs
  • Section 5.4.3 of [LaValle] describes RPP.
Mar. 3 Probabilistic Roadmap Planner (PRM)
  • PRM is introduced d in Section 7.1 of [Choset].
  • Section 5.4 of [LaValle] gives a good overview of sampling-based planners and various implementation issues, and Section 5.6 describes the basic PRM algorithm.
Mar. 8 Probabilistic completeness of PRM
  • A proof that PRM is probabilistically complete is given in Section 7.4.1 of [Choset].
  • A discussion of various notions of completeness is given in the begining of Chap. 5 of [LaValle].
Mar. 10 Variations on sampling-based planners
  • This material is covered in Section 7.1.3 [Choset] and Section 5.6 of [LaValle].
Mar. 15 Rapidly Exploring Random Trees (RRTs) Expansive-Space Trees (ESTs)
  • Section 5.5 of [LaValle] covers this material very well.
  • This material is also covered in Section 7.2 in [Choset].
Mar. 17 No Class (due to Midwest Robotics Workshop)  
Mar. 22 SPRING BREAK -- NO CLASS    
Mar. 24 SPRING BREAK -- NO CLASS    
Mar. 29 Quasirandom sampling, discrepancy, dispersion
  • Section 5.2 of [LaValle] gives a good coverage of this material.
  • This material is also covered in Section 7.1.3 of [Choset].
Mar. 31 Collision detection
  • An overview of collision detection is given in Section 5.3 of [LaValle].
  • FCL is described in this ICRA Paper.
  • Temporal and geometric coherence, along with the idea of using Voronoi regions to prune the set of feature tests, are included in I-Collide. You can read more about I-Collide, and many other collision detection packages, at the UNC website for collision detecion and query processing.
Apr. 5 No Class  
Apr. 7 The Gilbert-Johnson-Keerthi algorithm to compute the distance between polytopes
Apr. 12 A deeper look at why sampling-based methods work: (ε,α,β)-Expansiveness
  • This material is covered in Section 7.4.2 of [Choset].
Apr. 14 Optimal sampling-based methods: PRM*
  • The algorithms PRM* and RRT* are described in an IJRR article by Karaman and Frazzoli.
Apr. 19 Optimal sampling-based methods (Part 2): properties of PRM*, including convergence proofs
Apr. 21 Optimal sampling-based methods (Part 3): A brief overview of random graphs and percolation theory; RRT*.
Apr. 26 Programming assignment discussion  
Apr. 28 Sampling-based methods for feedback control design.
May 3 Sampling-based methods for feedback control design.