Soft Resolution-Exact Path Planning in Robotics: Theory and Practice

报告人：      Chee Yap,( Courant Institute, NYU)

(1) The notion of resolution-exact'' planners.
(2) Use of soft predicates'' to achieve resolution-exactness.
(3) A feature-based technique for constructing soft predicates.
We formulate an algorithmic framework called Soft Subdivision Search'' (SSS) that incorporates these foundation.  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
But compared to PRM and previous resolution work, SSS confers strong theoretical guarantees, including halting.

In a series of papers starting in 2013, we demonstrated the power of these ideas by producing planners for plane robots with 2, 3 and 4 degrees of freedom (DOFs) that outperform the state-of-art planars based on sampling.  Most recently, we produced planners for two spatial robots (rod and ring) with 5 DOFs that are competitive with state-of-art planners. We unify these by an general axiomatic theory that include subdivision in non-Euclidean configuration spaces, Joint work with  Y.-J.Chiang, B.Curto, J.-M.Lien, Z.Luo, J.P.Ryan, C.Wang, B.Zhou.