CCF- Algorithmic Foundations: Motion Planning for Geometrically Constrained Structures

链接重构问题是机器人、机械设计、结构工程和生物几何等领域现代数学研究的基础，并具有影响计算生物学的潜力，特别是在蛋白质折叠建模或更一般地说，蛋白质柔韧性和运动中出现的问题。本提案的重点是运动规划方法的基础几何约束结构。所选择的问题是一个长期计划的一部分，旨在理解几何重构问题的各种运动规划方法的组合，刚性理论，代数和算法方面。它建立在pi之前的工作基础上：(a)将刚性理论的概念应用于二维（2D）连杆重构问题（例如使用尖伪三角剖分的卡彭特规则问题），(b)组合刚性（将2D刚性的Pebble Game算法推广到其他类的矩阵稀疏图，计算刚性和应力簇），(c)运动生成（用于2D的伪三角剖分和3D中具有许多循环的复杂结构），(d)旋转关节机械臂极值构型的最新研究成果。该提案旨在开发系统的运动规划方法，使用数学证明的技术和开发正在研究的几何约束系统的离散底层结构。示例包括扩展运动和伪三角测量，3D结构（连杆，面板和铰链和多面体结构）的运动和重新配置以及机器人手臂对极端配置（最小和最大）的重新配置，以及对其3D工作空间的理论研究。

Linkage 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 proposal focuses on the foundations of motion planning approaches to geometrically constrained structures. The selected problems are part of a long-term program for understanding the combinatorial, rigidity-theoretic, algebraic and algorithmic aspects of a variety of motion planning approaches to geometric reconfiguration questions. It builds upon the PIs' previous work on: (a) applying concepts from Rigidity Theory to 2-dimensional (2D) linkage reconfiguration problems (such as the Carpenter's Rule problem using pointed pseudo-triangulation), (b) Combinatorial Rigidity (generalizations of Pebble Game algorithms for 2D-rigidity to other classes of matroidal sparse graphs, computation of rigid and stressed clusters), (c) motion generation (for pseudo-triangulations in 2D and for complex structures with many loops in 3D), and (d) recent results on finding extremal configurations of revolute jointed robotic manipulators. The proposal aims at developing systematic motion planning approaches, using mathematically proven techniques and exploiting discrete underlying structures of the geometrically constrained systems under investigation. Examples include expansive motions and pseudo-triangulations, motion and reconfiguration for 3D-structures (linkages, panel-and-hinge and polyhedral structures) and reconfigurations of robot arms towards extremal configurations (minima and maxima), together with a theoretical investigation of their 3D workspace.