AF: Small: Algorithmic Foundation and Framework for Subdivision Methods in Motion Planning and Computational Geometry

New York University, New York NY

Investigators

Abstract

This project addresses the fundamental problem of motion planning in robotics and related problems in Computational Geometry. There are three general approaches to robot motion planning: exact, sampling and subdivision. Exact Methods give the strongest guarantees of reliability, but exact algorithms are often unavailable or hard to implement. Roboticists today favor Sampling Methods, but these methods have difficulty in finding paths in narrow passages or in halting when there is no path. Subdivision Methods can overcome this halting problem, and can be as practical and efficient as Sampling Methods. However, Subdivision Methods today lack a clear foundation and non-trivial complexity analysis. This project develops a novel theory of Subdivision Methods in motion planning to provide both. The theory paves the way for a new class of efficient, practical and flexible path planners. These algorithms are validated by implementations and empirical comparisons with state-of-the-art path planners. Taking a leaf from the highly successful Probabilistic Roadmap (PRM) framework of the Sampling Methods, the researchers of this project formulate a similar framework called Soft Subdivision Search (SSS) for their new algorithms. The framework has several plug-and-play modules such as a search strategy and two primitives to split and classify subdivision boxes. The framework allows experimentation with a wide variety of algorithms, and is implemented in the research team's open source Core Library. This new theory of Subdivision Methods is based upon the twin foundations of resolution-exactness and soft predicates. Resolution-exactness is a principled response to the halting problem, and matches the needs of robotic systems with inherent uncertainties. Soft predicates are easy to implement correctly using interval methods and numerical approximation, and avoid the difficulties of exact algorithms. The complexity analysis of (adaptive) subdivision algorithms is a current challenge, which the research team addresses using the technique called continuous amortization. The theory extends and applies to many problems in Computational Geometry. It provides solutions where exact algorithms are currently non-existent (e.g., Voronoi-diagram construction of polyhedral objects) or impractical (e.g., Minkowski sum of polyhedra). Another significant direction is to introduce the subdivision framework in the external memory (or out-of-core) setting to reduce the I/O bottleneck when the input data is too large to fit in main memory. Such algorithms are critical in many big data applications. Overall, this project has the following potential impact. Practical and reliable planning algorithms will speed up the deployment of robot technology. Resolution-exactness provides the necessary safety factor as robots are employed in human environments and used in mission-critical applications like surgery. The ideas of soft primitives have broad implications for Computational Geometry. They allow computational geometers to attack continuous problems in Computational Science and Engineering (CS&E) where exact methods either do not exist or are unknown. The out-of-core extension enables these algorithms to cover the entire spectrum of the input sizes. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.