Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 46 ยท Robotics

Motion and Path Planning: Grids, Potential Fields and RRT

Learn robot motion planning in Python: configuration space, A* on occupancy grids, potential fields and their traps, probabilistic roadmaps and RRT with plots.

A robot that knows where it is and where it wants to go still has to answer a hard question: how do I get there without hitting anything? Motion planning (or path planning) computes a collision-free route from a start to a goal. It is search once again, but in a space that is continuous, high dimensional and full of obstacles, so the methods split into families depending on how they tame that space.

This lesson walks through four of them. Grid search with A* turns the world into cells. Potential fields let the goal pull and the obstacles push. Probabilistic roadmaps and RRT sample the space randomly instead of covering it. All four run live below, with plots.

Configuration space

Planning gets simpler when you change what the robot is. A configuration is a complete description of the robot's pose, such as (x, y, heading) for a mobile robot or a list of joint angles for an arm (see kinematics). The configuration space (C-space) is the set of all configurations. An obstacle in the real world becomes a forbidden region of C-space: all configurations in which any part of the robot touches it. The robot itself shrinks to a single point moving through that space.

For a circular robot, the conversion is easy: grow every obstacle by the robot's radius, and the robot can be treated as a point. For an arm with two joints, C-space is a flat sheet of (t1, t2) pairs, and a single obstacle in the workspace becomes a curved, twisted blob in it. The dimension of C-space equals the robot's degrees of freedom, and that is what makes planning hard: a 7-joint arm lives in seven dimensions, where covering the space with a grid is hopeless.

graph TD
    P["Motion planning"] --> G["Grid search<br/>A* on cells"]
    P --> F["Potential fields<br/>follow forces"]
    P --> S["Sampling based"]
    S --> R["PRM<br/>build a roadmap, then query"]
    S --> T["RRT<br/>grow a tree from the start"]

Four classic planning families. Grids and fields work well in low dimensions; sampling scales to many joints.

Planning on an occupancy grid

An occupancy grid divides the floor into cells marked free or blocked. Robot vacuums, warehouse robots and video-game characters all plan on grids. Once you have the grid, the problem is exactly the graph search from earlier lessons: states are cells, actions are moves to neighbors, step costs are distances, and the heuristic is the straight-line style distance to the goal.

Two details separate a robotics grid planner from the classroom version:

  • Eight-connected moves. A robot can move diagonally, at a cost of sqrt(2) instead of 1. The matching admissible heuristic is the octile distance: take the diagonal steps you can, then straight steps for the rest. (A heuristic is admissible if it never overestimates; see admissible heuristics.)
  • Inflation. Planning for a point on the raw grid would let a real, fat robot scrape walls. We inflate each obstacle cell by the robot's radius first.

