|prev | index | next
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.
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:
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.
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".
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).