Sampling near obstacles is important since it improves the configuration coverage
in difficult areas of C-space (such as narrow passages). There are several PRM
variants proposed to increase sampling in important regions of C-space,
particularly near C-obstacle boundaries. None of them could gaurantee the
node distribution and those methods are not very efficient. We propose a new
obstacle-based sampler, Uniform OBPRM (UOBPRM) which guarantees a uniform
distribution near the C-obstacle surfaces. UOBPRM basically generates a set of
uniformly distributed segments of fixed length and then finds all the
intersections between the segments and the obstacles by checking the validity
changes along the segment. The valid configurations adjacent to the invalid
configurations are retained as roadmap nodes.
For UOBPRM, if the bounding box is too close to a C-obstacle boundary, then
segments that would yield points on C-obstacle surface may be disqualified.
Therefore, we temporarily expand the bounding box for node generation which
provides enough space to generate line segments around obstacles. Although
the bounding box is adjusted, we do not generate nodes outside the original
bounding box, because we only retain samples contained in the original
bounding box as roadmap nodes.
In order to show how UOBPRM work comparing to other obstacle-based samplers,
we study the distribution of configurations and the cost of generating samples .
(2) Environment With 4 Balls of Equal Size:
Here we compare 5 different sampling strategies: PRM, OBPRM, Gaussian,
Bridge test 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 subregions and
count the number of configurations in each subregion. If the nodes are
uniformly distributed, the number of nodes should be proportional to the
surface area for every region.
(1) A Single Ball Environment:
We compute node distribution by putting a grid over space. The grid equally partitions
the environment into 16 small cubes. Starting from 1, the cubes are indexed from
left to the right, from top to the borrom. Since the ball only occupies
the center 4 pieces (number 6, 7, 10, and 11), a similar number of configurations
in these four regions 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. The red bars show the percentage of configurations
within the regions 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 surface.
We partition the space into 4 identical regions, and we separate each ball into
4 same sized regions. Therefore, we have a total of 16 regions which have the same
obstacle surface area. If the distribution is uniform, each region 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, it shows UOBPRM and
Bridge test sampler produce a distribution that is close to uniform distribution than the
(3) Environment With a Mixture of Balls and Cubes:
We separate the environment into four regions where one obstacle is either a ball or 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 regions to get 16 regions 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 region than OBPRM especially in the area close to the boundary. The node
distribution comparsion plot shows UOBPRM has better distribution than other sampling methods
where 4.31% is the ideal percentage of the nodes for the regions containing the balls and 8.19%
is the ideal percentage for the regions containing the cubes.
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 teh best and PRM is not good at solving this
kind of difficult problem.
We are also interested in the cost of generating samples. PRM is fast when the C-space
is freem but it does not work well in difficult problems. Gaussian sampling and Bridge test
sampling 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).
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)
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)