prev | index | next

RRT-Blossom

RRT-blossom is a novel variation on the RRT path & motion planning algorithm that significantly improves RRT's performance in highly-constrained environments. This work was presented and published at the International Conference on Robotics and Automation 2006 (paper PDF; slides from the talk: PowerPoint).

Paper abstract

The paper proposes a new variation of the RRT planner which demonstrates good performance on both loosely-constrained and highly-constrained environments. The key to the planner is an implicit flood-fill-like mechanism, a technique that is well suited to escaping local minima in highly constrained problems. We show sample results for a variety of problems and environments, and discuss future improvements.

  sample RRT-blossom tree

Experiments

We have tested RRT-blossom against plain RRT and RRT with Collision Tendency tracking on the following terrains, for a holonomic point, a nonholonomic car, and a kinodynamic bike. In the diagrams, `1' and `2' indicate the starting and goal configurations/states, respectively.

T
complex
rooms
tunnel
"T" "complex" "rooms" "tunnel"

 

Results - boxplots

The following boxplots summarize average query times for a variety of subjects and terrains for three algorithms: RRT (plain RRT), RRTCT (RRT with Collision Tendency), and RRT-blossom. In the kinodynamic case neither the boxplots or the subsequent data tables list RRT as this algorithm never really makes any progress on those queries. The boxplots show the query time distributions, in seconds.

boxplot of query times for holonomic point boxplot of query times for nonholonomic car
boxplot of query times for kinodynamic bike legend for boxplots

Results - table

The following tables summarize the query time results, as well as some other statistics. All values represent averages over the noted # of runs. Column legend:

  • time: query time
  • failure(): # of calls to failure(), a global constraint checking routine (generally a collision detection check, but in the case of the bike, also checks for whether the bike's lean exceeds safe levels)
  • NN: # of Nearest Neighbor checks
  • nodes: # of nodes in the generated trees when the solution is found
  • TOs: ("time outs") # of queries which did not find a solution within the given max_time

Rows in italics indicate experiments in which a significant amount of queries failed to find a solution; it is worth noting that the stats in those rows are therefore underestimating the true average (timed-out samples were discarded prior to averaging).

HOLONOMIC POINT:    |U|=8, averages over 100 runs, max_time=20s
terrain
algorithm
time
failure()
NN
nodes
TOs
           
RRT 3.45 21,100 2628 410 -
T RRT-CT 19.06 13,250 2870 2870 97
RRT-blossom 0.90 2246 280 316 -
           
RRT 2.75 10,048 1247 281 -
complex RRT-CT 10.90 8858 1889 1889 6
RRT-blossom 0.85 1767 221 266 -
           
RRT 13.10 39,398 4911 621 48
rooms RRT-CT N/A N/A N/A N/A 100
RRT-blossom 2.25 3276 409 499 -
           
RRT 3.68 22,080 2754 122 1
tunnel RRT-CT N/A N/A N/A N/A 100
RRT-blossom 0.21 944 118 118 -
NONHOLONOMIC CAR:    |U|=3, averages over 100 runs, max_time=60s
terrain
algorithm time failure() NN nodes TOs
           
RRT 9.39 13,317 4407 486 -
T RRT-CT 35.13 8890 3848 3585 8
RRT-blossom 1.36 1343 451 448 -
           
RRT 23.62 13,656 4542 294 9
complex RRT-CT 11.42 4049 1677 1465 -
RRT-blossom 1.39 811 295 267 -
           
RRT 32.62 27,119 9018 724 42
rooms RRT-CT 9.59 4071 1717 1507 -
RRT-blossom 3.53 1967 644 649 -
           
RRT 51.27 24,917 8281 408 77
tunnel RRT-CT N/A N/A N/A N/A 100
RRT-blossom 1.43 806 277 266 -
KINODYNAMIC BIKE:    |U|=5, averages over 40 runs, max_time=3600s
terrain
algorithm
time
failure()
NN
nodes
TOs
             
T RRT-CT 2359.45 163,632 43,440 29,963 7
RRT-blossom 103.02 34,054 8538 5808 -
             
complex RRT-CT 1310.84 129,546 34,140 22,604 1
RRT-blossom 67.49 27,368 7088 4675 -
             
