Session: Optimization on Manifolds
Chair: Christopher Criscitiello
Cluster: Optimization on Manifolds
Talk 1: Estimation of barycenters in convex domains of metric spaces
Speaker: Victor-Emmanuel Brunel
Abstract: In this talk, we study the statistical and algorithmic aspects of barycenter estimation in convex domains of metric spaces. For data that lie in a non-linear metric space, such as a sphere, barycenters are the natural extension of means, and their estimation is a fundamental statistical problem. Here, we assume that the space satisfies a curvature upper bound in Alexandrov’s sense: Then, barycenters are minimizers of geodesically convex functions, yielding good statistical and algorithmic guarantees.
Talk 2: Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets
Speaker: Thomas Cohn
Abstract: Mathematical optimization is a central tool for planning efficient, collision-free trajectories for robots. However, such trajectory optimization methods 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. One such tool is the Graph of Convex Sets framework, which yields tight convex relaxations and efficient approximation strategies that greatly reduce runtimes. These approaches were previously limited to Euclidean configuration spaces, but many robotic configuration spaces of interest are best represented as smooth manifolds. We introduce Graphs of Geodesically-Convex Sets, the natural generalization of GCS to Riemannian manifolds. We leverage a notion of "local" geodesic convexity to avoid the limitations that would otherwise arise from compact manifolds and closed geodesics, which often arise in robot configuration spaces. We demonstrate that this optimization framework encompasses the motion planning problems of interest, and examine when it can and cannot be solved efficiently. In the case of zero-curvature, we are able to reduce the problem to a mixed-integer convex program that can be solved efficiently. On the other hand, positive curvature makes the Riemannian distance function not even locally convex. In the general case, we describe a piecewise-linear approximation strategy to obtain approximate solutions to shortest path problems on manifolds of arbitrary curvature. We also specifically compare different parametrizations of the Lie groups SO(3) and SE(3). We present experiments demonstrating our methodology on various robot platforms, including producing efficient collision-free trajectories for a PR2 bimanual mobile manipulator.
Talk 3: Leveraging Manifold Structure for Fast Algorithms
Speaker: Brighton Ancelin
Abstract: In today's data-driven world, many problems require the processing of high-dimensional data. Methods like Principal Component Analysis (PCA) may help reduce the dimensionality of such problems, but may be ineffective or inefficient when data lies on non-linear manifolds. Some common manifolds even exhibit a natural Euclidean embedding dimension that far exceeds their intrinsic dimension, highlighting the need for more sophisticated approaches. In this talk, we will explore techniques for effectively handling data on such manifolds by operating on this lower intrinsic dimension. Such techniques can lead to much faster and more memory-efficient algorithms. We will first examine a specific problem on Grassmannian manifolds, then generalize to the broader class of quotient manifolds. Attendees may expect to gain a better understanding of how to view their structured data, and how to more efficiently process it.
