  We present a general and modular algorithmic framework for path planning of
robots. Our framework combines geometric methods for exact and complete
analysis of low-dimensional configuration spaces, together with practical,
considerably simpler sampling-based approaches that are appropriate for higher
dimensions. In order to facilitate the transfer of advanced geometric
algorithms into practical use, we suggest taking samples that are entire
low-dimensional manifolds of the configuration space that capture the
connectivity of the configuration space much better than isolated point
samples. Geometric algorithms for analysis of low-dimensional manifolds then
provide powerful primitive operations. The modular design of the framework
enables independent optimization of each modular component. Indeed, we have
developed, implemented and optimized a primitive operation for complete and
exact combinatorial analysis of a certain set of manifolds, using arrangements
of curves of rational functions and concepts of generic programming. This in
turn enabled us to implement our framework for the concrete case of a polygonal
robot translating and rotating amidst polygonal obstacles. We demonstrate that
the integration of several carefully engineered components leads to significant
speedup over the popular PRM sampling-based algorithm, which represents the
more simplistic approach that is prevalent in practice. We foresee possible
extensions of our framework to solving high-dimensional problems beyond motion
planning.
