A list,
RRT (Rapid Exploration of Random Trees) is a universal approach that works regardless of robot type, regardless of degree of freedom, and regardless of constraints. And its principle is very simple, which is one of the main reasons it is popular in the field of robotics. However, its disadvantages are also obvious. The path it produces is generally not of good quality. For example, it may contain edges and corners, is not smooth enough, and is often far from the optimal path.
RRT can stand out from the rest of the planning methods. What makes it so good? The world’s martial arts only fast, “fast” is a major advantage of RRT. The idea of RRT is to rapidly expand a group of tree-like paths to explore (fill) large areas of space, waiting to find a viable path. The tree was chosen because it can explore space. We know that sunlight is almost the only source of energy for trees. To make the most of sunlight, trees take up as much space as possible with as few branches as possible. Of course, it doesn’t have to be a tree to explore space. Peano curves, for example, can do it, and they can be as dense as possible, as shown on the left of the image above. A single continuous curve like the Peano curve can also explore space, but it’s too “deterministic.” We don’t know where the path should be when we search for it, and if it’s not in the “definite” search direction, we can’t find it (the probability of finding it is 0). Then show the beauty of “random”, although don’t know where is a way out, but by the repeated test can still touch to random, and touch the probability increased with the number of test is more and more big, like to buy lottery tickets, buy the more the number of the greater the probability of winning the meaning of “random” in the name (RRT). But random trials are also about strategy. If we pick a random point on the tree and grow in a random direction, what do we get? See above on the right. As you can see, it’s the same random tree, but this tree doesn’t explore space very well, it keeps going around the starting point, the red dot. That’s not good. We want trees to explore space as economically and evenly as possible, not over exploring one place and not missing most of it. How can such a tree be constructed?
The basic steps of RRT are: 1. Start as a seed from which to grow a branch. 2. Generate a random point in the “configuration” space of the robot; 3. Find the nearest point on the tree. 4. If there is no obstacle, add the branches and endpoints to the tree and return 2. Random points are generally evenly distributed, so when there are no obstacles the tree grows almost evenly in all directions, allowing for rapid exploration of space (RRT’s name means “rapid exploration”). Of course, if you know the area most likely to find a path in advance, you can concentrate your forces on exploring that area, which is not a good place to use even distribution.
One weakness of RRT is the difficulty of finding paths in environments with narrow channels. Because narrow passages are small and have a low chance of being encountered, the time it takes to find a path is a matter of luck. The example below is an RRT dealing with a narrow, artificially short passage. Sometimes the RRT finds its way out quickly, and sometimes it stays stuck inside the barrier.
RRT’s ability to explore space is good, as shown in the example on the left below, which is full of obstacles and cluttered (with Mathematica’s own powerful library of functions, it should take no more than 30 lines of code to implement this example). Is there an environment that stumbles the RRT? The maze shown on the right is a challenge for RRT. At this time, the space is very seriously divided, and RRT seems to be unable to do its job, so it can be seen that random strategy is not always effective.
“Randomness” makes the RRT very explorative. But success is nothing, and randomness also leads the RRT to be blind, running around like a chicken with its head cut off. If the robot knows nothing about the environment, then a random strategy is acceptable. The reality is that a robot knows something (if not everything) about its working environment. My blog has been emphasizing the importance of information for robots. This information can then be used to improve the algorithm. One way to improve is to give it an eye: in potential field methods, potential functions carry information about obstacles and targets, and it would be better to give the RRT this information so that it tends to follow the potential field as it explores space. In this way, the excellent exploration ability of RRT can just make up for the disadvantage of potential field method to easily fall into local minimum.
Second, the code
close(findobj('type','figure','name','RRT w/ Dubins curve')); close(findobj('type','figure','name','RRT growing')); clear; % Planning area initialization height = 10; width = 10; center = [0, 0]; % Initial condition of [x, y, direction] origin = [1,2, 20* PI /180]; Turning_rad = 0.5; % dubins turning raduis % Define iterations count iteration = 100; offset = center - [width, height]./2; th_range = 2*pi; % do not change without knowledge about Dubins th_center = 0; th_offset = 0; % prelocation of data edges.x = zeros(iteration,2); edges.y = zeros(iteration,2); edges.th = zeros(iteration,2); edges.param(iteration).p_init = [0, 0, 0]; % the initial configuration edges.param(iteration).seg_param = [0, 0, 0]; % the lengths of the three segments edges.param(iteration).r = turning_rad; % model forward velocity / model angular velocity turning radius edges.param(iteration).type = -1; % path type. one of LSL, LSR, ... edges.param(iteration).flag = 0; vertecies = origin; vert_count = 1; ind_nearest = zeros(iteration,1); edge_count = 0; % figure('name', 'RRT growing'); % originally for real-time animation tic; for i=1:iteration % random point generation x_rand = width*rand() + offset(1); y_rand = height*rand() + offset(2); th_rand = th_range*rand() + th_offset; % connect to nearest point [ind_nearest(i),param_nearest] = dubins_searchn(vertecies, [x_rand, y_rand, th_rand], turning_rad); % edge_rand = [x_rand, y_rand, th_rand ; vertecies(ind_nearest(i),:)]; % check availablility, see dubins_core.m for more info if( param_nearest.flag < 0) % goto next loop %i = i-1; %doesn't work under MATLAB else % append the newly generated point and edge to the existing list vertecies(vert_count+1,:) = [x_rand, y_rand, th_rand]; vert_count = vert_count + 1; edges.x(edge_count+1,:) = [vertecies(ind_nearest(i),1), x_rand]; edges.y(edge_count+1,:) = [vertecies(ind_nearest(i),2), y_rand]; edges.th(edge_count+1,:) = [vertecies(ind_nearest(i),3), th_rand]; edges.param(edge_count+1) = param_nearest; edge_count = edge_count + 1; end % plot animation here is undoable probably due to MATLAB running % optimization... % scatter(x_rand, y_rand, 10,'filled'); hold on; % plot([vertecies(ind_nearest(i),1); x_rand], [vertecies(ind_nearest(i),2); y_rand]); hold on; end toc; clear i x_rand y_rand edge_rand th_rand param_nearest figure('name', 'RRT w/ Dubins curve'); plot_RRT_Dubins(gca, vertecies, edges, vert_count); % plot bounderies boundary = [offset; offset+[width 0]; offset+[width height]; offset+[0 height]; offset]; plot(boundary(:,1),boundary(:,2),'--r');Copy the code
