Obstacle-Based

Sampling-based motion planning uses randomization to construct a graph or tree (roadmap) in C-space which can be used to answer queries (find paths connecting start and goal configurations). While the original sampling-based methods were able to solve some long standing planning problems very efficiently, they were not as successful in solving certain types of problems, such as those requiring navigation in crowded scenarios or traversing narrow passages.

In some such situations, it is useful to sample near configuration space surfaces. In our group, we proposed the first sampling-based methods to efficiently sample C-obstacle surfaces, which we call obstacle-based methods. We developed strategies for both graph-based (OBPRM) and tree-based (OBRRT) methods. While these methods work well in practice, they do not provide guarantees about the distribution of points on the C-obstacle surface.

We developed another strategy, Uniform Obstacle-based PRM (UOBPRM), which is less efficient but uniformly samples the C-obstacle surface.

OBPRM: Obstacle-Based PRM

Project Alumni:
O. Burchan Bayazit, Lucia K. Dale, Christopher Jones, Guang Song, Daniel Vallejo, Yan Wu

Probabilistic RoadMap (PRM) motion planners use randomization to construct a graph (roadmap) in C-space. Nodes correspond to collision-free configurations, and two nodes are connected by an edge if a local planner can connect them.

In this work, we proposed Obstacle-Based PRM (OBPRM).
The key idea is that roadmap nodes are sampled on or near C-obstacle surfaces (contact configurations). This improves roadmap quality in crowded environments and narrow passages where uniform sampling struggles.

View Demo

A demo is available at: /research/obprm/demos/obprm.html

Publications

UOBPRM: A uniformly distributed obstacle-based PRM

Yeh, Thomas, Eppstein, Amato — IROS 2012
DOI: 10.1109/IROS.2012.6385875
Keywords: obstacle-based, sampling-based motion planning
Published

Abstract

This paper presents a new sampling method for motion planning that generates configurations more uniformly distributed on C-obstacle surfaces than prior approaches. The results show that the method yields more uniform samples and requires fewer nodes and edges to solve challenging motion planning problems.

An Obstacle-Based Rapidly-Exploring Random Tree

Rodriguez, Tang, Lien, Amato — ICRA 2006
DOI: 10.1109/ROBOT.2006.1641823
Keywords: obstacle-based, RRT
Published

Abstract

This work presents a variant of RRT that better explores narrow passages using both workspace and C-space obstacle information. It performs well in difficult regions for free-flying rigid or articulated robots.

C-Space Subdivision and Integration in Feature-Sensitive Motion Planning

Morales et al. — ICRA 2005
DOI: 10.1109/ROBOT.2005.1570589
Keywords: machine learning, motion planning
Published

Ligand Binding with OBPRM and Haptic User Input

Bayazit, Song, Amato — 2000
Keywords: ligand binding, sampling-based planning
Published

OBPRM: An Obstacle-Based PRM for 3D Workspaces

Amato et al. — WAFR 1998
Published

A Randomized Roadmap Method for Path and Manipulation Planning

Amato & Wu — ICRA 1996
DOI: 10.1109/ROBOT.1996.503582

OBRRT: Obstacle-Based RRT

Project Alumni:
Xinyu Tang,
Jyh-Ming Lien,
Nancy Amato

Supported By: NSF, Dept. of Education, Texas Higher Education Coordinating Board

Tree-based path planners have been shown to be well suited to solve various high-dimensional motion planning problems. Here we present modifications that can be made to the Rapidly-Exploring Random Tree (RRT) path planning algorithm that allow it to explore narrow passages or difficult areas more effectively. We show that both workspace obstacle information and C-space information can be used when deciding which direction to grow. The method includes many ways to grow the tree, some taking into account the obstacles in the environment.

A tree grown using basic expansion

A tree grown using basic expansion.

A tree grown using obstacle information

A tree grown using obstacle information.

The presented algorithm modifies the basic RRT expansion algorithm. Modifications are made to how a source node is expanded and how extension is done from a source configuration.

Differences between basic RRT and OB-RRT expansion

Possible obstacle vectors

Possible obstacle vectors.

Growth Methods

Basic Extension
Random position, same orientation
Random obstacle vector, random orientation
Random obstacle vector, same orientation
Rotation followed by extension
Trace obstacle, random orientation
Trace obstacle, same orientation
Trace C-space obstacle
Medial Axis Push

Using obstacle hints for directions to grow a tree for path planning can be beneficial, especially when exploring difficult areas. Results can be viewed in the paper. The proposed planner performs best when expanding from narrow or difficult areas.

Publications

UOBPRM: A uniformly distributed obstacle-based PRM

