Marc Toussaint: NLP Sampling: A Joint View on Constrained Optimization and Sampling

Constrained optimization methods are a powerful tool for Task-and-Motion Planning and similar geometric or physical reasoning problems, also in higher-dimensions. However, in certain cases we would like solvers to return a diversity of solutions rather than only a single optimal one — e.g. to overcome local optima or guarantee probabilistic completeness when they are combined with higher-level search. I will discuss recent work on NLP Sampling as an integrative view and framework to combine existing methods from the fields of MCMC, constrained optimization, and robotics for diverse constrained sampling. Based on this we discuss several insights: An empirical evaluation on analytical and robotic manipulation planning problems yields (to me) somewhat surprising strengths and weaknesses. Quantifying diversity to compare methods is non-trivial — and I discuss a novel Minimum Spanning Tree Score. I will close with conceptual discussions on the role of Lagrange parameters in this approach, comparison to trained diffusion models, and an outlook on diverse robotic manipulation planning and learning.