报告题目：Theory and Practice of Subdivision Path Planning in Robotics

报告人：Chee K. Yap (Courant Institute of Mathematical Science, New York University, USA)

时间：2018年8月10日下午4：00-5：00

地点：2022世界杯官方买球网址新主楼F424

摘要：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 designing such algorithms within the subdivision framework. (3) A feature-based approach for constructing soft predicates. We then describe 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

Compared to PRM and previous resolution approaches,

SSS confers strong theoretical guarantees, including halting.

In a series of recent papers we demonstrated the power of these ideas, by producing planners for plane robots with 2, 3 and 4 degrees of freedom (DOF) that outperform the state-of-art planars based on random sampling. Finally, we produced a planner for two spatial robots (rod and ring) with 5 DOFs that is competitive with state-of-art planners.

We unify these by outlining 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.

报告人简介：Chee K. Yap is Professor of Computer Science at the Courant Institute of Mathematical Sciences, New York University. His research interests include computational geometry, algorithms and complexity, visualization, algebraic and topological computation, and algorithmic robotics. He has published about 200 papers in major conferences and journals, in the area of algorithms and complexity. He is a winner of the Lester R. Ford Award and has won the Best Paper Award of the conference RSS 2013, and his two books are Distinguished Lectures.

邀请人：牟晨琪