# Faster Algorithms for Growing Collision-Free Convex Polytopes in Robot Configuration Space

arXiv: https://arxiv.org/abs/2410.12649 · HTML: https://mlsanity.com/paper/2410.12649/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2024.

## Built on by (most cited first, 4 of 4)

- [Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning](https://mlsanity.com/paper/2508.20095/) (2025)
- [Neural Configuration-Space Barriers for Manipulation Planning and Control](https://mlsanity.com/paper/2503.04929/) (2025)
- [X-Safe: Embodiment-Agnostic Safeguarding for Robot Arm Manipulation Policies via Action Masking](https://mlsanity.com/paper/2606.22278/) (2026)
- [Approximately Optimal Global Planning for Contact-Rich SE(2) Manipulation on a Graph of Reachable Sets](https://mlsanity.com/paper/2601.10827/) (2026)

## Abstract (arXiv)

We propose two novel algorithms for constructing convex 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 [1] and is currently a major roadblock in the adoption of these approaches. In this paper, we build upon IRIS-NP (Iterative Regional Inflation by Semidefinite & Nonlinear Programming) [2] 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 near-by 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). We also propose a 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 compare performance across eight robot environments, showing that IRIS-ZO achieves an order-of-magnitude speed advantage over IRIS-NP. IRISNP2, also significantly faster than IRIS-NP, builds larger polytopes using fewer hyperplanes, enabling faster downstream computation. Website: https://sites.google.com/view/fastiris