UMAPRM: Uniformly sampling the medial axis

Hsin-Yi Cindy Yeh; Jory Denny; Aaron Lindsey; Shawna Thomas; Nancy M. Amato

doi:10.1109/ICRA.2014.6907711

UMAPRM: Uniformly sampling the medial axis

Hsin-Yi Cindy Yeh, Jory Denny, Aaron Lindsey, Shawna Thomas, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

15 Scopus citations

Abstract

© 2014 IEEE. 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 Cspace. 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.

Original language	English (US)
Title of host publication	2014 IEEE International Conference on Robotics and Automation (ICRA)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	5798-5803
Number of pages	6
ISBN (Print)	9781479936854
DOIs	https://doi.org/10.1109/ICRA.2014.6907711
State	Published - May 2014
Externally published	Yes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUS-C1-016-04
Acknowledgements: This research supported in part by NSF awards CNS-0551685, CCF-0833199, CCF-0830753, IIS-0916053, IIS-0917266, EFRI-1240483, RI-1217991, by NIH NCI R25 CA090301-11, by Chevron, IBM, Intel, Oracle/Sun and by Award KUS-C1-016-04, made by King Abdullah Universityof Science and Technology (KAUST). J. Denny supported in part by anNSF Graduate Research Fellowship.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

Access to Document

10.1109/ICRA.2014.6907711

Cite this

@inproceedings{bace58e5992c4b78bc5bb8d1ebb17c7f,

title = "UMAPRM: Uniformly sampling the medial axis",

abstract = "{\textcopyright} 2014 IEEE. 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 Cspace. 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.",

author = "Yeh, {Hsin-Yi Cindy} and Jory Denny and Aaron Lindsey and Shawna Thomas and Amato, {Nancy M.}",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledged KAUST grant number(s): KUS-C1-016-04 Acknowledgements: This research supported in part by NSF awards CNS-0551685, CCF-0833199, CCF-0830753, IIS-0916053, IIS-0917266, EFRI-1240483, RI-1217991, by NIH NCI R25 CA090301-11, by Chevron, IBM, Intel, Oracle/Sun and by Award KUS-C1-016-04, made by King Abdullah Universityof Science and Technology (KAUST). J. Denny supported in part by anNSF Graduate Research Fellowship. This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2014",

month = may,

doi = "10.1109/ICRA.2014.6907711",

language = "English (US)",

isbn = "9781479936854",

pages = "5798--5803",

booktitle = "2014 IEEE International Conference on Robotics and Automation (ICRA)",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

}

TY - GEN

T1 - UMAPRM: Uniformly sampling the medial axis

AU - Yeh, Hsin-Yi Cindy

AU - Denny, Jory

AU - Lindsey, Aaron

AU - Thomas, Shawna

AU - Amato, Nancy M.

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledged KAUST grant number(s): KUS-C1-016-04 Acknowledgements: This research supported in part by NSF awards CNS-0551685, CCF-0833199, CCF-0830753, IIS-0916053, IIS-0917266, EFRI-1240483, RI-1217991, by NIH NCI R25 CA090301-11, by Chevron, IBM, Intel, Oracle/Sun and by Award KUS-C1-016-04, made by King Abdullah Universityof Science and Technology (KAUST). J. Denny supported in part by anNSF Graduate Research Fellowship. This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2014/5

Y1 - 2014/5

N2 - © 2014 IEEE. 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 Cspace. 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.

AB - © 2014 IEEE. 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 Cspace. 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.

UR - http://hdl.handle.net/10754/600123

UR - http://ieeexplore.ieee.org/document/6907711/

UR - http://www.scopus.com/inward/record.url?scp=84929208707&partnerID=8YFLogxK

U2 - 10.1109/ICRA.2014.6907711

DO - 10.1109/ICRA.2014.6907711

M3 - Conference contribution

SN - 9781479936854

SP - 5798

EP - 5803

BT - 2014 IEEE International Conference on Robotics and Automation (ICRA)

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

UMAPRM: Uniformly sampling the medial axis

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this