# A Survey on Multi-robot Patrolling Algorithms

David Portugal, Rui Rocha

► To cite this version:

David Portugal, Rui Rocha. A Survey on Multi-robot Patrolling Algorithms. 2nd Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Feb 2011, Costa de Caparica, Portugal. pp.139-146, 10.1007/978-3-642-19170-1_15. hal-01566556

HAL Id: hal-01566556

https://inria.hal.science/hal-01566556

Submitted on 21 Jul 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Survey on Multi-Robot Patrolling Algorithms

David Portugal and Rui Rocha,

Instituto de Sistemas e Robótica, Department of Electrical and Computer
Engineering, University of Coimbra, 3030-290 Coimbra, Portugal
[davidbsp, rprocha]@isr.uc.pt

**Abstract.** This article presents a survey on cooperative multi-robot patrolling algorithms, which is a recent field of research. Every strategy proposed in the last decade is distinct and is normally based on operational research methods, simple and classic techniques for agent's coordination or alternative, and usually more complex, coordination mechanisms like market-based approaches or reinforcement-learning. The variety of approaches differs in various aspects such as agent type and their decision-making or the coordination and communication mechanisms. Considering the current work concerning the patrolling problem with teams of robots, it is felt that there is still a great potential to take a step forward in the knowledge of this field, approaching well-known limitations in previous works that should be overcome.

**Keywords:** Multi-Robot Systems; Patrol; Topological Maps and Graph Theory.

## 1 Introduction

To patrol is “the activity of going around or through an area at regular intervals for security purposes” [1]. In this context, the patrolling task should be performed by multiple mobile robots, which is considered a contemporary area with relevant work presented in the last decade, especially in terms of strategies for coordinating teams of mobile robots. We focus on area patrol, i.e., the activity of going through an area, as opposed to going around an area (perimeter patrol).

Patrolling is a somehow complex multi-robot mission, requiring agents to coordinate their decision-making with the ultimate goal of achieving optimal group performance. It also aims at monitoring and supervising environments, obtaining information, searching for objects and detecting anomalies in order to guard the grounds from intrusion, which involves frequent visits to every point of the infrastructure.

Robotic agents are normally endowed with a metric representation of the environment, which is typically an occupancy grid model, which in turn, is usually abstracted by a simpler, yet precise representation: a topological map (i.e., a graph). Having a graph representation, one can use vertices to represent specific locations and edges to represent the connectivity between those locations. The multi-robot patrolling problem can, thus, be reduced to coordinate robots in order to visit all vertices of the graph ensuring the absence of intruders or other abnormal situations,
with respect to a predefined optimization criterion, e.g. the average idleness of the vertices of the graph. It is consensual that a good strategy should minimize the time lag between visits in strategic places of the environment.

## 2 Contribution to Sustainability

The major motivation for studying this issue relates to its wide spectrum of applicability and the potential to replace or assist human operators in tedious or dangerous real-life scenarios, such as mine clearing or rescue operations in catastrophic scenarios, easing arduous, tiring and time-consuming tasks and offering the possibility to relieve human beings, enabling them to be occupied in nobler tasks like, for example, monitoring the system from a safe location.

Also, the patrolling problem is very challenging in the context of multi-robot systems, because agents must navigate autonomously, coordinate their actions, be distributed in space, may have communication constraints and must be independent of the number of robots and the environment's dimension. All of these characteristics result in an excellent case study in mobile robotics and conclusions drawn in this field of research may support the development of future approaches not only in the patrolling domain but also in multi-robot systems in general.

## 3 Pioneer Methods

One of the first works in this field is described in [2] and in more detail in [3], where several architectures of multi-agent patrolling and various evaluation criteria were presented.

Different agent behaviors are employed in the approaches described therein, namely in the agent's perception, which can be reactive (with local information) or cognitive (with access to global information). Also, these architectures differ in the communication mechanism and in the decision of the next vertex to be visited in the topological map.

To analyze the performance of each technique, criteria based on the average and maximum idleness of the vertices were proposed. Random decision algorithms scored the worst results and simple techniques conducted by the vertices' idleness scored close results to the same technique using a centralized coordinator. In general, the best strategy was a local strategy with no communication, based on individual idleness and without a centralized coordinator, called "Conscientious Reactive". Other good results were obtained by "Conscientious Cognitive", which is a similar method; however, agents are no longer reactive, choosing the next vertex to visit on the global graph (instead of their neighborhood).

