2013 | OriginalPaper | Buchkapitel
Toggle PRM: A Coordinated Mapping of C-Free and C-Obstacle in Arbitrary Dimension
verfasst von : Jory Denny, Nancy M. Amatoo
Erschienen in: Algorithmic Foundations of Robotics X
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Motion planning has received much attention over the past 40 years. More than 15 years have passed since the introduction of the successful sampling-based approach known as the Probabilistic RoadMap Method (PRM). PRM and its many variants have demonstrated great success for some high-dimensional problems, but they all have some level of difficulty in the presence of narrow passages. Recently, an approach called Toggle PRM has been introduced whose performance does not degrade for 2-dimensional problems with narrow passages. In Toggle PRM, a simultaneous, coordinated mapping of both C
free
and C
obst
is performed and every connection attempt augments one of the maps – either validating an edge in the current space or adding a configuration ’witnessing’ the connection failure to the other space. In this paper, we generalize Toggle PRM to
d
-dimensions and show that the benefits of mapping both C
free
and C
obst
continue to hold in higher dimensions. In particular, we introduce a new narrow passage characterization,
α
-
ε
-separable narrow passages, which describes the types of passages that can be successfully mapped by Toggle PRM. Intuitively,
α
-
ε
-separable narrow passages are arbitrarily narrow regions of C
free
that separate regions of C
obst
, at least locally, such as hallways in an office building. We experimentally compare Toggle PRM with other methods in a variety of scenarios with different types of narrow passages and robots with up to 16
dof
.