Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Uniform Sampling Framework for PRMs

Much effort has been put on biasing sampling towards some specific surfaces of C-space, such as near obstacle (such as OBPRM, Gaussian PRM, and Bridge Test PRM) or along the medial axis (such as MAPRM), to improve performance or to find paths with desirable properties. However, none of these methods provides any guarantee as to how well their target surface is sampled.

We develop a uniform sampling framework that guarantees to generate uniformly distributed configurations in the target surfaces. It only requires some simple membership test on a fixed length line segment with respect to the target surfaces, which can be relatively fast.

Two instances of the framework are presented: UOBPRM whose target surfaces are C-obstacle surfaces and UMAPRM whose target surfaces are the medial axis of C-space.

UOBPRM
UMAPRM

If the volume where the samples are distributed in the target surfaces is not l-away from the bounding box (where l is the line segment length), the segments that would yield potential samples may be disqualified. In order to maintain uniformity, the uniform sampling framework requires l-space around the valid parts in order to allow for sampling framework to generate the line segment with length l. Thus, we temporarily adjust the bounding box to make sure the sampler has enough room to generate line segments with length l over the entire environment. Since we still check the configuration validity with respect to the original bounding box, the original problem is not changed.

UOBPRM generates uniformly distributed configurations near C-obstacle surfaces by detecting when C-obstacle surfaces have been crossed. This is done by looking for validity changes between consecutive points along the line segment. When a validity change occurs, the valid sample is retained as a roadmap node.

Uniformity

Here we compare 5 different sampling strategies: PRM, OBPRM, Gaussian PRM, Bridge Test PRM, and UOBPRM. We study the distribution of configurations obtained by each sampler in different environments. For each environment, we generate samples and then partition the environment into several cells and count the number of configurations in each cell. If the nodes are uniformly distributed, the number of nodes should be proportional to the surface area for every cell.

A Single Ball Environment: We compute node distribution by putting a grid over space. The grid equally partitions the environment into 16 small cells. Starting from 1, the cells are indexed from left to the right, from top to the bottom. Since the ball only occupies the center 4 pieces (number 6, 7, 10, and 11), a similar number of configurations in these four cells is expected if the distribution is uniform around obstacle surfaces. Here we show the snapshots for OBPRM (left) and UOBPRM (middle) and the node distribution comparison (right). The red bars show the percentage of configurations within the cells that the ball occupies and the blue ones represents the free space. An ideal node distribution around obstacle surfaces will result with each red bar at 25% and blue bar at 0%. As shown, UOBPRM gives a more uniform distribution, and the configurations are closer to the obstacle surfaces.

Environment with 4 Balls of Equal Size: We partition the space into 4 identical regions, and we separate each ball into 4 same sized cells. Therefore, we have a total of 16 cells which have the same obstacle surface area. If the distribution is uniform, each cell will have 6.25% of the nodes. Here we show the sample distribution examples for OBPRM (left) and UOBPRM (middle). OBPRM has fewer nodes on the boundary side than it should for a uniform distribution. From the node distribution comparison plot (right), it shows UOBPRM and Bridge Test PRM produce a distribution that is close to uniform distribution than other samplers.

Environment with a Mixture of Balls and Cubes: We separate the environment into four regions where one obstacle is either a ball or a cube only. The node distribution should be proportional to the surface. So there should be about 1.9 times more nodes in the cube regions than in the ball regions if the nodes are distributed uniformly. We separate each obstacle into 4 same sized cells to get 16 cells for the whole environment. Here we show the sample distribution examples for OBPRM (left) and UOBPRM (middle) in the mixture environment. UOBPRM generates more uniformly distributed configurations within each cell than OBPRM especially in the area close to the boundary. The node distribution comparison plot (right) shows UOBPRM has better distribution than other sampling methods where 4.31% is the ideal percentage of the nodes for the cells containing the balls and 8.19% is the ideal percentage for the cells containing cubes.

Motion Planning

A Heterogeneous Tunnel Environment: This is a real planning problem with a narrow passage. We try to use different sampling methods to find a path between the start and the goal configurations. The more uniform the configurations are, the faster the sampler will be able to find a path in the roadmap by using fewer nodes and edges. The result shows UOBPRM performs the best and PRM is not good at solving this kind of difficult problem.

Cost

We are also interested in the cost of generating samples. PRM is fast when C-space is free but it does not work well in difficult problems. Gaussian PRM and Bridge Test PRM take longer to generate samples. The cost for OBPRM is largely related to the step size. The smaller the step size, the longer it takes to generate nodes. For UOBPRM, node generation time depends on both the length of the line segment and the step size. We examine cost in the single ball environment (left) and the tunnel environment (right).

UMAPRM generates uniformly distributed samples along the medial axis by checking the closest obstacle changes between two neighboring configurations on the segment. The medial axis is crossed when there is a closest obstacle change. A binary search finds and retains the configuration on the medial axis.

Uniformity

We first show how certain environments cause MAPRM samples to be non-uniformly distributed, while UMAPRM samples are uniformly distributed along the medial axis.

