Sampling based planning methods for 2D-Navigation

Question

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?

---

Originally posted by Pablo Iñigo Blasco on ROS Answers with karma: 2982 on 2011-04-01

Post score: 1

Answer 1

Hi Pablo,

Christian Connette had built up a global planner for navigation using ompl. His code is here: https://code.ros.org/svn/wg-ros-pkg/branches/trunk_cturtle/sandbox/ompl_planner_base . 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 - http://www.willowgarage.com/blog/2010/12/28/path-optimization-elastic-band).

Regards, Sachin

---

Originally posted by Sachin Chitta with karma: 1304 on 2011-04-03

This answer was ACCEPTED on the original site

Post score: 3

---

Original comments

Comment by Procópio on 2012-02-07:
Hey. I found out that the repository changed to: https://code.ros.org/svn/wg-ros-pkg/branches/trunk_dturtle/sandbox/ompl_planner_base/

Comment by Pablo Iñigo Blasco on 2011-04-05:
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.

Comment by Sachin Chitta on 2011-04-04:
https://code.ros.org/svn/wg-ros-pkg/branches/trunk_cturtle/sandbox/ompl_planner_base/ 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.

Comment by Pablo Iñigo Blasco on 2011-04-03:
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 and Quaternion with eigen2_AngleAxisd and eigen2_Quaterniond.

Answer 2

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.

---

Originally posted by egiljones with karma: 2031 on 2011-04-01

This answer was NOT ACCEPTED on the original site

Post score: 1

---

Original comments

Comment by Pablo Iñigo Blasco on 2011-04-05:
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

Comment by Pablo Iñigo Blasco on 2011-04-03:
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.