An Equivalence Relation for Local Path Sets - Robotics Institute Carnegie Mellon University

An Equivalence Relation for Local Path Sets

Workshop Paper, 9th International Workshop on the Algorithmic Foundations of Robotics (WAFR '10), pp. 19 - 35, December, 2010

Abstract

We propose a novel enhancement to the task of collision-testing a set of local paths. Our approach circumvents expensive collision-tests, yet it declares a continuum of paths collision-free by exploiting both the structure of paths and the outcome of previous tests. We define a homotopy-like equivalence relation among local paths and provide algorithms to (1) classify paths based on equivalence, and (2) implicitly collision-test up to 90% of them. We then prove both correctness and completeness of these algorithms before providing experimental results showing a performance increase up to 300%.

BibTeX

@workshop{Knepper-2010-10580,
author = {Ross Alan Knepper and Siddhartha Srinivasa and Matthew T. Mason},
title = {An Equivalence Relation for Local Path Sets},
booktitle = {Proceedings of 9th International Workshop on the Algorithmic Foundations of Robotics (WAFR '10)},
year = {2010},
month = {December},
editor = {David Hsu, Volkan Isler, Jean-Claude Latombe, and Ming C. Lin},
pages = {19 - 35},
publisher = {Springer},
address = {Tiergartenstrasse 17, 69121 Heidelberg, Germany},
}