Motion Planning with Uncertain Information in Robotic Tasks

In the real world, robots operate with imperfect sensors providing uncertain and incomplete information. We develop techniques to solve motion planning problems with imperfect information in order to accomplish a variety of robotic tasks including navigation, search-and-rescue, and exposure minimization. This thesis focuses on the challenge of creating robust policies for robots with imperfect actions and sensing. These policies map input observations to output actions. The tools that exist to solve these problems are typically Partially-Observable Markov Decision Processes (POMDPs), and can only handle small problem instances. This thesis proposes several techniques to expand the size of the problem instance that can be considered. Because executing a policy is simple once the offline computation is done, even inexpensive, computationally constrained robots can use these policies and solve the tasks mentioned. First we show that the solution of an abstracted action space can be used to bootstrap a complete solution for navigation. Generalizing this action space abstraction to both action and state spaces expands the set of problems that can be solved. Additionally, the concept of abstraction is applied to the workspace -- we develop a method to compute local solutions to a noisy navigation problem, then stitch them together into a global solution. Our proposed methods are run on large problem instances, and the output policies are compared against policies generated with existing techniques. Though these large tasks are often unsolvable with previous methods, abstraction allows us to find high quality policies. Our findings show that these techniques significantly increase the size of tasks involving planning with uncertain information for which solutions can be found. The techniques presented generally offer significant speed increases and often solution quality improvements as well. Additionally, this thesis includes work on two separate problems. First, we solve a task where several robots cooperate to quickly classify an observed object as one of several possible types using a camera. Then, we proceed to solve a task where a single robot navigates to a destination quickly, but the robot may need to allocate time towards obtaining information about a new object discovered along the way