1 Analyse théorique du problème de la patrouille multi-agent en utilisant le cadre des PDM Fabrice Lauri, François Charpillet, Daniel Szer Equipe MAIA

11

Analyse théorique du Analyse théorique du problème de la patrouille problème de la patrouille multi-agent en utilisant le multi-agent en utilisant le

cadre des PDMcadre des PDM

Fabrice Lauri, François Charpillet, Daniel Fabrice Lauri, François Charpillet, Daniel SzerSzer

Equipe MAIA – LORIAEquipe MAIA – LORIANancyNancy

2

PlanPlan

► Problématique généraleProblématique générale► Cadre de travail Cadre de travail [Machado, 2002][Machado, 2002]► Domaines d’applicationsDomaines d’applications► Etat de l’artEtat de l’art► Modélisation par un PDMModélisation par un PDM► Conclusions et PerspectivesConclusions et Perspectives

3

PlanPlan


4

Problématique généraleProblématique générale

Patrouille = « mission impliquant une équipe de plusieurs Patrouille = « mission impliquant une équipe de plusieurs agents dont le but consiste à visiter régulièrement les lieux agents dont le but consiste à visiter régulièrement les lieux stratégiques d’un environnement, afin de :stratégiques d’un environnement, afin de : le défendrele défendre le surveillerle surveiller ou le contrôler. »ou le contrôler. »

Plusieurs questions :Plusieurs questions : Comment représenter l’environnement ?Comment représenter l’environnement ? Qu’entend t’on par « lieu stratégique » ? Qu’entend t’on par « lieu stratégique » ? Quelle architecture d’agent utiliser ?Quelle architecture d’agent utiliser ? Quel(s) critère(s) utiliser ?Quel(s) critère(s) utiliser ? ……

5

Un exempleUn exempleEnvironnement 2D, 5 agentsEnvironnement 2D, 5 agents

6

PlanPlan


7

Cadre de travailCadre de travailEnvironnement graphiqueEnvironnement graphique

► Environnement à patrouiller graphe (de Environnement à patrouiller graphe (de patrouille)patrouille)

► Soit G = (V, E, c) un graphe de patrouille :Soit G = (V, E, c) un graphe de patrouille : V={1,2,…} : lieux pertinents de l’environnement,V={1,2,…} : lieux pertinents de l’environnement, E={(i,j) ; i,j V} : ensemble des liaisons sûres E={(i,j) ; i,j V} : ensemble des liaisons sûres

entre ces lieux.entre ces lieux. Pour chaque arc (i,j) :Pour chaque arc (i,j) :

c(i,j) : coût (temps) pour aller de i à j.c(i,j) : coût (temps) pour aller de i à j.

CC

8

Cadre de travail - ExempleCadre de travail - ExempleGraphe de patrouille, 5 agentsGraphe de patrouille, 5 agents

Graphe de :• 50 nœuds• 69 arcs• degré 5

9

Cadre de travailCadre de travailStratégie de patrouilleStratégie de patrouille

►Objectif :Trouver une stratégie multi-agent de parcours du graphe qui minimise le temps entre deux visites d’un même nœud pour chacun des nœuds.

► = ( 1, 2, …, N), avec : i : stratégie individuelle de l’agent i i(t) : nœud visité par l’agent i à l’instant t

10

Cadre de travailCadre de travailCritères d’évaluation d’une Critères d’évaluation d’une

stratégiestratégieSoient :Soient :► IInn(t) : oisiveté (ou (t) : oisiveté (ou IdlenessIdleness) du nœud n à l’instant t) du nœud n à l’instant t► AvgI(t) : oisiveté du graphe à l’instant t, avec :AvgI(t) : oisiveté du graphe à l’instant t, avec :

AvgI( t ) = moyenne des IAvgI( t ) = moyenne des Inn(t)(t)► AvgI : oisiveté du graphe à l’issue de T pas de AvgI : oisiveté du graphe à l’issue de T pas de

simulation (ou cycles)simulation (ou cycles)► WI : pire oisiveté rencontrée au cours de la simulationWI : pire oisiveté rencontrée au cours de la simulation

Mesurer la qualité d’une stratégie S de patrouille = Mesurer la qualité d’une stratégie S de patrouille = déterminer AvgI (ou WI) après T cycles de simulation déterminer AvgI (ou WI) après T cycles de simulation de S.de S.

La stratégie minimisant WI = stratégie optimale.La stratégie minimisant WI = stratégie optimale.

11

Cadre de travail – ExempleCadre de travail – ExempleStratégie de patrouille, 5 agentsStratégie de patrouille, 5 agents

Stratégie Agent #12,5,7,8,10,12

Stratégie Agent #21,3,4,9,12,15,20,

25,30

…

A l’issue de T pasde simulation

