CCF- Algorithmic Foundations: Motion Planning for Geometrically Constrained Structures

连杆重构问题是机器人、机械设计、结构工程和生物几何学等领域的现代数学研究的基础，并有可能影响计算生物学，特别是蛋白质折叠建模中出现的问题，或者更一般地说，蛋白质的柔性和motion.This建议侧重于几何约束结构运动规划方法的基础。 选定的问题是一个长期计划的一部分，了解组合，刚性理论，代数和算法方面的各种运动规划方法的几何重构问题。 它建立在PI以前在以下方面的工作基础上：（a）将来自刚性理论的概念应用于二维（2D）连杆重新配置问题（例如使用点伪三角测量的Carpenter规则问题），（B）组合刚性（推广卵石游戏算法的二维刚性到其他类拟阵稀疏图，计算刚性和强调集群），（c）运动生成（用于二维伪三角剖分和用于三维具有许多环的复杂结构），以及（d）关于寻找旋转关节机器人操纵器的极值配置的最新结果。该提案旨在开发系统的运动规划方法，使用数学证明的技术，并利用离散的基本结构的几何约束系统的调查。 例子包括膨胀运动和伪三角形，运动和重新配置的三维结构（连杆，面板和铰链和多面体结构）和重新配置的机器人手臂走向极端的配置（最小值和最大值），连同他们的三维工作空间的理论研究。

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.