Multi-Agent Patrolling
(page unfinished)
The Task
According
to the Oxford Dictionary, patrolling is the "act of walking around an area
in order to protect or supervise it. There are many variations of patrolling,
grouped into, at least, two categories: one, rather related to supervision,
concerned with minimizing the time lag between two visits to the same location,
and the other , related to detection, concerned with locating a given mobile
target, such as an intruder. Multi-agent patrolling is simply the patrolling
that is performed by various agents, which often the case. Multi-agent
patrolling requires coordinated behavior and decision-making in order to
achieve optimal global performance. In fact, it has been shown that it is not
because each agent do its best, that the performance of the entire society will
be the best one.
In order
to obtain an abstract, yet precise, definition of the patrolling task, the
terrain being patrolled can be represented as a graph, where the nodes
correspond to specific locations and the edges to possible paths. The main
advantage of adopting this abstract representation is that it can be easily
mapped to many different domains, from terrains to computer networks. Thus, for
the supervision case, patrolling can be formally defined as the task of
continuously visiting all the graph nodes so as to minimize the time gap
between two visits to each node. 
The
criteria for measuring performance...
There are
some variations in the graph to be patrolled. For instance, the graph may be
dynamic, representing for instance mobile obstacles or instable paths. Dynamicity
can also be introduced by working with a open agent society, where new agents
can join the initial group, and some agent can quit it. The graph nodes may
also have different priorities, some needing to be visit more frequently than
others, in order to represent some king of strategic/tactical importance.
Patrolling
Applications
Patrolling
can be useful for domains where distributed surveillance, inspection or control
is required. For instance, patrolling agents can help administrators in the
surveillance of failures or specific situations in an Intranet; to detect
recently modified or new web pages to be indexed by search engines; to plan
routes for policemen rounds or for healthcare personnel looking for eradicating
focus of infections diseases; etc.
Patrolling
can also be useful for various computer game genres. This is typically the case
of real-time strategy games (such as WarCraft) and RPG (such as Diablo) for
detecting mobile characters and new enemy buildings, protect cities and
resources, etc. Multi-agent patrolling can also be useful in combat games (such
as StarWars Rogue Squadron), in especial in first-person shooters (such as
CounterStrike), for the detection of enemies and the discovery of items.
Research
historic and state of the art
Despite
its potential applications, only recently multi-agent patrolling has been
studied in depth. ...
Simulator
...
Researchers
...
Publications
Santana,
H., Ramalho, G., Corruble, V. & Ratitch, B. (2004) Multi-Agent Patrolling
with Reinforcement Learning In proc. 3rd International Joint Conference on
Autonomous Agents and Multi-Agents Systems (AAMAS’04). pp. 1122-1129.
Chevaleyre,
Y. (2004). Theoretical Analysis of the Multi-Agent Patrolling Problem. In
Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent
Techonology,
Almeida,
A., Ramalho, G., Santana, H. Tedesco, P. Menezes, T. Corruble, V &
Chevaleyre, Y. (2004). Recent Advances on Multi-Agent Patrolling. In A. L.
Bazzan & S. Labidi (eds). Recent Advances in Artificial Intelligence.
SBIA’2004. LNAI 3171. pp. 474-483.
Chevaleyre,
Y., Sempé, F., Ramalho, G. L. (2004). A theoretical analysis of multi-agent
patrolling strategies. Short paper in 3rd International Joint Autonomous
Agents and Multi-agent Systems Conference, AAMAS-2004,
Sempé,
F., Drogoul, A. (2003) Adaptive Patrol for a Group of Robots. International
Conference on Intelligent Robots and Systems [pdf]
Almeida,
A, de Castro, P., Menezes, T. & Ramalho, G. (2003). Combining Idleness and
Distance to design Heuristic Agents for the Patrolling Task. II Workshop de Jogos e Entretenimento Digital. (pp.
33-40). Salvador: Sociedade Brasileira de Computação. [pdf]
Machado, A., Ramalho, G., Zucker, J.-D. & Drogoul, A. (2002) Multi-Agent Patrolling: an Empirical Analysis of Alternative Architectures. In J. Sichman, F. Bousquet and P. Davidsson (eds.). Multi-Agent-Based Simulation II - 3rd. International Workshop on Multiagent Based Simulation (MABS’02) - Revised Papers - LNAI 2581. pp. 155-70. Berlin: Springer-Verlag. [pdf]
Machado, A., Almeida. A., Ramalho, G.,
Zucker, J.-D. & Drogoul, A. (2002). Multi-Agent Movement
Coordination in Patrolling. In proceedings of 1st Workshop on Agents in
Computer Games, in 3rd International Conference on Computers and Games (CG'02),
(pp. 61-69).
Ph.D.
Thesis, M.Sc. Dissertations and technical reports
Menezes,Talita (2005) Negociação em
sistemas multiagente para patrulhamento. Master of Science dissertation.
Centro de Informática - UFPE, Brazil. (In Portuguese) - UNFINISHED
Chevaleyre, Y.
(2005). Le Problème Multiagent de la Patrouille. In Annales du LAMSADE
n°4. Post-doctoral Report (in french) [pdf]
Sempé, François
(2004) Auto-organisation d'une collectivité de robots : application à
l'activité de patrouille en présence de perturbations. Ph.D. Thesis.
Université Pierre et Marie Curie (Paris VI). France (In French) [link]
Cohen-Solal,
Julien (2004) Les Algorithmes de patrouilles dans les systèmes
multi-agents. Technical Report of DEA Stage. Laboratoire d'Informatique de
Paris 6, Université Paris 6.
Santana, Hugo (2005) Patrulha Multiagentes com Aprendizagem por reforço. Master of Science dissertation. Centro de Informática - UFPE, Brazil. (In Portuguese) [pdf/zip]
Almeida, Alessandro (2003) Patrulhamento Multiagente em Grafos com Pesos. Master of Science dissertation. Centro de Informática - UFPE, Brazil. (In Portuguese) [pdf/zip]
Machado, Aydano (2002) Patrulha Multiagente: uma Análise Empírica e Sistemática. Master of Science dissertation. Centro de Informática - UFPE, Brazil. (In Portuguese)
Leitão, André (2003) Patrulhamento e posicionamento tático para sistemas multiagente em jogos de combate. Final Graduation Work. Centro de Informática - UFPE, Brazil. [doc] (In Portuguese)