WI = 1463AvgI = 549.6

12

PlanPlan


13

Domaines d’applicationsDomaines d’applications

Toutes les applications pour lesquelles un contrôle ou Toutes les applications pour lesquelles un contrôle ou une surveillance distribué(e) dans un graphe est une surveillance distribué(e) dans un graphe est requis :requis :

► Surveillance contre les intrusions dans un réseau Surveillance contre les intrusions dans un réseau informatique,informatique,

► Sauvetage par des robots de blessés ayant subi une Sauvetage par des robots de blessés ayant subi une catastrophe (catastrophe (RoboCup RescueRoboCup Rescue),),

► Détection de menaces ennemis ou protection de Détection de menaces ennemis ou protection de territoires dans le domaine des jeux vidéos,territoires dans le domaine des jeux vidéos,

► etc.etc.

14

PlanPlan


15

Etat de l’artEtat de l’art(1/2)(1/2)

► [Machado et al., 2002a; Machado et al., 2002b][Machado et al., 2002a; Machado et al., 2002b] : : travaux pionniers. travaux pionniers.

► [Almeida et al., 2004][Almeida et al., 2004] : techniques de négociation : techniques de négociation

► [Chevaleyre, 2003][Chevaleyre, 2003] : PPMA = problème : PPMA = problème d’optimisation combinatoire :d’optimisation combinatoire : Avec 1 agent = Avec 1 agent = Graphical-TSPGraphical-TSP,, > 1 agent : proposition de stratégies proches de l’optimum > 1 agent : proposition de stratégies proches de l’optimum

(stratégies à cycle unique)(stratégies à cycle unique)

16

Etat de l’artEtat de l’art(2/2)(2/2)

► [Santana et al., 2004][Santana et al., 2004] : apprentissage par : apprentissage par renforcement de PDM.renforcement de PDM.

► [Almeida et al., 2004][Almeida et al., 2004] : comparaison des techniques : comparaison des techniques de l’état de l’art :de l’état de l’art : Travaux pionniers : les moins bons résultatsTravaux pionniers : les moins bons résultats Stratégie à cycle unique : les meilleurs résultatsStratégie à cycle unique : les meilleurs résultats Autres techniques : résultats équivalentsAutres techniques : résultats équivalents

17

PlanPlan


18

Définition du PDM Définition du PDM pour un graphe unitairepour un graphe unitaire

► S = { (<positions des agents>, <oisivetés des S = { (<positions des agents>, <oisivetés des nœuds>, <pire oisiveté rencontrée>) }nœuds>, <pire oisiveté rencontrée>) }

19

Définition du PDM Définition du PDM pour un graphe unitairepour un graphe unitaire


Optimisation sur le critère WI

20

Définition du PDMDéfinition du PDMpour un graphe unitairepour un graphe unitaire


► A = { <actions jointes des agents> }A = { <actions jointes des agents> }

► T : S x A x S { 0, 1 } T : S x A x S { 0, 1 } (déterministe)(déterministe)

► R : S x A x S { -1, 0 }R : S x A x S { -1, 0 }

R = R =

0 si pire oisiveté de l’état courant < pire oisiveté de l’état précédent

-1 sinon

21

Résolution du PPMARésolution du PPMApour un graphe unitairepour un graphe unitaire

► Déterminer la politique qui minimise le critère Déterminer la politique qui minimise le critère gamma pondéré :gamma pondéré :

et telle que la suite d’états set telle que la suite d’états s00, …, s, …, sii, …, s, …, skk constitue constitue un un cyclecycle, c’est-à-dire que i avec s, c’est-à-dire que i avec sii = s = skk..

► Stratégie obtenue est optimale (démonstration Stratégie obtenue est optimale (démonstration dans l’article)dans l’article)

t=0t=0

NNE{ E{ ΣΣ tt r rtt } avec [0,1] } avec [0,1] CC

22

Exemple d’une patrouilleExemple d’une patrouilleavec 2 agentsavec 2 agents

1

2

53

4

Configuration initiales0 = (<5, 2>, <0,0,0,0,0>, 0)

1

2

Séquence d’états représentant la meilleurestratégie de patrouille

23


1

2

53

4

Configuration initiales0 = (<5, 2>, <0,0,0,0,0>, 0)s1 = (<1, 1>, <0,1,1,1,1>, 1)

12


24


1

2

53

4

Configuration initiales0 = (<5, 2>, <0,0,0,0,0>, 0)s1 = (<1, 1>, <0,1,1,1,1>, 1)s2 = (<3, 4>, <1,2,0,0,2>, 2)

1

2


25


1

2

53

4

Configuration initiales0 = (<5, 2>, <0,0,0,0,0>, 0)s1 = (<1, 1>, <0,1,1,1,1>, 1)s2 = (<3, 4>, <1,2,0,0,2>, 2)s3 = (<1, 1>, <0,3,1,1,3>, 3)

