Ask Your Question

Sampling based planning methods for 2D-Navigation

asked 2011-04-01 02:51:32 -0600

Hi ROS community! Navigation and sbpl stack (which are used for robot base navigation) have classes which implement the nav_core::global_planner interface. AFAIK they use discrete search methods like A* and they're based on grid map representations (cost-maps).

Are there any simple way to use sampling based methods (like those which ompl provides) for robot navigation? Should I implement the adapter for the global_planner interface? or it is already implemented? What do you think about using sampled-based methods for 2d navigation? is it like using a sledgehammer to crack a nut?

edit retag flag offensive close merge delete

3 Answers

Sort by » oldest newest most voted

answered 2011-04-03 13:41:56 -0600

Sachin Chitta gravatar image

updated 2011-04-03 14:55:41 -0600

Hi Pablo,

Christian Connette had built up a global planner for navigation using ompl. His code is here: . It essentially implements the planners in ompl as global planner plugins for the navigation stack. Note that this code is unreleased and the API to ompl has changed since then but its a good start (he also got it working on the PR2 -

Regards, Sachin

edit flag offensive delete link more


Thanks Sachin. It seems a very good start point. However, I see it doesn't use ompl. It's standalone. The pkg is broken on diamondback but It's working with some minor changes on eband_visualization.cpp changing AngleAxis<double> and Quaternion<double> with eigen2_AngleAxisd and eigen2_Quaterniond.
Pablo Iñigo Blasco gravatar image Pablo Iñigo Blasco  ( 2011-04-03 22:23:53 -0600 )edit does use ompl - check src/ompl_planner_base.cpp. It has not been updated in a while and ompl's interface has changed a bit but you should be able to get it working with a few fixes.
Sachin Chitta gravatar image Sachin Chitta  ( 2011-04-04 15:06:38 -0600 )edit
Right Sachin. ompl_planner_base is working with some minor changes. It's interesting to see the poor quality of ompl paths in comparison with nav_fn ones. It would be interesting research to have a performance comparison with different map sizes, paths longitude and other parametrizations. Thanks.
Pablo Iñigo Blasco gravatar image Pablo Iñigo Blasco  ( 2011-04-05 03:19:09 -0600 )edit
Procópio gravatar image Procópio  ( 2012-02-07 19:59:26 -0600 )edit

answered 2011-04-01 11:33:14 -0600

egiljones gravatar image

Hi Pablo,

We've definitely thought about this to some extent, but if want you really want to do is 2D navigation sampling-based planners are probably not the best tool. Sampling based planners are great for getting feasible paths in high dimensional spaces, but the path that gets returned can be of arbitrarily bad quality as judged by metrics like path distance. This means you may end up driving across the room and back again to go to a point that's very close to you, which is generally not what you want from your planner. You can deal with this to some extent by using path smoothing, but you still may not get a path anywhere near the optimal one. The search-based planners like A*, on the other hand, will produce guaranteed optimal paths or bounded optimal paths, where you know that you are within a factor of the optimal path. If you are getting optimal paths in very short times in 2dnav then there's not really a lot of reason to move to a sampling-based planner.

In my opinion a general rule of thumb is that if you can run an optimal search-based planner in the amount of time you can allocate for planning then there's no reason to consider another planning strategy. If your search spaces are difficult enough in terms of dimensionality, your time available to plan limited enough, or you don't care about path quality then ompl may start to make more sense.

There's no ompl adaptor for the global_planner interface that I know about - if you are really interested I can make a few suggestions for how to go about writing such a things.

edit flag offensive delete link more


Thanks egiljones, I see that the discrete methods are now the best choice for 2D.However IMHO complexity problems may appear even in 2D. Besides, I see another important lack on these discrete methods: they ignore systematically kinematic constraints making inadmissible paths for the local planners.
Pablo Iñigo Blasco gravatar image Pablo Iñigo Blasco  ( 2011-04-03 21:09:37 -0600 )edit
The ompl_planner_base and works relatively well with the eband as local planner. It's curious, the original elastic band paper don't talk anything about any specific control method. It would be nice to have a 3-tier navigation system: global-planning, dynamic path optimization, local-planning
Pablo Iñigo Blasco gravatar image Pablo Iñigo Blasco  ( 2011-04-05 03:24:56 -0600 )edit

answered 2014-11-03 05:38:20 -0600

I tried to implement my own adapter between move_base and ompl. Here is where I put it:

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2011-04-01 02:51:32 -0600

Seen: 1,781 times

Last updated: Apr 03 '11