At a glance
IRIS-ZO and IRIS-NP2 accelerate the construction of convex configuration-space regions by using cheap collision samples before placing separating planes. IRIS-ZO moves samples toward an ellipsoid center with parallel bisection; IRIS-NP2 initializes nonlinear optimization from configurations already known to collide. Both replace an unreliable failed-solver stopping heuristic with a statistical test on the region’s collision volume. Across eight simulated systems, the reported average speedups are substantial, with a tradeoff between runtime, region volume, and number of faces. The result bounds the fraction of a region in collision with specified confidence; it does not certify every configuration or planned trajectory as collision-free.
1 Introduction
Convex regions can make downstream trajectory optimization efficient because they describe volumes of free space rather than isolated samples. Their construction is difficult when simple workspace obstacles become nonconvex configuration-space obstacles. IRIS-NP [2] repeatedly solves a closest-collision nonlinear program for each geometry pair, then stops after sufficiently many unsuccessful solves; these failures are both costly and a weak proxy for safety. The proposed algorithms exploit the much lower cost of collision checking. Samples identify relevant obstacles, guide plane placement, and provide a directly interpretable statistical stopping rule. Large regions and few faces are desirable for planning, so runtime alone is not the quality criterion.
2 Problem Formulation
The output is a positive-volume polytope whose collision-volume fraction exceeds an admissible ε with probability at most δ. Thus ε controls permitted contamination and δ controls false certification, rather than δ being a per-step collision probability. Inputs describe robot collision geometries and forward kinematics, available through formats such as URDF or SDF. A configuration is in collision when any considered geometry pair overlaps in task space. This gives an implicit obstacle description without explicitly computing its configuration-space boundary. The guarantee is relative to the selected collision pairs and the supplied geometry/checker; unmodeled geometry or excluded pairs are outside it.
Equations 1–2
| (1) |
| (2) |
3 Related Works
Original IRIS handles explicitly represented convex obstacles through convex optimization. Manipulator kinematics usually require implicit obstacle constraints, motivating IRIS-NP and alternative initialization strategies. Sums-of-squares formulations [19] can give rigorous collision-free certificates, but cost more and use a stereographic configuration parametrization. Ellipsoidal coverings and dense sampled decompositions offer other approximations with scaling limitations. The present contribution targets practical construction speed and controllable volume error rather than replacing exact certification.
4 Background on IRIS Algorithms
Both new methods retain the IRIS alternation between constructing separating planes around an ellipsoid and fitting a maximum-volume inscribed ellipsoid in the resulting polytope.
4.1 IRIS with Convex Obstacles
For convex obstacles, IRIS finds the closest obstacle point in the ellipsoid’s quadratic metric. The normal E(x*−c) defines a supporting plane through that point, and the intersection of all resulting halfspaces excludes the obstacles. Refitting the maximum-volume inscribed ellipsoid then increases its volume monotonically under the original convex assumptions. This supplies the geometric template; the same separation guarantee does not automatically survive nonconvex configuration obstacles or approximate boundary searches.
Equations 3–5
| (3) |
| (4) |
| (5) |
4.2 Computing Separating Planes in Robot Configuration Space
IRIS-NP searches jointly for a robot configuration and a common point inside a pair of task-space collision geometries. The configuration must remain in the current polytope. Each locally optimal collision yields a new halfspace, shifted inward by a positive margin to remove the boundary configuration and avoid infinitely many cuts. Repeated local searches may find different parts of one nonconvex obstacle. Terminating after consecutive solver failures is inconclusive because local failure does not prove that the polytope contains no collision. Equation 7 is retained as printed but places q* rather than the variable x in its plane equation; the following halfspace description and Algorithm 3 provide the actionable construction.
Equations 6a–6b
| (6a) | ||||
| (6b) | ||||
Equation 7
| (7) |
5 Improving the Separating Hyperplanes Routine
The improvements replace the separating-plane subroutine while retaining outer stopping rules such as an iteration cap, ellipsoid-volume convergence, or losing the seed point. A small ball initializes the ellipsoid. Table 1 separates the collision threshold ε, uncertainty budget δ, inward step Δ, particle count, bisection count, and face cap. The new statistical rule stops the inner plane-refinement loop, not the outer ellipsoid alternation. In particular, the procedure can terminate without preserving the original seed, and the two loops have distinct purposes.
| Parameter | Description | IRIS-ZO | IRIS-NP2 |
|---|---|---|---|
| Admissible fraction of the region in collision | ✓ | ✓ | |
| Max admissible uncertainty | ✓ | ✓ | |
| Configuration margin, i.e.“step back” | ✓ | ✓ | |
| Termination condition (as in [2]) | ✓ | ✓ | |
| Number of optimized particles per inner iteration | ✓ | ✓ | |
| Number of bisection steps | ✓ | ✗ | |
| Max number of hyperplanes added per inner iteration | ✓ | ✓ |
5.1 Termination Condition for the Separating Planes Step
A test draws M uniform collision indicators and accepts when their mean is at most (1−τ)ε. For a region whose true collision fraction is at least ε, the multiplicative Chernoff bound makes false acceptance at most δ when M ≥ 2 log(1/δ)/(ετ²), rounded upward. The proof compares the threshold with the unknown true mean and bounds the lower tail exponentially. Smaller τ needs more samples but a less conservative threshold; τ=0.5 is used in practice. To control repeated testing, the kth inner test receives δk=6δ/(π²k²); with repeated outer iterations, test (i,k) instead receives 36δ/(π⁴i²k²). A union bound then limits the total false-accept probability over arbitrarily many tests. These sequences require positive indices: Algorithm 2’s printed initialization k=0 must be reconciled before implementation. The proof assumes independent uniform draws, whereas the implementation uses approximately uniform hit-and-run samples [23] after finite mixing. The paper does not add a mixing-error correction, so the formal probability statement is conditional on the sampling assumptions.
Equations 8–9
| (8) |
| (9) |
5.2 The IRIS-ZO Algorithm
IRIS-ZO starts from the domain polytope and assumes a collision-free ellipsoid center. It draws at least enough samples for the statistical test and the particle budget, checks collisions in parallel, and returns if the test accepts. Otherwise, selected colliding particles are bisected toward the center for a fixed number of steps. Their updated locations are sorted by ellipsoid distance, and nonredundant candidates generate inward-shifted planes until the face budget is reached. Bisection uses only collision checks and can be highly parallel, but it finds some obstacle boundary along each ray rather than necessarily the nearest obstacle or the original sampled obstacle. Approximate plane placement can therefore shrink useful space substantially. The sampling/test/cutting cycle repeats until accepted.
5.3 The IRIS-NP2 Algorithm
IRIS-NP2 uses known colliding configurations, together with the responsible body pair, as feasible initial guesses for the nonlinear closest-collision program. It prioritizes small ellipsoid distance and skips pairs that samples never find colliding, avoiding the many infeasible searches required by IRIS-NP. The greedy finder orders colliding test samples and discards candidates cut out by earlier planes. The ray finder instead steps outward from the center toward sampled directions, returning the first detected collision before leaving the polytope; the subsequent nonlinear solve refines that candidate. Outward search can locate closer obstacles than inward bisection, at additional cost, although finite ray steps can skip small obstacles. The resulting regions usually need fewer faces. Algorithm 3 reuses i both for the outer iteration and an inner particle counter; the probability-budget index must remain distinct in an implementation. The original pseudocode is preserved for comparison.
6 Experiments
Eight environments span 3–15 degrees of freedom and 137–302 valid collision pairs, including two 7-DOF arms and an Allegro hand. Ten manually chosen seeds per environment are repeated ten times, giving 800 trials per algorithm and setting. Only one outer iteration is run to isolate the separating-plane routine. The fast setting allows 10% collision volume with 90% confidence; the precise setting allows 1% with 95% confidence. IRIS-NP is manually tuned to roughly comparable average contamination, and IRIS-NP2 parameters are tuned per environment. Computation uses a 10-core/20-thread CPU, MOSEK, and SNOPT. Table 2 reports means across all seeds; Figure 6 shows variability for one selected seed per environment. Volume is measured through the maximum-volume inscribed ellipsoid and normalized by the baseline, not by directly computing polytope volume. Reported mean speedups for IRIS-ZO are 15.5× fast and 14× precise. The greedy NP2 variant obtains 6.55× and 12.3×; the ray variant 4.2× and 8×, generally with fewer faces. These averages hide important exceptions: precise Allegro ZO takes 7.455 s versus 2.164 s for IRIS-NP, and fast two-arm NP2 is slower than the baseline. Two-arm ZO produces relative ellipsoid volumes of only 0.0008 and 0.0003 in the fast and precise settings. Conversely, some enormous relative gains arise when baseline ellipsoids are tiny. Thus the table supports a tunable speed/representation tradeoff, not universal dominance or a measured downstream planning speedup.
| Domain | Flipper | UR3 | UR3Wrist | IIWAShelf | 4Shelves | IIWABins | 2IIWAs | Allegro |
|---|---|---|---|---|---|---|---|---|
| # dof | 3 | 5 | 6 | 7 | 7 | 7 | 14 | 15 |
| # col. pairs | 137 | 142 | 142 | 172 | 302 | 212 | 264 | 187 |
| 0.149 | 0.268 | 0.254 | 0.480 | 0.117 | 0.577 | 0.536 | 0.261 |
| Environment | Time [s] | Num Hyperplanes | Rel Volume | Frac in collision | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NP | ZO | Greedy | Ray | NP | ZO | Greedy | Ray | NP | ZO | Greedy | Ray | NP | ZO | Greedy | Ray | ||
| Fast | Flipper | 0.168 | 0.025 | 0.045 | 0.847 | 22.7 | 15.8 | 13.6 | 13.4 | 1.0 | 0.627 | 2.167 | 2.017 | 0.040 | 0.013 | 0.022 | 0.016 |
| UR3 | 0.994 | 0.041 | 0.113 | 0.221 | 41.6 | 27.8 | 25.4 | 22.7 | 1.0 | 0.971 | 3.598 | 3.296 | 0.040 | 0.029 | 0.020 | 0.028 | |
| UR3Wrist | 1.227 | 0.050 | 0.168 | 0.948 | 51.4 | 34.0 | 30.8 | 26.5 | 1.0 | 3.824 | 5.376 | 1.663 | 0.029 | 0.031 | 0.023 | 0.023 | |
| IIWAShelf | 1.345 | 0.091 | 0.442 | 0.633 | 77.3 | 47.2 | 32.7 | 31.0 | 1.0 | 6.196 | 8.73e3 | 16.249 | 0.068 | 0.034 | 0.027 | 0.052 | |
| 4Shelves | 1.317 | 0.092 | 0.313 | 0.845 | 62.9 | 46.9 | 35.1 | 30.3 | 1.0 | 0.139 | 1.388 | 1.724 | 0.102 | 0.038 | 0.025 | 0.033 | |
| IIWABins | 1.536 | 0.074 | 0.627 | 0.861 | 84.0 | 44.3 | 33.4 | 31.1 | 1.0 | 542.228 | 4.99e4 | 604.161 | 0.092 | 0.035 | 0.027 | 0.021 | |
| 2IIWAs | 20.482 | 2.024 | 62.060 | 46.527 | 242.1 | 246.2 | 77.7 | 65.7 | 1.0 | 0.0008 | 316.777 | 95.052 | 0.061 | 0.057 | 0.037 | 0.055 | |
| Allegro | 2.277 | 0.264 | 0.101 | 0.106 | 75.3 | 83.7 | 41.9 | 39.6 | 1.0 | 0.036 | 152.040 | 60.554 | 0.0007 | 0.052 | 0.015 | 0.033 | |
| Precise | Flipper | 1.002 | 0.172 | 0.152 | 0.269 | 26.1 | 17.8 | 14.3 | 14.4 | 1.0 | 0.621 | 1.169 | 1.236 | 0.003 | 0.001 | 0.001 | 0.0004 |
| UR3 | 5.222 | 0.304 | 0.325 | 0.642 | 52.9 | 44.5 | 28.1 | 27.0 | 1.0 | 3.698 | 13.656 | 2.301 | 0.003 | 0.002 | 0.002 | 0.003 | |
| UR3Wrist | 4.664 | 0.359 | 0.359 | 0.410 | 61.8 | 56.1 | 31.5 | 28.6 | 1.0 | 3.811 | 183.345 | 4.959 | 0.002 | 0.003 | 0.001 | 0.002 | |
| IIWAShelf | 11.261 | 0.787 | 1.087 | 3.008 | 126.3 | 92.0 | 41.0 | 37.8 | 1.0 | 763.826 | 7.817 | 9.260 | 0.004 | 0.003 | 0.002 | 0.004 | |
| 4Shelves | 25.315 | 0.699 | 0.838 | 1.002 | 85.2 | 81.3 | 40.5 | 36.1 | 1.0 | 0.124 | 1.592 | 1.672 | 0.012 | 0.003 | 0.002 | 0.003 | |
| IIWABins | 15.487 | 0.763 | 0.997 | 2.188 | 128.6 | 98.6 | 44.1 | 39.6 | 1.0 | 504.123 | 603.431 | 92.268 | 0.003 | 0.003 | 0.002 | 0.003 | |
| 2IIWAs | 202.913 | 43.194 | 84.973 | 77.181 | 395.1 | 738.7 | 90.8 | 82.7 | 1.0 | 0.0003 | 37.507 | 48.984 | 0.006 | 0.005 | 0.004 | 0.004 | |
| Allegro | 2.164 | 7.455 | 0.499 | 1.271 | 75.3 | 290.6 | 45.5 | 42.2 | 1.0 | 0.005 | 8.237 | 20.434 | 0.0007 | 0.005 | 0.001 | 0.003 | |
7 Discussion
The main practical gain is to spend expensive optimization on confirmed collisions while using samples to decide when further cuts are unnecessary. IRIS-ZO favors fast parallel construction; IRIS-NP2 more carefully places faces and often preserves larger regions. Limits include nonzero allowed collision volume, approximate sampling, collision-free-center assumptions, per-environment tuning, only one tested outer iteration, and highly variable region quality in high dimensions. A small fraction of colliding volume does not bound the collision probability along a deliberately selected trajectory or guarantee free-space connectivity. GPU/SIMD collision checks, improved initialization near small obstacles, better free-space covers, and direct downstream planning evaluation are proposed future work.
7.0.1 Acknowledgements
The authors acknowledge technical feedback and support from Amazon, the MIT Quest for Intelligence, Toyota Research Institute, and Draper.