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

本项目探讨机器人运动规划的基本问题及计算几何中的相关问题。机器人运动规划一般有三种方法：精确、采样和细分。精确方法为可靠性提供了最强有力的保证，但精确算法通常不可用或难以实现。如今的机器人专家青睐采样方法，但这些方法在狭窄的通道中很难找到路径，或者在没有路径的情况下很难停下来。细分方法可以克服这种停止问题，并且可以像采样方法一样实用和有效。然而，目前的细分方法缺乏明确的基础和非琐碎的复杂性分析。本项目发展了一种新的细分方法理论，在运动规划中提供这两种方法。该理论为新型高效、实用、灵活的路径规划者铺平了道路。这些算法通过实现和与最先进的路径规划器的经验比较进行了验证。该项目的研究人员借鉴了采样方法中非常成功的概率路线图（PRM）框架，为他们的新算法制定了一个类似的框架，称为软细分搜索（SSS）。该框架有几个即插即用模块，如搜索策略和两个用于分割和分类细分框的原语。该框架允许对各种各样的算法进行实验，并在研究团队的开源核心库中实现。这种新的细分方法理论是建立在分辨率精确性和软谓词的双重基础之上的。精确分辨率是对停止问题的一种原则性响应，能够满足具有固有不确定性的机器人系统的需求。软谓词易于使用区间方法和数值逼近正确实现，避免了精确算法的困难。（自适应）细分算法的复杂性分析是当前的一个挑战，研究小组使用称为连续摊销的技术来解决这个问题。该理论扩展并应用于计算几何中的许多问题。它提供了目前不存在精确算法（例如，多面体对象的voronoi图构造）或不切实际（例如，多面体的Minkowski和）的解决方案。另一个重要的方向是在外部内存（或外核）设置中引入细分框架，以在输入数据太大而无法装入主存时减少I/O瓶颈。这种算法在许多大数据应用中至关重要。总体而言，该项目具有以下潜在影响。实用可靠的规划算法将加速机器人技术的部署。当机器人在人类环境中使用并用于手术等关键任务应用时，分辨率精度提供了必要的安全因素。软基元的思想在计算几何中有着广泛的含义。它们允许计算几何学者解决计算科学与工程（CS&amp；E）中不存在或不知道精确方法的连续问题。核外扩展使这些算法能够覆盖输入大小的整个范围。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.