The program below plans on a 10 by 20 map twice, for a robot of radius 0 (a point) and radius 1. It also runs the same search with a zero heuristic (which is Dijkstra's algorithm) to show how much the heuristic saves.

Python A* on an occupancy grid with inflated obstacles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the point robot the cheapest route costs 24.49 and A* expands 66 cells, while the zero-heuristic search expands 178. With radius 1 the walls grow, the route has to detour through the gaps that remain, the cost rises to 25.66, and the heuristic still halves the work (50 cells versus 90). Look at the second map: the inflated obstacles are drawn as solid blocks, and the path never touches them, which is exactly what a real robot body needs.

A grid path is made of 45-degree and axis-aligned segments, so it is not the true shortest path through continuous space. Real systems smooth it afterward, or use variants such as Theta* that allow any-angle moves, and a separate controller then follows the smoothed path.

Potential fields

A completely different idea comes from physics. Imagine the goal as a magnet that attracts the robot and every obstacle as a magnet of the same polarity as the robot that pushes it away. At any point the robot adds up the forces and takes a small step in that direction:

  • Attractive force: proportional to the vector toward the goal, k_att * (goal - p).
  • Repulsive force: zero beyond an influence distance, and growing rapidly as the robot approaches an obstacle's surface.

Potential fields are cheap (one force evaluation per step), smooth and reactive, so they are used for real-time obstacle avoidance. Their famous weakness is local minima: places where attraction and repulsion cancel and the robot stops far from the goal, just as hill climbing stalls on a local peak. The program compares a single obstacle, which the robot slides around, with a wall of three obstacles placed directly between the start and the goal.

Python Potential fields: success and a local minimum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With one obstacle slightly off the straight line, the robot is nudged around it and reaches the goal in 103 steps. With the wall, it walks up to x = 3.22 and stops there for good: the push from the three obstacles exactly balances the pull of the goal along y = 5, and by symmetry nothing nudges it sideways. A real robot would be jostled by noise, but the lesson stands: a potential field alone gives no guarantee. Common remedies are random perturbations, a "wall-following" mode when stuck, or using the field only as a local obstacle-avoidance layer under a global planner such as A*.

Probabilistic roadmaps

When the space has many dimensions, a grid with a million cells in two dimensions becomes a million to the seventh power in seven. Sampling-based planners avoid building the whole space. They draw random configurations, keep those that are collision-free, and use only a collision checker (a function that says "this pose touches something" or not) to explore. They do not need an explicit description of the obstacles in C-space.

The probabilistic roadmap (PRM) works in two phases:

  1. Learning phase. Sample many random collision-free configurations. Connect each to its nearby neighbors when the straight segment between them is free. The result is a graph, the roadmap.
  2. Query phase. Add the start and goal to the roadmap and run a graph search (A* or Dijkstra) to get the path.

The roadmap can be reused for many queries as long as the environment does not change, which is why PRMs suit static factory cells.

Python Build a probabilistic roadmap and query it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The roadmap has 120 nodes and 706 edges, and the best path through it is 13.86 long against a straight-line distance of 12.73. The quality depends on the number of samples: too few and the roadmap may be disconnected around a narrow gap (try changing 120 to 25 and see "no path"); too many and the connection step gets slow. The guarantee is probabilistic completeness: if a path exists, the probability of finding it tends to 1 as the number of samples grows.

Rapidly-exploring random trees

The RRT is designed for a single query. It grows one tree from the start and tries to reach the goal:

  1. Sample a random point in the space (now and then, the goal itself: the goal bias).
  2. Find the nearest node already in the tree.
  3. Steer: move a fixed small step from that node toward the sample.
  4. If the new segment is collision-free, add the node to the tree.
  5. Stop when a node is close enough to the goal.

The magic is in step 2. Nearest-node selection biases growth toward unexplored space: a random sample far out in empty territory is closest to a node at the frontier, so the tree races outward into big open regions. RRTs also cope with robots that cannot move in straight lines (cars, for example), because the steering step can follow the robot's real motion model.

Python Grow an RRT and smooth its path

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each seed grows a different tree (128 to 180 nodes), and each raw path wanders: 15.26, 15.86 and 17.05 long. RRT finds a path fast but not a good one, because the tree follows random turns. A simple shortcutting pass, which repeatedly jumps to the farthest waypoint you can see directly, cuts the lengths to 14.56, 14.58 and 14.14. A variant called RRT* rewires the tree as it grows and converges toward the optimal path, at the cost of more computation; production planners such as those in robot arm software mostly use RRT-style planners followed by smoothing.

Choosing a planner

  • Small 2D map, known obstacles: A* on a grid (with inflation and smoothing). Simple, optimal on the grid, predictable.
  • Fast local reactions to unexpected obstacles: potential fields or similar local methods, under a global planner.
  • Many joints (arms), static environment, many queries: PRM.
  • Many joints, one query, complex motion constraints: RRT or RRT*.

Real navigation stacks combine them: a global planner finds a route, a local planner tracks it while dodging moving obstacles, and a replanner reacts when the map changes. The project at the end of this track, a robot maze navigator, puts A* and replanning to work together.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the main benefit of working in configuration space?

    In C-space the whole robot is one point, and obstacles are grown to forbidden regions, so planning becomes pathfinding for a point. The dimension is the robot's degrees of freedom.
  2. 2. Why is the octile distance used as the heuristic for A* on an eight-connected grid?

    Octile distance is the exact cost in an obstacle-free eight-connected grid (diagonals cost sqrt 2), so with obstacles the true cost can only be higher: it is admissible.
  3. 3. What is the classic failure of potential-field planning?

    Attractive and repulsive forces can cancel at a point that is not the goal, so a simple gradient-following robot stops there.
  4. 4. Which statement describes a probabilistic roadmap (PRM)?

    A PRM builds a reusable graph of collision-free samples and connections, then answers each start-goal query with a graph search.
  5. 5. Why is an RRT path often smoothed afterward?

    RRT finds feasible paths quickly but they follow random turns. Shortcutting or RRT* improves their length.

Summary

  • Configuration space turns a robot of any shape into a point and obstacles into forbidden regions; its dimension equals the degrees of freedom.
  • On occupancy grids, run A* with eight-connected moves, the octile heuristic and obstacles inflated by the robot's radius.
  • Potential fields are cheap and reactive but can stall in local minima, so use them only locally.
  • PRM samples free configurations, connects neighbors and searches the roadmap; it is reusable and probabilistically complete.
  • RRT grows a tree toward random samples with goal bias, finds feasible paths fast, and needs smoothing or RRT* for quality.
  • Real robots combine a global planner, a local planner and replanning.

Next: Project: Sliding-Puzzle Solver.