MSPA-MCS: Fundamental Geodesic Problems in Computational Topology

MSPA-MCS：计算拓扑中的基本测地线问题

• 批准号: 0528086
• 负责人: Jeff Erickson
• 金额: $ 49.98万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-15 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0528086&HistoricalAwards=false
• 关键词: MSPA; MCS; Fundamental; Geodesic; Problems

This proposal describes an aggressive program of research in computational topology with a focus on computing and characterizing shortest paths in a variety of domains relevant to applications in robotics, coordination, and locomotion. We will investigate efficient descriptions of shortest-path information and geodesic structures in spaces with different types of constraints. The three main goals of our project are (1) developing algorithms to compute optimal paths, cycles, and other one-dimensional substructures, primarily in two-dimensional surfaces; (2) applying tools from Alexandrov geometry and topology to more efficiently characterize and compute shortest paths in non-positively curved spaces; and (3) developing languages to characterize spaces of optimal paths for motion systems with mechanical and/or nonholonomic constraints. Our proposed work draws on techniques from low-dimensional geometric and algebraic topology, combinatorial group theory, computational geometry, and non-holonomic motion planning.At a high level, our research focuses on techniques for computing the cheapest way to move from one point to another in a variety of interesting spaces. Consider, for example, a collection of robots moving around a factory floor. The positions of the robots can be encoded as a single point in a high-dimensional configuration space. The geometry of this space is governed by certain mechanical and/or kinematic constraints; for example, robots must never collide with each other, and they have a limited rate of acceleration. A shortest path in the configuration space describes a set of motions of the robots from one set of locations to another that is as efficient as possible. We plan to develop algorithms that compute such shortest paths quickly, by exploiting the overall ``shape" of the underlying space.

该提案描述了一个积极的计划，研究计算拓扑结构的重点是计算和表征最短路径在各种领域的相关应用，在机器人，协调和运动。 我们将研究在不同类型的约束空间中最短路径信息和测地线结构的有效描述。 我们的项目的三个主要目标是：（1）开发算法来计算最优路径，循环和其他一维子结构，主要是在二维表面上;（2）应用Alexandrov几何和拓扑学的工具来更有效地描述和计算非正弯曲空间中的最短路径;（3）开发语言来描述具有机械和/或非完整约束的运动系统的最优路径空间。 我们的工作借鉴了低维几何和代数拓扑，组合群论，计算几何和非完整运动规划的技术。在高层次上，我们的研究重点是计算在各种有趣的空间中从一个点移动到另一个点的最便宜的方法。 例如，考虑一组机器人在工厂地板上移动。 机器人的位置可以被编码为高维配置空间中的单个点。 这个空间的几何形状由某些机械和/或运动学约束决定;例如，机器人必须永远不会相互碰撞，并且它们具有有限的加速度。 配置空间中的最短路径描述了机器人从一组位置到另一组位置的尽可能有效的一组运动。 我们计划通过利用底层空间的整体“形状”来开发快速计算这种最短路径的算法。