Superfast Configuration-Space Convex Set Computation on GPUs for Online Motion Planning

Peter Werner, Richard Cheng, Tom Stewart, Russ Tedrake, Daniela Rus · 2025

Read Superfast Configuration-Space Convex Set Computation on GPUs for Online Motion Planning by Peter Werner, Richard Cheng, Tom Stewart, Russ Tedrake, Daniela Rus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10783.txt.

Introduction

Peter Werner and co-authors race robot motion planning by building safe convex regions in configuration space on graphics chips. Modern planners love convex sets because paths through them optimize fast and reliably, dodging nasty collision math. Yet computing the sets was too slow for scenes that change while the robot works.

Their 2025 paper inflates piecewise linear paths into chains of probably collision-free convex sets with massive parallelism. A dynamic roadmap finds the paths, and the candidate path itself helps spot and cut collisions from its own sets. On a benchmark and a real KUKA arm with live perception, the pipeline runs many times faster and plans far more reliably than a nonlinear baseline, at equal path quality.

Catalog record

CREATORPeter Werner, Richard Cheng, Tom Stewart, Russ Tedrake, Daniela Rus
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10783

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Superfast Configuration-Space Convex Set Computation on GPUs for Online Motion Planning Peter Werner, Richard Cheng, Tom Stewart, Russ Tedrake, Daniela Rus Abstract In this work, we leverage GPUs to construct probabilistically collision-free convex sets in robot configuration space on the fly. This extends the use of modern motion planning algorithms that leverage such representations to changing environments. These planners rapidly and reliably optimize high-quality trajectories, without the burden of challenging nonconvex collision-avoidance constraints. We present an algorithm that inflates collision-free piecewise linear paths into sequences of convex sets (SCS) that are probabilistically collision-free using massive parallelism. We then integrate this algorithm into a motion planning pipeline, which leverages dynamic roadmaps to rapidly find one or multiple collision-free paths, and inflates them. We then optimize the trajectory through the probabilistically collision-free sets, simultaneously using the candidate trajectory to detect and remove collisions from the sets. We demonstrate the efficacy of our approach on a simulation benchmark and a KUKA iiwa 7 robot manipulator with perception in the loop. On our benchmark, our approach runs 17.1 times faster and yields a 27.9% increase in reliability over the nonlinear trajectory optimization baseline, while still producing high-quality motion plans. Website: https://sites.google.com/view/GPUPolytopes Fig. 1: On the left, our hardware setup with a KUKA LBR iiwa 7 R800 robotic manipulator and three Intel RealSense D415 depth cameras for perceiving obstacles is shown. In the center, the simulated system with the perceived obstacles is shown. The target end effector pose is indicated by the yellow gripper and the collision geometries of the system are shown in red. The perceived obstacles are approximated by a union of spheres shown in the center of the table. The figure on the right shows a two-dimensional slice of the seven-dimensional configuration space, along with a slice of the safe sets (blue and green), and a slice of the configuration obstacles (self-collisions in black, collisions with perceived obstacles in red). The slice lies tangent to the trajectory such that the u-direction is co-linear with the velocity and the v-direction is a random orthogonal vector. The current configuration is indicated by the black dot. I Introduction Finding high-quality collision-free motion plans remains one of the most fundamental and challenging problems in robotics [ 1 , 2 ] . Systems with high demands on reliability and performance, e.g. on production lines or in warehouses, often require carefully tailored ad hoc solutions, which afford reliability at the cost of engineering effort and performance. Over the years, sampling-based motion planning, trajectory optimization using nonlinear programming, and combinations thereof, have become the most established approaches for motion planning. Sampling-based motion planners are simple to implement [ 2 , 3 ] , work well in lower dimensions, can have completeness guarantees, and can be massively accelerated using large-scale parallelization [ 4 , 5 ] . See [ 6 ] for an overview on sampling-based motion planning. Unfortunately, these methods become impractical as the dimension increases, yielding suboptimal motion plans and long planning times. Directly transcribing motion planning as a general nonlinear optimization problem and finding solutions with local methods, e.g. [ 7 , 8 , 9 ] , has the benefit of scaling to higher-dimensional problems and allowing the user to encode a wider variety of costs and constraints. Unfortunately, such local optimization approaches are sensitive to initialization and often struggle to find a feasible solution when one exists. To capture the strengths of both trajectory optimization and sampling-based motion planning, a series of recent works [ 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 ] initially proposed in [ 18 ] investigate planning through collections of collision-free convex sets that approximately decompose the free space. For the remainder of this paper, we will refer to this class of planners as decomposition-based motion planners (DBMPs). A challenging nonconvexity in trajectory optimization stems from the collision-avoidance constraints. Given a collection of collision-free convex sets, DBMPs replace these nonconvex constraints with simple convex constraints, which allows them to profit from the fast solve times and reliability of convex optimization. This shifts the challenges that stem from these collision-avoidance constraints to constructing a high-quality representation of the collision-free space through a union of convex sets. For a candidate approximate convex decomposition to be effective, it should consist of a small number of sets, contain high-quality trajectories in the union of the sets, and its individual sets should be described by few constraints in order to keep the trajectory optimization problems small. Many robot motion planning problems are most naturally formulated in the robot’s configuration space \mathcal{C} . Therefore, we seek to construct the convex sets in \mathcal{C}^{\mathrm{free}} , the collision-free subset of \mathcal{C} . Unfortunately, this is particularly challenging because configuration spaces tend to be high-dimensional with complicated geometries, and we often only have implicit descriptions of \mathcal{C}^{\mathrm{free}} [ 1 , §4.3.3] . Therefore, the go-to algorithms used by practitioners for constructing convex decompositions of \mathcal{C}^{\mathrm{free}} are slow, scale poorly with the environment complexity, and are difficult to use [ 19 , 20 ] , mainly due to their complexity or because they are difficult to tune. Additionally, these algorithms only consider static environments. Generally, the sets need to be recomputed in case the environment changes. So far, these challenges have made set construction a bottleneck, and have prevented DBMPs from being applied successfully to scenarios involving changing environments like mobile manipulation. In this paper, our aim is to tackle two key challenges: (1) computing convex sets in robot configuration space for motion planning in real-time, and (2) reliable and effective positioning of the sets such that they contain high-quality trajectories. By addressing these challenges, our aim is to unlock the benefits of DBMPs and enable their use in general, changing environments. To tackle challenge (1), we build on the recently developed IRIS-ZO algorithm [ 21 ] , which lends itself to large-scale parallelism. In particular, we propose Zero-Order Edge Inflation (EI-ZO), and demonstrate that GPU acceleration of our algorithm enables real-time set construction in changing configuration spaces. EI-ZO also addresses challenge (2) by inflating collision-free line segments rather than points, yielding probabilistically collision-free polytopes which are guaranteed to contain the seed line segment. This enables us to inflate collision-free, piecewise-linear (PWL) paths between the start and the goal into sequences of convex sets (SCS) in which successive sets in the sequence intersect. By construction, this SCS connects the start to the goal and guarantees the containment of a collision-free path. In comparison to approximating the entire free space with a union of convex sets [ 22 ] , this approach dramatically reduces the computational burden by reducing the number of required sets. Perhaps more importantly, it makes the step of finding a collection of sets that connect the start to the goal reliable, even in complicated, changing configuration spaces. Finally, we propose a motion planning pipeline that combines these ideas with large-scale dynamic road maps (DRMs). The pipeline first leverages the DRM to rapidly find a collision-free PWL path from a starting configuration to a goal configuration. Next, this path is inflated with EI-ZO to produce a SCS, which is then used to recover high-quality motion plans using DBMPs. We demonstrate the efficacy

Read the complete text