DMS-EPSRC: Topology of Automated Motion Planning

这个项目将研究有助于理解机器人在物理环境中动作的复杂性的新数学。因此，该项目专注于那些不同于纯粹计算工作的方面。相反，当机器人从一个地方移动到另一个地方时，它会感知环境，在其中行动以实现某个目标，对其中的变化做出反应，并可能与其他人进行交流。与外部环境的交互通常通过改变某些内部状态来实现，因此，例如，在两个不同的场合(即使在相同的外部条件下)执行的给定运动可能是机器人内部状态的不同改变的结果。通过建立这些问题的抽象拓扑模型，PI将与英国的M.Farber合作，使用代数和几何工具来阐明解决这些问题时必然出现的一些权衡(例如，输出的稳定性与能够处理各种环境的灵活性)。朝着这个方向的第一步是一个数值不变量，它衡量机器人运动规划所需的不稳定性的数量，无论可用的计算资源如何，或者等价地测量所需的最小随机性的量是近20年前由Farber发明的拓扑复杂性，并经常被上同调工具研究。为了了解灵活性的额外成本“，需要解决运动规划问题但在各种不同的环境中施加的成本(例如，Roomba在家具移动后学习在房间周围移动的方式)，D.Cohen，Farber和PI引入了参数化拓扑复杂性；初步计算表明，它确实捕捉到了普通复杂性无法捕捉到的一些新现象。除了拓扑学和参数化复杂性的进一步发展，该项目旨在研究隐藏状态(例如，从工作图的一根光纤移动到另一根光纤)、感知(例如，随时间展开的关于环境的不完整信息的作用)、为非纤颤属开发有用的技术，以及使用持久同源性来了解资源的作用(例如，速度、路径长度、能量使用、感知成本等)。在规划任务方面。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project will investigate new mathematics useful for understanding the complexity of robotic action in a physical environment. The project thus concentrates on those aspects that are different from purely computational work. Instead, as a robot moves from place to place, it senses its environment, acts within it to achieve some goal, responds to changes in it, and might communicate with others. The interactions with the external environment are typically achieved via changes to some internal states, so that, for example, a given motion performed on two different occasions (even under identical external conditions) could be the result of different changes to the internal state of the robot. By building abstract topological models of these issues, the PI, in collaboration with M. Farber in the UK, will use algebraic and geometric tools to shed light on some of the tradeoffs (for example of stability of output against flexibility in being able to handle a variety of environments) that necessarily arise when solving such problems.The first step in this direction, a numerical invariant that measures the amount of instability necessary, no matter the computational resources available, for robotic motion planning, or equivalently the minimum amount of stochasticity necessary is the topological complexity invented almost twenty years ago by Farber, and frequently studied by cohomological tools. To understand the additional cost of flexibility", the costs imposed by needing to solve a motion planning problem but in a variety of different environments (say for a Roomba to learn its way around a room after the furniture has been moved), D. Cohen, Farber, and the PI introduced parametrized topological complexity; preliminary calculations show that it does indeed capture some new phenomena that the ordinary complexity does not. Besides further development of topological and parametrized complexity, this project aims to study the role of hidden states (e.g. moving from one fiber to another of a work map), sensing (e.g. the role of incomplete information about the environment that unfolds over time), the development of a useful technology for genus of non-fibrations, and the use of persistent homology to understand about the role of resources (e.g. the speed, path length, energy usage, sensing costs, etc.) in planning tasks.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.