We propose to design motion planning algorithms
using two ingredients: the subdivision paradigm coupled
with ``soft predicates''. This leads to a strong form of resolution completeness,
which we call ``resolution-exactness''.
We describe an algorithmic framework, called
``Soft Subdivision Search'' (SSS) for designing such algorithms.
There are many parallels between our framework and
the well-known Probabilistic Roadmap (PRM) framework.
Both frameworks lead to algorithms that are
* practical
* easy to implement
* flexible and extensible
* with adaptive and local complexity
We claim that SSS confers some major advantages: stronger
theoretical guarantees and halting.
Our several recent papers have demonstrated these properties
on various non-trivial motion planning problems.
In this talk, we outline a general axiomatic theory
underlying these results.
We address the issue of subdivision in non-Euclidean configuration spaces,
and also show how exact algorithms can be recovered within our framework.
SSS provides a theoretically sound basis for new
classes of algorithms in motion planning and beyond.
Such algorithms are novel, even in the exact case.
