Configuration Space (C-Space)

The dimensionality of a configuration space is determined by the minimum number of parameters (degrees of freedom) required to uniquely specify the robot's state. A simple mobile robot on a plane has a 3D C-space (x, y, θ). A 6-axis industrial arm has a 6D C-space (six joint angles). A humanoid robot can have a C-space with 30+ dimensions. This high dimensionality is the primary cause of the curse of dimensionality, making exhaustive search or grid-based planning computationally intractable and necessitating sampling-based methods like RRT and PRM.

A fundamental power of the C-space formulation is the transformation of physical obstacles into C-space obstacles (C-obst). For a given robot geometry and a workspace obstacle, the C-obst is the set of all configurations where the robot collides with that obstacle.

• Construction: Computed via Minkowski sums (for translational motion) or more complex convolution for full rigid-body motion.
• Result: The planning problem simplifies to finding a path for a point through the C-free space (the complement of all C-obst). This elegantly handles the robot's complex geometry but shifts the computational burden to obstacle representation.

The topology (shape) of C-space is not always Euclidean (Rⁿ). It is dictated by the joint types.

• Revolute Joints: A joint angle θ is cyclic, meaning θ and θ + 2π represent the same physical configuration. Therefore, the C-space for a single revolute joint is a circle (S¹), not a line.
• Common Topologies:
  • A planar mobile robot: R² × S¹ (a cylinder).
  • A spherical joint: S² × S¹.
  • A 2R planar arm: T² (a torus). This non-Euclidean structure must be accounted for in distance metrics, sampling, and interpolation to avoid discontinuous jumps in the planned path.

A valid metric is required to measure distances between configurations for nearest-neighbor searches, local planning, and cost calculations. The choice of metric significantly impacts planner performance.

• Simple Metrics: Weighted Euclidean distance in joint space. Weights can reflect different joint travel costs.
• Geodesic Metrics: On non-Euclidean spaces like S¹, the shortest distance is along the manifold (e.g., min(|θ₁ - θ₂|, 2π - |θ₁ - θ₂|)).
• Workspace-Sensitive Metrics: Incorporate end-effector displacement, making the metric more task-relevant but more expensive to compute. An inappropriate metric can make nearby configurations in C-space correspond to large motions in the workspace, or vice-versa.

Singularities are configurations where the robot loses one or more degrees of freedom in its end-effector motion. In C-space, they correspond to points where the Jacobian matrix loses rank.

• Consequences: At a singularity, infinitesimal joint motions in certain directions produce no end-effector motion. This causes issues for velocity control, leads to infinite solutions for inverse kinematics, and often requires infinite joint torques.
• Planning Implication: Paths passing near singularities can be poorly conditioned. Advanced planners may explicitly penalize or avoid regions near singularities in the C-space to ensure stable, feasible execution.

The connectivity of the free space (C-free) determines the existence of a feasible path. A key property for sampling-based planners is whether C-free is path-connected (any two points can be joined by a continuous path staying in C-free).

• Challenges: Narrow passages in the workspace become even narrower, lower-dimensional regions in C-space, making them exponentially hard to sample. This is known as the narrow passage problem.
• Analysis: Understanding the homotopy classes (distinct types of paths around obstacles) in C-free can be important for finding optimal or preferred paths. Planners like PRM explicitly aim to capture the connectivity of C-free through their probabilistic roadmap.

A simple differential-drive robot that moves on a flat plane has a 3-dimensional C-Space: (x, y, θ). Its configuration is defined by its 2D Cartesian position (x, y) and its heading angle θ (yaw).

• C-Space Topology: R² × S¹. The (x, y) coordinates span the Euclidean plane R², while the angle θ wraps around at 2π, forming a circle S¹.
• Obstacle Transformation: A physical obstacle in the workspace becomes an expanded region in C-Space, often called a C-obstacle. For a circular robot, this expansion is uniform; for a non-circular body, the C-obstacle is the Minkowski sum of the obstacle and the robot's geometry.
• Constraint Example: A nonholonomic constraint, like the robot's inability to move directly sideways, restricts allowable velocities but does not reduce the dimension of the C-Space itself.

A standard industrial robotic arm with n rotary (revolute) joints has an n-dimensional C-Space. Each joint angle q_i is a coordinate.

• C-Space Topology: T^n = S¹ × S¹ × ... × S¹ (the n-torus). Since each joint angle wraps around at 2π, the C-Space for a 6-DOF arm is a 6-dimensional torus.
• Singularities: Certain configurations, known as kinematic singularities, correspond to points where the robot loses one or more degrees of freedom in its end-effector motion. These appear as lower-dimensional manifolds within the C-Space.
• Visualization Challenge: While a 2-joint (θ₁, θ₂) arm's C-Space can be visualized as a square with wrapped edges (a torus), higher-dimensional C-Spaces are abstract and must be analyzed mathematically or through projections.

A robot with a prismatic (sliding) joint has a C-Space coordinate that is a linear displacement d. This is common in gantry robots, 3D printers, and telescoping mechanisms.

• C-Space Topology: R (the real line). The coordinate d is typically bounded by the physical limits of the actuator, defining a line segment [d_min, d_max] within the C-Space.
• Composite Systems: Most robots are hybrids. A SCARA robot has a C-Space of (θ₁, θ₂, d₃, θ₄), mixing revolute and prismatic joints, resulting in a topology of S¹ × S¹ × R × S¹.
• Planning Implication: In sampling-based planners like RRT or PRM, sampling a prismatic joint coordinate involves drawing from a continuous interval, not a cyclic domain.

A body free to move and rotate in 3D space, like a quadrotor or satellite, has a 6-dimensional C-Space representing its pose.

