EAGER: Provably Efficient Motion Planning After Finite Computation Time

Motion planning is a fundamental capability needed for robots to operate autonomously. This project advances the understanding of state-of-the-art methods for robot motion planning and uses results from analysis to develop increasingly more capable and practical solutions, which are relevant to important applications such as driverless cars and automated manufacturing.

Modern sampling-based algorithms for robot motion planning asymptotically converge to optimal trajectories. In practice, however, their execution is stopped after a finite amount of computation. This project reasons about the properties of these popular methods after finite computation time instead of an asymptotic analysis. Based on this progress, methods are developed with improved practical computational efficiency and formal probabilistic near-optimality guarantees. These techniques address a wide set of planning challenges, including problems that involve significant dynamics. This is an especially important direction, for which it is harder to apply existing solutions with near-optimality guarantees. If successful, this work will result in a paradigm shift in algorithmic motion planning and its application domains, since it provides more efficient methods with stronger formal guarantees. This project includes outreach and educational activities to disseminate research results and integrate them into curriculum.