Robot Motion Planning and Control (Mech 450, Fall 2018, Lehigh U.)
Nov 15, 2018
Catalog Description: This course will start with an introduction to the configuration spaces and kinematics of different robotic systems, including holonomic & non-holonomic mobile robots, spatial robots, and robotic manipulators. Following that basic motion planning algorithms, including potential & navigation function-based motion planning and graph search based motion planning, will be introduced. Sensor-based motion planning and motion planning under uncertainties using probabilistic representations will be introduced. Students will learn about estimation and filtering (Kalman filter, Markov filter, particle filters) and probabilistic robot action models (Markov chains, Markov decision processes, POMDP). Students will get hands-on experience in implementing the algorithms on MATLAB/C++. Application to multi-robot coordination problems, multi-robot coverage problems, pursuit-evasion problems, task allocation problems and exploration problems will be discussed. If time permits, students will be briefly introduced to topological motion planning, motion planning on manifolds and motion planning on flow fields. The evaluation will be based on two term projects and a final presentation.
Course Site:
Course Documents:
Course Schedule:
The list of topics in the schedule below is tentative and is subject to change. The list will be updated after every lecture.
08/28 (Tuesday): Lecture 1
Introduction to robot motion planning and control: the big picture.
Introduction
to the configuration spaces of robotic systems (mobile robots, robotic manipulators, etc).
Configuration space of rigid bodies: Introduction to Special orthogonal, SO(2), and Special Euclidean, SE(2), groups.
08/30 (Thursday): Lecture 2
Continued discussion on configuration spaces: Space of spatial orientations and poses: SO(3) and SE(3).
Basics of coordinate representation, coordinate chart and atlas. Coordinate transformation.
Introduction to kinematics: Holonomic and non-holonomic systems.
09/04 (Tuesday): Lecture 3
Revisit coordinate transformation: Jacobian matrix.
Forward and inverse kinematics.
Introduction to vector-field based robot navigation and goal-directed path planning / motion control.
09/06 (Thursday): Lecture 4
Introduction to vector fields on a plane: Types of critical points / singularities; Jacobian and degree of critical points; Poincare-hopf theorem for such vector fields.
Review and discussion of papers by Khosla, et al., and Rimon, et al.
09/11 (Tuesday): Lecture 5
Identifying domains of attraction of stable equilibrium: LaSalle's principle, Lyapunov function candidate; Review and discussion of paper by Heish, et al.
Introduction to graph-based discrete representation of configuration space, Introduction to Dijkstra's search.
09/13 (Thursday): Lecture 6
Continued discussion on graph search algorithm -- Dijkstra's and A*, heuristic functions, weighted A*; Discussed 4- and 8-connected grid world representations and admissible heuristic functions on them; Introduction to D* Lite.
09/18 (Tuesday): Lecture 7
Continued discussion on graph search algorithm -- review of search algorithms Dijkstra's, A* and D* Lite. Discussed papers on lattice graph (Pivtoraiko, et al.) and task graph (Bhattacharya et al.).
09/20 (Thursday): Lecture 8
Highlighted the required format of input graph to search algorithms (vertex type, graph connectivity); Discussed DOSL library and example programs (bare-bones, 2d planar domain, robot arm, multi-start search for Voronoi partitioning).
Started discussion on probabilistic robotics -- grid-based representation and localization of obstacle; Bayesian inference, measurement/sensor model, prior, normalization (to be continued later).
09/25 (Tuesday): Lecture 9
Revisit path planning -- MIQP and QP+safe corridor formulations for smooth path generation. Reviewed papers by Mellinger, et al. and Liu, et al.
09/27 (Thursday): Lecture 10
Kalman Filter introduction -- motivation, mathematical foundation, application. Reviewed paper by Jun, et al.
10/11 (Thursday): Lecture 11
Markov chain, Hidden Markov Model -- motivation (as a generalization of Kalman filter) and mathematical foundation.
10/16 (Tuesday): Lecture 12
Completed discussion on HMM and reviewed paper by Song, et al. Introduction to Markov Decision Process.
10/18 (Thursday): Lecture 13
Completed discussion on MDP and reviewed paper by Burlet et al.
10/23 (Tuesday): Lecture 14
Introduction to coverage control on convex domains -- coverage functional, Voronoi partition and derivation of controller; Reviewed papers by Cortes, et al. and Pimenta et. al.
10/25 (Thursday): Lecture 15
Review of coverage control; Generaliation of distance functions -- power distance, power Voronoi diagram; Geodesic distance. Reviewed paper by Pimenta et. al.
10/30 (Tuesday): Lecture 16
Review of coverage control -- geodesic distance on planar domain with obstacles, gradient of distance function on planar domain with obstacles; Further generaliation of distance functions -- Riemannian metric tensor, distance on manifolds, gradeient of distance function.
11/01 (Thursday): Lecture 17
Review of covarient/contravarient vectors and tensors; Riemannian metric tensors, distance function and relationship between gradient of distance function and tangent to shortest path; wave-front based algorithm for computing voronoi tesselation and coverage control on a manifold -- Review of paper by Bhattachaya et al.
11/06 (Tuesday): Lecture 18
Introduction to sensor coverage with sensors with finite sensing radius -- sensing and communication graph; Description of graph in terms of incidence/boundary matrix, definition "equivalence classes" of vertices based on difference by boundary of paths, interpretation of image of he boundary map, the set of classes as the quotient space of vector space spanned by the vertex vectors and the image of the boundary matrix, and interpretation of the independent directions in that quotient space as the connected components of the graph; Definition of Laplacian matrix for computing the quotient space.
11/08 (Thursday): Lecture 19
Review of equivalence and classification of vertices in graph based on connected components, linear algebra on the vector spaces spanned by the vertices & edges using the boundary map, Laplacian matrix; Introduction to simplicial complexes, generalization of boundary maps in higher dimensions, equivalence classes of cycles and homology computation as the quotient of kernel by image of boundary maps; Definitions: Chain complex, homology groups, generalized Laplacians.
11/13 (Tuesday): Lecture 20
Review of chain complexes, homology, and its interpretations; Example of an explicit computation using Matlab, brief comments about pesistent algorithms; Cech complex of sensor coverage -- the role of communication radius for detrmining n-way overlap; Discussion of paper by Derenick, et al.; Generalization of Cech complex to arbitrary cover, "good cover", Nerve theorem;