How to construct small probabilistic roadmaps with a good coverage?

Abstract

We investigate how we can construct small probabilistic roadmaps in a reasonable time while still keeping a good coverage and connectivity. We propose a new neighborhood-based method that can reduce the size of the roadmaps by filtering out unnecessary nodes. We then experimentally test it against a basic probabilistic roadmap planner and a visibility-based planner. We use both a uniform sampling and a bridge test sampling in our tests. The results show that the neighborhood-based method can reduce the number of nodes considerably. The neighborhood-based method is simple to implement, it works well with a uniform sampling, and it does not need any additional parameters when compared with the basic planner.

Keywords:

• motion planning
• probabilistic roadmaps
• small roadmaps

Acknowledgements

The research of the first author was supported by the Tampere Doctoral Programme in Information Science and Engineering (TISE).