MARRT: Medial Axis biased rapidly-exploring random trees

Jory Denny; Evan Greco; Shawna Thomas; Nancy M. Amato

doi:10.1109/ICRA.2014.6906594

MARRT: Medial Axis biased rapidly-exploring random trees

Jory Denny, Evan Greco, Shawna Thomas, Nancy M. Amato

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

44 Scopus citations

Abstract

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

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	90-97
Number of pages	8
ISBN (Print)	9781479936854
DOIs	https://doi.org/10.1109/ICRA.2014.6906594
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 University of Science and Technology (KAUST). J. Denny supported in part by an NSF Graduate Research Fellowship.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

Access to Document

10.1109/ICRA.2014.6906594

Cite this

@inproceedings{a3fa211ebd364ca4b61cea1f40466984,

title = "MARRT: Medial Axis biased rapidly-exploring random trees",

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

author = "Jory Denny and Evan Greco 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 University of Science and Technology (KAUST). J. Denny supported in part by an NSF Graduate Research Fellowship. This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2014",

month = may,

doi = "10.1109/ICRA.2014.6906594",

language = "English (US)",

isbn = "9781479936854",

pages = "90--97",

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

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

}

TY - GEN

T1 - MARRT: Medial Axis biased rapidly-exploring random trees

AU - Denny, Jory

AU - Greco, Evan

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 University of Science and Technology (KAUST). J. Denny supported in part by an NSF Graduate Research Fellowship. This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2014/5

Y1 - 2014/5

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

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

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

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

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

U2 - 10.1109/ICRA.2014.6906594

DO - 10.1109/ICRA.2014.6906594

M3 - Conference contribution

SN - 9781479936854

SP - 90

EP - 97

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

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

MARRT: Medial Axis biased rapidly-exploring random trees

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this