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

重构问题是机器人学、机械设计、结构工程和生物几何等现代数学研究的基础，具有潜在的影响计算生物学的潜力，特别是蛋白质折叠或更一般的蛋白质柔性和运动建模所产生的问题。本研究集中于连杆和其他柔性结构的重构问题的基本数学性质和算法(特别是运动规划)，这些柔性结构由刚性部件连接在一起。这项研究建立在首席研究员之前在二维机器人手臂重构(木匠规则问题和定点伪三角剖分)方面的工作，以及她目前在组合刚性(二维Pebble游戏算法的推广到其他类型的稀疏图、刚性和应力簇的计算)和运动生成(平面伪三角剖分和三维中具有许多环的分子结构)方面的工作的基础上。这项研究的目的是促进对一个臭名昭著的140年前悬而未决的问题的普遍理解，即杆与关节框架的组合刚度、三维扩张运动和伪三角剖分以及其他三维结构(连杆、板铰和多面体结构)的运动和重构。这些问题超越了应用领域，但它们是由开发模型和技术来解决科学和工程其他领域中出现的问题所驱动的，并可能导致这些模型和技术的发展。

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.