Personal tools
You are here: Home Projects LBT-RRT
« August 2017 »
August
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Asymptotically near-optimal RRT for fast, high-quality, motion planning


       extended_thumbnail

LBT-RRT roadmaps: Two trees are simultaneously maintained by our
algorithm. A lower bound (T_lb) tree and an approximation tree.  
The cost  for reaching a node using the (possibly non collision-free) edges
of the T_lb will serve as a lower bound for the optimal cost. The second
tree, T_apx  maintains collision-free nodes that approximate the optimal cost.
We present Lower Bound Tree-RRT (LBT-RRT), a novel, single-query sampling-based algorithm that is asymptotically near-optimal. 

Namely, the solution extracted from LBT-RRT converges to a solution that is within an approximation factor of $1+\varepsilon$ of the optimal solution. Our algorithm allows for a continuous interpolation between the fast RRT algorithm and the asymptotically optimal RRT* and RRG algorithms. When the approximation factor is 1 (i.e., no approximation is allowed), LBT-RRT behaves like the RRT* algorithm. When the approximation factor is unbounded, LBT-RRT behaves like the RRT algorithm. In between, LBT-RRT is shown to produce paths that have higher quality than RRT would produce and run faster than RRT* would run.

This is done by maintaining a tree which is a sub-graph of the RRG roadmap and a second, auxiliary tree, which we call the lower-bound tree. The combination of the two trees, which is faster to maintain than the tree maintained by RRT*, efficiently guarantee asymptotic near-optimality. 

We demonstrate the performance of the algorithm for scenarios ranging from 3 to 12 degrees of freedom and show that even for small approximation factors, the algorithm produces high-quality solutions (comparable to RRT*)  with little runtime overhead when compared to RRT.

 

 

Experimental results*:

Benchmark scenarios. The start and goal configuration are depicted in green and red, respectively
 
maze
barrier cubicles

3 DOF Maze scenario 6 DOF Alternating barriers scenario 12 DOF 2-robot Cubicles scenario  

 

Success rate for algorithms on different scenarios.

Maze_success_rate
alternating_success_rate cubicles_success_rate

Maze scenario Alternating barriers scenario Cubicles scenario  

 
Path lengths for algorithms on different scenarios
Maze_length
alternating_length cubicles_length

Maze scenario Alternating barriers scenario  Cubicles scenario  


* Implemented using OMPL, the cubicles and the maze scenarios are provided with the OMPLdistribution.

Links

  • Oren Salzman,  and Dan Halperin. 
    Asymptotically near-optimal RRT for fast, high-quality, motion planning,
    In International Conference on Robotics and Automation (ICRA), 2014 [link]

Contacts

Oren Salzman  
http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Document Actions