EAGER: Computing Compact Roadmaps for Motion Planning

Dartmouth College, Hanover NH

Investigators

Abstract

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.