There are a few weaknesses in this work. Conclusions were drawn based on only two particular environments. Also, unweighted edges were used, meaning that agents travel from one vertex to another in every iteration, independently of the distance between them, which is a rather imprecise simplification. Moreover, the solutions presented are directed to virtual agents in simulation environments, since no real robots were used during experiments.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** On the left, an example of a cyclic strategy. On the right, an example of a partition based strategy.</figcaption></figure>

Following the pioneer work of Machado et al., a more complete study was conducted in [4], enriching the representation with weighted graphs, using more and distinct environments, and proposing advanced versions of Machado’s architectures to solve the same problem. Essentially, a new path-finding technique was implemented for cognitive agents, based not only in the shortest path between the source and destination vertex but also in the instantaneous idleness of the vertices along the current and goal position. In addition, a decision-making heuristic that considers the idleness of a candidate vertex, as well as the distance to that same vertex, was developed.

The main results show that cognitive architectures have a significant gain when using the new heuristic, if compared to the same technique with the original decision-making process. On the other hand, there was no great benefit for reactive architectures, only in cases when there is high connectivity (several choices of paths between two vertices in the graph) and great variance in the edges' weight. As for pathfinder agents, the performance is always better, especially for graphs with high connectivity. Combining the heuristic decision-making with pathfinder agents and using communication via a central coordinator, one gets the best performing approach in all criteria: Heuristic Pathfinder Cognitive Coordinator.

In [5] the area patrol algorithm developed guarantees that each point in the target area is covered at the same optimal frequency. This is done by computing minimal-costs cyclic patrol paths that visit all points in the target area, i.e. Hamilton cycles. Agents are uniformly distributed along this path and they follow the same patrol route over and over again. One of the key aspects of this strategy is the fact that it is robust, being independent of the number of robots. Uniform frequency of the patrolling task is achieved as long as there is, at least, one robot working properly. A possible disadvantage of this approach is its deterministic nature. An intelligent intruder that apprehends the patrolling scheme may take advantage of the idle time between passages of robots in some points of the area.

Similarly, [6] focuses on two graph-theory centralized planning strategies: cyclic strategies, which are similar to the previously described technique, however it uses a heuristic to compute a TSP<fnref n="1" /> cycle; and partitioning strategies, which are approaches that use segmentation of the environment and assign different patrolling regions to each agent. Examples of such strategies are presented in Figure 1.

Both strategies have generally good performance. The first one is better suited for graphs that are highly connected or have large closed paths. The second one is better when graphs have long corridors separating regions. Also, the author explains

<footnote n="1">¹ TSP stands for the well-known Travelling Salesman Problem (a NP-hard problem).</footnote>
that very simple strategies, with nearly no communication ability, can achieve impressive results.

# 4 Alternative Methods

In [7], the patrolling task is modeled as a reinforcement learning problem in an attempt to allow automatic adaptation of the agents' strategies to the environment. In summary, agents have a probability of choosing an action from a finite set of actions, having the goal of maximizing a long-term performance criterion, in this case node idleness. Two Reinforcement Learning Techniques, using different communication schemes were implemented and compared to non-adaptive architectures. Although not always scoring the best results, the adaptive solutions are superior to other solutions compared in most of the experiments. The main attractive characteristics in this work is distribution (no centralized communication is assumed) and the adaptive behavior of agents, which can be desirable in this domain.

In [8], a negotiation mechanism is proposed. Agents reveal a scalable and reactive behavior, being able to patrol infrastructures of all sizes and topologies. Also, they need no learning time or path pre-computation.

Each agent acts as a negotiator and receives a set of random graph vertices to patrol. Agents negotiate those vertices using auctions to exchange them with other agents. Aiming to minimize visits to the same node, these agents will try to get a set of nodes in the same region of the graph. Results show that the proposed strategy outperforms most of previously described architectures.

Likewise, [9] also studied cooperative auction systems to solve the patrolling problem. They consider robot's energetic issues and the length of the patrolling routes as performance criteria. However they only experiment in an open space scenario with no obstacles. Nevertheless, despite its weaknesses, the cooperation method among robots has the potential to be used in future works.

A comparative study up to 2004 was presented in [10], which analyzed many different approaches. They observed that the best strategy depends on the topology of the environment and the agents' population size.

Generally, it was concluded that the TSP cyclic approach has the best performance for most cases. However, this architecture will have problems in dynamic environments, large graphs (because of the complexity of a TSP cycle computation in these cases) and graphs containing long edges, due to its predefined nature. Secondly, agents with no communication ability, whose strategies consisted of moving towards the vertex with the highest idleness, performed nearly as well as the most complex algorithm implemented. In general, heuristic-decision agents and reinforcement learning techniques considered have the second best performance, followed by the Negotiation Mechanisms techniques.

