Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
UOBPRM: A Uniformly Distributed Obstacle-Based PRM

Project Collaborators:David Eppstein

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 .


Configuration Distribution
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.



(2) Environment With 4 Balls of Equal Size: 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 other samplers.


(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)

Supported by NSF

Related Projects
OBPRM
UMAPRM