  Motion planning has been studied for nearly four decades now. Complete,
combinatorial motion planning approaches are theoretically well-rooted with
completeness guarantees but they are hard to implement. Sampling-based and
heuristic methods are easy to implement and quite simple to customize but they
lack completeness guarantees. Can the best of both worlds be ever achieved,
particularly for mission critical applications such as robotic surgery, space
explorations, and handling hazardous material? In this paper, we answer
affirmatively to that question. We present a new methodology, NUROA, to
numerically approximate the Canny's roadmap, which is a network of
one-dimensional algebraic curves. Our algorithm encloses the roadmap with a
chain of tiny boxes each of which contains a piece of the roadmap and whose
connectivity captures the roadmap connectivity. It starts by enclosing the
entire space with a box. In each iteration, remaining boxes are shrunk on all
sides and then split into smaller sized boxes. Those boxes that are empty are
detected in the shrink phase and removed. The algorithm terminates when all
remaining boxes are smaller than a resolution that can be either given as input
or automatically computed using root separation lower bounds. Shrink operation
is cast as a polynomial optimization with semialgebraic constraints, which is
in turn transformed into a (series of) semidefinite programs (SDP) using the
Lasserre's approach. NUROA's success is due to fast SDP solvers. NUROA
correctly captured the connectivity of multiple curves/skeletons whereas
competitors such as IBEX and Realpaver failed in some cases. Since boxes are
independent from one another, NUROA can be parallelized particularly on GPUs.
NUROA is available as an open source package at http://nuroa.sourceforge.net/.
