Path Planning: Guiding Machines
Pascual Vila
Robotics Instructor // Code Syllabus
"Without an optimal path, an autonomous system is just a machine with sensors. Path planning is the algorithmic bridge between 'where I am' and 'where I need to be'."
1. Configuration Space (C-Space)
Before running any algorithm, we must mathematically simplify the problem. A robot has physical dimensions. Instead of checking if a rectangle fits through a door, we inflate the obstacles by the robot's radius. This creates the Configuration Space, allowing us to treat the robot as a single infinitely small point.
2. A* Search Algorithm
For grid-based 2D maps, A* is the gold standard. It uses a priority queue based on the formula: f(n) = g(n) + h(n)
- g(n): The exact cost from the starting node to node n.
- h(n): The heuristic—an estimated cost from node n to the goal.
If the heuristic is admissible (meaning it never overestimates the true cost), A* is mathematically guaranteed to find the shortest path.
3. Rapidly-exploring Random Trees (RRT)
What happens when you have a 6-axis robotic arm? Discretizing a 6-dimensional space into a grid requires astronomical amounts of memory. A* fails here.
RRT solves this by sampling. Instead of checking every grid cell, it picks a random point in space, finds the nearest existing branch of the tree, and grows a tiny step toward the random point. Over thousands of iterations, it rapidly searches high-dimensional spaces to find a valid (though not always optimal) path.
❓ Neural Query FAQ
What is the difference between Dijkstra and A* algorithms?
Dijkstra expands outward in all directions equally. A* uses a heuristic $h(n)$ to "pull" the search toward the goal, making it significantly faster while remaining optimal.
Why use RRT over A* for autonomous systems?
A* suffers from the "curse of dimensionality". In complex configuration spaces (like a drone flying in 3D or a multi-jointed arm), grid-search memory usage explodes. RRT is sampling-based, meaning it explores continuous space efficiently without needing a grid.