On the Foundations of Soft Subdivision Search in Robotics

We propose to design motion planning algorithms with a strong form of resolution completeness, called resolution-exactness. Such planners can be implemented using soft predicates within the subdivision paradigm.  The advantage of softness is that we avoid the Zero Problem and other issues of exact computation.  We also describe the Soft Subdivision Search (SSS) framework for such planners. It has many parallels with the well-known Probabilistic Road Map (PRM) framework. Both frameworks lead to algorithms that are practical, easy to implement, flexible, extensible, with adaptive and local complexity.

However, SSS offers much stronger theoretical guarantees than PRM. Our several recent papers have demonstrated these favorable properties on various non-trivial motion planning problems. This talk provides a general axiomatic theory underlying these results.  We also address the issue of subdivision in non-Euclidean configuration spaces.

Chee Yap is Professor of Computer Science at the Courant Institute of Mathematical Sciences, New York University.  He has published over 170 papers in the areas of computational geometry, visualization, computer algebra, robotics and complexity theory. His book "Fundamental Problems in Algorithmic Algebra" published in 2000 by Oxford University Press, is widely cited in algebraic computation. He obtained a double BS degree in Computer Science and Mathematics from MIT in 1975, and a PhD from Yale in 1980, under Richard Lipton. He has served on editorial boards of SIAM Journal of Computing, Journal of Symbolic Computation, Algorithmica, JCSS, IJCGA, CGTA and MCS.