- Cet évènement est passé.
Department 1 seminar : Chee Yap (New York University)
8 novembre 2018 @ 14:00 pm - 15:30 pm
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.
(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.
