Multimodal Planning under Uncertainty: Task-Motion Planning and Collision Avoidance

In this thesis we investigate the problem of motion planning under environment uncertainty. Specifically, we focus on Task-Motion Planning (TMP) and probabilistic collision avoidance which are presented as two parts in this thesis. Though the two parts are largely self-contained, collision avoidance is an integral part of TMP or any robot motion planning problem in general. The problem of TMP which is the subject of Part I is by itself challenging and hence in Part I, collision computation is not the main focus and is addressed with a deterministic approach. Moreover, motion planning is performed offline since we assume static obstacles in the environment. Online TMP, incorporating dynamic obstacles or other environment changes is rather difficult due to the computational challenges associated with updating the changing task domain. As such, we devote Part II entirely to the field of online probabilistic collision avoidance motion planning. Of late, TMP for manipulation has attracted significant interest resulting in a proliferation of different approaches. In contrast, TMP for navigation has received considerably less attention. Autonomous robots operating in real-world complex scenarios require planning in the discrete (task) space and the continuous (motion) space. In knowledge-intensive domains, on the one hand, a robot has to reason at the highest-level, for example, the objects to procure, the regions to navigate to in order to acquire them; on the other hand, the feasibility of the respective navigation tasks have to be checked at the execution level. This presents a need for motion-planning-aware task planners. In Part I of this thesis, we discuss a probabilistically complete approach that leverages this task-motion interaction for navigating in large knowledge-intensive domains, returning a plan that is optimal at the task-level. The framework is intended for motion planning under motion and sensing uncertainty, which is formally known as Belief Space Planning (BSP). The underlying methodology is validated in simulation, in an office environment and its scalability is tested in the larger Willow Garage world. A reasonable comparison with a work that is closest to our approach is also provided. We also demonstrate the adaptability of our method by considering a building floor navigation domain. Finally, we also discuss the limitations of our approach and put forward suggestions for improvements and future work. In Part II of this thesis, we present a BSP framework that accounts for the landmark uncertainties during robot localization. We further extend the state-of-the-art by computing an exact expression for the collision probability under Gaussian motion and perception uncertainties. Existing BSP approaches assume that the landmark locations are well known or are known with little uncertainty. However, this might not be true in practice. Noisy sensors and imperfect motions compound to the errors originating from the estimate of environment features. Moreover, possible occlusions and dynamic objects in the environment render imperfect landmark estimation. Consequently, not considering this uncertainty can result in wrongly localizing the robot, leading to inefficient plans. Our approach incorporates the landmark uncertainty within the Bayes filter framework. We also analyze the effect of considering this uncertainty and delineate the conditions under which it can be ignored. Furthermore, we also investigate the problem of safe motion planning under Gaussian motion and sensing uncertainties. Existing approaches approximate the collision probability using upper-bounds that can lead to overly conservative estimate and thereby suboptimal plans. We formulate the collision probability process as a quadratic form in random variables. Under Gaussian distribution assumptions, an exact expression for collision probability is thus obtained which is computable in real-time. Further, we compute a tight upper bound for fast online computation of collision probability and also derive a collision avoidance constraint to be used in an optimization setting. We demonstrate and evaluate our approach using a theoretical example and simulations in single and multi-robot settings using mobile and aerial robots. A comparison of our approach to different state-of-the-art methods are also provided.