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.