Defining Geodesic Convexity

In my previous blog post, I discussed the notion of geodesic convexity, which is a generalization of ordinary convexity in Euclidean space to Riemannian manifolds. This is essential for disciplined optimization over manifolds; hence, it's very relevant to my research in optimization-based motion planning over manifolds.

Unfortunately, in the current literature, there are various definitions of geodesic convexity, with key differing properties. This is chiefly because if a geodesic connecting two points exists (it may not exist), it may not be unique, and it may not be minimizing. In this brief blog post, I'll discuss the various definitions that are used, and then explain why we use the one we did in our GGCS paper.

The Definitions

Nicholas Boumal's textbook An introduction to optimization on smooth manifolds is an excellent reference on the subject, and he discusses the various definitions of geodesic convexity in Section 11.3.

The first definition of geodesic convexity is the one used throughout Boumal's textbook. I'll be referring to it as "weakly" g-convex, to distinguish from the definition of g-convex we use in our paper. A set S is weakly g-convex if for every pair of points x and y in S, there is a geodesic segment connecting them that is contained in S. (Definition 11.2 of Boumal.) This is a very permissive definition for convexity, but is still suitable for optimization. However, it leads to a nasty side-effect: the intersection of two weakly g-convex sets may not be weakly g-convex!

The next two definitions handle this issue. A set S is totally convex if for every pair of points x and y in S, there is at least one geodesic segment connecting them, and all such segments are contained in S. (Definition 11.16 of Boumal.) In other sources, this definition may also include the requirement that S is nonempty, or that every pair of points in the manifold is connected by at least one geodesic ("geodesic completeness"). Finally, we reach the definition used for GGCS. A set S is strongly convex (which we call g-convex) if for every pair of points x and y in S, there is a unique minimizing geodesic connecting them, and that geodesic is contained in S.

Both strong convexity and total convexity directly imply weak convexity. But no other implications hold. For a certain special class of manifolds, called Cartan-Hadamard manifolds, all three definitions are equivalent. This includes Euclidean space with the canonical metric, and in that case, it also coincides with the ordinary definition of convexity.

Why We Use G-Convexity

To use geodesic convexity with the graph of convex sets framework, we desired two properties. For one, we needed the intersection of two convex sets to be convex, as we often need to constrain points to lie in the intersection of convex sets. For another, we needed two points in a convex set to uniquely describe a path between them (since we're optimization for trajectories). Thus, strong convexity (which we call g-convexity) was the appropriate definition for our purposes.

Comments

Post a Comment

Popular posts from this blog

Reimplementing GCS (Shortest Paths in Graphs of Convex Sets)

Image
In a previous blog post , I discussed my experiences reimplementing Iterative Regional Inflation by Semidefinite programming (IRIS) , which is an algorithm for finding large convex regions of collision free space (C-Free). In this blog post, I'll be discussing my experiences reimplementing shortest paths in Graphs of Convex Sets (GCS) , an algorithm for motion planning when the configuration space is described as the union of convex sets. Disclaimer: the intent is not to build a codebase for future use, since the Drake toolbox has mature implementations of both IRIS and GCS . Disclaimer: if you have not read the previous blog post , you should do so before reading this one. In this blogpost, I'll give a brief overview of the GCS paper, and then discuss my experiences reimplementing it. Before reading this blog post, you should read my previous blog post about reimplementing IRIS, as it provides some background and context which I will not repeat in this post. I have also ma...
Read more

Differing Formulations of GCS for Motion Planning

Image
In case you haven't heard of it before, GCS stands for "Graph of Convex Sets", and it is a framework for certain mixed integer convex optimization problems, primarily used for robot motion planning. I previously wrote a blog post on my experience implementing a basic version of it, which you can find here . I'd recommend reading that blog post before looking at this one. If you've read that previous blog post, you may recall that I described two different ways of transcribing the motion planning problem into a graph of convex sets. I implemented one version, which seems more faithful to the original GCS paper . However, the other transcription, presented in the planning-specific followup paper , has several benefits over the previous approach. In this blog post, I'll briefly present both methodologies, and explain their costs and benefits. Formulation 1: Conjugate Graph Fig. 1 of Shortest Paths in Graphs of Convex Sets The classic picture of GCS is the one sho...
Read more

IRIS on a Torus: Growing Convex Sets on Manifolds

Image
My current research focus at MIT is motion planning along manifolds, which we're primarily exploring through the lens of the graph of convex sets framework, abbreviated as GCS. (Refer to a previous blog post for more details, or check out the papers of Marcucci et. al. here and here .) Convexity is a property that is examined through the lens of Euclidean geometry, but it is possible to consider it in the broader context of smooth manifolds. This is reliant on the idea of a geodesic: a shortest path on a manifold. Replacing Euclidean spaces with manifolds and lines with geodesics allows us to consider a graph of geodesically convex sets (GGCS). We've begun laying the groundwork for planning over manifolds with such a tool, and you can read about it in our paper Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets , to appear at RSS 2023. (You can read the preprint today on arXiv!) While GGCS assumes the geodesically convex sets are given, computing such set...
Read more