M4-T3 — PRM and RRT

Learning objectives

After this lesson, you should be able to:

• Build a roadmap with the PRM learning and query phases and say when it pays off.
• Write the RRT extend step: sample, find the nearest node, steer by at most η, check the edge.
• Explain the Voronoi bias of RRT and the role of goal bias.
• State what probabilistic completeness means and why neither algorithm returns a shortest path.

The intuition

PRM is a road network you build before you need it. Scatter points in the free space, join each point to a few near neighbours when the straight line between them is free, and you have a graph. To plan, attach the start and the goal to the graph and run Dijkstra or A* on it (module 3). If the building does not change, the same roadmap answers every later question at the price of a graph search. Scout could keep one for the hospital wing.

RRT is a tree that grows towards the unexplored. Start with the start pose as the root. Repeatedly draw a random point anywhere in the space, find the tree node closest to it, and take a short step from that node towards the point. If the step is free, the new node joins the tree. A random point in a large empty region is closest to a node on the edge of the tree, so the tree stretches out into the empty parts almost by itself. When a node lands near the goal, the path is the chain of parents back to the root.

RRT needs no preparation and no map of free space. It suits one question asked once, such as the arm that must move now, or the tug in a freshly rearranged yard.

The mathematics

PRM

1. Learning phase. Draw n configurations; keep those that are collision-free as the vertices.
2. Connect. For each vertex, find its k nearest vertices (or all within a radius) and try the local planner, usually a straight edge checked by sampling (lesson M4-T2). Keep the edges that are free.
3. Query phase. Connect the start and the goal to the roadmap in the same way and run a graph search for the shortest path in the graph.

The cost is dominated by collision tests: about n·k edge attempts. The roadmap is reusable as long as the obstacles do not change, which is why PRM is called a multi-query planner. If the roadmap has several components, the query may fail even though a path exists, and the usual repair is to add samples or to connect components.

RRT

T ← { xstart }
repeat:
    q       ← sample()                       (with probability pgoal: q ← xgoal)
    xnear  ← the node of T nearest to q
    xnew   ← xnear + η · (q − xnear) / |q − xnear|      if |q − xnear| > η, else q
    if the edge xnear → xnew is free: add xnew to T with parent xnear
until xnew is within the goal radius of xgoal

η

the step size: the farthest a single extension can reach.

p_goal

goal bias: the fraction of samples that are replaced by the goal. 5–10% is typical.

x_near, x_new

the nearest tree node and the node being added.

The path is read back by following parents from the node that reached the goal. A slight variant, RRT-Connect, grows one tree from the start and one from the goal and tries to join them greedily; it is often much faster in practice.

The Voronoi bias

The nearest-node rule means that a random sample selects the node whose Voronoi region (the set of points closer to it than to any other node) contains the sample. Nodes with large regions are picked most often, and the largest regions belong to nodes at the frontier of the tree, facing large unexplored space. The tree therefore expands towards unexplored space quickly and fills it in later. It is not exploration by design: it is a consequence of uniform samples plus a nearest-neighbour rule.

What is guaranteed

A worked example

One extension. The tree node nearest to the sample q = (4, 5) is at (1, 1). The step size is η = 0.7 m.

If the sample had been 0.5 m from the node, the step would end at the sample itself, not overshoot it. The edge from (1, 1) to (1.42, 1.56) is 0.7 m long, which lets the collision check use a fixed number of samples (lesson M4-T2).

The Voronoi bias in numbers. A 10 m × 10 m yard has two tree nodes on the line y = 5: the root at x = 1 and a frontier node at x = 3. The points equally far from both lie on x = 2. The root’s region is x < 2: 20% of the yard. The frontier node’s region is x > 2: 80%. A uniform sample picks the frontier node four times in five, so the next node extends outwards, away from the root.

A roadmap. With n = 100 free samples and k = 5 neighbours each, the learning phase tries up to 100 × 5 = 500 edges, of which about half are mutual, leaving at most about 250 to 500 distinct edges for the graph search. Each edge is checked by sampling, so with edges of 3 m checked every 0.2 m (16 poses each) this is already between 4 000 and 8 000 pose checks.

A real run. In lab M4-L2 an RRT with η = 0.7 m crosses the 10 m × 6 m dock. On 40 generated docks with 400 samples it succeeded every time, and the first path was between 1.25 and 1.86 times the shortest route (mean 1.54). On the practice dock it is 16.6 m against 10.45 m, and 3000 more samples change nothing: once an edge is in the tree, RRT does not revisit it.

Engineering implications and limitations

Choosing the step and the neighbourhood

A large η makes the tree grow fast but can overshoot narrow gaps and makes each edge expensive to check; a small η is slow. A common choice is a few percent of the space’s extent, or of the order of the robot’s size. For PRM, k between 5 and 15 is usual for 2D problems.

Distance is a design decision

“Nearest” needs a metric. For a point robot it is Euclidean. For a pose with heading, an angle must be weighted against metres, and for a vehicle with turning constraints the true cost of getting from one pose to another is a Dubins or Reeds-Shepp length (lesson M4-T5). A poor metric makes the tree stall.

Nearest-neighbour search

The simple scan is O(n) per sample, so a tree of 10 000 nodes costs 50 million distance evaluations. A k-d tree or a similar structure makes the search O(log n). Compare it with the cost of collision tests before optimising.

Goal bias and failure

Without goal bias the tree reaches a small goal region only by chance. With too much bias the tree runs into walls and stalls. Add a time limit and a node limit, and report failure rather than loop.

Paths are rough

A raw RRT or PRM path wiggles. Shortcutting and smoothing (module 5) repair much of it, and RRT* (lesson M4-T4) improves the path as part of the search.

Common misconceptions

Engineering takeaways

1. PRM builds a roadmap of free samples joined by free edges and answers many queries by graph search.
2. RRT grows a tree from the start: sample, nearest node, step of at most η, check the edge, add the node.
3. The Voronoi bias, the nearest-node rule, pulls the tree towards unexplored space.
4. Goal bias replaces a small fraction of samples by the goal; 5–10% is usual.
5. Both are probabilistically complete; neither returns a shortest path, and RRT’s cost does not converge to the optimum.

References and further reading

The original papers for roadmaps and trees, and the completeness proof.

• L. E. Kavraki, P. Švestka, J.-C. Latombe and M. H. Overmars, “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces”, IEEE Transactions on Robotics and Automation, 12(4), 1996.
• S. M. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning”, Technical Report TR 98-11, Iowa State University, 1998.
• S. M. LaValle and J. J. Kuffner, “Randomized Kinodynamic Planning”, The International Journal of Robotics Research, 20(5), 2001.
• J. J. Kuffner and S. M. LaValle, “RRT-Connect: An Efficient Approach to Single-Query Path Planning”, IEEE ICRA, 2000.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: RRT*, which changes the tree as it grows so that the path gets shorter, and how informed sampling focuses the search.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T2: Collision Checking

  Check a footprint against obstacles with circles and polygons, and check an edge by sampling at a safe resolution.

• Lab
  M4-L2: Grow an RRT

  Find a way through the loading dock with random sampling, and see why it finds a path but not a good one.