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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/IROS.2014.6942585 | Intelligent Robots and Systems |
Keywords | Field | DocType |
graph theory,mobile robots,multi-robot systems,optimal control,path planning,security,surveillance,travelling salesman problems,NP-hard,TSP,coordination,cyclic traveling salesman problem,cyclic-based strategies,generic graphs,graph partitioning,graph topology,multirobot patrolling,optimal routes,optimal task assignment,overall team travel cost,partitioning strategies,patrol strategy,robots spacing,security,surveillance,team size | Infrastructure security,Computer science,Patrolling,Operations research,Network topology,Artificial intelligence,Intelligent transportation system,Robot,Topological graph theory,Mobile robot,Robotics | Conference |
ISSN | Citations | PageRank |
2153-0858 | 3 | 0.40 |
References | Authors | |
9 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
David Portugal | 1 | 175 | 18.74 |
Charles Pippin | 2 | 10 | 2.00 |
Rui P. Rocha | 3 | 407 | 35.91 |
Henrik I. Christensen | 4 | 2848 | 235.82 |