The first known patrolling approach, which was focused and implemented on robotic agents, was presented in [11]. Patrolling is seen in a task allocation perspective, where each robot is assigned a different region to visit. Both a reactive and an adaptive approach are described to solve the area patrolling problem, through task data propagation.

Robots send their current state to a centralized system running on a remote computer, through a wireless communication network, to compute the task strength
and drive the robot through propagated data. In the experimental setup, robots can estimate their remaining autonomy, thus battery recharges are taken into account and physical interference can occur. The authors claim that efficient patrol is achieved and present interesting properties of adaptability concerning group size and the environment.

In a work with wider scope, [12] presents a motion planning algorithm, which selects effective patrol patterns based on a neural network coverage approach where each robot becomes responsible for a patrol region of the environment. When they operate in patrol mode, robots may update their 3D maps to incorporate possible changes in the environment. If an intruder is detected, some robots will switch their operation mode to threat response scenario and the algorithm is run to successfully respond to the threat, guaranteeing that robots reach the evader in the quickest possible way. The others robots will carry on with the patrol task and replan their trajectories to compensate for those that switched their operation mode.

Recently, swarm intelligence has also been used to tackle the multi-robot patrolling problem as in [13], where a grid-based algorithm is proposed. It relies on the evaporation process of pheromones dropped by agents (an indicator of time passed since the last visit). The agents' behavior is naturally defined by moving towards cells containing less pheromone quantity. Agents only have local perception, and follow paths according to the pheromone quantity in their neighboring cells.

Results show that an approach with global perception is more effective in more complex infrastructures, in terms of idleness. However, it proves to be twice as costly, in terms of computational complexity. Due to the marking of the environment, the system self-organizes and an effective patrolling behavior emerges.

# 5 Recent Studies

In a very thorough study, [14] explores the concept of unpredictability in the multi-agent area patrol task. In this context, intruders will not have access to patrolling trajectory information. Metrics are presented in terms of probability of catching intruders with different intelligence. The authors evaluate six different algorithms. Two are purely random (one locally and one globally), one is a deterministic TSP-based solution and three are based on the TSP solution together with local random nuances to create unpredictability in the trajectories.

Intensive simulation results, using a large set of graphs, made evident some distinct facts. Partitioning schemes are more effective against random attackers; however, non-partitioning schemes perform better when the attacker has some level of intelligence. With random attackers or attackers with limited information, the deterministic TSP algorithm was the best solution found, because it covers all the nodes with the minimal time needed. The algorithm that performed better against statistical intruders was an unpredictable variant of the TSP cycle, thus confirming the importance of unpredictability in the patrolling task. Random-based strategies although being very unpredictable, have very high worst idleness values, which makes them generally useless for the patrolling problem.
<figure><img src="image_3.png" /><figcaption>Fig. 2. MSP running on the patrolling simulator window [15].</figcaption></figure>

Patrolling related issues were also studied in [15] like map representation, graph extraction, surveillance, pursuit-evasion, coverage, navigation and exploration strategies. By analyzing approaches, not limited exclusively to patrolling works, an original, scalable, centralized and efficient algorithm was presented, called Multilevel Subgraph Patrolling (MSP) Algorithm, which is also described in [16]. The MSP algorithm is a multilevel partitioning algorithm that assigns different regions (subgraphs) to each mobile agent. The algorithm deals with effectively computing paths for every robot using a classical algorithm for Euler cycles and various heuristics for Hamiltonian cycles, non-Hamiltonian Cycles and Longest paths. The algorithm was compared to a cyclic algorithm, like the one presented in [5]. The MSP Algorithm scored slightly better results in half of the cases and obtained slightly worse results in the other half. Given that cyclic algorithms are well-known for their performance in terms of visiting frequency, these results are very optimistic and confirm the flexible, scalable and high performance nature of the approach, which also benefits from being non-redundant and does not need inter-agent communication. However, like the cyclic algorithm, MSP is deterministic. Nevertheless, it is much more difficult for an evader to attack in this case, because it would need to keep track of every single robot local patrolling path. Following this work, four different genetic algorithms for approximating the longest path in a graph were also presented in [17].

In the next page, Table 1 was built to summarize the main characteristics of the architectures described in the previous sections.

# 6 Existing Limitations and Future Work

