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.