I am interested in RRT algorithm because I am excited that it can be used not only in two-dimensional plane, but also in high dimensional space. I am busy recently, and I will implement it in code next week or sometime.
What are the methods of path planning? More popular are: graph search, potential field method, RRT and so on.
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.
The effect of applying the RRT method to the manipulator is shown below (green indicates the target state). I set up four obstacles (one of which was the earth), which was a small challenge for the robot arm. Because we live in a three-dimensional space, can’t see six dimensional joint space, so I took six dimensional joint space is split into two 3 d space, corresponding to the first three joints and after three joints (strictly speaking, 6 d rotational joint space is not a European space, it is a manifold, but here we don’t have to struggle the difference) :
function c; CLC Clear all close all % MAP1 % a=10; % b = 0.2; % c = 0.1; % d = 0.6; % e=1; % f = 0.1; % g = 0.1; % for x=1:80 % for y=1:80 % Z1=sin(y+a)+b*sin(x)+cos(d*(x^2+y^2)^(1/2))+e*cos(y)+f*sin(f*(x^2+y^2)^(1/2))+g*cos(y); % % Z1 = SquareDiamond,2,8 (6); % figure(1); % surf(Z1); % shading flat; % %map2 peaks tic; % h =,35,25,38,20,25 [20]; % x0 =,40,45,60,20,20 [20]; % y0 =,25,50,30,45,10 [10]; Xi % = [5.5, 8,5,4.5, 5.5, 3.5]. Yi % = [5,7,6,5.5, 6,4.5]; H =,35,25,38,20,25 [20]; ,40,45,60,20,20 x0 = [20]; ,25,50,30,45,10 y0 = [10]; Xi = [5.5, 8,5,4.5, 5.5, 3.5]. Yi = [5,7,6,5.5, 6,4.5]; Z2=CeatHill(6,h,x0,y0,xi,yi,80); figure(2); surf(Z2); % Draw 3d curved shading flat; % Z3= Max (Z1,Z2); % figure(3); % surf(Z3); % shading flat; % No mesh segmentLength =5 between small surfaces; ,80,5,0,0,0 start_node = [10]; 60,0,5,1,0,0 end_node = []; hold on plot3(start_node(:,1),start_node(:,2),start_node(:,3),'r*'); plot3(end_node(:,1),end_node(:,2),end_node(:,3),'r*'); tree = start_node; if ( (norm(start_node(1:3)-end_node(1:3))<segmentLength )... &(collision(start_node,end_node)==0) ) path = [start_node; end_node]; else numPaths = 0; while numPaths<1, [tree,flag] = extendTree(tree,end_node,segmentLength,Z2); numPaths = numPaths + flag; end end path = findMinimumPath(tree); plot3(path(:,1),path(:,2),path(:,3),'r'); toc; function [data]=CeatHill(N,h,x0,y0,xi,yi,num) x=1:1:num; y=1:1:num; for m=1:num for n=1:num Sum=0; for k=1:N s=h(k)*exp(-((x(m)-x0(k))/xi(k))^2-((y(n)-y0(k))/yi(k))^2); Sum=Sum+s; end data(m,n)=Sum; end endCopy the code