Authors: Hsin-Yi Yeh, Shawna Thomas, David Eppstein, Nancy M. Amato
Venue: IEEE/RSJ International Conference on Intelligent Robots and Systems, Oct 2012, pp. 2655–2662
DOI: 10.1109/IROS.2012.6385875
Keywords: obstacle-based, sampling-based motion planning
Links: Published

Abstract (shortened):
This paper presents a new sampling method for motion planning that can generate configurations more uniformly distributed on C-obstacle surfaces than prior approaches. Roadmap nodes are generated from intersections between C-obstacles and a set of uniformly distributed fixed-length segments in C-space. The method yields more uniform samples and requires fewer nodes and edges to solve challenging motion planning problems with narrow passages.

An Obstacle-Based Rapidly-Exploring Random Tree

Authors: Samuel Rodriguez, Xinyu Tang, Jyh-Ming Lien, Nancy M. Amato
Venue: IEEE International Conference on Robotics and Automation (ICRA), Orlando, Florida, USA, May 2006
DOI: 10.1109/ROBOT.2006.1641823
Keywords: obstacle-based, Rapidly-exploring Random Tree (RRT), sampling-based motion planning
Links: Published

Abstract (shortened):
This work presents a variant of the RRT path planning algorithm that is able to explore narrow passages or difficult areas more effectively. Both workspace obstacle information and C-space information are used when deciding which direction to grow. The planner works best in difficult areas for free-flying rigid or articulated robots, where standard RRT can struggle.

Ligand Binding with OBPRM and Haptic User Input: Enhancing Automatic Motion Planning with Virtual Touch

Authors: O. Burchan Bayazit, Guang Song, Nancy M. Amato
Venue: ACM Digital Library, College Station, Texas, USA, Oct 2000
Keywords: ligand binding, sampling-based motion planning
Links: Published

Abstract (shortened):
This paper presents a framework for studying ligand binding using motion planning techniques. It investigates automatic planning and improvements obtained from supplementary haptic user input. Using an obstacle-based PRM, the method can automatically generate configurations near true binding sites and benefits from user interaction via haptic feedback.

OBPRM: An Obstacle-Based PRM for 3D Workspaces

Authors: Nancy M. Amato, O. Burchan Bayazit, Lucia K. Dale, Christopher Jones, Daniel Vallejo
Venue: Robotics: The Algorithmic Perspective (WAFR 1998), pp. 155–168, Houston, TX, Mar 1998
Keywords: obstacle-based, sampling-based motion planning
Links: Published

Abstract (shortened):
Probabilistic Roadmap Methods (PRMs) use randomization to construct a roadmap in C-space. This work introduces an obstacle-based PRM where candidate points are chosen on C-obstacle surfaces, increasing the likelihood of capturing difficult paths such as those in long, narrow passages.

A Randomized Roadmap Method for Path and Manipulation Planning

Authors: Nancy M. Amato, Yan Wu
Venue: IEEE International Conference on Robotics and Automation, Vol. 1, pp. 113–120, Minneapolis, MN, Apr 1996
DOI: 10.1109/ROBOT.1996.503582
Keywords: sampling-based motion planning
Links: Published

Abstract (shortened):
This paper presents a randomized roadmap method for motion planning for many-DOF robots that obtains high-quality roadmaps even when C-space is crowded. Candidate points are chosen on C-obstacle surfaces, making it more likely to capture difficult paths and enabling efficient planning for both collision-free paths and manipulation tasks.

UOBPRM: Uniform OBPRM

Project Alumni:
Hsin-Yi (Cindy) Yeh,
Mukulika Ghosh,
Shawna Thomas,
Nancy Amato

Supported By: NSF

Sampling near obstacles is important since it improves 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. However, none of them guarantee the node distribution and many are not very efficient.

We propose a new obstacle-based sampler, Uniform OBPRM (UOBPRM), which guarantees a uniform distribution near C-obstacle surfaces. UOBPRM generates a set of uniformly distributed fixed-length segments and then finds all intersections between these segments and the obstacles by checking validity changes along the segment. The valid configurations adjacent to invalid configurations are retained as roadmap nodes.

For UOBPRM, if the bounding box is too close to a C-obstacle boundary, segments that would yield points on the C-obstacle surface may be disqualified. Therefore, we temporarily expand the bounding box for node generation, providing 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 compare UOBPRM with other obstacle-based samplers, we study the distribution of configurations and the cost of generating samples.

We compare five different sampling strategies:

PRM
OBPRM
Gaussian sampling
Bridge test sampling
UOBPRM

