Motion Planning

These algorithms avoid explicitly modeling obstacle geometry by sampling the configuration space. Rapidly-exploring Random Trees (RRT) grow a tree from the start state by randomly sampling and connecting to the nearest node, biasing growth toward unexplored regions. Probabilistic Roadmaps (PRM) pre-compute a network of feasible configurations (a roadmap) in the free space, then query it for paths between specific start and goal points. These methods are probabilistically complete—they will find a solution if one exists, given enough time—and excel in high-dimensional spaces.

These methods treat the environment as a discrete graph of connected states. A* is the foundational optimal search algorithm, 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. D* (Dynamic A*) and its variant D Lite* are incremental search algorithms that efficiently replan when edge costs change (e.g., new obstacles are detected), making them essential for real-time navigation in dynamic environments. These algorithms guarantee optimality but require a discretized state space.

This approach formulates planning as a continuous optimization problem. It directly computes smooth, dynamically feasible trajectories that minimize objectives like energy or time while satisfying constraints (e.g., acceleration limits, obstacle avoidance). Model Predictive Control (MPC) solves a finite-horizon optimization at each time step, executing the first control input and then re-planning. CHOMP (Covariant Hamiltonian Optimization for Motion Planning) and STOMP (Stochastic Trajectory Optimization for Motion Planning) treat the trajectory as a parameterized curve and optimize it using gradient-based or stochastic methods. This yields high-quality paths but is computationally intensive.

Designed for real-time obstacle avoidance in unknown or dynamic settings, these algorithms compute immediate steering commands based on local sensor data. The Dynamic Window Approach (DWA) searches the space of achievable velocities (considering robot dynamics) over a short time window and selects the velocity pair that maximizes an objective balancing progress toward the goal, speed, and clearance from obstacles. Potential Field Methods treat the robot as a particle moving in an artificial field where the goal exerts an attractive force and obstacles exert repulsive forces. While fast, these methods can suffer from local minima (e.g., getting stuck).

Machine learning is used to overcome limitations of classical planners. Imitation Learning trains a policy (often a neural network) to mimic expert demonstrations of successful paths. Reinforcement Learning (RL) agents learn planning policies through trial-and-error to maximize a reward signal. A Goal-Conditioned Policy takes the current state and a goal representation as input, enabling generalization to novel goals. These methods can capture complex, hard-to-model behaviors and generalize across environments but require significant data and lack the formal guarantees of classical planners.

This approach decomposes complex problems into layers of abstraction. A task planner (or symbolic planner) operating in a high-level domain (e.g., using PDDL) might generate a sequence of abstract actions like NavigateTo(RoomA), PickUp(Object). A motion planner then solves the geometric sub-problem for each action (e.g., finding a collision-free path to the object). Hierarchical Reinforcement Learning (HRL) implements this idea within RL, where a high-level policy selects among temporally extended skills (options) which are themselves learned low-level policies. This enables solving long-horizon tasks efficiently.

Autonomous Mobile Robots (AMRs) in logistics and manufacturing use motion planning to navigate dynamic warehouse floors. Algorithms like Rapidly-Exploring Random Trees (RRT)* and Hybrid A* compute collision-free paths around moving obstacles (e.g., people, other robots) while optimizing for time and energy. Key challenges include real-time replanning and kinodynamic constraints (acceleration, turning radius).

• Example: An AMR uses a local planner to adjust its path in real-time when a pallet is unexpectedly placed in its corridor, while a global planner recalculates the overall route to the loading dock.

Self-driving cars perform hierarchical motion planning across multiple layers. A behavioral layer decides lane changes or merges, a global route planner charts the course using road networks, and a local motion planner generates smooth, safe trajectories. This often involves Model Predictive Control (MPC) to optimize a trajectory over a short horizon, obeying vehicle dynamics and traffic rules while reacting to pedestrians and other cars.

• Critical Constraint: Plans must be dynamically feasible, meaning the generated path must be physically executable by the car's steering and acceleration systems.

