State Space

The dimensionality of a state space is defined by the number of independent variables (degrees of freedom) required to uniquely specify a system's configuration. For a rigid body in 3D space, this is typically 6 (position: x, y, z; orientation: roll, pitch, yaw). A robotic arm with N joints has an N-dimensional configuration space. High-dimensional state spaces (e.g., >10 DOF) are a primary source of computational complexity, leading to the 'curse of dimensionality' where planning and search become exponentially harder.

A state space can be continuous or discrete. A continuous state space contains an uncountably infinite number of states, such as all possible joint angles for a robot arm. Most physical systems are modeled with continuous spaces. A discrete state space has a finite or countably infinite set of distinct states, often used in high-level task planning (e.g., 'robot in room A' vs. 'robot in room B'). Many algorithms discretize continuous spaces for tractability.

Connectivity refers to whether a path exists between two states within the space. The reachable state space is the subset of all theoretically possible states that a system can actually achieve from a given initial state, considering its kinematic and dynamic constraints. Obstacles in the physical world create holes or forbidden regions in the state space, breaking connectivity. Analyzing connectivity is central to motion planning feasibility.

A state space often has a distance metric (e.g., Euclidean distance in Cartesian space, angular distance for orientations) that quantifies similarity between states. This metric is crucial for nearest-neighbor searches in sampling-based planners like RRT. The topology (global shape) of the space matters: the space of 2D orientations (SO2) is topologically a circle, while 3D orientations (SO3) have the complex topology of a 3-sphere, affecting how paths are represented and optimized.

The choice of state representation is critical. A good representation is sufficient (captures all relevant info), efficient for computation, and often low-dimensional. Common representations include:

• Raw Sensor Data: High-dimensional, noisy.
• Feature Vectors: Extracted relevant parameters.
• Latent Embeddings: Learned compact representations from world models. Abstraction involves creating a simplified, higher-level state space (e.g., symbolic states) to make planning tractable for complex, long-horizon tasks.

The configuration space (C-Space) is a specific type of state space where each point represents a unique geometric arrangement of the robot's bodies, defined solely by its joint angles or pose. The state space is often a superset of C-Space, as it may include dynamic variables like velocities, accelerations, and internal system modes. Formally: C-Space + time derivatives + other internal variables = Full State Space. This distinction separates kinematic planning from dynamic control.

For a wheeled robot navigating a 2D plane, the state space is defined by its pose (position and orientation). A common representation is (x, y, θ), where x and y are Cartesian coordinates and θ is the heading angle. The configuration space (C-Space) extends this to include the robot's geometry, mapping physical obstacles to forbidden regions. Planning algorithms like RRT or A* search through this continuous state space to find a collision-free path from start to goal.

The state of a multi-jointed robotic arm is defined by its joint angles. For a 6-degree-of-freedom arm, the state is a 6D vector: (θ₁, θ₂, θ₃, θ₄, θ₅, θ₆). Each unique combination of angles corresponds to a specific end-effector position and orientation, calculated via forward kinematics. Motion planning in this high-dimensional space involves solving inverse kinematics and avoiding self-collisions, often using sampling-based planners like PRM.

In discrete games like Chess, the state space is the set of all possible board configurations. The state is defined by:

• The type and position of each piece on the 8x8 board.
• Which player's turn it is.
• Castling rights and en passant status. This creates a finite but astronomically large state space (~10⁴⁷ nodes). AI agents use heuristic search algorithms like Minimax with Alpha-Beta pruning to explore this tree and evaluate future states, aiming for checkmate.

A self-driving car's state is a high-dimensional vector fusing sensor data. A core representation includes:

• Ego-state: (x, y, z, roll, pitch, yaw, velocity, acceleration).
• Object states: For each detected vehicle/pedestrian: (position, velocity, heading, classification).
• Road context: Lane topology, traffic signals, and road markings. This partially observable state is estimated from LiDAR, cameras, and GPS. Model Predictive Control (MPC) uses this state to optimize a safe, smooth trajectory over a finite horizon.

In Reinforcement Learning (RL), an agent interacts with an environment defined by its state space. In the classic CartPole benchmark, the state is a 4D continuous vector: (cart_position, cart_velocity, pole_angle, pole_angular_velocity). The agent's policy (a neural network) maps this state to an action (move left/right). The agent's goal is to learn a policy that maximizes cumulative reward by exploring and exploiting this state space. Complex tasks use world models to learn compressed state representations.

A quadrotor drone's dynamic state is defined by 12+ variables:

• Position: (x, y, z) in world coordinates.
• Orientation: Roll (φ), Pitch (θ), Yaw (ψ) angles.
• Linear Velocity: (vx, vy, vz).
• Angular Velocity: (p, q, r). This 12-dimensional state space is governed by nonlinear dynamics. Flight controllers use state feedback (from IMUs and vision) to stabilize attitude. High-level task and motion planning might decompose a mission (e.g., 'inspect bridge') into a sequence of target states in this space.

A mathematical abstraction where every possible physical configuration of a robot (defined by its joint angles) is mapped to a single point. This transforms the problem of navigating a physical robot around obstacles into the simpler problem of navigating a point through forbidden regions in this abstract space. It is a core representation for motion planning algorithms.

• Key Transformation: Converts complex robot geometry into a point robot.
• Central to Sampling-Based Planners: Algorithms like RRT and PRM operate directly in C-Space.

The set of all discrete or continuous control inputs an agent can execute. In robotics, this defines the primitive actions available to transition between states in the state space. For a mobile robot, this might be velocity commands; for a manipulator, joint torque commands.

• Discrete vs. Continuous: Can be a finite set of moves or an infinite continuum of motor commands.
• Relation to Policy: A control policy is a mapping from the state space to the action space.

A learned or engineered compact representation of an environment that enables an agent to predict future states without direct interaction. A world model acts as a simulator inside the agent's mind, allowing for planning via mental rehearsal. It compresses the raw state space into a latent representation for efficient reasoning.

• Predictive Function: f(state, action) -> next_state.
• Enables Model-Based RL: Agents can plan sequences of actions by "imagining" their consequences.

A class of graph search algorithms used to find optimal paths through a state space. They use a heuristic function h(n) to estimate the cost from any state to the goal, guiding exploration efficiently. The A algorithm* is the canonical example, guaranteeing an optimal solution if the heuristic is admissible (never overestimates).

• Core Mechanism: Balances cost-so-far (g(n)) and estimated cost-to-go (h(n)).
• Application: Fundamental to many task planning and path planning systems.

Algorithms designed to solve motion planning problems in high-dimensional state spaces (like C-Space) by probing the space with random samples. They avoid the computational intractability of explicitly modeling all obstacles.

• RRT (Rapidly-exploring Random Tree): Builds a tree incrementally from the start state, biased to explore unexplored regions. Used for single-query problems.
• PRM (Probabilistic Roadmap): Builds a graph of feasible states in a preprocessing phase. Used for multi-query problems.

The process of computing a smooth, time-parameterized path through state space that minimizes a cost function (e.g., energy, time, jerk) while satisfying dynamic constraints and avoiding collisions. It refines a geometric path into a physically executable motion profile.

• Input: Often a geometric path from a planner.
• Output: A sequence of states and their time derivatives (velocity, acceleration).
• Methods: Include Model Predictive Control (MPC) and direct collocation.