Carnegie Mellon University
Graph Planning for Environmental Coverage

Ling Xu
doctoral dissertation, tech. report CMU-RI-TR-11-24, Robotics Institute, Carnegie Mellon University, August, 2011

  • Adobe portable document format (pdf) (3MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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 effective 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 effectively covers the graph while accounting for space restrictions and online changes. For real-time applications, we seek a complete but efficient 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

Text Reference
Ling Xu, "Graph Planning for Environmental Coverage," doctoral dissertation, tech. report CMU-RI-TR-11-24, Robotics Institute, Carnegie Mellon University, August, 2011

BibTeX Reference
   author = "Ling Xu",
   title = "Graph Planning for Environmental Coverage",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "August",
   year = "2011",
   number= "CMU-RI-TR-11-24",
   address= "Pittsburgh, PA",