Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets

Thomas B Cohn
Massachusetts Institute of Technology
Mark Petersen
Harvard University
Max Simchowitz
Massachusetts Institute of Technology
Russ Tedrake
Massachusetts Institute of Technology
Paper Website

Paper ID 57

Nominated for Best Paper

Session 8. Robot Planning

Poster Session Wednesday, July 12

Poster 25

Abstract: Computing optimal, collision-free trajectories for high-dimensional systems is a challenging problem. Sampling-based planners struggle with the dimensionality, whereas trajectory optimizers may get stuck in local minima due to inherent nonconvexities in the optimization landscape. The use of mixed-integer programming to encapsulate these nonconvexities and find globally optimal trajectories has recently shown great promise, thanks in part to tight convex relaxations and efficient approximation strategies that greatly reduce runtimes. These approaches were previously limited to Euclidean configuration spaces, precluding their use with mobile bases or continuous revolute joints. In this paper, we handle such scenarios by modeling configuration spaces as Riemannian manifolds, and we describe a reduction procedure for the zero-curvature case to a mixed-integer convex optimization problem. We demonstrate our results on various robot platforms, including producing efficient collision-free trajectories for a PR2 bimanual mobile manipulator.