We give a brief history of Path Planning, also known as FIND-PATH Problem in AI. It is a paradigmic problem of AI in two senses: first, path planning is a key characteristic of autonomous intelligence. Second, it illustrates an ongoing debate: is AI fundamentally symbolic or connectionist (numeric)? FIND-PATH has been a standard problem in the symbolic/algebraic computation literature ever since the work of Schwartz-Sharir (1983). In Symbolic Computation (SC) as in AI, there is increasing interest in numerical approaches to SC. This is a paradox since traditionally, symbolic computation is the pathway to avoid numerical error and arbitrary thresholds. The correct implementation of exact/algebraic algorithms is highly non-trivial for problems such as FIND-PATH because of numerical errors. Recently, we introduced resolution-exactness as a soft-numerical approach to FIND-PATH problems. Using our Soft Subdivision Search (SSS) framework, we have demonstrated that our theory leads to correct (validated) implementations that matches or exceeds the state-of-art performance. We have demonstrated this with a variety of robots, including spatial robots with 5 degrees-of-freedom. Finally, we outline new challenges and extensions.

This lecture will be in two parts.

Chee Yap is Professor of Computer Science at the Courant Institute of Mathematical Sciences of New York University. He has published over 190 papers in computational geometry, computer algebra, robotics, visualization and complexity theory. His book "Fundamental Problems of Algorithmic Algebra" (Oxford Press 2000) is widely cited in algebraic computation. He has a double BS degree in Computer Science and Mathematics from MIT (1972-75) and PhD in Computer Science from Yale (1975-80) under Richard Lipton. He has served on editorial boards of SIAM Journal of Computing, Journal of Symbolic Computation, Algorithmica, JCSS, IJCGA, CGTA and MCS. Recently, he was conference chairs of ISSAC 2017 and ICMS 2014.