Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets
Thomas Cohn, Mark Petersen, Max Simchowitz, Russ Tedrake
Abstract
Computing optimal, collision-free trajectories for high-dimensional systems is a challenging problem.Samplingbased 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 mixedinteger 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.