The analysis made allows us to conclude that several drawbacks, common to most strategies, remain. Among others, future work will focus on overcoming weaknesses such as: the absence of studies on scalability, flexibility, resource utilization, interference, communication load or workload among robots when performing the patrolling task; the lack of experimental work using teams of robots in real
scenarios; simplifications and unfeasibility of simulation approaches towards real life experiments; lack of comparisons of the actual time spent between different strategies in their patrolling cycles; lack of diversity and classification of the environments tested and the deterministic nature of many centralized approaches. To materialize this, we intend to create a formal mathematical model for the multi-robot patrolling problem by analyzing and comparing the performance of different approaches, through realistic simulations, focusing especially on how these teams scale and extracting the important variables for this problem, so as to create an automatic estimation tool to dimension the team for a patrolling task. In addition, we intended to develop a new distributed, non-deterministic and cooperative strategy, which will be tested firstly by simulations in a wide variety of environments and secondly using a team of mobile robots in real-world scenarios.

<table><caption>**Table 1.** Summary of the main architectures analyzed.</caption><thead><tr><td>Proposed Strategy</td><td>Type/Perception</td><td>Communication</td><td>Coordination</td><td>Decision-Making</td></tr></thead><tbody><tr><td>Conscientious Reactive [3]</td><td>Reactive / Local</td><td>None</td><td>Emergent</td><td>Local Idleness-based</td></tr><tr><td>Conscientious Cognitive [3]</td><td>Cognitive / Global</td><td>None</td><td>Emergent</td><td>Global Idleness-based</td></tr><tr><td>Idleness Coordinator Monitored [3]</td><td>Cognitive / Global</td><td>Coordinator Messages</td><td>Centralized</td><td>Idleness-based with Monitoring</td></tr><tr><td>Heuristic Pathfinder Cognitive Coordinated [4]</td><td>Cognitive / Global</td><td>Coordinator Messages</td><td>Centralized</td><td>Heuristic (Idleness + Distance) with Path-finding technique</td></tr><tr><td>Untitled #1 [5]</td><td>Cognitive / Global</td><td>Coordinator Trajectory Cycle</td><td>Centralized</td><td>Hamilton Cycle Computation</td></tr><tr><td>Cyclic Approach [6]</td><td>Cognitive / Global</td><td>Coordinator Trajectory Cycle</td><td>Centralized</td><td>TSP Heuristic Calculation</td></tr><tr><td>Partitioning Approach [6]</td><td>Cognitive / Global</td><td>Coordinator Trajectory Cycle</td><td>Centralized</td><td>TSP Heuristic inside each region</td></tr><tr><td>Gray-Box Learner Agent [7]</td><td>Reactive / Local</td><td>Flags</td><td>Emergent + Adaptive</td><td>Idleness-based Reinforcement Learning with Monitoring</td></tr><tr><td>Bidder Agent [8]</td><td>Cognitive / Global</td><td>Bidding Messages</td><td>Auctions</td><td>Self-Interested Idleness-based</td></tr><tr><td>Sequential Single-Item Auctions [9]</td><td>Cognitive / Global</td><td>Bidding Messages</td><td>Auctions</td><td>Minimize the maximum patrol path</td></tr><tr><td>Heuristic Pathfinder Two-Shot Bidder [10]</td><td>Cognitive / Global</td><td>Bidding Messages</td><td>Two-Shot Auctions</td><td>Heuristic (Idleness + Distance) with Path-finding technique</td></tr><tr><td>Untitled #2 [11]</td><td>Reactive / Local</td><td>Task Propagation Messages</td><td>Centralized + Adaptive</td><td>Task strength Idleness-based measure</td></tr><tr><td>Untitled #3 [12]</td><td>Cognitive / Global</td><td>Coordinator Messages</td><td>Centralized</td><td>Neural network coverage approach inside each region</td></tr><tr><td>EVAP [13]</td><td>Reactive / Local</td><td>Flags</td><td>Emergent</td><td>Local Idleness-based</td></tr><tr><td>CLInG [13]</td><td>Reactive / Local</td><td>Flags</td><td>Emergent</td><td>Idleness-based with diffusion of information</td></tr><tr><td>TSP rank of solutions [14]</td><td>Cognitive / Global</td><td>Coordinator Messages</td><td>Centralized</td><td>Queue of TSP sub-optimal solutions (Unpredictable)</td></tr><tr><td>MSP [16]</td><td>Cognitive / Global</td><td>Coordinator Trajectory Cycle</td><td>Centralized</td><td>Operation research algorithms inside each region</td></tr></tbody></table>
Acknowledgments

