Russ Tedrake
Mark Petersen
David von Wrangel
Bernhard Græsdal
Boyuan Chen
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
Default playback at .25x
Graph of Convex Sets (GCS)
PRM
PRM w/ short-cutting
Preprocessor now makes easy optimizations fast!
Kinematic Trajectory Optimization
(for robot arms)
Note: The blue regions are not obstacles.
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.
Formulating motion planning with differential constraints as a Graph of Convex Sets (GCS)
+ time-rescaling
minimum distance
minimum time
Transcription to a mixed-integer convex program, but with a very tight convex relaxation.
The Probabilistic Roadmap (PRM)
from Choset, Howie M., et al. Principles of robot motion: theory, algorithms, and implementation. MIT press, 2005.
JBT has said "people like RRT as being cognitively relevant". The connection to graph search seems more natural to me?
LPK + TLP -- for TAMP, this motion planner says "yes" or "no" (compared to "yes" or "maybe, if you draw more samples")