Faster algorithms for growing collision-free convex polytopes in robot configuration space

We propose two novel algorithms for constructing convex probabilistically collision-free polytopes in robot configuration space. Finding these polytopes enables the application of stronger motion-planning frameworks such as trajectory optimization with Graphs of Convex Sets ( Marcucci et al., 2023 ) and is currently a major roadblock in the adoption of these approaches. In this paper, we build upon the IRIS-NP algorithm (Iterative Regional Inflation by Semidefinite & Nonlinear Programming) of Petersen and Tedrake (2023) to significantly improve tunability, runtimes, and scaling to complex environments. IRIS-NP uses nonlinear programming paired with uniform random initialization to find configurations on the boundary of the free configuration space. Our key insight is that finding nearby configuration-space obstacles using sampling is inexpensive and greatly accelerates region generation. We propose two algorithms using such samples to either employ nonlinear programming more efficiently (IRIS-NP2) or circumvent it altogether using a massively parallel zero-order optimization strategy (IRIS-ZO). Both algorithms employ a novel termination condition that controls the probability of exceeding a user-specified permissible fraction-in-collision, eliminating a significant source of tuning difficulty in IRIS-NP. We further present an approach for applying both algorithms in parametrized configuration spaces. We compare the performance across eight robot environments, showing that IRIS-ZO achieves an order-of-magnitude speed advantage over IRIS-NP, which is extended roughly by an additional order of magnitude by parallelizing it with a GPU. IRIS-NP2, also significantly faster than IRIS-NP, builds larger polytopes using fewer hyperplanes which has the additional benefit of accelerating downstream motion planning. Website: https://sites.google.com/view/fastiris .