12


26


1

2

53

4

Configuration initiales0 = (<5, 2>, <0,0,0,0,0>, 0)s1 = (<1, 1>, <0,1,1,1,1>, 1)s2 = (<3, 4>, <1,2,0,0,2>, 2)s3 = (<1, 1>, <0,3,1,1,3>, 3)s4 = (<5, 2>, <1,0,2,2,0>, 3)

1

2


27


1

2

53

4

Configuration initiales0 = (<5, 2>, <0,0,0,0,0>, 0)s1 = (<1, 1>, <0,1,1,1,1>, 1)s2 = (<3, 4>, <1,2,0,0,2>, 2)s3 = (<1, 1>, <0,3,1,1,3>, 3)s4 = (<5, 2>, <1,0,2,2,0>, 3)s5 = (<1, 1>, <0,1,3,3,1>, 3)

12


28


1

2

53

4

Configuration initiales0 = (<5, 2>, <0,0,0,0,0>, 0)s1 = (<1, 1>, <0,1,1,1,1>, 1)s2 = (<3, 4>, <1,2,0,0,2>, 2)s3 = (<1, 1>, <0,3,1,1,3>, 3)s4 = (<5, 2>, <1,0,2,2,0>, 3)s5 = (<1, 1>, <0,1,3,3,1>, 3)s6 = (<3, 4>, <1,2,0,0,2>, 3)

1

2


29


1

2

53

4

Configuration initiales0 = (<5, 2>, <0,0,0,0,0>, 0)s1 = (<1, 1>, <0,1,1,1,1>, 1)s2 = (<3, 4>, <1,2,0,0,2>, 2)s3 = (<1, 1>, <0,3,1,1,3>, 3)s4 = (<5, 2>, <1,0,2,2,0>, 3)s5 = (<1, 1>, <0,1,3,3,1>, 3)s6 = (<3, 4>, <1,2,0,0,2>, 3)s7 = (<1, 1>, <0,3,1,1,3>, 3)

12

=


Stratégie Agent #15, 1, 3, 1, { 5, 1, 3, 1 }*

Stratégie Agent #22, 1, 4, 1, { 2, 1, 4, 1 }*

1

2

30

Transformation d’un graphe non Transformation d’un graphe non unitaire en graphe unitaire (1/2)unitaire en graphe unitaire (1/2)► Soit G = (V, E) un graphe non unitaire. G’ = (V’, E’ ) Soit G = (V, E) un graphe non unitaire. G’ = (V’, E’ )

est le graphe unitaire à construire.est le graphe unitaire à construire.

► Soit c : coût minimal du graphe G.Soit c : coût minimal du graphe G.► Pour chaque paire i, j V, ajouter mPour chaque paire i, j V, ajouter m ijij = ( - 1) = ( - 1)

nœuds.nœuds.

► Si mSi mijij = 0, ajouter les arcs (i,j) et (j,i) = 0, ajouter les arcs (i,j) et (j,i)

► Sinon, ajouter les arcs (i, nSinon, ajouter les arcs (i, n11), (n), (n11, n, n22), …, (n , j).), …, (n , j).

cij

cCC

mij

31

Transformation d’un graphe non Transformation d’un graphe non unitaire en graphe unitaire (2/2)unitaire en graphe unitaire (2/2)

01

2

3

24

5

01

2

3

4

5

67

89

Graphe non unitaire Graphe unitaire correspondant

32

PlanPlan


33

ConclusionsConclusions

► Première analyse formelle du PPMA à l’aide d’un PDMPremière analyse formelle du PPMA à l’aide d’un PDM► Solutions exactes sur les instances les moins complexes du Solutions exactes sur les instances les moins complexes du

problèmeproblème

► Proposer un algorithme pour résoudre efficacement le PDM du Proposer un algorithme pour résoudre efficacement le PDM du PPMAPPMA

► Tester cette approche sur des instances du PPMATester cette approche sur des instances du PPMA► Déterminer la complexité des graphes qui peuvent être traités par Déterminer la complexité des graphes qui peuvent être traités par

cette approchecette approche► Evaluer le biais de la transformation d’un graphe non unitaire en Evaluer le biais de la transformation d’un graphe non unitaire en

graphe unitairegraphe unitaire

► Proposer un autre cadre de travail prenant en compte :Proposer un autre cadre de travail prenant en compte : la perception des agentsla perception des agents la superficie effectivement surveilléela superficie effectivement surveillée

PerspectivesPerspectives

Documents

1 Analyse théorique du problème de la patrouille multi-agent en utilisant le cadre des PDM Fabrice Lauri, François Charpillet, Daniel Szer Equipe MAIA