An Efficient Algorithm for Environmental Coverage with Multiple Robots

Ling Xu and Anthony (Tony) Stentz
International Conference on Robotics and Automation, May, 2011.


Download
  • Adobe portable document format (pdf) (691KB)
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 searching the space for an object. In many cases, the use of multiple robots can greatly improve the performance of these tasks. We assume a prior map is available, but it may be inaccurate due to factors such as occlusion, age, dynamic objects, and resolution limitations. In this work, we address the NP-hard problem of environmental coverage with incomplete prior map information using k robots. To utilize related algorithms in graph theory, we represent the environment as a graph and model the coverage problem as a k-Rural Postman Problem. Using this representation, we present a graph coverage approach for plan generation that can handle graph changes online. Our approach proposes two improvements to an existing heuristic algorithm for the coverage problem. Our improvements seek to equalize the length of the k paths by minimizing the length of the maximum tour. We evaluate our approach on a set of comparison tests in simulation.

Notes
Number of pages: 6

Text Reference
Ling Xu and Anthony (Tony) Stentz, "An Efficient Algorithm for Environmental Coverage with Multiple Robots," International Conference on Robotics and Automation, May, 2011.

BibTeX Reference
@inproceedings{Xu_2011_6897,
   author = "Ling Xu and Anthony (Tony) Stentz",
   title = "An Efficient Algorithm for Environmental Coverage with Multiple Robots",
   booktitle = "International Conference on Robotics and Automation",
   month = "May",
   year = "2011",
}