Date 
Topic 
Reading Assignment 
Jan. 19 
General course overview 

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 introductorylevel 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, angleaxis parameterization of rotations,
quaternions 
 In addition to the readings for previous lectures, Appendix E of [Choset]
covers this material.
 A derivation of the axisangle 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.14.4 of [Choset],
Secs. 5.15.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: NonEuclidean spaces 
 This material is covered in Sec. 4.7 of [Choset],
Secs. 5.15.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 samplingbased
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 samplingbased planners 
 This material is covered in Section 7.1.3 [Choset] and Section 5.6 of [LaValle].

Mar. 15 
Rapidly Exploring Random Trees (RRTs)
ExpansiveSpace 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
ICollide.
You can read more about ICollide, and many other collision detection packages, at the UNC
website for collision detecion and query processing.

Apr. 5 
No Class 

Apr. 7 
The GilbertJohnsonKeerthi algorithm to compute the distance
between polytopes

 The GJK algorithm is described in their
JRA paper.

Apr. 12 
A deeper look at why samplingbased methods work:
(ε,α,β)Expansiveness 
 This material is covered in Section 7.4.2 of [Choset].

Apr. 14 
Optimal samplingbased methods: PRM*

 The algorithms PRM* and RRT* are described in an
IJRR article
by Karaman and Frazzoli.

Apr. 19 
Optimal samplingbased methods (Part 2): properties of PRM*, including
convergence proofs


Apr. 21 
Optimal samplingbased methods (Part 3):
A brief overview of random graphs and percolation theory;
RRT*.


Apr. 26 
Programming assignment discussion 

Apr. 28 
Samplingbased methods for feedback control design. 

May 3 
Samplingbased methods for feedback control design. 
