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.

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

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.

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).

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
nonholonomic car
kinodynamic bike

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)

Visualization of planner's work

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

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).