Personal tools
You are here: Home Projects MPLB
« April 2017 »
April
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
30
Log in


Forgot your password?
 

Asymptotically-Optimal Motion Planning using Lower Bounds on Cost


Many path-finding algorithms on graphs such as A* are sped up by using a
heuristic function that gives lower bounds on the cost to reach the goal.
Aiming to apply similar techniques to speed up sampling-based motion-planning
algorithms, we use effective lower bounds on the cost between configurations
to tightly estimate the cost-to-go. We then use these estimates in an anytime
asymptotically-optimal algorithm which we call Motion Planning using Lower
Bounds 
(MPLB).
MPLB is based on the Fast Marching Trees (FMT*) algorithm recently presented
by Janson and Pavone. An advantage of our approach is that in many cases
(especially as the number of samples grows) the weight of collision detection in
the computation is almost negligible with respect to nearest-neighbor calls.
We prove that MPLB performs no more collision-detection calls than an anytime
version of FMT*.  Additionally, we demonstrate in simulations that for certain
scenarios, the algorithmic tools presented here enable efficiently producing
low-cost paths while spending only a small fraction of the running time on
collision detection.
CTC
ctc_ctg
 

 

Experimental results*:

Benchmark scenarios. The start and goal configuration are depicted in green and red, respectively
 
two_corridors
grids
home

2 DOF Two Corridors scenario
Environment, Robot
3 DOF Gridss scenario
Environment, Robot
6 DOF Home scenario
Environment, Robot
 

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Percentage of time spent for each of the main components in each iteration for both algorithms. 
Each iteration is represented by the number of samples used, the bars on the left (right) of each iteration represent the result of aFMT* (MPLB, respectively). 
Note that the time of each iteration for each algorithm is di erent, the results are presented in percentages of the total running time for each algorithm.
 
Grids_profiler    legend
 
                                        Grids scenario                                                      Legend
 

 

* Implemented using OMPL, the cubicles scenario is provided with the OMPL distribution.

 

 

Links

  • Oren Salzman,  and Dan Halperin. 
    Asymptotically-Optimal Motion Planning using Lower Bounds on Cost
    In International Conference on Robotics and Automation (ICRA), 2015 [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