Finding Optimal Routes for Multi-Robot Patrolling in Generic Graphs
In Proc. of 2014 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS 2014), Chicago, Illinois, USA, pp. 363-369, Sep. 14-18, 2014. DOI: 10.1109/IROS.2014.6942585
Abstract
Multi-robot patrolling is a problem that has important applications in security and surveillance. However, the optimal task assignment is known to be NP-hard. We consider evenly spacing the robots in a cyclic Traveling Salesman Problem (TSP) tour or partitioning the graph of the environment. The trade-off in performance, overall team travel cost and coordination is analyzed in this paper. We provide both a theoretical analysis and simulation results across multiple environments. The results demonstrate that generally cyclic-based strategies are superior, especially when small teams are used but at the expense of greater team cost, whereas partitioning strategies are especially suitable for larger teams and unbalanced graph topologies. The reported results show that graph topology and team size are fundamental to determine the best choice for a patrol strategy.
Index Terms — Multi-robot patrolling; cyclic strategies; partitioning strategies; theoretical analysis.
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_et_al_14,
AUTHOR = "Portugal, D. and
Pippin, C. and Rocha, R. P. and Christensen, H. I.",
TITLE = "Finding Optimal Routes for Multi-Robot Patrolling in Generic Graphs",
BOOKTITLE = "Proc. of 2014 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS 2014)",
ADDRESS = "Chicago, Illinois, USA",
YEAR = "2014",
MONTH = "Sep.",
PAGES = "363-369"
)
Last
update: 17/09/2014
Copyright ©
2014 Rui Rocha, Dep. of Electrical and Computer Engineering,