rooms RRT-CT 609.06 83,549 22,094 14,949 -
RRT-blossom 154.90 43,822 11,049 7461 -
             
tunnel RRT-CT 1957.93 194,767 51,322 31,952 -
RRT-blossom 62.65 28,744 7476 4903 -
 

 

Evolved tree structure

The following diagrams illustrate the typical resultant tree structure at the moment a solution is found. In the case of the bike, RRT and RRT-CT did not find a solution in reasonable amount of time, and hence only show the progress made after a very large number of iterations.

RRT
RRT-CT
RRT-blossom

holonomic point

pic pic pic
nonholonomic car pic pic pic
kinodynamic bike pic pic pic

 

Node production rates

It is also interesting and perhaps instructive to look at the node generation rates of the algorithms (i.e., # of nodes created per iteration). The following plot shows typical node creation timelines for RRT, RRT-CT, and RRT-blossom, for a holonomic point agent in "complex" environment. X-axis represents the sequence of planner iterations, while the y-axis is the # of created tree nodes in a particular iteration. The red line represents a moving average in an 11-sample window. (NOTE: "RRTExtExtFan" == RRT-blossom)

node production rate plots

 

Visualization of planner's work

Click on the image below to see the planner in action, "thinking".

planner "thought" for car in "tunnel"

 

Post-talk questions

There were some good questions after the talk (at ICRA 2006, Orlando, Florida), ones that required some thought, and thus could not be answered on the spot due to talk time constraints. Here we present more thought out answers to these questions, or rather their approximations, in the hope that they may shed further light on the inner workings of this algorithm.

Q1. What about using RRT-Blossom for motion planning for complex non-actuated systems, such as a kinematic arm or chain with many segments?

RRT-Blossom is primarily applicable to actuated systems whose control input space has been discretized to some finite set. Non-actuated systems, such as a kinematic arm, can be made to fit the mold, in the usual way: the set of control inputs is made to consist of various angular perturbations at each of the arm's joints. As has been pointed out, for an arm or chain with many segments, this input space could get rather large; in those cases RRT-blossom, like other RRT variants for actuated systems (e.g., RRT w/Collision Tendency), is a poor choice of planner, and more direct variants should be used. But if the agent is amenable to the discretized actuated robot framework, then RRT-Blossom will work very well, usually outperforming its counterparts to a significant degree.

Q2. What about the anti-regression/anti-re-exploration check and systems for which L2 is a poor metric?

One of the agents we've tested with, the kinodynamic bike, is actually such a system: the L2 metric is a particularly bad metric to use, as frequently it suggests the precisely wrong course of action (e.g., if the bike is driving straight ahead and we want to go left, the L2 metric suggests immediately steering left, which is terribly myopic and the bike will fall over if it persists on that course; the proper action is of course to first steer right, to set up a left lean, and only then to steer left, with the leftward lean counterbalancing the centrifugal force).

As can be seen from our tests, despite using the L2 metric for its anti-regression check, RRT-Blossom still performs very well in the bike tests. It is unclear at this point whether even better performance could be gained by using a better metric.

Q3. a) What about comparisons against RRT-Connect?

That was a good point: for the holonomic point it would have been useful to compare against RRT-Connect style tree extensions, rather than just the single step RRT-Extend operation. Our choice to go with RRT-Extend operations was due to the desire to present the results in a unified, directly comparable framework, with as much code being shared as possible between the various test cases, and RRT-Connect provides little benefit in more complex systems (e.g., car and bike), where sustaining a fixed control input for prolonged periods of time is counter-productive.

Still, the comparison would be an interesting one. Of course, it would be quite interesting to allow RRT-Blossom to also use RRT-Connect type expansions for such kinematic scenarios, where appropriate; we do not forsee any difficulties in doing so, although the magnitude of improvement to expect is unclear.

Q3.b) What about RRT-Connect variant where nodes are placed at each step of the Connect edge?

We do not expect this to make much difference. In highly constrained environments the lackluster performance of RRT does not come so much from poor choice of node from which the tree is extended, but rather from the oft unnecessary self-limitation on the allowable directions of this expansion. Having more nodes in the tree does not really address this problem (whereas RRT-Blossom's use of "receding edges" does).