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
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.
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.
UMAPRM
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.
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
3D Block Environment
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.
We examine 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.
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 passage in the smallest case, generating only about 13% in Obstacle 1.
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.
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.
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.