MSP Algorithm: Multi-Robot Patrolling based on Territory Allocation using Balanced Graph Partitioning

D. Portugal and R. Rocha

In Proc. of 25th ACM Symposium on Applied Computing (SAC’2010), Special Track on Intelligent Robotic Systems (ROBOT), Sierre, Switzerland, pages 1270-1275, Mar. 22-26, 2010

Abstract

This article addresses the problem of efficient multi-robot patrolling in a known environment. The proposed approach assigns regions to each mobile agent. Every region is represented by a subgraph extracted from the topological representation of the global environment. A new algorithm is proposed in order to deal with the local patrolling task assigned for each robot, named Multilevel Subgraph Patrolling (MSP) Algorithm. It handles some major graph theory classic problems like graph partitioning, Hamilton cycles, non-Hamilton cycles and longest path searches. The flexible, scalable, robust and high performance nature of this approach is testified by simulation results.

Index Terms — Multi-robot patrolling, multi-robot systems, graph partitioning, graph theory.

Full text

You may ask Rui Rocha for an electronic copy of this publication’s full text by e-mail:
.

Please select for your message’s subject ‘Requesting Rui Rocha’s electronic copy’ and include on the message’s body your full name, title and affiliation, why do you need to access the publication and the BibTeX information below.

BibTeX

@INPROCEEDINGS(Portugal_Rocha_2010,

AUTHOR = "D. Portugal and R. Rocha",

TITLE = "\textsc{MSP} Algorithm: Multi-Robot Patrolling based on Territory Allocation using Balanced Graph Partitioning",

BOOKTITLE = "roc. of 25th ACM Symposium on Applied Computing (SAC'2010), Special Track on Intelligent Robotic Systems (ROBOT)",

ADDRESS = "Sierre, Switzerland",

YEAR = "2010",

MONTH = "Mar.",

PAGES = "1270-1275"

)

(top of the page)

Last update: 17/12/2009