CCF- Algorithmic Foundations: Motion Planning for Geometrically Constrained Structures

CCF-算法基础：几何约束结构的运动规划

• 批准号: 1016988
• 负责人: Ileana Streinu
• 金额: $ 21.46万
• 依托单位: Smith College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016988&HistoricalAwards=false
• 关键词: CCF; Algorithmic; Foundations; Motion; Planning

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.

连杆重构问题是机器人学、机械设计、结构工程和生物几何学等现代数学研究的基础，并且有可能影响计算生物学，尤其是蛋白质折叠或更普遍的蛋白质灵活性和运动建模中出现的问题。重点关注几何约束结构运动规划方法的基础。 所选问题是长期计划的一部分，旨在理解几何重构问题的各种运动规划方法的组合、刚性理论、代数和算法方面。 它建立在 PI 之前的工作基础上：(a) 将刚性理论的概念应用于二维 (2D) 连杆重新配置问题（例如使用尖点伪三角剖分的卡彭特规则问题），(b) 组合刚性（用于 2D 刚度到其他类拟阵稀疏图的 Pebble Game 算法、刚性和应力簇的计算），(c) 运动生成（用于2D 中的伪三角剖分和 3D 中具有许多循环的复杂结构），以及 (d) 寻找旋转关节机器人操纵器极值配置的最新结果。该提案旨在开发系统的运动规划方法，使用经过数学​​验证的技术并利用所研究的几何约束系统的离散基础结构。 示例包括膨胀运动和伪三角测量、3D 结构的运动和重新配置（连杆、面板铰链和多面体结构）以及机器人手臂针对极值配置（最小值和最大值）的重新配置，以及对其 3D 结构的理论研究工作区。