Event Location: Newell Simon Hall 1305

Abstract: Tasks such as street mapping and security surveillance seek a route that traverses a given space to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or processing the space for object detection. When these tasks are performed autonomously by robots, the constraints of the robot must be considered in order to generate more feasible paths. Additionally, performing these tasks in the real world presents the challenge of operating in dynamic environments.

This thesis addresses the problem of effective graph coverage with vehicle constraints and incomplete prior map information. Prior information of the environment is assumed to be given in the form of a graph. We seek a solution that effectively covers the graph while accounting for vehicle restrictions and online changes. For real-time applications, we seek an optimal but efficient solution that has fast replanning capabilities.

For this work, we use two types of routing problems: the arc and vertex routing problems. Although these routing problems are generally NP-hard, our approach aims for an anytime solution through the use of low complexity algorithms in a branch-and-bound framework. This approach allows feasible solutions to be computed quickly and incrementally improved if more time is available. Additionally, we account for vehicle constraints by embedding those restrictions into the graph. Finally, our technique addresses interrelated routing problems through an integrated approach.

Committee:Thesis Committee Members:

Anthony (Tony) Stentz, Co-chair

Omead Amidi, Co-chair

Howie Choset

John Krumm, Microsoft Research