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.