Basic sampling-based motion planning methods: PRMs, RRTs

These exercises are devoted to study how the PRM, RRT and RRTconnect planners work and evaluate their performance. Some simple 2D scenarios are proposed as well as a problem with a 8-DOF mobile manipulator.

If not already done, first install or build Kautham. Then run the kautham-gui application.

Qualitative evaluation of PRMs

Open the demo demos/OMPL_geo_demos/Cube_Maze_R2/OMPL_PRM_bigcube_maze2D_R2_r.xml to analyze how the PRM planner solves the problem. Focus will be put on the sampling source and on the Distance Threshold parameter. The default parameter values of the demo will be used if not otherwise stated.

../../_images/cube_maze.png

The sampling source

To see how the random sampling explores the configuration space in comparison to the deterministic Halton sequence, execute the following steps:

  1. Set _MaxPlanningTime to 0.01 (to let the generation of few samples) and DistanceThreshold to 0.0 (not to allow the samples to be connected). Then, press Get Path repeatedly to visualize the generation of different sets of random samples (in the CollisionWSpace tab).

To see how the space is filled with more samples, set _Incremental to 1 (not to delete the samples already created) and press Get Path repeatedly.

  1. Change the sampling source to the Halton sequence by setting the parameter _Sampler 0(r) 1(h) 2(sdk) 3(g) to 1, and repeat the steps.



>>> EXERCISE 1: Discuss how the different sampling sources fill the free cspace and the effect this may have in the planning procedure. Set _Incremental to 0, _MaxPlanningTime to 1.5 and DistanceThreshold to 0.2 and run several times the planner using both sampling sources.
../../_images/cube_maze_PRM_r.png ../../_images/cube_maze_PRM_h.png

The growing of the roadmap

The standard PRM algorithm, as proposed in this paper and implemented in the OMPL library, allocates 2/3 of the time to grow the roadmap and 1/3 of the time to expand it. This feature is overridden in Kautham by allowing to allocate variable slots of time to each part. To do so, the planner parameters MinExpandTime and MinGrowTime have been defined. The planner interleaves them iterativelly until the _MaxPlanningTime is reached.

In this section we are going to analyze only the basic growing procedure. Follow these steps to visualize the PRM construction:

  • set MinExpandTime to 0,

  • set DistanceThreshold to 0.2,

  • set _MaxPlanningTime to 0.01,

  • set _Simplify Solution to 0,

  • set _Incremental to 0,

  • set _Sampler 0(r) 1(h) 2(sdk) 3(g) to 0

Then, press Get Path once, change _Incremental to 1, and press Get Path repeatedly.

Repeat for the Halton sampling sequence.



Any new generated sample is attempted to be connected to its neighbor samples, according to the Distance Threshold. Observe how the different connected components keep growing and joining, creating the final roadmap that captures the connectivity of the free configuration space.

>>> EXERCISE 2:  Repeat by setting the Distance Threshold to 0.05 and to 0.5, and discuss the effects of this parameter.

>>> EXERCISE 3: Repeat for different 2D environments (Cube-sPassage_R2 and *Cube_Cluttered_R2). Discuss whether the environment may condition the value of the Distance Threshold to be chosen.

>>> EXERCISE 4: Run the PRM planner to solve the TX90_R6_mobileBase demo (set the sampling source to random).
../../_images/TX90-mobile_PRM.png

Qualitative evaluation of RRTs

Open the demo demos/OMPL_geo_demos/Cube_Maze_R2/OMPL_RRT_bigcube_maze2D_R2.xml to analyze how the RRT planner solves the problem. Focus will be put on the Range and Goal Bias parameters.

Extending the tree

First we are going to visualize how the RRT planner growing nature, filling uniformly the space from the initial node.

  • set Goal Bias to 0.0,

  • set _MaxPlanningTime to 0.01,

  • set _Simplify Solution to 0,

  • set _Incremental to 0,

Then, press Get Path once, change _Incremental to 1, and press Get Path repeatedly.



Observe how the different branches keep rapidly exploring the free configuration space.

The length of the tree edge is equal or less than the Range value, according to whether the Extend process of the tree returns Reached or Advanced, as described in the introductory paper.

>>> EXERCISE 5: Repeat for different values of the Range (e.g. 0.05 and 0.5), and discuss the effects of this parameter.

>>> EXERCISE 6: Repeat for different 2D environments (Cube-sPassage_R2 and Cube_Cluttered_R2).  Discuss whether the environment may condition the value of the Range to be chosen.

The Goal Bias parameter

The exploration capacity of the RRT planner can be tunned towards the objective of finding the goal configuration, by selecting, from time to time, this goal configuration as the one towards which to extend instead of a random one. The probability of this choice is the Goal Bias.

>>> EXERCISE 7: Set the Range to 0.05 and test for different values of the Goal Bias (e.g. 0.05, 0.2 and 0.95), and discuss the effects of this parameter.

>>> EXERCISE 8: Run the RRT planner to solve the TX90_R6_mobileBase demo.
../../_images/TX90-mobile_RRT.png

Bi-directional RRTs

Open the demo demos/OMPL_geo_demos/Cube_Maze_R2/OMPL_RRTconnect_bigcube_maze2D_R2.xml to analyze how the RRTconnect planner solves the problem. It grows two trees, and the single parameter it has is the Range.

In order to visualize how the RRTconnect planner works:

  • set _MaxPlanningTime to 0.01,

  • set _Simplify Solution to 0,

  • set _Incremental to 0,

Then, press Get Path once, change _Incremental to 1, and press Get Path repeatedly.



>>> EXERCISE 9: RRTconnect is one of the best planners. Discuss why it outperforms the RRT.

>>> EXERCISE 10: Repeat for different values of the Range (0.05 and 0.5), and discuss the effects of this parameter.

>>> EXERCISE 11: Run the RRTconnect planner to solve the TX90_R6_mobileBase demo.
../../_images/TX90-mobile_RRTconnect.png

Benchmarking PRMs and RRTs

Take a look at the benchmarking files available at the Cube-sPassage_R2 folder demo, and at the problem files that have been prepared to be benchmarked. Follow the steps to generate the db file and visualize the results at plannerarena.org, as detailed in Section Benchmarking planners.

Use the bigcube_maze2D_R2 demos to benchmark the PRM, RRT and RRTConnect planners.

For each planner use two or three sets of parameters (the ones that qualitatively worked best in the previous exercises) and:

  1. Write a problem file per set of planner parameters

  2. Write the benchmarking.xml file to launch all the problems.

>>> EXERCISE 12: Discuss the results focusing the comparison based on the plots of graph states, solved (%), and time.

Repeat for the TX90_R6_mobileBase demo: First use the kautham-gui to test some parameter values that may work, then create the problem files and the benchmarking file, and run it.

>>> EXERCISE 13: Compare the planners and discuss their pros and cons for high-dimensional configuration spaces.