ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 28/6 - 2014  - pp.665-687  - doi:10.3166/ria.28.665-687
TITRE
Le problème de la patrouille multiagent. Étude de convergence de l'évaluation des stratégies cycliques

TITLE
The multiagent patrolling problem. Convergence analysis about the evaluation of cyclic strategies

RÉSUMÉ
Le problème de la patrouille multiagent implique une équipe d’agents qui doivent visiter les lieux stratégiques d’un environnement le plus fréquemment possible. Ce problème d’optimisation consiste généralement à déterminer une stratégie de patrouille multiagent minimisant la pire oisiveté d’un graphe, c’est-à-dire la plus grande durée pendant laquelle un nœud n’a pas été visité. Nous proposons dans cet article d’étudier de manière théorique l’évaluation des stratégies de patrouille cycliques. Une telle stratégie est constituée de n couples de pré-cycles et de cycles, n étant le nombre d’agents patrouilleurs. Chaque cycle définit la liste des nœuds qu’un agent doit visiter indéfiniment, le premier nœud étant le même que le dernier nœud. Chaque pré-cycle définit la liste des nœuds visités par un agent pour atteindre son cycle de patrouille. Nous présentons dans cet article les conditions de convergence permettant à un algorithme efficace d’évaluer en un nombre fini d’étapes la pire oisiveté de telles stratégies. Un algorithme d’évaluation basé sur ces résultats théoriques est également décrit.


ABSTRACT
Patrolling an environment involves a team of agents whose goal consists in continuously visiting its most relevant areas as frequently as possible. The current research that tackles this complex multi-agent problem usually defines the environment as a graph upon which agents move and seek to optimize the worst idleness of a graph, that is the delay during which a node remains unvisited. This paper deals with the problem of evaluating cyclic multi-agent patrolling strategies, those where every agent ultimately visits the same set of nodes indefinitely. We provide theoretical results about the computation time required for the convergence in the evaluation of any such strategy. An evaluation algorithm is also presented.


AUTEUR(S)
Fabrice LAURI, Abderrafiaa KOUKAM, Jean-Charles CRÉPUT

MOTS-CLÉS
patrouille multiagent, stratégies de patrouille cycliques, étude théorique

KEYWORDS
multi-agent patrolling, cyclic patrolling strategies, theoretical results

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (319 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier