Sampling-Based Motion Planning with Discrete Configuration-Space Symmetries

Thomas Cohn, Russ Tedrake · 2025

Read Sampling-Based Motion Planning with Discrete Configuration-Space Symmetries by Thomas Cohn, Russ Tedrake (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-2503-00614.txt.

Introduction

Thomas Cohn and Russ Tedrake improve motion planning for robots that handle symmetric objects, in a paper from 2025. When an object looks the same after a flip or turn, many poses are in effect the same. A good planner should use that fact to find shorter paths, but symmetry also warps the shape of the search space.

The pair show how the core steps of sampling-based planning can be done well in such warped spaces. Theory built on the geometry of the space proves lower sample needs for several standard methods. Broad tests then show real gains in both path length and run time.

Catalog record

CREATORThomas Cohn, Russ Tedrake
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00614

Browse the full library · About the Tower of Babel

Full text

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

Sampling-Based Motion Planning with Discrete Configuration-Space Symmetries Thomas Cohn, Russ Tedrake Abstract When planning motions in a configuration space that has underlying symmetries (e.g. when manipulating one or multiple symmetric objects), the ideal planning algorithm should take advantage of those symmetries to produce shorter trajectories. However, finite symmetries lead to complicated changes to the underlying topology of configuration space, preventing the use of standard algorithms. We demonstrate how the key primitives used for sampling-based planning can be efficiently implemented in spaces with finite symmetries. A rigorous theoretical analysis, building upon a study of the geometry of the configuration space, shows improvements in the sample complexity of several standard algorithms. Furthermore, a comprehensive slate of experiments demonstrates the practical improvements in both path length and runtime. I Introduction When solving motion planning problems that have underlying symmetries, the ideal planner should leverage this additional structure to find lower cost paths, reduce runtime, or both. In this paper, we study discrete symmetries, where for each system state, there is a finite set of other states that are functionally indistinguishable. Such symmetries appear in contact-rich manipulation problems when the object (or objects) being manipulated is a symmetric object, such as a cube [ 1 , 2 , 3 , 4 ] . Outside of robotic manipulation, these symmetries appear in assembly/disassembly planning tasks, where paths must be planned for individual (possibly symmetric) parts [ 5 ] . Finally, when using unit quaternions to represent orientations in 3D space, the equivalence of two antipodal unit quaternions can be interpreted as a form of symmetry. A common property of all these symmetries is that they appear explicitly in the system’s configuration space . In configuration space (or C-space), each coordinate corresponds to an individual degree of freedom, so a single point describes the position and orientation of each part of the robot [ 6 ] . For many robots, C-space can be interpreted as a bounded subset of Euclidean space. (For example, in the case of a robot arm, where each joint has physical limits to its motion.) But this is not always the case, and the topology of C-space may be inherently non-Euclidean. For example, the C-space of a revolute joint without limits is the unit circle S^{1} , and the C-space of a mobile robot is the Lie group \SE(2) (or \SE(3) if the robot can move in 3D space). Finally, closed kinematic chains (or the presence of certain constraints on the motion planning problem) will cause the set of valid configurations to be a curved, measure-zero subset of the full ambient C-space. In all of these cases, the standard strategy is to represent C-space as a smooth manifold [ 7 , 8 , 9 ] . A common attribute of the standard types of manifolds considered in robotics is that they have clear descriptions. Continuous revolute joints can be represented using straightforward switching logic for the wraparound. There are several well-understood representations available for \SO(3) and \SE(3) [ 10 ] . And kinematically-constrained spaces are still a subset of an ambient C-space [ 9 ] . However, representing the C-space of an object with symmetries is more challenging. Mathematically, it is described as a quotient manifold , a topological construction that does not yield an explicit representation as a subset of Euclidean space [ 11 , p. 540] . While continuous symmetries can be handled via dropping dimensions (e.g., the C-space of a sphere is just its position in \mathbb{R}^{3} ), in the case of discrete symmetries, the dimension of the resulting space is unchanged, so this strategy clearly cannot work. In this paper, we present a strategy for extending sampling-based motion planning algorithms to exploit discrete C-space symmetries. We show how the key primitive operations needed for sampling-based planning (distance computation, local and global sampling, and local planning) can all be implemented in closed-form for the quotient manifolds of interest. We demonstrate how this can be viewed through the lens of the IMACS (Implicit Manifold Configuration Space) framework for planning on general manifolds [ 12 ] , even without an explicit embedding into Euclidean space. We present a rigorous theoretical analysis of several standard sampling-based planning algorithms when planning in the quotient spaces of interest, quantifying the improvement in bounds on sample complexity. We also present a comprehensive slate of experiments to demonstrate the efficacy of our strategies for symmetry-aware planning, including path planning in both 2D and 3D for a variety of objects with symmetries. Across our experiments, leveraging the symmetries yields shorter paths, and despite the more complex approach, actually leads to shorter runtimes. II Related Work Motion planning is one of the most-studied problems in robotics. Algorithms for solving this problem can broadly be divided into two categories: trajectory optimizers and sampling-based planners . In a trajectory optimization problem, the control points of the robot’s trajectory are used as decision variables, and costs and constraints are imposed to shape the desired trajectories [ 13 , 14 , 15 , 16 ] . These optimization problems are almost always nonconvex, so trajectory optimizers frequently get stuck in local minima, and without a good initialization, may fail to compute a feasible trajectory altogether [ 17 , Ch.6] . To avoid local minima, one must try many different random initializations [ 18 ] or build complex representations of the collision-free space [ 19 ] . Sampling-based planners function by drawing random samples from C-space, rejecting those that are in collision, and connecting samples if the path between them is collision free. The Rapidly-Exploring Random Tree (RRT) [ 20 ] and Probabilistic Roadmap (PRM) [ 21 ] algorithms are the most widely-used sampling-based planning algorithms, although there are many others [ 22 ] . RRT incrementally constructs a space-filling tree, rooted at the start configuration, until a path to the goal configuration is found. PRM builds a roadmap in an offline construction phase, so it only has to link a start and goal configuration into the roadmap to find a path. The idea of exploiting symmetry to improve planning is not a new idea. System symmetries can be exploited for model predictive control [ 23 ] . In planning-as-search, graph-theoretic symmetries can be exploited for dramatic improvements [ 24 , 25 ] . Symmetries in certain motion primitives for nonlinear systems can also be leveraged [ 26 , 27 ] . Cheng et al. [ 28 ] used system symmetries to avoid costly numerical integration steps in kinodynamic planning. However, there is not much motion planning literature specifically focusing on symmetries in configuration space. Orthey et al. [ 29 ] examined planning on quotient manifolds, but each quotient had to be positive dimensional, and this approach could not handle more topologically-complex quotient spaces. The symmetries we consider in this paper have finitely many representatives, so a straightforward way to apply existing work is to cast the problem as a continuous planning problem with discrete decisions describing the representative of the planning goal. This can be interpreted as task-and-motion planning [ 30 ] , or one can avoid explicitly modeling the decision with a cost function that captures the symmetries. Scott et al. [ 31 ] used this strategy for differential dynamic programming,

Read the complete text