
Project Personnel:Jory Denny,Shawna Thomas,Nancy Amato
Motion planning is a difficult and widely studied problem in robotics. Current research aims not ony to find feasible paths, but to ensure paths have certain properties, e.g., shortest or safest paths. This is difficult for current stateoftheart samplingbased techniques as they typically focus on simply finding any path.
The medial axis is the set of all points equidistant between two or more obstacle boundaries. For an ndimensional space, the medial axis is an n1dimensional manifold which represents the connectivity of the space. Thus, the medial axis is a useful tool for computing high clearance motions and paths.
We use the observation that any point, free or not, may be retracted to the medial axis by monitoring when the witness point (for collision) changes during the retraction. We use this function to apply medial axis retraction two two large classes of sampling based motion planning algorithms: PRMs and RRTs. We develop two samplingbased algorithms: MAPRM and MARRT and show their effectiveness in solving narrow passage problems and generating high clearance solutions.
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.
Algorithm  Clearance Computation  Penetration Computation 
MAPRM  exact  exact 
MAPRM~  exact  approximate 
MAPRM~~  approximate  approximate 
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.
2D Experimental Results
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.
2D Experimental Results
We compare uniform sampling to MAPRM in 3D environments, both for rigid bodies and articulated linkages.
Here we apply our medial axis planning framework to Rapidly Exploring Random Trees (RRTs). RRTs search the planning space by biasing exploration toward unexplored regions. We introduce a novel RRT variant, Medial Axis RRT (MARRT), which biases tree exploration to the medial axis of the free space by pushing all configurations from expansion steps towards the medial axis. We prove that this biasing increases the tree's clearance from obstacles. Improving obstacle clearance is useful where path safety is important, e.g., path planning for robots performing tasks in close proximity to the elderly. We also experimentally analyze MARRT, emphasizing its ability to effectively map difficult passages while increasing obstacle clearance, and compare it to contemporary RRT techniques. MARRT differs from RRT in that instead of growing from the tree directly toward a random configuration, it constrains the growth near the medial axis. It does so by taking a small step towards the random configuration and then pushes the resulting intermediate configuration to the medial axis. It repeats this expansion process until it reaches the maximum expansion length or fails to make progress. Below is an example of this process:
Below are examples of different tree growth in the Tunnel environment. MARRT's growth is nicely constrained to the medial axis.
We also see that MARRT increases both roadmap and path clearances.
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:Evan Greco,JyhMing Lien,Peter Stiller,Steve Wilmarth
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 