Motion Planning with Graphs of Convex Sets
1 study materials · 4 sections
This course explores the Graphs of Convex Sets (GCS) framework, a revolutionary approach to motion planning that unifies discrete graph search with continuous trajectory optimization. It addresses the fundamental challenge of navigating complex environments by decomposing configuration space into overlapping convex regions. Students will learn how to formulate motion planning as a convex optimization problem, providing global optimality and dynamic feasibility without the computational burden of traditional mixed-integer programming.
Course Sections
The Gap Between Discrete and Continuous Planning
Key concepts: Combinatorial Optimization · Trajectory Optimization · Local Minima · Completeness
An analysis of the traditional divide between combinatorial graph search and continuous trajectory optimization.
The GCS Mathematical Framework
Key concepts: Convex Decomposition · Perspective Functions · Mixed-Integer Programming · Convex Hull
Introduction to the core mechanics of Graphs of Convex Sets, including convex decomposition and the shortest path formulation.
Convex Relaxations and Tightness
Key concepts: Convex Relaxation · Integrality Gap · Strong Formulations · Dual Problems
Deep dive into why GCS is computationally efficient and how it avoids the exponential complexity of traditional solvers.
Applications and Performance in Robotics
Key concepts: Dynamic Feasibility · UAV Navigation · Manipulator Planning · Footstep Planning
Practical demonstrations of GCS applied to UAVs, robotic arms, and walking robots.
Source Materials
Study Motion Planning with Graphs of Convex Sets on Lykke
This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.
Add the free extensionSign in to open every section