Learning Efficient Constraint Graph Sampling for Robotic Sequential Manipulation

Efficient sampling from constraint manifolds, and thereby generating a\ndiverse set of solutions for feasibility problems, is a fundamental challenge.\nWe consider the case where a problem is factored, that is, the underlying\nnonlinear program is decomposed into differentiable equality and inequality\nconstraints, each of which depends only on some variables. Such problems are at\nthe core of efficient and robust sequential robot manipulation planning. Naive\nsequential conditional sampling of individual variables, as well as fully joint\nsampling of all variables at once (e.g., leveraging optimization methods), can\nbe highly inefficient and non-robust. We propose a novel framework to learn how\nto break the overall problem into smaller sequential sampling problems.\nSpecifically, we leverage Monte-Carlo Tree Search to learn assignment orders\nfor the variable-subsets, in order to minimize the computation time to generate\nfeasible full samples. This strategy allows us to efficiently compute a set of\ndiverse valid robot configurations for mode-switches within sequential\nmanipulation tasks, which are waypoints for subsequent trajectory optimization\nor sampling-based motion planning algorithms. We show that the learning method\nquickly converges to the best sampling strategy for a given problem, and\noutperforms user-defined orderings or fully joint optimization, while providing\na higher sample diversity.\n