
Project Personnel:Jory Denny,Shawna Thomas,Nancy Amato
Probabilistic roadmap planning methods have been shown to perform well in a number of practical situations, but their performance degrades when paths are required to pass through narrow passages in the free space. We propose a general framework for sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. This framework provides a template encompassing both exact and approximate retraction approaches. 
The fundamental primitive operations are the computation of penetration depth and clearance in configuration space. As these quantities can only be computed efficiently in lowdimensional Cspace, the application to highdimensional problems employs approximate clearance and penetration depth calculations. Thus, our framework supports methods that exactly or approximately retract a given configuration onto the medial axis. Exact methods provide fast and accurate retraction in low (2 or 3) dimensional space, while approximate methods extend the method to high dimensional problems, such as many DOF articulated robots. 

Theoretical and experimental results show improved performance on problems requiring traversal of narrow passages. We also study the tradeoffs between accuracy and efficiency for different levels of approximation, and investigate how the level of approximation affects the quality of the resulting roadmap.
We compare uniform sampling to MAPRM in two 2D environments, one in which MAPRM shows significant improvement and one in which it does not. For each experiment, we sampled 1000 valid nodes. In the first example, MAPRM produces many nodes in the corridor because the obstacles are "thick". In the second example, MAPRM is less successful because the corridor is sourronded by "thin" obstacles.
PRM 
MAPRM 
PRM 
MAPRM 
We compare uniform sampling to MAPRM in 3D environments, both for rigid bodies and articulated linkages.
Stunnel.
Uniform random sampling was unable to solve the query with 11 hours of computation time.
In contrast, all MAPRM variants were able to produce a valid solution path.
MAPRM~ takes slightly longer than MAPRM because the penetration approximation calculation
takes longer than the exact calculation. MAPRM~~ is the slowest variant because
it approximates both clearance and penetration calculation.

Hook.
MAPRM cannot be used in this environment because it contains nonconvex objects.
MAPRM~~ was able to solve the query in just over one minute,
an order of magnitude faster than uniform random sampling,
requiring only 1354.3 nodes,
an order of magnitude smaller than uniform random sampling.
For environments like this, it is critical that nodes are generated in the narrow corridor.
MAPRM~~ performs better than MAPRM~ because MAPRM~~ considers robot rotation,
in addition to translation, in computating clearance and penetration depth.

Walls.
For the stick robot, both MAPRM~ and MAPRM~~ outperformed uniform random sampling.
Although MAPRM~ finds a solution faster than MAPRM~~, the difference is not as pronounced
as in the Stunnel environment. Since the robot needs to maintain certain orientations to
pass through the holes, we conclude that constraints on rotation decrease the performance of
MAPRM~.
For the articulated robot, only MAPRM~~ can be applied because of the robots high degrees of freedom. MAPRM~~ again beat uniform random samply by solving the query with a roadmap half the size. MAPRM~~ requires more time to generate a node (33.74ms on average) than uniform random sampling (0.92ms on average). The time MAPRM~~ lost during node generation was more than made up for during node connection. 
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)
UMAPRM: Uniformly Sampling the Medial Axis, HsinYi (Cindy) Yeh, Jory Denny, Aaron Lindsey, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 5798  5803, Hong Kong, China, Jun 2014.
Proceedings(ps, pdf, abstract)
MARRT: Medial Axis Biased RapidlyExploring Random Trees, Jory Denny, Evan Greco, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 90  97, Hong Kong, China, Jun 2014.
Proceedings(ps, pdf, abstract)
A General Framework for Sampling on the Medial Axis of the Free Space, JyhMing Lien, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 44394444, Taipei, Taiwan, Sep 2003.
Proceedings(ps, pdf, abstract)
A Probabilistic Method for Rigid Body Motion Planning Using Sampling from the Medial Axis of the Free Space, Steven A. Wilmarth, Ph.D. Thesis, Department of Mathematics, Texas A&M University, Dec 1999.
Ph.D. Thesis(ps, pdf, abstract)
Motion Planning for a Rigid Body Using Random Networks on the Medial Axis of the Free Space, Steven A. Wilmarth, Nancy M. Amato, Peter F. Stiller, In Proc. ACM Symp. Comput. Geom., pp. 173180, Miami Beach, FL, Jun 1999. Also, Technical Report, TR98028, Department of Computer Science and Engineering, Texas A&M University, Dec 1998.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space, Steven A. Wilmarth, Nancy M. Amato, Peter F. Stiller, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 10241031, Detroit, MI, May 1999. Also, Technical Report, TR980022, Department of Computer Science and Engineering, Texas A&M University, Nov 1998.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
Supported by NSF
Project Alumni:JyhMing Lien,Peter Stiller,Steve Wilmarth
Parasol Home  Research  People  General info  Seminars  Resources Parasol Laboratory, 425 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 