We compare UMAPRM's and MAPRM's distributions and levels of uniformity in simple 2D and 3D environments with a narrow passage created by two unit blocks. In each trial, we generated 1000 samples with each method along the segment of the medial axis between the blocks (we ignore the portions of the medial axis related to the boundary). As a measure of uniformity, we computed the standard deviation of the distances between each node and its closest neighbor. We averaged the results over 40 runs.

Two environments used to compare the distributions of UMAPRM and MAPRM
2D Block
3D Block
Standard deviation of the distances between every node and its closest neighbor

The results show that UMAPRM has a lower average standard deviation in both environments, implying a more uniform distribution. Additionally, UMAPRM has roughly the same average as uniformly random distributed points along the medial axis plane.

Distributions of samples along the medial axis

We also check the sample distributions from the maps generated from 1000 samples for UMAPRM, MAPRM, and uniform random sampling on the medial axis. MAPRM is highly biased towards the area between the blocks in the experiments, while UMAPRM is uniformly distributed across the entire medial axis plane for both 2D and 3D environments.

2D Block environment
PRM
MAPRM
UMAPRM
3D Block environment
PRM
MAPRM
UMAPRM

Varying Surrounding Obstacle Width

MAPRM has a known bias towards narrow passages because its probability of sampling in a narrow passage is proportional to the volume of the narrow passage and its surrounding obstacles. UMAPRM however, is unaffected by changes in surrounding obstacle volume. Here we generate 1000 samples along the medial axis of the whole space (considering the boundary) and determine how many lie inside the narrow passage.

Three environments with various surrounding obstacle width

Obstacle 1 has the smallest obstacle volume, while Obstacle 3 has the largest. We averaged the results over 40 trials.

Obstacle 1
Obstacle 2
Obstacle 3
The ratio of nodes inside the narrow passage

UMAPRM consistently generates around 18% of nodes in each narrow passage, as the surface area of the medial axis in the narrow passage is constant. MAPRM performance is not consistent. It has difficulty generating samples in the narrow passgae in the smallest case, generating only about 13% in Obstacle 1.

The time it takes to generate the samples

UMAPRM is also more consistent in the time it takes to generate successful samples across the three narrow passage examples, whereas MAPRM's efficiency is related to the distance each node must be pushed to reach the medial axis. As the obstacle width increases, each node mush traverse a smaller distance to the medial axis on average.

Motion Planning

We compare PRM, MAPRM, and UMAPRM for planning between start and goal configurations in four environments: 2DMaze, STunnel, 2DHeterogeneous, and Bug Trap. All results are averaged over 40 trials. While both MAPRM and UMAPRM sample configurations along the medial axis, MAPRM's distribution is not guaranteed to be uniform and performance is dependent on the surrounding obstacle volume. Only UMAPRM guarantees a uniform distribution and its performance is unaffected by obstacle volume.

Time

The time is normalized to PRM. The results show that UMAPRM takes less time than MAPRM, but is slower than PRM since PRM performs fewer collision detection calls in 2DMaze and 2DHeterogeneous environment. UMAPRM outperforms both methods in STunnel environment. MAPRM is hampered because the volume of the surrounding obstacles is small compared with the rest of the planning space. In Bug Trap, UMAPRM finds the solution path in 2 hours, while neither PRM nor MAPRM is able to solve the problem after running for 10 hours.

Clearance

In addition to the time, we are also interested in the path quality by calculating the path clearance for each sampler. The clearance is normalized to PRM. UMAPRM generates higher quality paths than MAPRM in both 2DMaze and STunnel. In 2DHeterogeneous, the average path clearance between UMAPRM and MAPRM is comparable. Only UMAPRM solves the Bug Trap, so there is no normalized average path clearance in this environment.

Uniform Sampling Framework for Sampling Based Motion Planning and Its Applications to Robotics and Protein Ligand Binding, Hsin-Yi (Cindy) Yeh, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, May 2016.
Ph.D. Thesis(pdf, abstract)

UMAPRM: Uniformly Sampling the Medial Axis, Hsin-Yi (Cindy) Yeh, Jory Denny, Aaron Lindsey, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 5798 - 5803, Hong Kong, China, Jun 2014.
Proceedings(ps, pdf, abstract)

Nearly Uniform Sampling on Surfaces with Applications to Motion Planning, Mukulika Ghosh, Cindy (Hsin-Yi) Yeh, Shawna Thomas, Nancy M. Amato, Technical Report, TR13-005, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Apr 2013.
Technical Report(pdf, abstract)

UOBPRM: A Uniformly Distributed Obstacle-Based PRM, Cindy (Hsin-Yi) Yeh, Shawna Thomas, David Eppstein, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 2655-2662, Vilamoura, Algarve, Portugal, Oct 2012.
Proceedings(ps, pdf, ppt, abstract)

Supported by NSF

Project Alumni:Aaron Lindsey,Marco Morales

Related Projects
OBPRM
MAPRM