Python Path Planning for Robotics — Core Concepts

What Is Path Planning?

Path planning computes a collision-free route from a start position to a goal position given a map of obstacles. It is the “thinking” step before a robot moves — deciding not just where to go, but how to get there safely.

The problem splits into two layers in most robotics systems:

• Global planning: Find a path across the entire known map (done once or occasionally)
• Local planning: Adjust the path in real time to avoid newly detected obstacles (done continuously)

Grid-Based Search Algorithms

Dijkstra’s Algorithm

The foundational search algorithm. It explores outward from the start position in all directions equally, guaranteeing the shortest path but potentially searching the entire map. On a 1000×1000 grid, that means examining up to 1 million cells.

A* (A-Star)

A* improves on Dijkstra by adding a heuristic — an estimate of how far each cell is from the goal. The standard heuristic is Euclidean distance (straight line to the goal). A* preferentially explores cells that are both close to the start (low cost so far) and close to the goal (low estimated remaining cost).

The result: A* finds the same optimal path as Dijkstra but examines far fewer cells. In practice, A* on a grid explores 5–20% of the cells that Dijkstra would check.

D* and D* Lite

Variants designed for environments that change. When an obstacle appears in the planned path, D* Lite replans efficiently by reusing most of the previous computation instead of starting from scratch. Used in Mars rover navigation software.

Sampling-Based Algorithms

Grid-based methods struggle in high-dimensional spaces. A robotic arm with 6 joints has a 6-dimensional configuration space — a grid over 6 dimensions is impossibly large. Sampling-based methods avoid this by randomly probing the space.

RRT (Rapidly-exploring Random Tree)

RRT builds a tree of reachable positions by:

1. Picking a random point in the space
2. Finding the nearest existing tree node to that random point
3. Extending from that node toward the random point by a step distance
4. Checking if the extension collides with obstacles
5. Repeating until the tree reaches the goal

RRT is probabilistically complete — given enough time, it will find a path if one exists. However, the path it finds is rarely optimal. It tends to be jagged and unnecessarily long.

RRT*

An improved version that rewires the tree as it grows. After adding a new node, RRT* checks if any nearby existing nodes would have a shorter path through the new node, and rewires connections accordingly. Given enough iterations, RRT* converges to the optimal path.

PRM (Probabilistic Roadmap)

PRM works in two phases. In the learning phase, it scatters random points across free space and connects nearby points that have collision-free straight lines between them, building a graph (roadmap). In the query phase, it connects the start and goal to the roadmap and runs A* on the graph. PRM is efficient when you need to plan many different paths in the same environment.

Potential Field Methods

An alternative to search: treat the goal as an attractive force pulling the robot and obstacles as repulsive forces pushing it away. The robot follows the combined force field like a ball rolling downhill. This approach is simple and fast, making it popular for real-time local obstacle avoidance.

The fatal flaw is local minima. Two obstacles can create a “valley” that traps the robot away from the goal. Practical systems use potential fields only for local adjustments, paired with a global planner that provides waypoints.

Configuration Space

A subtle but important concept. Path planning does not happen in the physical world directly — it happens in “configuration space” (C-space). For a point robot on a 2D floor, C-space is just 2D (x, y). For a car, it is 3D (x, y, heading angle). For a robot arm with 6 joints, it is 6D (one dimension per joint angle).

Obstacles in the physical world become different shapes in C-space. A circular robot navigating around a rectangular obstacle needs the obstacle inflated by the robot’s radius in C-space — effectively shrinking the free space.

Common Misconception

“The shortest path is always the best path.” In robotics, the best path considers smoothness (sharp turns are hard for wheeled robots), distance from obstacles (staying centered in corridors is safer), energy cost (climbing costs more than flat movement), and dynamic feasibility (a car cannot turn in place). Production planners optimize for a weighted combination of these, not just distance.

One thing to remember: A* excels on grids for 2D navigation, RRT handles high-dimensional spaces like robot arms, and real systems combine a global planner for the big picture with a local planner for real-time obstacle dodging.