Industrial robot arms performing tasks like welding, painting, or circuit board assembly require precise manipulation planning. This involves planning paths in configuration space for multi-jointed arms to avoid self-collision and collisions with the environment. For complex assembly in cluttered spaces, planners must consider grasp planning and fine-motion planning with contact. Sampling-based planners like Probabilistic Roadmaps (PRM) are commonly used for these high-dimensional problems.

Drones for infrastructure inspection, delivery, or cinematography use motion planning to fly through complex 3D environments. They must plan paths that consider aerodynamic constraints, battery life, and no-fly zones. For inspecting a bridge or wind turbine, the planner generates a coverage path that ensures every surface is viewed. In cluttered environments like forests or urban canyons, real-time sensor-based planning with octree mapping is used to avoid previously unknown obstacles.

The broader computational process of generating a sequence of actions (a plan) to transform an initial state into a goal state. Motion planning is a specialized form of automated planning focused on physical movement through configuration space.

• Classical vs. Motion Planning: Classical planning (e.g., STRIPS) often uses symbolic, discrete states (e.g., 'block A is on block B'), while motion planning deals with continuous, geometric states (e.g., robot joint angles, XYZ coordinates).
• Corrective Action Context: When an agent detects it is in an erroneous state, it triggers an automated planning subroutine to generate a recovery plan, which may be a motion plan if physical repositioning is required.

A sampling-based algorithm designed to efficiently search high-dimensional, continuous spaces for feasible paths, making it highly effective for complex motion planning problems.

• How it Works: Incrementally builds a space-filling tree by randomly sampling points in the configuration space and extending the tree toward them.
• Key Advantage: Excels in spaces with narrow passages and is probabilistically complete (guaranteed to find a path if one exists, given enough time).
• Application: Widely used in robotics for arm manipulation, drone navigation, and autonomous vehicle planning where the environment is not fully known in advance.

The process of computing not just a feasible path, but an optimal sequence of control inputs and state trajectories that minimizes a cost function (e.g., energy, time, jerk) while satisfying dynamics and constraints.

• Path vs. Trajectory: A path is a geometric curve. A trajectory is a path parameterized by time, including velocities and accelerations.
• Corrective Action Use: After a motion planner like RRT finds a rough path, trajectory optimization refines it into a smooth, efficient, and dynamically feasible motion for execution.
• Methods: Includes direct (shooting, collocation) and indirect (calculus of variations) methods, often solved via nonlinear programming.

An advanced, online control strategy that repeatedly solves a finite-horizon trajectory optimization problem at each control step, executing only the first action before re-planning with new sensor data.

• Core Principle: Uses an explicit model of the system's dynamics to predict future states and optimize a sequence of controls, providing inherent feedback for disturbance rejection.
• Link to Motion Planning: MPC functions as a receding-horizon motion planner. It is the dominant method for dynamic systems like self-driving cars and drones that require real-time, reactive correction to unforeseen obstacles or errors.
• Corrective Action: Embodies a continuous planning-and-execution loop, making it ideal for systems that must constantly adjust their motion plan based on new observations.

The fundamental mathematical representation in motion planning, where every possible state of a robot is represented as a single point.

• Definition: The set of all possible configurations (e.g., joint angles for a robotic arm, pose [x, y, theta] for a mobile robot).
• C-Obstacles: Physical obstacles in the workspace are mapped to forbidden regions in C-space. Motion planning then becomes the problem of finding a continuous curve for a point (the robot) from a start point to a goal point while avoiding C-obstacles.
• Dimensionality: The complexity of planning grows with the dimensionality of the C-space, which is why sampling-based planners like RRT are essential for robots with many degrees of freedom.

A classic sampling-based motion planning method that builds a graph (roadmap) of feasible configurations in C-space during a preprocessing phase, which can then be queried to find paths between specific start and goal points.

• Two-Phase Approach: 1) Learning Phase: Randomly sample collision-free configurations and connect nearby ones with simple local planners. 2) Query Phase: Connect the start and goal to the roadmap and search the graph for a path.
• Best For: Multi-query planning problems in static environments, where the same roadmap can be reused for many different start-goal pairs.
• Contrast with RRT: PRM is multi-query and builds a graph covering the free space. RRT is typically single-query and builds a tree biased toward exploration.