Faster Algorithms for Growing Collision-Free Convex Polytopes in Robot Configuration Space
Reviewed by Pithpith:ACUP3MHOopen to challenge →
read the original abstract
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
This paper has not been read by Pith yet.
Forward citations
Cited by 6 Pith papers
-
Signal Temporal Logic Motion Planning via Graphs of Convex Sets
The STL motion-planning problem is reformulated as a shortest-path problem over a graph of convex sets to generate smooth Bézier-spline trajectories satisfying logical, timing, smoothness, and velocity constraints.
-
Neural Configuration-Space Barriers for Manipulation Planning and Control
Neural CDF barriers enable efficient planning and robust safe control for manipulators in cluttered dynamic environments from point-cloud observations.
-
Any-Body Guard: Universal Safeguarding for Manipulation Policies via Action Masking
X-Safe masks actions in configuration space using forward kinematics and quasi-static object models to give probabilistic collision-avoidance guarantees that transfer across robot embodiments without per-setup engineering.
-
Learning Unions of Convex Sets via Invertible Latent Decomposition for Path Planning
ILD learns an invertible latent decomposition into unions of convex polytopes to support feasible path planning in high-DoF configuration spaces.
-
Neural Configuration-Space Barriers for Manipulation Planning and Control
Neural CDF barriers enable efficient planning and distributionally robust safe control for manipulators in cluttered dynamic environments using only point-cloud observations.
-
Task Allocation and Motion Planning in Dynamic, Cluttered Environments via CBBA and Graphs of Convex Sets
Integrates CBBA task allocation with GCS trajectory optimization in time-extended space for multi-agent systems in dynamic cluttered environments.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.