For each environment, we generate samples, partition the environment into subregions, and count the number of configurations in each subregion. If nodes are uniformly distributed near obstacle surfaces, the number of nodes in each region should be proportional to the corresponding obstacle surface area.

(1) Single Ball Environment

The space is partitioned into 16 equal cubes. The ball occupies the central 4 cubes (6, 7, 10, 11). For a uniform distribution around the obstacle surface, these 4 regions should contain a similar number of configurations, while the other regions should contain none (or very few) if we focus on obstacle surfaces.

Below are sample distributions for OBPRM (left) and UOBPRM (middle), followed by a node distribution comparison:

OBPRM samples in single-ball environment
UOBPRM samples in single-ball environment

Node distribution comparison for single-ball environment

An ideal distribution would have each of the four occupied cubes at 25% and the others at 0%. UOBPRM produces a more uniform distribution with configurations closer to the obstacle surface than OBPRM.

(2) Environment with 4 Balls of Equal Size

The space is partitioned into 4 identical regions, and each ball is subdivided into 4 equal parts, yielding 16 regions with the same obstacle surface area. For a uniform distribution, each region should contain 6.25% of the nodes.

Sample distributions for OBPRM (left) and UOBPRM (middle):

OBPRM samples in 4-ball environment
UOBPRM samples in 4-ball environment

Node distribution comparison for 4-ball environment

OBPRM has fewer nodes on boundary sides than expected for a uniform distribution. UOBPRM and Bridge test sampling produce distributions closer to uniform than the other samplers.

(3) Environment with a Mixture of Balls and Cubes

The environment is divided into four regions, each containing a single obstacle (either a ball or a cube). Node distribution should be proportional to the obstacle surface area, so there should be about 1.9 times more nodes in cube regions than in ball regions for a uniform distribution.

Each obstacle is subdivided into 4 equal regions, giving 16 regions total. Sample distributions for OBPRM (left) and UOBPRM (middle):

OBPRM samples in mixed environment
UOBPRM samples in mixed environment

Node distribution comparison for mixed environment

UOBPRM generates more uniformly distributed configurations in each region than OBPRM, especially near boundaries. The ideal node percentages are about 4.31% for ball regions and 8.19% for cube regions; UOBPRM is closest to this ideal.

Heterogeneous Tunnel Environment

This is a real planning problem with a narrow passage. We use different sampling methods to find a path between start and goal configurations. The more uniformly configurations are distributed (especially in the narrow passage), the faster a valid path can be found with fewer nodes and edges.

Heterogeneous tunnel environment
Cost comparison in tunnel environment

The results show that UOBPRM performs best, while standard PRM performs poorly on this kind of difficult problem.

Cost of Generating Samples

We also examine the cost of sample generation:

PRM is fast when C-space is free but does not work well on difficult problems.
Gaussian and Bridge test sampling are more expensive per sample.
OBPRM’s cost is strongly tied to step size (smaller step size → higher cost).
For UOBPRM, node generation time depends on both the segment length and step size.

Generation costs are illustrated in:

Single ball environment (left)
Tunnel environment (right)

Generation cost in single-ball environment
Generation cost in tunnel environment

UOBPRM Demo

A demo is available at:

/research/uobprm/demos/uobprm.html

Publications

UOBPRM: A uniformly distributed obstacle-based PRM

Abstract (shortened):
This paper presents a sampling method that generates configurations more uniformly distributed on C-obstacle surfaces than prior approaches (OBPRM, Gaussian sampling, Bridge test). Roadmap nodes are generated from intersections between C-obstacles and uniformly distributed segments. UOBPRM yields more uniform samples and requires fewer nodes and edges to solve challenging motion planning problems with narrow passages.

An Obstacle-Based Rapidly-Exploring Random Tree

Abstract (shortened):
This work presents a variant of the RRT algorithm that can explore narrow passages and difficult regions more effectively by using both workspace obstacle information and C-space information when choosing growth directions.

Ligand Binding with OBPRM and Haptic User Input: Enhancing Automatic Motion Planning with Virtual Touch

Abstract (shortened):
This paper presents a framework for studying ligand binding based on motion planning techniques and enhanced with haptic user input. An obstacle-based PRM is used to locate binding sites, and haptic feedback helps users understand protein structures by letting them feel interaction forces.

OBPRM: An Obstacle-Based PRM for 3D Workspaces

A Randomized Roadmap Method for Path and Manipulation Planning

Abstract (shortened):
A randomized roadmap method for many-DOF robots that achieves high-quality roadmaps even in crowded C-spaces by choosing candidate points on C-obstacle surfaces. The method applies to both collision-free path planning and manipulation tasks.

No papers listed in our current papers database.