Topic Reading Assignment
BUG Algorithms
  • BUG1 (algorithm, bounds on path lengths)
  • BUG2 (algorithm, bounds on path lengths)
    		•  Chapter 2
    Configuration Space
  • General concepts about the geometry and topology of configuration spaces
  • Collision tests for polygons in the plane
  • configuration space obstacles for Q = R^2
  • SO(n), SE(n)
  • Charts and atlasses
  • Quaternions
    		• Chapter 3, Appendix E, Appendix F
    Artificial Potential Fields
  • Potential functions and their gradients in Euclidean spaces
  • Gradient descent algorithms
  • Potential functions for noneuclidean spaces.
  • Numerical navigation functions
  • Continuous navigation functions
    		• Chapter 4
    Roadmap algorithms
  • Visibility graph  
  • Retracts and deformation retracts
  • the Voronoi diagram and the generalized Voronoi diagram for Q = R^2
  • The generalized Voronoi diagram in R^n, the generalized Voronoi graph
  • Canny's Silhouette method
    		• Chapter 5  
    Sampling-based methods
  • The basic Probabilistic Roadmap Planner (PRM)
  • Analysis of PRMs
  • Gaussian sampling
  • obstacle-based sampling
  • Manipulability-based sampling
  • Visibility PRM
  • Rapidly-exploring Random Trees (RRTs)
  • Expansive-Space Trees (ESTs)
    		• Chapter 7, Chapter 5 of Steve LaValle's book