Path Planning

Definition

Path planning (also called motion planning) is the process of computing a collision-free trajectory for a robot to move from a start configuration to a goal configuration. It considers the robot's geometry, joint limits, and the obstacles in its environment to find a feasible and often optimal path.

Formula

f(n) = g(n) + h(n) \quad \text{(A* evaluation function)}

In-Depth Explanation

Path planning is a core capability of autonomous robots. It operates at two levels: 1. Global path planning: Computes an overall route from start to goal using a full map (run once or infrequently) 2. Local path planning: Dynamically avoids obstacles detected in real-time by sensors (run continuously) Configuration Space (C-space): Path planning operates in C-space, where each point represents a complete robot configuration (e.g., all joint angles for an arm, or (x, y, θ) for a mobile robot). Obstacles in the real world become regions in C-space that the planner must avoid. Classic planning algorithms: 1. Graph-based (discrete): - Dijkstra's algorithm: Finds shortest path in a weighted graph (optimal, but slow for large spaces) - A* (A-star): Dijkstra + heuristic → significantly faster, still optimal with admissible heuristic - D* Lite: Dynamic replanning as map updates 2. Sampling-based (continuous, high-DOF): - RRT (Rapidly-exploring Random Tree): Randomly samples C-space and grows a tree toward the goal - RRT* (RRT-star): Asymptotically optimal version of RRT - PRM (Probabilistic Roadmap Method): Builds a roadmap by sampling and connecting feasible configurations 3. Potential field methods: - Goal exerts attractive force, obstacles exert repulsive forces - Simple but susceptible to local minima 4. Optimization-based: - CHOMP, TrajOpt: Optimize trajectory quality (smoothness, clearance) - Used in robotic arm motion planning For mobile robots (ROS Nav2 stack): - Global planner: NavFn (Dijkstra/A*) or Smac Planner - Local planner: DWA (Dynamic Window Approach) or TEB (Timed Elastic Band) - Costmap: 2D or 3D occupancy grid used by planners A* heuristic: f(n) = g(n) + h(n) where g(n) = cost from start, h(n) = estimated cost to goal Practical example: A mobile robot in a hospital uses Nav2. The global planner (A*) computes a path from Room 101 to the pharmacy on an occupancy map. The local planner (DWA) continuously adjusts the velocity commands to follow the global path while dynamically avoiding staff and carts detected by the LiDAR. In robotic arm planning, MoveIt uses OMPL (Open Motion Planning Library), which includes RRT, RRT*, PRM, and many other algorithms, to plan collision-free joint trajectories.

Related Terms

Inverse Kinematics (IK)

Inverse Kinematics (IK) is the mathematical process of determining the joint parameters (angles or displacements) required to place a robot's end-effector at a desired position and orientation in space. It is the inverse of forward kinematics, which calculates end-effector pose from known joint values.

LiDAR

LiDAR (Light Detection and Ranging) is a remote sensing technology that measures distances by emitting laser pulses and detecting the reflected light. In robotics, LiDAR sensors generate 2D or 3D point clouds of the surrounding environment, enabling obstacle detection, mapping, and localization.

ROS (Robot Operating System)

ROS (Robot Operating System) is an open-source middleware framework for robot software development. Despite its name, ROS is not a traditional operating system — it provides tools, libraries, and conventions that simplify the creation of complex and reusable robot software across a wide variety of robotic platforms.

SLAM (Simultaneous Localization and Mapping)

SLAM (Simultaneous Localization and Mapping) is the computational problem of constructing or updating a map of an unknown environment while simultaneously tracking a robot's location within it. It is a foundational capability for autonomous mobile robots operating without GPS or pre-built maps.