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.
