CRII:IIS:Topology Aware Configuration Spaces

运动规划是机器人技术中的一个重要概念，其定义很简单-为机器人从起点到目标位置找到一条路径，其中起点和目标由机器人期望执行的任务决定，例如，在工厂车间导航，操纵手臂拿起物体等。然而，这很难建模和计算。为了有效地规划运动，需要事先获得关于机器人环境的完整信息，然后构建有效的算法来产生机器人可以利用的轨迹；不幸的是，事实证明这很难实现。为了减轻这一缺点，基于采样的算法被开发出来，以近似给定的环境信息。对这些算法的分析表明，如果一个轨迹存在，这些采样算法将找到这个轨迹。但是，出现的问题是，如何很好地近似环境信息以确保高成功率。该项目将开发算法，通过使用基于拓扑和几何的公式为这种近似产生度量，从而更好地近似环境信息规划空间。这个项目将给采样算法更多的控制，以帮助确定环境中的哪些区域需要更多的关注和表现，这将反过来改善执行运动规划所需的时间。由于对运动规划算法的需求日益增长，即使在逼近规划空间时也要快速准确，并且需要测量这种逼近，以便更好地操纵和控制规划过程，因此本项目旨在设计一套形式化表示和算法，以a)更好地表征规划空间的拓扑结构，b)结合形式化方法来规划和逼近规划空间。C)提供这种近似的度量，并利用这些信息来更好地指导困难地区的规划，d)随后减少规划时间和内存使用，这可能会导致更实时的规划算法。此外，本项目中开发的算法和定理将适用于任何类型环境（动态、复杂或异构）中的任何规划方法。因此，这项研究消除了当前运动规划实践中的一个主要障碍，其中近似技术是最先进的。该项目将极大地增加运动规划算法的可扩展性，因为它将具有拓扑丰富的信息，测量在规划空间中所做的采样近似，并随后给出这些规划空间的更明智的描述。该项目将以一种独特而新颖的方式捕捉规划空间的拓扑结构，使用数学公式，如Vietoris Rips复合体、图形“粘合”，以及在规划算法中创新地使用简单折叠。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Motion planning is an important concept in robotics with a simple definition - find a path for a robot from its start to a goal position, where the start and goal is determined by the task the robot is expected to perform e.g., navigate a factory floor, manipulate an arm to pick up an object etc. This however is difficult to model and compute. To efficiently plan motions neccessitates having complete information about the robot's environment beforehand, then building efficient algorithms that produces a trajectory the robot can utilize; unfortunately, this has proven difficult to achieve. To mitigate this shortcoming, sampling-based algorithms were developed that approximate the information given about the environment. Analysis of these algorithms shows that if a trajectory exists, these sampling algorithms will find such trajectory. The question that arises, though, is how well was the environment information approximated to ensure a high success rate. This project will develop algorithms that better approximate the environment information planning space by producing a measure for this approximation using topology and geometric based formulations. This project will give more control to sampling algorithms to help determine what areas in the environment needs more attention and representation, which will in turn improve on the time needed to perform motion planning.Motivated by the increasing need for motion planning algorithms that are fast and accurate even when they approximate the planning space, and a need to also measure such approximations so as to better manipulate and control the planning process, this project aims to devise a set of formal representations and algorithms to a) better characterize the topology of the planning space, b) combine formal methods to plan and approximate the planning space, c) provide a measure of such approximations and utilize this information to better guide planning in difficult regions, and d) subsequently reduce planning time and memory use which will potentially lead to more real time planning algorithms. In addition, the algorithms and theorems developed in this project will be adaptable to any planning method in any type of environment (dynamic, complex or heterogeneous). This research thus removes a major barrier in the current practice of motion planning where approximate techniques are the state of the art. This project will greatly increase the scalability of motion planning algorithms because it will be topologically rich with information, measure the sampling approximations made in the planning space, and subsequently give a more informed description of these planning spaces. This project will capture in a unique and novel way the topology of the planning space using mathematical formulations such as the Vietoris Rips complex, graph "gluing", and an innovative use of simplicial collapses in planning algorithms.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.