Roadmap subsampling for changing environments

Conference Paper

Precomputed roadmaps can enable effective multi-query motion planning: a roadmap can be built for a robot as if no obstacles were present, and then after edges invalidated by obstacles observed at query time are deleted, path search through the remaining roadmap returns a collision-free plan. However, large roadmaps are memory intensive to store, and can be too slow for practical use. We present an algorithm for compressing a large roadmap so that the collision detection phase fits into a computational budget, while retaining a high probability of finding high-quality paths. Our algorithm adapts work from graph theory and data mining by treating roadmaps as unreliable networks, where the probability of edge failure models the probability of a query-time obstacle causing a collision. We experimentally evaluate the quality of the resulting roadmaps in a suite of four motion planning benchmarks.

Full Text

Duke Authors

Cited Authors

  • Murray, S; Konidaris, GD; Sorin, DJ

Published Date

  • October 24, 2020

Published In

Start / End Page

  • 5664 - 5670

Electronic International Standard Serial Number (EISSN)

  • 2153-0866

International Standard Serial Number (ISSN)

  • 2153-0858

International Standard Book Number 13 (ISBN-13)

  • 9781728162126

Digital Object Identifier (DOI)

  • 10.1109/IROS45743.2020.9341431

Citation Source

  • Scopus