AF: Small: Collaborative Research: Reconfiguration Algorithms

AF：小型：协作研究：重构算法

• 批准号: 1422311
• 负责人: Diane Souvaine
• 金额: $ 21.14万
• 依托单位: Tufts University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422311&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Reconfiguration

Computational geometry uses graphs, polygons, and arrangements to model physical objects and phenomena. Some of the objects are inherently flexible (e.g., proteins and robotic arms), others are stationary but require adjustments on a regular basis (e.g., communication and transportation networks). The focus of this project is on reconfigurations. The goal is to describe, understand, and control the combinatorial, geometric and topological changes in geometric configurations. This research project will develop new algorithms and data structures for modifying geometric configurations in three areas: (1) Optimization problems for in the configuration space of geometric objects, including graph augmentation, variations of the classical TSP tour problem, and network design for multiple criteria. (2) Reconfiguration through discrete moves, where current challenges include designing efficient data structures to support shortest path computation in the configuration space, approximating the diameter and radius of configuration spaces, and deciding whether reconfiguration is possible. (3) Modeling continuous motion, which includes motion planning algorithms and corresponding dynamic data structures for bar-and-joint frameworks, hinged polygons, and disk arrangements, motivated by applications in protein folding. A unified approach to discrete and continuous reconfiguration problems allows breaking down complex systems into elementary operations, which in turn leads to more efficient computational tools. The collaboration between faculty members and students from two universities ensures a high quality of training and opens new opportunities for all participating students.

计算几何学使用图形、多边形和排列来模拟物理对象和现象。一些物体是固有柔性的（例如，蛋白质和机械臂），其它的是固定的但需要定期调整（例如，交通运输网络）。这个项目的重点是重新配置。其目标是描述，理解和控制的组合，几何和拓扑变化的几何配置。本研究计画将在三个领域发展新的演算法与资料结构以修正几何组态：（1）几何物件组态空间的最佳化问题，包括图扩充、经典TSP巡回问题的变形、以及多准则网路设计。(2)通过离散移动的重构，其中当前的挑战包括设计有效的数据结构，以支持配置空间中的最短路径计算，近似配置空间的直径和半径，并决定是否可以重构。(3)建模连续运动，其中包括运动规划算法和相应的动态数据结构的酒吧和关节的框架，铰链多边形，和磁盘的安排，在蛋白质折叠的应用程序的动机。离散和连续重构问题的统一方法允许将复杂系统分解为基本操作，这反过来又导致更有效的计算工具。来自两所大学的教师和学生之间的合作确保了高质量的培训，并为所有参与的学生开辟了新的机会。