Carnegie Mellon Robotics Institute
doctoral dissertation, tech. report CMU-RI-TR-11-24, Robotics Institute, Carnegie Mellon University, August, 2011
|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 searching the space for objects. When these tasks are performed autonomously by robots, the constraints of the environment 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, changing environments.
This thesis addresses the problem of eﬀective graph coverage with environmental constraints and incomplete prior map information. Prior information about the environment is assumed to be given in the form of a graph. We seek a solution that eﬀectively covers the graph while accounting for space restrictions and online changes. For real-time applications, we seek a complete but eﬃcient solution that has fast replanning capabilities.
For this work, we model the set of coverage problems as arc routing problems. Although these routing problems are generally NP-hard, our approach aims for optimal solutions through the use of low-complexity algorithms in a branch-and-bound framework when time permits and approximations when time restrictions apply. Additionally, we account for environmental constraints by embedding those constraints into the graph. In this thesis, we present algorithms that address the multi-dimensional routing problem and its subproblems and evaluate them on both computer-generated and physical road network data.
Number of pages: 134
|Ling Xu, "Graph Planning for Environmental Coverage," doctoral dissertation, tech. report CMU-RI-TR-11-24, Robotics Institute, Carnegie Mellon University, August, 2011|
author = "Ling Xu",
title = "Graph Planning for Environmental Coverage",
booktitle = "",
school = "Robotics Institute, Carnegie Mellon University",
month = "August",
year = "2011",
address= "Pittsburgh, PA",
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions