Ask Your Question

Difference between search and sampling based motion planning

asked 2017-07-08 11:46:27 -0600

OMC gravatar image


I do not quite get the difference between search and sampling based motion plannings (implemented in the SBPL and OMPL, respectively).

Both use precomputed primitives of the robot to generate a solution. I read the search-based motion planners create a graph from this set of motion primitives and then explores this graph to find an optimum solution, while sample-based motion planners do not create any graph, which leads to faster computations, but less likely to be optimal solutions. How are the motion plans generated by OMPL, then?

I intend to create a car planner to follow a road while avoiding obstacles and keeping inside the lane. The problem here is that I need the planner to operate in real time (check the current planner feasibility or generate a new one at 10Hz, at least). To that end, It would be best to use the OMPL approach and leave SBPL for parking maneuvers, which may require a more exhaustive search, and time is not a problem there.

So, the strategy I want to implement is to use a precomputed set of motion primitives whose radius will be limited by the car's velocity at eath step and check if the chosen plan if the returned plan is feasible by checking an occupancy grid (whose associated cells' coordinated will also be precomputed for each motion primitive to speed up the checking).

Any suggested alternatives are welcome.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2021-02-22 09:59:45 -0600

marcusvini178 gravatar image

updated 2021-02-22 10:01:08 -0600

Hi There are years ago you asked the question. Currently Autoware Auto is working within Autonomous Valet Parking. You can check here:

There is also an specific class about motion planners for ROS2 pretty interesting and that goes deep:

Besides that the main difference of sample-based and graph search planners are described here:

To quickly implement these 2 kind of plannings (SBPL and OMPL) I would suggest you use A Primer. It is very intuitive 2D software that you can see the planner behaviour, as well as read how these planners are generated step-by-step as you asked. You can get the answer of your teoritically question reading this document and afterwards visualize the behaviour installing A Primer:

About how to implement I suggest watching these AutowareAuto classes and read their planners documentation:

There is also a good phd work with obstacle avoidance:

Well I am also currently doing a master thesis on this topic and I am in implementation phase also. If you have a material and simulation about your work and could share I will be grateful (even if be on ROS1) :). Bye

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



Asked: 2017-07-08 11:46:27 -0600

Seen: 256 times

Last updated: Feb 22