Rigidity, Flexibility, Stress and Motion: Foundations of Reconfiguration Problems in Computational Geometry

刚性、柔性、应力和运动：计算几何中重构问题的基础

• 批准号: 0728783
• 负责人: Ileana Streinu
• 金额: $ 20万
• 依托单位: Smith College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728783&HistoricalAwards=false
• 关键词: Rigidity; Flexibility; Stress; Motion; Foundations

Reconfiguration problems underlie modern mathematical investigations in robotics, mechanical design, structural engineering, and bio-geometry, and have the potential of impacting computational biology, especially the problems emerging from modeling protein folding or, more generally, protein flexibility and motion.This research is focused on fundamental mathematical properties and algorithms for reconfiguration problems (in particular, motion planning) of linkages and other flexible structures made from rigid parts connected together with various types of joints and hinges. The research builds upon the principal investigator's previous work on 2-dimensional robot arm reconfiguration (the Carpenter's Rule problem and pointed pseudo-triangulations), as well as on her current work in Combinatorial Rigidity (generalizations of Pebble Game algorithms for 2-dimensional-rigidity to other classes of sparse graphs, computation of rigid and stressed clusters) and Motion generation (for pseudo-triangulations in the plane, and for molecular structures with many loops in 3-dimensions). The goal of this research is furthering the general understanding of a notorious 140-old open problem in the Combinatorial Rigidity of bar-and-joint frameworks, expansive motions and pseudo-triangulations in 3-dimensions, as well as motion and reconfiguration for other 3d-structures (linkages, panel-and-hinge and polyhedral structures). These problems transcend application domains, but they are motivated by and may lead to developing models and techniques for addressing questions that arise in other areas of science and engineering.

重构问题是机器人学、机械设计、结构工程和生物几何学等现代数学研究的基础，并且有可能影响计算生物学，特别是蛋白质折叠或更普遍的蛋白质灵活性和运动建模中出现的问题。这项研究是专注于由通过各种类型的关节和铰链连接在一起的刚性部件制成的连杆和其他柔性结构的重新配置问题（特别是运动规划）的基本数学特性和算法。该研究建立在首席研究员之前关于二维机器人手臂重新配置（卡彭特规则问题和指向伪三角剖分）的工作以及她目前在组合刚性（二维刚性的卵石游戏算法的推广）方面的工作的基础上其他类别的稀疏图，刚性和应力簇的计算）和运动生成（用于平面中的伪三角剖分，以及用于3 维）。这项研究的目标是加深对一个臭名昭著的 140 年历史的开放问题的一般理解，该问题涉及杆和关节框架的组合刚性、3 维的膨胀运动和伪三角剖分，以及其他 3d 的运动和重新配置-结构（连杆、面板铰链和多面体结构）。这些问题超越了应用领域，但它们的动机是并可能导致开发模型和技术来解决其他科学和工程领域中出现的问题。