The next seminar of Department 1 will take place on Thursday, November 8th at 2pm in room A008.
Chee Yap (New York University) will give a presentation entitled “Subdivision Path Planning in Robotics: Theory and Practice”.
ABSTRACT:
Motion planning is a fundamental problem in robotics. We propose to design path planners based on three foundations:
(1) The notion of resolution-exact” planners. Conceptually, it avoids the zero problem of exact computation.
(2) The use of soft predicates” for achieving such algorithms in the subdivision approach.
(3) The feature-based technique” for constructing such soft predicates.
We formulate an algorithmic framework called Soft Subdivision Search” (SSS) that incorporates these ideas. There are many parallels between our framework and the well-known Sampling or Probabilistic Roadmap framework. Both frameworks lead to algorithms that are – practical – easy to implement – flexible and extensible – with adaptive and local complexity. In contrast to sampling and previous resolution approaches, SSS confers strong theoretical guarantees, including halting.
In a series of papers we demonstrated the power of these ideas, by producing planners for planar robots with 2, 3 and 4 degrees of freedom (DOF) that outperform or matches state-of-art sampling-based planners. Most recently, we produced a planner for two spatial robots (rod and ring) with 5 DOFs. Non-heuristic planners for such robots has been considered a challenge for the subdivision approach. We outline a general axiomatic theory underlying these results, including subdivision in non-Euclidean configuration spaces,
Joint work with Y.J.Chiang, C.H.Hsu, C.Wang, Z.Luo, B.Zhou, J.P.Ryan.
