16-811: Math Fundamentals for Robotics, Fall 2024

Professor:   Michael Erdmann (me51).
Teaching Assistants:   Diana Frias Franco  (dfriasfr),  Mark Lee  (moonyoul),  Willa Potosnak  (wpotosna),  Huy Quyen Ngo  (huyquyen).
Emails:      AndrewID -at- andrew.cmu.edu (with "AndrewID" shown in parentheses above).
Location: HOA 160 (Hall of the Arts, near Posner)
Time: TR 2:00-3:20pm

Michael Erdmann's Office Hours: Prefer after class (or by appointment, office is GHC 9203).
TA Office hours: Please see Piazza.

Assignments

Lecture Synopses

Topics

1. Solution of Linear Equations.

2. Polynomial Interpolation and Approximation.

3. Solution of Nonlinear Equations.

4. Roots of Polynomials, Resultants.

5. Approximation by Orthogonal Functions (includes Fourier series).

6. Integration of Ordinary Differential Equations.

7. Optimization.

8. Calculus of Variations (with applications to Mechanics).

9. Probability and Stochastic Processes (Markov chains).

10. Computational Geometry.

11. Differential Geometry.

Course Activity

This is a graduate course. You are thus expected to pursue ideas and topics discussed in this course on your own beyond the level of the lectures. My aim is to cover some of the easy early material quickly, then spend more detailed time on the later material. My goal throughout the course is to acquaint you with fundamental algorithms and mathematical reasoning, as well as give you some implementation experience.

The course grade will be determined by performance on assignments and participation in class. Class assignments will entail solving some problems on paper or implementing some of the algorithms discussed in the course.

Course Goals

• Understand the geometry of linear systems of equations, including null spaces, row spaces and column spaces. Understand eigenvalues, diagonalization, singular value decomposition, least-squares solutions. Apply these skills to infer rigid-body transformations from data.
• Learn how to model data using interpolation, linear regression, and higher-order approximation methods. Apply these skills to recognize objects from point-cloud data.
• Understand different methods for finding roots of equations, in one dimension and higher, including bisection, Newton's method, Müller's method. Develop skills to analyze convergence rates.
• Generalize finite-dimensional linear algebra concepts such as orthogonal bases to perform function approximation, including using Legendre polynomials and Fourier series to compute least-squares approximations. Learn about different function norms.
• Develop techniques for solving differential equations numerically.
• Understand optimization techniques such as gradient descent, conjugate gradient, Newton's method. Learn the basics of convex optimization. Implement obstacle-avoidance viewed as cost-minimization.
• Develop methods from the Calculus of Variations for higher-order optimization. Understand the Principle of Least Action. Apply these techniques to develop the Lagrangian dynamics of a robot manipulator.
• Learn basic computational geometry techniques, such as Convex Hull and Voronoi diagrams. Implement a geometric robot motion planner.
• Understand Markov chains from the perspective of eigenvalues and matrix representations.
• Understand basic constructs of Differential Geometry, in particular curvature and torsion of curves, along with the Frenet formulas.

Grading

In order to pass this course you must do all the work required. "Doing all the work" entails attending class and submitting solutions for every problem on every assignment.

You must submit a reasonable attempt at a solution for every problem on an assignment by that assignment's due date. Assignment problems are graded on a "minus/check" scale. Numerically, in Gradescope you will see a 0 or 1 (sometimes we may award a partial point for a problem).

If you receive less than a "1" on any problem, you may resubmit a correct solution for that problem by the resubmission deadline for the assignment, if the assignment has a resubmission deadline. You can learn from the feedback provided after your first submission, improve your submission, with the goal of raising your point score to a "1". (The resubmission deadline is not an alternate deadline for the original assignment; you need to attempt every problem by the original deadline.)

We expect that there will be 6 assignments this semester. The first 5 assignments will have resubmission deadlines. The last assignment will not have an opportunity for resubmission. Instead, the last assignment will consist of some implementations, and you will know yourself whether you have completed the assignment correctly.

There are no "grace" or "late days" for submissions. Hand in assignments on time.

Assuming you attend class and try every problem as required, grades in the course will be determined by the total number of points you receive for all six assignments combined. In order to get an "A", you need to accumulate at least 90% of the possible points. The cutoff for a "B" will be 75% of the possible points. The cutoff for a "C" will be 60% of the possible points.

Note Taking

Research has shown that taking notes, by hand, using a pen or pencil is a vital part of learning for most students. Taking notes on a laptop is a poor substitute. In fact, research has shown that you are better off taking notes by hand and then throwing those notes away, than taking notes on a laptop. It seems that the act of processing material into handwritten notes involves the parts of the brain responsible for learning, while the act of transcribing class material on a laptop largely bypasses those parts. You can learn about this research, which some people find counterintuitive, here.

Bibliography

1. W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. Numerical Recipes in C. Cambridge University Press. (Any edition.)

2. G. Strang. Introduction to Applied Mathematics. Wellesley-Cambridge Press. 1986.

3. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press. 1983.

4. S. D. Conte and C. de Boor. Elementary Numerical Analysis. Third edition. McGraw-Hill. 1980.

5. G. E. Forsythe, M. A. Malcolm, and C. B. Moler. Computer Methods for Mathematical Computations. Prentice-Hall. 1977.

6. D. G. Luenberger. Introduction to Linear and Nonlinear Programming. Addison-Wesley. 1973.

7. R. Weinstock. Calculus of Variations. Dover Publications. 1974. (Reprint of 1952 McGraw-Hill edition.)

8. R. Courant and D. Hilbert. Methods of Mathematical Physics. Volume I. John Wiley and Sons. 1989. (Reprint of 1953 Interscience edition.)

9. W. Yourgrau and S. Madelstam. Variational Principles in Dynamics and Quantum Theory. Dover Publications. 1979. (Reprint of a 1968 edition.)

10. F. P. Preparata and M. I. Shamos, Computational Geometry, Springer-Verlag, New York, 1985. (Corrected and expanded printing: 1988.)

11. J.-C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, Boston, 1991.

12. W. Feller. An Introduction to Probability Theory and Its Applications. Volume 1. Third edition. John Wiley and Sons. 1968.

13. B. O'Neill, Elementary Differential Geometry, Academic Press, New York, 1966. 2nd Edition: 1997.

Note to Students

Take care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often helpful.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit their website at https://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty, or family member you trust for help getting connected to the support that can help.

If you or someone you know is feeling suicidal or in danger of self-harm, call someone immediately, day or night:

CaPS: 412-268-2922
Resolve Crisis Network: 888-796-8226
If the situation is life threatening, call the police:
On campus: CMU Police: 412-268-2323
Off campus: 911

Use of Recording Devices

Please do not record lectures or take images of the professor. University policy on this matter suggests the following formal statement:

No student may record any classroom activity without express written consent from the professor. If you have (or think you may have) a disability such that you need to record or tape classroom activities, you should contact the Office of Equal Opportunity Services, Disability Resources to request an appropriate accommodation.