russtedrake PRO
Roboticist at MIT and TRI
Russ Tedrake
CMU Robotics Institute Seminar
Jan 27, 2023
Slides available live at https://slides.com/d/Dqc6oN4/live
or later at https://slides.com/russtedrake/2023-cmu-ri
Shortest Paths in Graphs of Convex Sets.
Tobia Marcucci, Jack Umenberger, Pablo Parrilo, Russ Tedrake.
Available at: https://arxiv.org/abs/2101.11565
Motion Planning around Obstacles with Convex Optimization.
Tobia Marcucci, Mark Petersen, David von Wrangel, Russ Tedrake.
Available at: https://arxiv.org/abs/2205.04422
start
goal
Two aspects of the motion planning problem:
start
goal
The Probabilistic Roadmap (PRM)
from Choset, Howie M., et al. Principles of robot motion: theory, algorithms, and implementation. MIT press, 2005.
Efficient algorithms for (approximate) global optimization-based planning for manipulators with dynamic constraints
image credit: James Kuffner
Trajectory optimization
Sample-based planning
AI-style logical planning
Combinatorial optimization
Default playback at .25x
The Probabilistic Roadmap (PRM)
from Choset, Howie M., et al. Principles of robot motion: theory, algorithms, and implementation. MIT press, 2005.
Kinematic Trajectory Optimization
(for robot arms)
start
goal
fixed number of samples
collision-avoidance
(outside the \(L^1\) ball)
nonconvex
goal
start
disjunctive
constraints
"Convex relaxation" replaces this with:
"Mixed-integer convex" iff \(f\) and \(g\) are convex.
Convex relaxation is "tight" when the relaxed solution is a solution to the original problem.
Convex relaxations provide lower bounds
Feasible solutions provide upper bounds
convex
convex
convex
convex
convex
\(\Rightarrow\) Long solve times.
This is the convex relaxation
(it is very loose!).
"We know that the LP formulation of the shortest path problem is tight. Why exactly are your relaxations so loose?"
\(\varphi_{ij} = 1\) if the edge \((i,j)\) in shortest path, otherwise \(\varphi_{ij} = 0.\)
\(c_{ij} \) is the (constant) length of edge \((i,j).\)
"flow constraints"
binary relaxation
path length
Note: The blue regions are not obstacles.
Classic shortest path LP
now w/ Convex Sets
Non-negative scaling of a convex set is still convex (e.g. via "perspective functions")
Achieved orders of magnitude speedups.
Conservation of flow
Spatial conservation of flow
(this was the missing constraint!)
start
goal
This is the convex relaxation
(it is tight!).
is the convex relaxation. (it's tight!)
Previous formulations were intractable; would have required \( 6.25 \times 10^6\) binaries.
Previous best formulations | New formulation | |
---|---|---|
Lower Bound (from convex relaxation) |
7% of MICP | 80% of MICP |
Formulating motion planning with differential constraints as a Graph of Convex Sets (GCS)
+ time-rescaling
duration
path length
path "energy"
note: not just at samples
continuous derivatives
collision avoidance
velocity constraints
minimum distance
minimum time
Transcription to a mixed-integer convex program, but with a very tight convex relaxation.
IRIS (Fast approximate convex segmentation). Deits and Tedrake, 2014
WAFR 2022;
Journal version out this month.
Solve using rational polynomial kinematics
The separating plane (green) is the non-collision certificate between the two highlighted polytopic collision geometries (red), with a distance of 7.3mm.
Graph of Convex Sets (GCS)
PRM
PRM w/ short-cutting
Preprocessor now makes easy optimizations fast!
with Tommy Cohn, Mark Petersen, and Max Simchowitz
I've focused today on Graphs of convex sets (GCS) for motion planning
GCS is a more general modeling framework
GCS version (top down)
Prelimary results by Savva Morozov
This is version 0.1 of a new framework.
There is much more to do, for example:
by Tobia Marcucci in collaboration w/ Stephen Boyd
Give it a try:
pip install drake
sudo apt install drake
Trajectory optimization
Sample-based planning
AI-style logical planning
Combinatorial optimization
http://manipulation.mit.edu
http://underactuated.mit.edu
Shortest Paths in Graphs of Convex Sets.
Tobia Marcucci, Jack Umenberger, Pablo Parrilo, Russ Tedrake.
Available at: https://arxiv.org/abs/2101.11565
Motion Planning around Obstacles with Convex Optimization.
Tobia Marcucci, Mark Petersen, David von Wrangel, Russ Tedrake.
Available at: https://arxiv.org/abs/2205.04422
By russtedrake
CMU RI Seminar