Candidate
Ryan MacDonald
Title
Robotic Motion Planning in Uncertain Environments via Active Sensing
Supervisor
Stephen L. Smith
Abstract
Perception and control are at the foundation of automation, and in recent years, we have seen growth in feasible applications including self-driving cars and smart homes. As automation moves from regulated, well-monitored locations (e.g., factories) into society, uncertainty in hardware and the environment poses a safety concern. Within this thesis, we focus primarily on uncertainty in the environment and discuss models of the environment known a priori and learned as the robot functions. The robot is tasked with moving from one location or configuration to another while minimizing the expected cost of observation and motion actions. We focus on control that guides the robot to a position/configuration or identifies that it is impossible to reach the position/configuration.
The first focus on a robot creating a plan, prior to deployment, based on a known environment model. This model encodes obstacle configurations into different environmental realizations along with a probably this realization will be encountered. The robot is also provided an observation model it may use to sense the environment during the task. We show that minimizing the expected cost from start to goal within these models is NP-Hard. Therefore, we present an efficient algorithm to create a policy which can react to obstacles in real-time while maintaining safety constraints on motion. A by-product of this algorithm is a lower bound on the expected cost of an optimal policy. We compare the policy and lower bound, generated by our algorithm, against that of an optimal policy and existing research.
Our focus then shifts to remove prior information about environmental obstacles. We ask the robot to complete a finite number of start to goal tasks and show the general version of this problem is PSPACE-Hard. To reduce the complexity, we develop a method that uses an arbitrary reactionary algorithm from prior work to handle unexpected obstacles. For each new environment experienced, we incrementally update the robot's policy and show that the dependence on the reactionary algorithm is not increasing. Tests are performed on a flexible factory to demonstrate the scalability of this method.