
Project Personnel:HsinYi (Cindy) Yeh,Mukulika Ghosh,Shawna Thomas,Nancy Amato
Project Collaborators:David Eppstein
Sampling near obstacles is important since it improves the configuration coverage in difficult areas of Cspace (such as narrow passages). There are several PRM variants proposed to increase sampling in important regions of Cspace, particularly near Cobstacle boundaries. None of them could gaurantee the node distribution and those methods are not very efficient. We propose a new obstaclebased sampler, Uniform OBPRM (UOBPRM) which guarantees a uniform distribution near the Cobstacle 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 Cobstacle boundary, then segments that would yield points on Cobstacle 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 obstaclebased 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.
We are also interested in the cost of generating samples. PRM is fast when the Cspace
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, HsinYi (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 (HsinYi) Yeh, Shawna Thomas, Nancy M. Amato, Technical Report, TR13005, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Apr 2013.
Technical Report(pdf, abstract)
UOBPRM: A Uniformly Distributed ObstacleBased PRM, Cindy (HsinYi) Yeh, Shawna Thomas, David Eppstein, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel.
Rob. Syst. (IROS), pp. 26552662, Vilamoura, Algarve, Portugal, Oct 2012.
Proceedings(ps, pdf, ppt, abstract)
Supported by NSF
Parasol Home  Research  People  General info  Seminars  Resources Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 778433112 parasoladmin@cse.tamu.edu Phone 979.458.0722 Fax 979.458.0718 Department of Computer Science and Engineering  Dwight Look College of Engineering  Texas A&M University Privacy statement: Computer Science and Engineering Engineering TAMU Web Accessibility Policy and Law  Web Accessibility and Usability Standards  Contact Webmaster 