Motion Planning

These algorithms avoid the computational complexity of explicitly modeling high-dimensional configuration spaces by using random or deterministic sampling to probe for feasible paths. They are probabilistically complete, meaning the probability of finding a solution approaches 1 given infinite time.

• RRT (Rapidly-exploring Random Tree): Incrementally builds a space-filling tree biased toward unexplored regions. Widely used for its simplicity and effectiveness in high-dimensional spaces.
• PRM (Probabilistic Roadmap): Constructs a graph of collision-free configurations in a preprocessing phase. Efficient for multiple queries in static environments.
• Key advantage: Scalability to robots with many degrees of freedom, such as robotic arms or humanoid robots.

These methods treat the planning problem as a search through a discrete graph of states. They are optimal for the given graph representation and are foundational for path planning on grids or roadmaps.

• A Algorithm*: A best-first search using a cost function f(n) = g(n) + h(n), where g(n) is the cost from the start and h(n) is an admissible heuristic estimating cost to the goal. Guarantees optimality if the heuristic is admissible.
• Dijkstra's Algorithm: A special case of A* with a heuristic of zero. Explores all nodes in order of increasing cost from the start.
• Primary use: Low-dimensional planning (e.g., 2D navigation maps) or searching the graphs built by sampling-based methods like PRM.

Also known as local planning or direct optimization, this approach formulates motion planning as a continuous optimization problem. It computes a smooth, time-parameterized path that minimizes a cost function (e.g., energy, jerk, time) subject to dynamics and collision constraints.

• Mathematical Form: Solves for a sequence of states and controls that minimize total cost while satisfying differential constraints ẋ = f(x, u).
• Connection to Control: Tightly linked to Model Predictive Control (MPC), which solves a finite-horizon trajectory optimization problem online in a receding horizon fashion.
• Output: A dynamically feasible trajectory specifying positions, velocities, and accelerations over time.

These algorithms provide complete, exact solutions by performing a geometric decomposition of the free space. They construct an explicit representation of all possible paths.

• Visibility Graphs: For polygonal obstacles in 2D, the shortest path is a sequence of straight lines connecting the start, goal, and vertices of obstacles. The planner builds a graph of these visible connections.
• Cell Decomposition: Divides the free space into simple, non-overlapping cells (e.g., trapezoids). A connectivity graph between cells is then searched.
• Characteristic: They are complete—they will find a solution if one exists, or definitively report failure. However, they are generally limited to low-dimensional (typically 2D or 3D) problems with geometric obstacles.

Designed for real-time operation in dynamic environments, these algorithms compute immediate velocity or steering commands based on current sensor data, often without a pre-computed global path.

• Dynamic Window Approach (DWA): Samples achievable velocities within the next time interval, simulates the resulting short-term trajectories, and selects the one that maximizes an objective (progress, clearance, speed).
• Potential Fields: Treats the robot as a particle moving in an artificial field—attracted to the goal and repelled from obstacles. The negative gradient of the combined field provides the steering direction.
• Use case: Collision avoidance against moving obstacles and final-stage execution of a globally planned path.

These methods use machine learning, particularly deep reinforcement learning and imitation learning, to train neural network policies that map sensor inputs (or a world model) directly to actions or planned paths.

• End-to-End Visuomotor Policies: A neural network processes pixel input and outputs joint torques or velocities, bypassing explicit geometric planning.
• Learning for Search Guidance: A learned heuristic function can dramatically accelerate algorithms like A* in complex environments.
• Advantage: Can capture complex, hard-to-model aspects of the world and produce highly adaptive behaviors. A key challenge is ensuring safety and generalization beyond training distributions.

The Configuration Space (C-Space) is a fundamental mathematical abstraction in motion planning. It is a space where every possible state, or configuration, of a robot is mapped to a single point. This transformation converts the complex physical geometry of the robot and its obstacles into simpler, forbidden regions within this abstract space. For a simple 2D mobile robot, its C-space might be its (x, y) position. For a robotic arm with N joints, its C-space is an N-dimensional space where each dimension is a joint angle. Planning a path in C-space, rather than the physical workspace, simplifies collision checking to determining if a point lies within an obstacle region.

Path Planning is a core subset of motion planning focused on finding a purely geometric, collision-free route from a start to a goal configuration. It typically deals with the topology of the free space without considering timing, dynamics, or velocities. The output is a sequence of waypoints or a continuous curve through the Configuration Space. It is often distinguished from trajectory planning or trajectory optimization, which adds the dimension of time. Common algorithms include:

• A*: A heuristic graph search algorithm optimal for finding shortest paths on a discretized grid.
• RRT (Rapidly-exploring Random Tree): A sampling-based algorithm efficient for high-dimensional spaces.
• PRM (Probabilistic Roadmap): A sampling-based method that builds a reusable graph of the free space.

Trajectory Optimization is the process of computing a time-parameterized path—a trajectory—that not only avoids collisions but also minimizes a cost function (e.g., energy, execution time, jerk) while satisfying the robot's dynamic constraints (e.g., torque limits, acceleration bounds). It transforms a geometric path into a physically executable motion profile. This is a continuous optimization problem often solved using techniques like direct collocation or sequential quadratic programming. It is closely related to Model Predictive Control (MPC), which performs receding-horizon trajectory optimization online to handle disturbances.

Sampling-Based Planning is a dominant algorithmic paradigm for motion planning in complex, high-dimensional Configuration Spaces. Instead of explicitly modeling the geometry of obstacles, these algorithms probe the C-space with random or deterministic samples to incrementally build a representation of the free space. They are probabilistically complete, meaning the probability of finding a solution, if one exists, approaches 1 as computation time increases. Key algorithms include:

• PRM (Probabilistic Roadmap): A multi-query method that builds a graph (roadmap) in a preprocessing phase for later path queries.
• RRT (Rapidly-exploring Random Tree) & RRT*: Single-query methods that grow a tree rapidly toward unexplored regions, with RRT* providing asymptotic optimality. These methods are essential for planning for robotic arms and mobile manipulators.

Collision Avoidance refers to the real-time, reactive layer of control that dynamically adjusts a robot's trajectory to prevent contact with unexpected, unmapped, or moving obstacles. It operates on a shorter timescale than global path planning. While motion planning generates a nominal global path, collision avoidance uses immediate sensor data (e.g., from LiDAR or depth cameras) to compute repulsive forces or local maneuvers. Common techniques include the Artificial Potential Field method, where obstacles generate repulsive fields and the goal generates an attractive field, and Velocity Obstacles, which compute the set of velocities that would lead to a collision within a time window.

Task Decomposition is the higher-level cognitive process of breaking a complex, abstract goal into a structured sequence or hierarchy of simpler, executable subtasks. It is the "task" in Task and Motion Planning (TAMP). For example, the goal "make coffee" decomposes into subtasks like "navigate to kitchen," "grasp mug," "operate machine." Each subtask may then require its own motion plan. This is often modeled using formalisms like Hierarchical Task Networks (HTNs) or Behavior Trees. The output is a task graph or plan where nodes are actions and edges are dependencies, which is then passed to the motion planner for geometric feasibility checking and path generation.