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

AF：小：运动规划和计算几何中细分方法的算法基础和框架

• 批准号: 2008768
• 负责人: Yi-Jen Chiang
• 金额: $ 49.9万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008768&HistoricalAwards=false
• 关键词: AF; Small; Algorithmic; Foundation; Framework

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.

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

项目成果

Soft subdivision motion planning for complex planar robots

复杂平面机器人的软细分运动规划

• DOI: 10.1016/j.comgeo.2020.101683
• 发表时间: 2021-01
• 期刊: Computational Geometry
• 作者: Zhou, Bo;Chiang, Yi;Yap, Chee
• 通讯作者: Yap, Chee

Novel Range Functions via Taylor Expansions and Recursive Lagrange Interpolation with Application to Real Root Isolation

通过泰勒展开和递归拉格朗日插值的新颖范围函数及其在实根隔离中的应用

• DOI: 10.1145/3452143.3465532
• 发表时间: 2021-07-18
• 期刊: Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation
• 作者: K. Hormann;Lucas Kania;C. Yap
• 通讯作者: C. Yap

Streaming Approach to In Situ Selection of Key Time Steps for Time‐Varying Volume Data

用于时间变化体积数据关键时间步长的流式方法

• DOI: 10.1111/cgf.14542
• 发表时间: 2022-06-01
• 期刊: Computer Graphics Forum
• 影响因子: 2.5
• 作者: Mengxi Wu;Yi;Christopher Musco
• 通讯作者: Christopher Musco