• Coordinates: (x, y, z, α, β, γ). The position (x, y, z) ∈ R³. The orientation requires three parameters (e.g., roll, pitch, yaw).
• Orientation Topology: Using Euler angles (α, β, γ) leads to a topology of R³, but this representation suffers from gimbal lock. The more rigorous representation uses SO(3), the 3D rotation group, which is a 3-dimensional manifold that is not equivalent to R³.
• C-Obstacles: Obstacles are expanded in all six dimensions, making visualization impossible but computation tractable by checking collisions for sampled (x, y, z) and a swept volume of orientations.

A humanoid robot with two arms, legs, and a torso has a high-dimensional C-Space, often exceeding 30 dimensions (>30-DOF).

• Composite Topology: A mix of many S¹ (revolute) and some R (prismatic) components. The space is a high-dimensional torus cross Euclidean spaces.
• Self-Collision Constraints: A critical component of the C-Space obstacle region is defined by self-collision—configurations where the robot's own limbs intersect. This creates complex, non-convex forbidden regions within the C-Space.
• Reduced-Order Models: For locomotion planning, the full C-Space is often reduced using a base link (torso) pose (x, y, z, α, β, γ) and key joint angles, treating the rest with simplified inverse kinematics.

Parallel robots, where the end-effector is connected to the base via multiple independent kinematic chains, have a C-Space that is constrained by complex closure equations.

• Actuator vs. End-Effector Space: The joint space (actuator lengths/angles) is often easier to parameterize. However, the task space (end-effector pose) is the true C-Space of interest but is subject to intricate kinematic constraints.
• Multiple Solutions: For a given end-effector pose, there can be multiple sets of actuator configurations (assembly modes). This means the mapping from task space to joint space is not one-to-one.
• Singularities Abound: Parallel manipulators have various singularity types (e.g., serial, parallel) that appear as surfaces in the C-Space where the mechanism gains or loses controllability, making planning particularly challenging.

Free Space is the subset of the configuration space where the robot's geometry does not intersect with any obstacles. It is the set of all valid, collision-free configurations. Motion planning algorithms exclusively search within this region.

• Definition: C_free = { q ∈ C | R(q) ∩ O = ∅ }, where R(q) is the robot's geometry at configuration q and O is the set of obstacles.
• Complexity: The geometry of C_free is often highly non-convex and complex, even for simple robots and obstacles, which is why sampling-based planners are preferred over exact geometric decomposition.
• Core Challenge: The primary task of motion planning is to find a continuous path entirely contained within C_free connecting a start and goal configuration.

State Space is a broader representation that includes both the robot's configuration (position) and its time derivatives (velocity, momentum). While C-Space defines where the robot can be, state space defines how it can be moving.

• Relation to C-Space: For a simple kinematic planner, the state space may be identical to C-Space. For dynamic planning, state = (configuration, velocity).
• Dimensionality: State space is typically twice the dimensionality of C-Space for second-order systems.
• Planning Implication: Trajectory optimization and Model Predictive Control (MPC) operate directly in state space to satisfy dynamic constraints and minimize costs like energy or jerk.

Workspace is the physical, three-dimensional environment in which the robot operates. It is the familiar Euclidean space (ℝ² or ℝ³) containing the robot's physical body and obstacles.

• Contrast with C-Space: C-Space is an abstract, often higher-dimensional representation; Workspace is the tangible, low-dimensional world. A point in C-Space maps to a specific placement of the entire robot in the Workspace.
• Obstacle Mapping: Obstacles defined in the Workspace are transformed into forbidden regions in C-Space through a process called obstacle mapping or C-Space obstacle (C-obst) computation.
• Task Specification: High-level goals (e.g., "move the cup to the table") are naturally specified in Workspace coordinates, which must then be translated into goals in C-Space via inverse kinematics.

Sampling-Based Planning is a class of algorithms that avoid explicitly constructing the complex geometry of C_free. Instead, they probe the space with random or deterministic samples to build a graph or tree representation of feasible paths.

• Core Principle: Algorithms like RRT (Rapidly-exploring Random Tree) and PRM (Probabilistic Roadmap) sample configurations, check them for collision (i.e., if they are in C_free), and connect valid samples.
• Probabilistic Completeness: These planners are not guaranteed to find a solution if one exists, but the probability of finding one approaches 1 as the number of samples increases.
• Scalability: This approach is the de facto standard for high-dimensional C-Spaces (e.g., >7 DOF) where geometric methods are computationally intractable.

A C-Space Obstacle is the region within the configuration space that corresponds to all robot configurations that result in a collision with a physical obstacle in the workspace.

• Formal Definition: For a workspace obstacle O, the C-obst is defined as: C-obst = { q ∈ C | R(q) ∩ O ≠ ∅ }, where R(q) is the robot geometry.
• Minkowski Sum: For a rigid robot translating in ℝ² or ℝ³, the C-obst for a point robot can be computed as the Minkowski sum of the physical obstacle and the robot's geometry (reflected about its origin).
• Complexity: Computing exact C-obsts for articulated robots with many degrees of freedom is extremely difficult, which is a key motivation for using collision checking within sampling-based planners instead.

The Degrees of Freedom of a robot is the minimum number of independent parameters (coordinates) needed to uniquely define its configuration. This number directly defines the dimensionality of its Configuration Space.

• Examples: A rigid body in 3D space has 6 DOF (3 translation, 3 rotation). A typical industrial robotic arm has 6 or 7 DOF. A mobile robot moving on a plane has 3 DOF (x, y, heading).
• C-Space Manifold: The DOFs determine the topological manifold of the C-Space. For example, a 2D planar robot's C-Space is ℝ² × S¹ (a cylinder).
• Curse of Dimensionality: Planning difficulty generally increases exponentially with the number of DOFs, as the volume of the C-Space grows astronomically, making exhaustive search impossible.