The Robotics Institute

Carnegie Mellon Robotics Institute

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.

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. With a prior map, an optimal path can be computed using a graph to represent the environment and generating the solution using known graph algorithms. However, the prior map may be inaccurate due to factors such as occlusion, outdatedness, dynamic objects, and resolution limitations. In this work, we address the NP-hard problem of optimal environmental coverage with incomplete prior map information.

To utilize related algorithms in graph theory, we represent the environment as a graph. Using this representation, we present a graph coverage approach for optimal plan generation based on the Undirected Chinese Postman and Rural Postman problems. This approach produces a tractable solution through the use of low complexity algorithms in a branch-and-bound framework. Additionally, as the robot receives sensor updates during traversal of the environment, we update the graph to reflect those changes. The updated graph can be highly disconnected so computing an optimal solution can be NP-hard. To combat this, we introduce a heuristic for coverage path generation that helps maximize the connectivity of the updated graph. We evaluate our approach on a set of comparison tests in simulation.

Notes

Text Reference

Ling Xu and Anthony (Tony) Stentz, "A Fast Traversal Heuristic and Optimal Algorithm for Effective Environmental Coverage," Robotics: Science and Systems (RSS), June, 2010.

BibTeX Reference

@inproceedings{Xu_2010_6690,
   author = "Ling Xu and Anthony (Tony) Stentz",
   title = "A Fast Traversal Heuristic and Optimal Algorithm for Effective Environmental Coverage",
   booktitle = "Robotics: Science and Systems (RSS)",
   month = "June",
   year = "2010",
}

The Robotics Institute

Menu