MAPRM: Medial Axis PRM

@INPROCEEDINGS{6906594, author={J. {Denny} and E. {Greco} and S. {Thomas} and N. M. {Amato}}, booktitle={2014 IEEE International Conference on Robotics and Automation (ICRA)}, title={MARRT: Medial Axis biased rapidly-exploring random trees}, year={2014}, volume={}, number={}, pages={90-97}, doi={10.1109/ICRA.2014.6906594}}

Motion planning is a difficult and widely studied problem in robotics. Current research aims not only to find feasible paths, but to ensure paths have certain properties, e.g., shortest or safest paths. This is difficult for current state-of-the-art sampling-based techniques as they typically focus on simply finding any path. Despite this difficulty, sampling-based techniques have shown great success in planning for a wide range of applications. Among such planners, Rapidly-Exploring Random Trees (RRTs) search the planning space by biasing exploration toward unexplored regions. This paper introduces a novel RRT variant, Medial Axis RRT (MARRT), which biases tree exploration to the medial axis of 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. Finally, we experimentally analyze MARRT, emphasizing its ability to effectively map difficult passages while increasing obstacle clearance, and compare it to contemporary RRT techniques.

@INPROCEEDINGS{6907711, author={H. C. {Yeh} and J. {Denny} and A. {Lindsey} and S. {Thomas} and N. M. {Amato}}, booktitle={2014 IEEE International Conference on Robotics and Automation (ICRA)}, title={UMAPRM: Uniformly sampling the medial axis}, year={2014}, volume={}, number={}, pages={5798-5803}, doi={10.1109/ICRA.2014.6907711}}

Maintaining clearance, or distance from obstacles, is a vital component of successful motion planning algorithms. Maintaining high clearance often creates safer paths for robots. Contemporary sampling-based planning algorithms that utilize the medial axis, or the set of all points equidistant to two or more obstacles, produce higher clearance paths. However, they are biased heavily toward certain portions of the medial axis, sometimes ignoring parts critical to planning, e.g., specific types of narrow passages. We introduce Uniform Medial Axis Probabilistic RoadMap (UMAPRM), a novel planning variant that generates samples uniformly on the medial axis of the free portion of C space . We theoretically analyze the distribution generated by UMAPRM and show its uniformity. Our results show that UMAPRM's distribution of samples along the medial axis is not only uniform but also preferable to other medial axis samplers in certain planning problems. We demonstrate that UMAPRM has negligible computational overhead over other sampling techniques and can solve problems the others could not, e.g., a bug trap. Finally, we demonstrate UMAPRM successfully generates higher clearance paths in the examples.

@INPROCEEDINGS{1242288,
author={ {Jyh-Ming Lien} and S. L. {Thomas} and N. M. {Amato}},
booktitle={2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422)}, title={A general framework for sampling on the medial axis of the free space},
year={2003},
volume={3},
number={},
pages={4439-4444 vol.3},
doi={10.1109/ROBOT.2003.1242288}}

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. Generalizing our previous work, this framework provides a template encompassing all possible retraction approaches. It also removes the requirement of exactly computing distance metrics thereby enabling application to more realistic high dimensional problems. In particular, our framework supports methods that retract a given configuration exactly or approximately onto the medial axis. As in our previous work, exact methods provide fast and accurate retraction in low (2 or 3) dimensional space. We also propose new approximate methods that can be applied 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 tradeoffs between accuracy and efficiency for different levels of approximation, and how the level of approximation effects the quality of the resulting roadmap.

@phdthesis{wilmarth-phd-1999
, author = "Steven A. Wilmarth"
, title = "A Probabilistic Method for Rigid-Body Motion Planning Using Sampling from the Medial Axis of the Free Space"
, school = "Department of Mathematics, Texas A\&M University"
, year = "1999"
, month = "December"
}

Motion planning in the presence of obstacles is an important problem in robotics with numerous applications in other areas. While complete motion planning algorithms do exist, they are rarely used in practice since they are computationally infeasible in all but the simplest cases. For this reason, many recent efforts have focused on probabilistic methods, which sacrifice completeness in favor of computational feasibility and applicability. In particular, several algorithms, known as probabilistic roadmap planners, have been shown to perform well in a number of practical situations; however, their performance degrades when paths are required to pass through narrow passages in the free space. In this dissertation we present a method of sampling the configuration space of a rigid body moving in three dimensions in which randomly generated configurations are retracted onto the medial axis of the free space. We develop some theory of the medial axis on the configuration space SE(3) and present algorithms that perform the retraction while avoiding explicit computation of the medial axis. Finally, we give some preliminary experimental results demonstrating the performance of the algorithm.

@INPROCEEDINGS{was-mprb-99,
author={Steven A. Wilmarth and and Nancy M. Amato and Peter F. Stiller},
booktitle={Proceedings of the Annual Symposium on Computational Geometry}
title={Motion Planning for a Rigid Body Using Random Networks on the Medial Axis of the Free Space},
year={1999},
pages={173-180},
doi={10.1145/304893.304967}}

Several motion planning methods using networks of randomly generated nodes in the free space have been shown to perform well in a number of cases, however their performance degrades when paths are required to pass through narrow passages in the,jree space. In [16] we proposed MAPRM, a method of sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space without having to first compute the medial axis; this was shown to increase sampling in narrow passages. In this paper we give details of the MAPRM algorithm for the case of a free-flying rigid body moving in three dimensions, and show that the retraction may be carried out without explicitly computing the C-obstacles or the medial axis. We give theoretical arguments to show that this improves sampling in narrow corridors, and present preliminary experimental results comparing the performance to uniform random sampling from the free space.

@INPROCEEDINGS{772448,
author={Wilmarth, S.A. and Amato, N.M. and Stiller, P.F.},
booktitle={Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C)},
title={MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space},
year={1999},
volume={2},
number={},
pages={1024-1031 vol.2},
doi={10.1109/ROBOT.1999.772448}}

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 new method of sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. We give algorithms that perform this retraction while avoiding explicit computation of the medial axis, and we show that sampling and retracting in this manner increases the number of nodes found in small volume corridors in a way that is independent of the volume of the corridor and depends only on the characteristics of the obstacles bounding it. Theoretical and experimental results are given to show that this improves performance on problems requiring traversal of narrow passages.