Cell-based Probabilistic Roadmaps (CPRM) for Efficient Path Planning in Large Environments
Klaas Klasing, Dirk Wollherr, MARTIN J. BUSS · 2007
Abstract — This paper presents a novel sampling-based path planning method called Cell-based Probabilistic Roadmaps (CPRM). The algorithm has both anytime and replanning characteristics and is superior to classical approaches in that it incrementally builds and reuses the roadmap. Because it maintains a graph structure that is tailored to the queries, CPRM is very fast in answering repeated queries, e.g. in replanning scenarios. Different design parameters allow to control and fine-tune the behavior of the algorithm. I.