EAGER: Compact Roadmaps for Planning Under Uncertainty

几乎所有的机器人应用中都存在某种形式的不确定性。例如，控制机器人或其环境的动力学不能被完美地建模，或者机器人上的传感器提供噪声测量。因此，在许多现实的情况下，规划算法面临着很大的不确定性。不幸的是，规划下的不确定性问题是众所周知的计算上的挑战。该项目旨在利用紧凑路线图的新算法方法解决不确定性问题下的规划问题，该方法旨在在计算工作量和性能目标之间取得最佳平衡。该方法是基于新的技术和进步，在高维空间中的概率措施的理解。 预期成果包括：（i）在不确定性问题下规划的背景下对紧凑数据结构进行彻底的理论分析，这可能导致计算工作量和性能的严格限制;（ii）开发具有可证明的性能保证和理想的计算特性的算法。这些结果将促进我们的理解规划问题中的不确定性的计算影响。此外，它们将导致实用的算法，有可能对机器人技术及其他领域产生直接影响。实验评估包括对自动驾驶汽车的演示。研究结果将通过国际机器人技术期刊和国际机器人技术会议的出版物传播。更广泛的影响还包括研究生和本科生参与研究活动及其培训。

Some form of uncertainty is embedded in almost all robotics applications. For example, the dynamics governing the robot or its environment cannot be modeled perfectly, or the sensors on board the robot provide noisy measurements. Hence, in many realistic scenarios, planning algorithms are faced with substantial uncertainty. Unfortunately, planning under uncertainty problems are known to be computationally challenging. This project aims to solve planning under uncertainty problems with a new algorithmic approach utilizing compact roadmaps, which aim to strike the best balance between computational effort and performance objectives. The approach is based on new techniques and advances in understanding probability measures in high-dimensional spaces. Expected results include: (i) a thorough theoretical analysis of compact data structures in the context of planning under uncertainty problems, which may lead to tight bounds on computational effort and performance; (ii) the development of algorithms with provable performance guarantees, and desirable computational properties. These results will advance our understanding of the computational impact of uncertainty in planning problems. Furthermore, they will lead to practical algorithms with potential for immediate impact in robotics and beyond. The experimental evaluation includes demonstration on self-driving cars. The results will be disseminated through publications in archival international robotics journals and international robotics conferences. The broader impacts also include the involvement of graduate- and undergraduate-level students in research activities and their training.