Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

3.3: Introduction to Rapidly Exploring Random Trees

Loading...

Robotics: Computational Motion Planning

University of Pennsylvania

4.2 (757 ratings) | 25K Students Enrolled

Course 2 of 6 in the Robotics Specialization

Robotic systems typically include three components: a mechanism which is capable of exerting forces and torques on the environment, a perception system for sensing the world and a decision and control system which modulates the robot's behavior to achieve the desired ends. In this course we will consider the problem of how a robot decides what to do to achieve its goals. This problem is often referred to as Motion Planning and it has been formulated in various ways to model different situations. You will learn some of the most common approaches to addressing this problem including graph-based methods, randomized planners and artificial potential fields. Throughout the course, we will discuss the aspects of the problem that make planning challenging.

Skills You'll Learn

Motion Planning, Automated Planning And Scheduling, A* Search Algorithm, Matlab

Reviews

4.2 (757 ratings)

5 stars
400 ratings
4 stars
204 ratings
3 stars
89 ratings
2 stars
33 ratings
1 star
31 ratings

LC

May 07, 2016

This course is supposed to be easier but somehow it also makes it difficult because implementations of the algorithms in Matlab are bit non-standard as I am used to. Altogether very challenging.

JM

Mar 11, 2016

I like this course because they are covering really complicated topics in very less material. And the assignments are amazing. They are worth the learning effect they create.

From the lesson

Sampling-based Planning Methods

Welcome to Week 3! In this module, we introduce the concept of sample-based path planning techniques. These involve sampling points randomly in the configuration space and then forging collision free edges between neighboring sample points to form a graph that captures the structure of the robots configuration space. We will talk about Probabilistic Road Maps and Randomly Exploring Rapid Trees (RRTs) and their application to motion planning problems.

3.3: Introduction to Rapidly Exploring Random Trees6:47

Taught By

CJ Taylor
Professor of Computer and Information Science

Transcript

In the probabilistic roadmap procedure, the basic idea was to construct

a roadmap of the free space consisting of random samples and edges between them.

Once that had been constructed, you could connect your desired start and

endpoints to this graph and plan a path from one end to the other.

Note that the first phase constructs a generic roadmap of the entire

free space without considering any particular pair of start and end points.

The advantage of this approach is that you can reuse the roadmap over and

over again to answer multiple planning problems.

There are times though,

when you're only interested in answering one specific planning problem.

And in those situations,

it can be wasteful to construct roadmaps that span the entire free space.

In these situations, it may be better to use procedures that explicitly consider

the start and the goal locations in the sampling procedure.

In this section, we will describe one such approach.

The Rapidly Exploring Random Tree or RRT Method.

Like the probabilistic roadmap technique,

this approach works by generating random samples and connecting them together

to form a graph, but the sampling scheme is a bit different.

The RRT procedure proceeds by constructing a special kind of graph called a tree,

where every node is connected to a single parent and

the tree is rooted at a given starting location.

The following animation shows how the algorithm evolves to construct a tree

in a two-dimensional configuration space containing obstacles.

Notice how the graph grows outward organically from the start or

seed location at the center of the figure.

The basic tree construction algorithm is outlined here in pseudocode.

Just as in the PRM procedure, the basic algorithm proceeds

by sampling points at random and connecting them to the current graph.

The difference lies in the way the construction is carried out.

On every iteration, the system generates a random point in the configurations base

and checks if there's a free space.

It then searches for the closest point in the existing tree and

tries to generate a new node in the tree by moving in a straight line

between the current vertex of the tree and new random vertex.

The distance that it tries to move, delta is a parameter of the algorithm.

Note that id the distance between the random configuration and

the closest existing node in the tree is less than delta,

the algorithm will try to directly connect these two locations.

These sequence of figures shows the basic idea.

The first slide shows the original tree.

Here the red node depicts the new random configuration that the system generates,

while y depicts the closest existing node in the tree.

This next figure shows a new node z, which is generated by finding a configuration

that is distance delta away from y along the line towards x.

Finally, this slide shows the new state of the tree after adding the node z.

If the procedure does not succeed in this process of stepping towards a random node,

it's simply abandons a point and moves on to the next iteration

where it will generate a new random sample and try again.

Like the PRM algorithm,

this procedure assumes that we have some kind of distance function that we can use

to measure the effective displacement between two points in configuration space.

We also use the same local planner procedure to decide whether two

points in configuration space can be linked by a collision free trajectory.

It turns out that this procedure for generating random samples is

very effective at growing trees that explore and span the free space.

Hence, the name, Rapidly Exploring Random Tree or RRT.

In order to construct a path between the stark configuration and

an end configuration, we actually construct two trees.

One rooted at the start location and one at the goal.

The procedure then tries to grow both trees until they meet.

This animation shows the procedure in action

on a two-dimensional configuration space with obstacles.

Here, we have outlined this two-tree procedure in pseudocode.

On every iteration of the algorithm, the system generates a random sample and

tries to grow the current tree towards that random sample.

If it succeeds in adding a new node to the tree,

it tries to connect that new node to the other tree to form a bridge.

Note that if you succeed in finding such a bridge, you can claim success since it

means that you have now forged a path between the two trees.

On every route of this procedure, it swaps the two trees.

That way, both trees are growing towards each other at the same rate.

Here's a depiction of a few rounds of this procedure.

On the first round, we generate a random sample and

grow the blue tree towards that sample as shown here.

We then try to link the newly added node to the red tree by seeing if we can link

the new node that we just added to the closest node in the red tree.

In this case, this linking attempt does not succeed,

because of an intervening obstacle.

In the next round, we generate a new random sample and

try to grow the red tree towards that point.

Once we have done this, we turn around and

try to connect that point to the blue tree.

Here we succeed, so we can now forge her out between the start and

the goal locations.

Like the probabilistic roadmap procedure,

the RRT algorithm is probabilisticly complete.

So, there's a certain probability that the method will find the path from the start

to the goal if one exists.

In practice, the RRT Method is very effective at forging paths in

high-dimensional configuration spaces.

Another important feature of the RRT approach is it can be used on systems that

have dynamic constraints, which limit how they can move.

A simple example of this would be a car-like robot where limits on the turning

radius imply that it can not translate sideways or

turn in place around it's center.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates