2013 | OriginalPaper | Buchkapitel
Sparse Roadmap Spanners
verfasst von : Andrew Dobson, Athanasios Krontiris, Kostas E. Bekris
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
Asymptotically optimal planners like
prm
* guarantee that solutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed, asymptotically near-optimal solutions produce sparser graphs by not including all edges. The idea stems from graph spanners, which produce sparse subgraphs that guarantee near-optimal paths. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes, meaning only infinite graphs have the desired properties. This work proposes an approach, called
spars
, that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner converges to zero as iterations increase, which suggests that finite-size data structures may exist that have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of
prm
* with graph spanners. Simulations for rigid bodies show that
spars
indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions is even better than the theoretical bounds.