This work was financially supported by a PhD grant (SFRH/BD/64426/2009) from the Portuguese Foundation for Science and Technology (FCT) and the Institute of Systems and Robotics (ISR-Coimbra) also under regular funding by FCT.

References

1. "Webster's Online Dictionary". http://www.websters-online-dictionary.org (Nov. 2010).

2. A. Machado, G. Ramalho, J. Zucker and A. Drogoul. "Multi-Agent Patrolling: an Empirical Analysis of Alternative Architectures", Multi-Agent-Based Simulation (MABS'2002), Third International Workshop, 155-170, Bologna, Italy, July 15-16, 2002.

2. A. Machado. "Patrulha Multiagente: Uma Análise Empírica e Sistemática". M.Sc. Thesis, Centro de Informática, Univ. Federal de Pernambuco, Brasil, 2002 (In Portuguese).

4. A. Almeida. "Patrulhamento Multiagente em Grafos com Pesos". M.Sc. Thesis, Centro de Informática, Univ. Federal de Pernambuco, Recife, Brasil, 2003 (In Portuguese).

5. Y. Elmaliach, N. Agmon and G. Kaminka. "Multi-Robot Area Patrol under Frequency Constraints", Int. Conf. on Robotics and Automation, 385-390, Rome, Italy, 2007.

6. Y. Chevaleyre. "Theoretical Analysis of the Multi-agent Patrolling Problem", In Proc. of the Int. Conf. On Intelligent Agent Technology, 302-308, Beijing, China, 2004.

7. H. Santana, G. Ramalho, V. Corruble and B. Ratitch. "Multi-Agent Patrolling with Reinforcement Learning", In Proc. of the Third Int. Joint Conf. on Autonomous Agents and Multiagent Systems, 1122-1129, Vol. 3, New York, 2004.

8. T. Menezes, P. Tedesco and G. Ramalho. "Negotiator Agents for the Patrolling Task". In Proc. of the Int. Conf. IBERAMIA/SBIA, LNAI. 4140, 48-57, São Paulo, 2006.

9. K. Hwang, J. Lin and H. Huang. "Cooperative Patrol Planning of Multi-Robot Systems by a Competitive Auction System". Int. Joint Conf., Fukuoka, Japan, August 18-21, 2009.

10. A. Almeida, G. Ramalho, H. Sanana, P. Tedesco, T. Menezes, V. Corruble and Y. Chaveleyre. "Recent Advances on Multi-Agent Patrolling". Brazilian Symposium on Artificial Intelligence, 474-483, Vol. 3171, São Luís, Brazil, 2004.

11. F. Sempé and A. Drogoul. "Adaptive Patrol for a Group of Robots". In Proc. of the Int. Conf. on Intelligent Robots and Systems, Las Vegas, Nevada, October, 2003.

12. Y. Guo, L. Parker and R. Madhavan. "9 Collaborative Robots for Infrastructure Security Applications", Studies in Computational Intelligence (SCI), Springer-Verlag Berlin Heidelberg, 185-200, Vol. 50, April 22, 2007.

13. H. Chu, A. Glad, O. Simonin, F. Sempé, A. Drogoul and F. Charpillet. "Swarm Approaches for the Patrolling Problem, Information Propagation vs. Pheromone Evaporation", Int. Conf. on Tools with Art. Intelligence, 1, 442-449, France, 2007.

14. T. Sak, J. Wainer and S. Goldenstein. "Probabilistic Multiagent Patrolling", In Proc. of the Brazilian Symposium on Artificial Intelligence, Salvador, Bahia, Brazil, 2008.

15. D. Portugal. "RoboCops: A Study of Coordination Algorithms for Autonomous Mobile Robots in Patrolling Missions", Msc. Dissertation, Faculty of Science and Technology, University of Coimbra, Portugal, September, 2009.

16. D. Portugal and R. Rocha. "MSP Algorithm: Multi-Robot Patrolling based on Territory Allocation using Balanced Graph Partitioning", In Proc. of Symposium on Applied Computing (SAC'2010), 1271-1276, Sierre, Switzerland, March 22-26, 2010.

17. D. Portugal, C. Henggeler Antunes, R. Rocha. "A Study of Genetic Algorithms for Approximating the Longest Path in Generic Graphs". In Proc. 2010 IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC'2010), Istanbul, Turkey, Oct. 10-13, 2010.