research-article

Multi-robot area coverage with limited visibility

Authors:

Pooyan Fazli,

Alireza Davoodi,

Philippe Pasquier,

Alan K. MackworthAuthors Info & Claims

AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1

Pages 1501 - 1502

Published: 10 May 2010 Publication History

Get Access

Abstract

We address the problem of multi-robot area coverage and present a new approach in the case where the map of the area and its static obstacles are known and the robots have a limited visibility range. The proposed method starts by locating a set of static guards on the map of the target area and then builds a graph called Reduced-CDT, a new environment representation method based on the Constrained Delaunay Triangulation (CDT). Multi-Prim's is used to decompose the resultant graph into a forest of partial spanning trees (PSTs). Each PST is modified through a mechanism called Constrained Spanning Tour (CST) to build a cycle which is then assigned to a covering robot. Subsequently, robots start navigating the cycles and consequently cover the whole area. The proposed approach is complete provided that at least one of the robots operates correctly.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, February 1993.

Digital Library

Google Scholar

[2]

W. Burgard, M. Moors, D. Fox, R. Simmons, and S. Thrun. Collaborative multi-robot exploration. In Proceedings of the IEEE International Conference on Robotics and Automation, ICRA '00., volume 1, pages 476--481, 2000.

Crossref

Google Scholar

[3]

L. P. Chew. Constrained delaunay triangulations. In Proceedings of the Symposium on Computational Geometry, pages 215--222, 1987.

Digital Library

Google Scholar

[4]

H. Choset. Coverage for robotics - a survey of recent results. In Annals of Mathematics and Artificial Intelligence, volume 31, pages 113--126, 2001.

Digital Library

Google Scholar

[5]

A. Davoodi, P. Fazli, P. Pasquier, and A. K. Mackworth. On multi-robot area coverage. In Proceedings of the 7th Japan Conference on Computational Geometry and Graphs, JCCGG09, pages 75--76, November 2009.

Google Scholar

[6]

G. D. Kazazakis and A. A. Argyros. Fast positioning of limited visibility guards for inspection of 2D workspaces. In Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2843--2848, October 2002.

Crossref

Google Scholar

[7]

R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Computational Geometry: Theory and Applications, 1(1):51--64, 1991.

Digital Library

Google Scholar

Cited By

View all

Fazli PLuck MSen S(2010)On multi-robot area coverageProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 110.5555/1838206.1838534(1669-1670)Online publication date: 10-May-2010
https://dl.acm.org/doi/10.5555/1838206.1838534
Fazli P(2010)On multi-robot area coverageProceedings of the 23rd Canadian conference on Advances in Artificial Intelligence10.1007/978-3-642-13059-5_52(384-387)Online publication date: 31-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13059-5_52

Index Terms

Multi-robot area coverage with limited visibility
1. Applied computing
  1. Operations research
    1. Industry and manufacturing
      1. Command and control
2. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

On multi-robot area coverage
AI'10: Proceedings of the 23rd Canadian conference on Advances in Artificial Intelligence

Area coverage is one of the emerging problems in multi-robot coordination In this task a team of robots is cooperatively trying to observe or sweep an entire area, possibly containing obstacles, with their sensors or actuators The goal is to build an ...
On multi-robot area coverage
AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1

Area coverage is one of the emerging problems in multi-robot coordination. In this task a team of robots is cooperatively trying to observe or sweep an entire area, possibly containing obstacles, with their sensors or actuators. The goal is to build an ...
Multi-robot repeated area coverage

We address the problem of repeated coverage of a target area, of any polygonal shape, by a team of robots having a limited visual range. Three distributed Cluster-based algorithms, and a method called Cyclic Coverage are introduced for the problem. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1

May 2010

1578 pages

ISBN:9780982657119

General Chairs:
Michael Luck
King's College London, UK
,
Sandip Sen
University of Tulsa

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 10 May 2010

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS '10

Sponsor:

AAMAS '10: The Ninth International Conference on Autonomous Agents and Multiagent Systems

May 10 - 14, 2010

Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
155
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fazli PLuck MSen S(2010)On multi-robot area coverageProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 110.5555/1838206.1838534(1669-1670)Online publication date: 10-May-2010
https://dl.acm.org/doi/10.5555/1838206.1838534
Fazli P(2010)On multi-robot area coverageProceedings of the 23rd Canadian conference on Advances in Artificial Intelligence10.1007/978-3-642-13059-5_52(384-387)Online publication date: 31-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13059-5_52

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On multi-robot area coverage

On multi-robot area coverage

Multi-robot repeated area coverage