EAGER: Computing Compact Roadmaps for Motion Planning

运动规划是机器人从一个位置移动到另一个位置需要解决的基本问题。这个问题出现在许多领域，如自动驾驶汽车和自动装配。运动规划算法通常对机器人的配置进行采样以构建机器人配置的空间的地图。 随着更多的计算能力变得可用，样本可以更快地放置，构建更好的地图，但在内存中的巨大成本。 这个项目探讨了寻找低内存近似地图，允许快速和准确的运动规划的问题。 方法包括算法的数学分析，以及在仿真中应用算法的实验。预期的结果包括新的算法，允许生成的配置空间映射，需要的数量级比现有的表示少的空间。 预期的结果还包括算法的运动规划，利用这些地图，并正式保证质量的运动计划和计算成本的生成地图和计划。这些结果有望推进运动规划的基本理论特征的理解。 这些结果还将对自动化制造和自动驾驶汽车等应用领域产生直接的实际影响，因为它们允许利用更大的计算能力来生成可以有效存储并在网络上快速传输的地图。研究结果将在专门用于该项目的新的运动规划网页、国际机器人杂志和国际机器人会议上发布。预计这项工作将产生更广泛的影响，包括在本科和研究生两级培训下一代科学家和工程师。

Motion planning is fundamental problem that need to be solved for a robot to move from one location to another. This problem arises in many domains such as self-driving cars and automated assembly. Motion planning algorithms typically sample configurations of the robot to build a map of the space of robot configurations. As more computational power becomes available, samples can be placed more quickly, building a better map, but at tremendous cost in memory. This project explores the problem of finding low-memory approximate maps that allow rapid and accurate motion planning. Methods include mathematical analysis of algorithms, and experiments applying algorithms in simulation. Expected results include new algorithms that allow generation of configuration space maps that require orders of magnitude less space than existing representations. Expected results also include algorithms for motion planning that make use of these maps, and formal guarantees about quality of motion plans and computational costs of generating maps and plans. These results are expected to advance the understanding of fundamental theoretical characteristics of motion planning. These results will also have direct practical impact in application areas, including automated manufacturing and self-driving vehicles, by allowing vastly greater computational power to be leveraged to generate maps that can be stored efficiently and transmitted quickly across a network. Results will be disseminated on new motion planning web pages devoted to the project, in international robotics journals, and at international robotics conferences. Anticipated broader impacts of the work include training of the next generation of scientists and engineers at both the undergraduate and graduate level.