6.8210 Spring 2024 Lecture 17: Mixed-discrete (combinatorial) and continuous optimization

This lecture provides a comprehensive and rigorous introduction to mixed-integer convex programming (MICP) for robotics motion planning. The instructor, Russ Tedrake, is a renowned expert in the field, and the content reflects his deep understanding of both theoretical foundations and practical implementation. The lecture is well-structured, starting with a motivating example (obstacle avoidance) and progressively building up to more complex formulations. The explanation of big-M formulations and branch and bound is clear and accessible, even for those new to the topic. The use of live coding demonstrations enhances the learning experience, showing real-world application of the concepts. The lecture also touches on important practical considerations, such as the choice of solvers and the challenges of scaling to larger problems. However, the lecture assumes a solid background in optimization and control, making it less suitable for beginners. Additionally, the discussion of alternative methods like GCS is brief and could be expanded. Overall, this is an excellent resource for graduate students and researchers in robotics and optimization, offering both theoretical depth and practical insights.

The title accurately describes the lecture's focus on mixed-discrete (combinatorial) and continuous optimization, as the content covers these topics in depth.

8/10

Lecture from MIT course 6.8210 by Russ Tedrake, a leading expert in robotics and control. Content is technically rigorous, well-structured, and based on established optimization methods. The lecture is part of a formal academic course, ensuring high reliability.

Markers derived by PSI from the transcript: the creator did not define chapters.

• 00:00Introduction to the lecture and the challenge of combining discrete and continuous optimization.
• 02:00Motivating example: obstacle avoidance as a mixed-discrete continuous problem.
• 05:00Introduction to disjunctive constraints and the need for mixed-integer programming.
• 10:00Explanation of big-M formulation for disjunctive constraints.
• 15:00Discussion of mixed-integer convex programming (MICP) and its solvers.
• 20:00Branch and bound algorithm for solving MICP problems.
• 30:00Alternative approach: graph-based convex optimization (GCS).
• 40:00Mixed-integer quadratic programming (MIQP) for trajectory optimization.
• 50:00Practical challenges and future directions in mixed-integer optimization for robotics.

• Drake: A model-based design tool for robotics — Mentioned as the software framework used for the examples and collision checking.
• Gurobi Optimizer — Mentioned as a powerful mixed-integer programming solver used in the lecture.
• Mosek — Mentioned as a solver for convex optimization problems.
• SNOPT — Mentioned as a solver for nonlinear optimization problems.

• Drake: A model-based design tool for robotics — The lecture uses Drake for examples and collision checking, and the tool is widely used in robotics research.
• Gurobi Optimizer — Gurobi is a leading solver for mixed-integer programming, consistent with the lecture's recommendation.