Introduction to MASEM (Manifold Sampling via Entropy Maximization)

This post is an introduction/explanation to the paper “Manifold Sampling via Entropy Maximization” by Cornelius V. Braun, me, and Marc Toussaint [1], where we introduce a framework called MASEM. I will explain MASEM very informally; I recommend reading the paper (perhaps armed with the intuition gained here) for a rigorous treatment.

Sampling under Constraints

In robotics, we often deal with constraints. For example, our robot shouldn’t collide with obstacles and it should respect it’s joint limits. We express this as a mathematical function like distance(robot, obstacle) ≥ safe_distance. These constraint-functions form a so-called manifold. An example of a manifold is a piece of paper in three-dimensional space. No matter how you bend it, it always stays two-dimensional. We now want to pick random points from this manifold (in robotics this gives us redundancy: If one path is blocked, we know other ways to get around the obstacles). This, turns out, is surprisingly hard.

Imagine you throw darts at a wall. Even if you throw completely at random, some of them will hit your dartboard just by pure luck. If however, I replace your two-dimensional dartboard with a one-dimensional line, you would need an incredible aim to have any chance of hitting it. Mathematically speaking, the chance of hitting this line with random throws is 0. This provides us with intuition about sampling (ie selecting random points) from a manifold. If the manifold dimension (the one-dimensional line) is smaller than the dimension of the space it lives in (the two-dimensional wall), hitting it randomly is impossible. We need a more sophisticated method: First, we select random points in the ambient space and then move them onto their closest point on the manifold. Since they might not be random after this projection step, we shuffle them around a bit on the manifold (called “mixing”). Mixing works by walking along our manifold randomly until we don’t know where the points initially came from. We call this a constrained sampler.

Sampling Disconnected Components

This works well if we have only one connected component (one piece of paper). However, if we have multiple disconnected components (papers scattered across the room), this mixing process struggles with jumping between them. That means if we are unlucky and one component gets a lot more samples in the projection step, mixing is not going to fix that imbalance. The image below shows this problem. The smaller circle started with more samples, and the constrained sampler (NHR [2]) is not able to move the points towards the bigger one.

This is where our method MASEM comes in. We combine a local sampler as described above with a resampling step. The local sampler mixes points within components, while the resampling step takes care of global allocation. It takes points from crowded components and moves them towards those with little samples. In essence, MASEM helps the particles spread out fairly across all components of the constraint set.

Interestingly, we only need local information to do that. Each point estimates its distance to its closest neighbors. If this distance is small, it means the neighborhood of this point is crowded and it likely belongs to an oversampled component. Conversely, if the distance is large, the point likely lies in an undersampled component. By treating these points with large neighbor distances as more important, we balance points between different components.

In our experiments we see that this method works well, especially if our manifold has disconnected components. It only introduces a small runtime overhead and greatly improves the quality of our samples. We also test it on robotics-related problems, where we see that it helps with finding more diverse paths around obstacles. The graphic shows the paths found by two constrained samplers (OLLA [3] and NHR [2]), first as-is without MASEM, and then after we modify them with the MASEM-resampling step.

To be slightly more rigorous

A feasible set defined by constraints is not automatically a manifold. You need additional conditions, for example LICQ and smooth constraints. The resulting manifold is often called Riemannian manifold with corners, as it is locally diffeomorph to a euclidean half-space. The constrained sampler I describe resembles Non-linear Hit and Run [2]. While it can somewhat mix across disconnected components (given a large enough step size and enough time), it struggles if they are far apart or have high curvature. Resampling is done with weights proportional to the k-nearest neighbour distance with some temperature tau which should lie between 0 and the intrinsic dimension of the manifold.

Sources

[1] C. V. Braun, T. Burghoff and M. Toussaint, “Manifold Sampling via Entropy Maximization,” arXiv preprint arXiv:2605.12338, 2026.

[2] M. Toussaint, C. V. Braun, and J. Ortiz-Haro, “NLP Sampling: Combining MCMC and NLP Methods for Diverse Constrained Sampling,” arXiv preprint arXiv:2407.03035, 2024.

[3] K. Jeon, M. Muehlebach, and M. Tao, “Fast Non-Log-Concave Sampling under Nonconvex Equality and Inequality Constraints with Landing,” in the thirty-ninth annual conference on neural information processing systems (Neurips), 2025. Online