Date of Award

2020

Document Type

Thesis

Degree Name

Bachelor of Science

Department

Mathematics

First Advisor

Dr. Jory Denny

Abstract

Motion planning is a difficult but important problem in robotics. Research has tended toward approximations and randomized algorithms, like sampling-based planning. Probabilistic RoadMaps (PRMs) are one common sampling-based planning approach, but they lack safety guarantees. One main approach, Medial Axis PRM (MAPRM) addressed this deficiency by generating robot configurations as far away from the obstacles as possible, but it introduced an extensive computational burden. We present two techniques, Medial Axis Bridge and Medial Axis Spherical Step, to reduce the computational cost of sampling in MAPRM and additionally propose recycling previously computed clearance information to reduce the cost of connection in MAPRM. We provide experimental results that demonstrate the effectiveness of our proposed methods by: (1) showing that Medial Axis Bridge and Medial Axis Spherical Step both reduce the sampling time of MAPRM by nearly 50% while guaranteeing the same degree of safety, and (2) showing a nearly 50% decrease in connection time in MAPRM.

Download

Share

COinS