权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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）。该框架有几个即插即用的模块，如搜索策略和两个原语分裂和分类细分框。该框架允许使用各种算法进行实验，并在研究团队的开源Core Library中实现。这种新的细分方法理论基于分辨率精确性和软谓词的双重基础。分辨率精确性是对停机问题的原则性响应，并且匹配具有固有不确定性的机器人系统的需求。软谓词易于使用区间方法和数值逼近正确实现，避免了精确算法的困难。（自适应）细分算法的复杂性分析是当前的一个挑战，研究团队使用称为连续摊销的技术来解决这个问题。该理论扩展并适用于计算几何中的许多问题。它提供了目前不存在精确算法的解决方案（例如，多面体对象的Voronoi图构造）或不切实际（例如，Minkowski sum of polyhedra）。另一个重要的方向是在外部存储器（或核外）设置中引入细分框架，以减少输入数据太大而无法放入主存时的I/O瓶颈。这些算法在许多大数据应用中至关重要。总体而言，该项目具有以下潜在影响。实用和可靠的规划算法将加快机器人技术的部署。分辨率精确度提供了必要的安全因素，因为机器人在人类环境中使用，并用于手术等关键任务应用。软基元的思想对计算几何有着广泛的影响。它们允许计算几何学家攻击计算科学与工程（CS E）中的连续问题，其中精确的方法不存在或未知。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

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

DOI：
10.1145/3452143.3465532
发表时间：
2021-07
期刊：
Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation
影响因子：
0
作者：
K. Hormann;Lucas Kania;C. Yap
通讯作者：
K. Hormann;Lucas Kania;C. Yap

Soft subdivision motion planning for complex planar robots