  We consider path planning for a rigid spatial robot with 6 degrees of freedom
(6 DOFs), moving amidst polyhedral obstacles. A correct, complete and practical
path planner for such a robot has never been achieved, although this is widely
recognized as a key challenge in robotics. This paper provides a complete
"explicit" design, down to explicit geometric primitives that are easily
implementable.
  Our design is within an algorithmic framework for path planners, called Soft
Subdivision Search (SSS). The framework is based on the twin foundations of
$\epsilon$-exactness and soft predicates, which are critical for rigorous
numerical implementations. The practicality of SSS has been previously
demonstrated for various robots including 5-DOF spatial robots.
  In this paper, we solve several significant technical challenges for SE(3)
robots: (1) We first ensure the correct theory by proving a general form of the
Fundamental Theorem of the SSS theory. We prove this within an axiomatic
framework, thus making it easy for future applications of this theory. (2) One
component of $SE(3) = R^3 \times SO(3)$ is the non-Euclidean, non-orientable
space SO(3). We design a novel topologically correct data structure for SO(3).
Using the concept of subdivision charts and atlases for SO(3), we can now carry
out subdivision of SO(3). (3) The geometric problem of collision detection
takes place in $R^3$, via the footprint map. Unlike sampling-based approaches,
we must reason with the notion of footprints of configuration boxes, which is
much harder to characterize. Exploiting the theory of soft predicates, we
design suitable approximate footprints which, when combined with the highly
effective feature-set technique, lead to soft predicates. (4) Finally, we make
the underlying geometric computation "explicit", i.e., avoiding a general
solver of polynomial systems, in order to allow a direct implementation.
