Le probleme multi-agents de la patrouillechevaley/papers/anna_patro.pdf · Le probleme multi-agents de la patrouille ... communs avec le problème de la patrouille : citons les Vehicule

Le probleme multi-agents de la patrouilleYann Chevaleyre∗

Résumé

Le problème multi-agents de la patrouille a été récemment introduit dans [2]. Ceproblème consiste a faire se déplacer un ensemble d’agents ou de robots sur un ter-ritoire prédéfini de telle sorte, informellement, que chaque partie de ce territoire soitvisitée par des agents le plus souvent possible. Pour résoudre ce problème, des ap-proches basées sur des architectures d’agents réactifs et cognitifs avaient été décritesdans [2]. Ce problème est ici abordé comme une tâche d’optimisation combinatoire.Pour cela, le territoire est modélisé sous forme d’un graphe. Différentes stratégiesd’exploration du graphe sont envisagées, en particulier basées sur des cycles issus duvoyageur de commerce. Avec ces dernières et dans le cas où le graphe est métrique,nous obtenons en temps polynomial une stratégie d’exploration dont la valeur estborné par 3 × opt + 4 × maxij{cij}, avec cij désignant le poids de l’arête (i, j).On montre enfin qu’avec une autre approche basée sur un partitionnement du grapheen régions distinctes, le problème devient 15-approximable, même dans le cas degraphes non métriques.

Mots-clefs : Systèmes Multiagents, Problème de la Patrouille, Optimisation combi-natoire, Approximation polynomiale

1 Introduction

Le problème multi-agents de la patrouille consiste à faire parcourir à des agents unterritoire, de telle sorte que les différentes parties du territoire soient visitées le plus sou-vent possible par ces agents. Ce problème se pose typiquement dans les jeux vidéos [2, 3]lorsqu’une équipe de créatures virtuelles a pour mission de patrouiller sur un territoire dé-terminé, dans certaines applications internet, ainsi que pour le déplacement d’une équipede robots [15].

∗LAMSADE, Université Paris-Dauphine, 75775 Paris cedex 16, [email protected]

Le probleme multi-agents de la patrouille

Ce problème avait été initialement introduit dans le cadre des systèmes multi-agents(SMA) par Geber Ramalho [2]. Ce dernier avait abordé le problème en utilisant le para-digme multi-agents classique. Mentionnons deux des algorithmes représentatifs de cetteapproche : une première solution avait consisté à développer des agents réactifs, ne possè-dant aucune capacité de plannification ou de raisonnement, chaque agent se déplaçant endirection de la zone de son voisinage immédiat qui soit restée sans visite le plus long-temps. Dans une deuxième approche basée sur des agents cognitifs, chaque agent sedirigeait vers la partie du territoire - pas nécessairement voisine - ayant été sans visited’agent le plus longtemps possible, en utilisant un algorithme du plus court chemin. Unmécanisme de communication entre agents leur permettait de se coordonner en se parta-geant les régions à visiter, afin que deux agents ne se dirigent pas vers le même lieu. Lesdifférents algorithmes développés par Machado et Ramalho ont été implémentés dans unsimulteurs, pour permettre la visualisation du comportement de chaque agent (figure 1).

Cet article aborde le problème sous l’angle très différent de l’optimisation combi-natoire. Notons que de nombreux problèmes d’optimisation combinatoire ont des pointscommuns avec le problème de la patrouille : citons les Vehicule Routing Problem, et enparticulier le min-max-VRP. Il est peut-etre possible d’établir d’autres résultats en utilisantune réduction de notre problème vers ce dernier. Cependant, les problèmes de la familledes VRP supposent l’existance d’un dépot, auquel chaque agent se retourne à la fin desa tournée. A cause de cette différence, nous n’avons pu trouver de réduction efficace denotre problème vers un VRP. La contribution principale de cet article a consisté à mettreen évidence le lien entre notre problème et le problème du voyageur de commerce. En ex-ploitant ce lien et en introduisant certains biais sur l’espace de recherche, on peut aboutirà des solutions de bonnes qualités.

Des expérimentations ont été mis en oeuvre pour comparer certaines des solutions pro-posées dans cet article et les algorithmes multiagents de [2]. Des résultats préliminaires,qui sont détaillés dans [1], ont montré sur divers graphes que les stratégies obtenus par lesméthodes décrites (en section 6) étaient jusqu’à deux fois meilleures que les algorithmesmultiagents classiques de [2].

Cet article commence par une présentation du problème multi-agents de la patrouille,et du formalisme employé. Ensuite, le lien avec le problème du voyageur de commerce(TSP) est établi dans le cas mono-agent. Puis, des biais sont introduits sur l’espace derecherche sous la forme de classes de stratégies. Ensuite, ces classes sont comparées lesunes aux autres afin de déterminer dans lesquelles ont peut trouver de bonnes stratégies.Enfin, les deux dernières sections montrent des résultats d’approximation obtenus à l’aidede certaines de ces classes : la section 6 montre que dans le cas métrique, en utilisantdes algorithmes d’approximation pour TSP, on peut obtenir dans le cas multi-agents desstratégies dont le critère est borné par 3 × opt + 4 × maxij{cij}, et la dernière sectionmontre que le problème de la patrouille est 15-approximable y compris dans le cas nonmétrique.

2

Annales du LAMSADE n◦4

2 Le problème de la patrouille

Le territoire que patrouillent les agents peut-être décrit par un graphe, comme dans [2].Soit un graphe G = (V, E) représentant le territoire, V étant l’ensemble des n sommetsdu graphe et E l’ensemble des arêtes. A l’instant initial, chacun des r agents se trouvesur l’un des noeuds du graphe. Notons que le nombre d’agents est constant, et ne variepas durant le processus de patrouille. On associe à chaque arête (i, j) de E un coût cij ,représentant la distance entre i et j. On suppose dans la suite de cet article que la fonctioncij est positive, symétrique. Pour se déplacer de i à j, un agent nécessitera donc un tempségal à cij. On souhaite pour chacun des r agents à disposition élaborer une stratégie deparcours dans ce graphe de telle sorte que chaque noeud du graphe soit visité le plussouvent possible.

agents

FIG. 1 – Simulateur d’agent de patrouille, développé par Aydano et al.

Définition 1 Nous appellerons stratégie d’un agent la fonction π : N → V telle que π(j)désigne le jime noeud visité par l’agent. Nous désignerons par Π = {π1...πr} la stratégiemultiagent, définie comme étant l’ensemble des stratégies π1...πr des r agents. Πr(G)désigne l’ensemble des stratégies multiagents possibles avec r agents sur le graphe G.Lorsqu’il n’y a pas d’ambiguité sur le nombre d’agents impliqués ni sur le graphe consi-déré, nous noterons cet ensemble Π.

Connaissant la stratégie d’un agent i, nous pouvons déterminer les instants auxquelschaque noeud est visité. Ainsi, l’agent i ayant la stratégie πi visitera le noeud πi(0) à l’ins-tant 0. De même, il visitera le noeud πi(j) à l’instant égal au poids du chemin πi(0)...πi(j),c’est à dire

∑j−1k=0 cπi(k)πi(k+1). Pour alléger l’écriture, nous définirons le poids d’un che-

min (et donc d’un cycle) s0...sm comme étant la somme des poids des arêtes présentes

3


dans ce chemin c(s0...sm) =∑m−1

i=0 csisi+1. Par extension, nous désignerons le poids

d’un ensemble d’aretes E ′ avec la même fonction c(E ′). Notre objectif étant de créer desbonnes stratégies d’exploration du territoire, il nous faut décider de critères d’évaluationpour ces stratégies. Pour cela, nous introduisons la notion d’oisiveté d’un noeud :

Définition 2 L’oisiveté d’un noeud i au temps t, notée Idlet(i) est l’intervalle de tempsécoulé depuis la dernière visite d’un agent sur ce noeud. Par convention, à l’instant 0,l’oisiveté de chaque noeud est nulle. A partir de l’oisiveté d’un noeud, on peut construiredivers critères pour mesurer l’oisiveté du graphe à un instant donné. En voila trois : l’oisi-veté maximale, moyenne, et polynomiale : AvgIdlt(G) = 1

n

∑ni=1 Idlet(i), MaxIdlt(G) =

maxi∈V Idlet(i), PolyIdlαt (G) = α

√1n

∑i=1 Idlet(i)α

L’oisiveté polynomiale, inspirée de [8], offre un compromis entre les mesures moyennes etmaximales. En effet, selon que le paramètre α est proche de 1 ou de l’infini, l’oisiveté po-lynomiale tendra vers l’oisiveté moyenne ou maximale. Nous lui préfèrerons néanmoinsdes critères plus simples à analyser, comme par exemple l’oisiveté maximale. A partirde ces mesure instantanées, on peut définir des critères qui nous serviront à comparer lesdifférentes stratégies multiagents.

Définition 3 Soit Π = {π1...πr}, une stratégie multiagents de parcours du graphe par ragents. A partir des oisivetés instantanées, nous définissons les critères suivants :

– MaxMaxIdlΠ(G) = maxt∈R+(lim inft′→t MaxIdlt′(G)). voir figure 2.– MaxAvgIdlΠ(G) = maxt∈R+(lim inft′→t AvgIdlt′(G)),

– AvgMaxIdlΠ(G) = limt′→∞ 1t′

∫ t′

t=0MaxIdlt(G)dt,

– AvgAvgIdlΠ(G) = limt′→∞ 1t′

∫ t′

t=0AvgIdlt(G)dt.

Dans un soucis de simplicité, nous nous limiterons essentiellement à l’étude du critèreMaxMaxIdl, que l’on peut formuler de façon plus simple : La valeur de MaxMaxIdl estégale au plus grand interval de temps durant lequel un noeud ne reçoit la visite d’aucunagent. Notons que pour toute stratégie Π, nous aurons : MaxMaxIdlΠ ≥ AvgMaxIdlΠ ≥AvgAvgIdlΠ et MaxMaxIdlΠ ≥ MaxAvgIdlΠ ≥ AvgAvgIdlΠ. Le critère choisiMaxMaxIdl étant une borne supérieure des autres critères, sa minimisation produiravraissemblablement des solutions acceptables, relativement aux autres critères. Remar-quons par ailleurs que si le poids des arêtes cij ∈ N, alors on peut simplifier l’expressiondu critère de la façon suivante : MaxMaxIdlΠ(G) = maxt∈R+ �MaxIdlt(G)�.

Pour finir cette section, donnons une définition formelle du problème de la patrouille.

Définition 4 (le problème de la patrouille) Soit un graphe G = (V, E) connexe, ainsiqu’un nombre r d’agents. Le problème de la patrouille consiste à déterminer une stratégiemultiagents Π = {π1...πr} qui minimise MaxMaxIdlΠ(G).

4


1 2

Idl(1)=0 Idl(2)=0t=0

1 2

Idl(1)=0.9 Idl(2)=0.9t=0.9

1 2

Idl(1)=1.8 Idl(2)=0.8t=1.8

1 2

Idl(1)=0.2 Idl(2)=1.3t=2.3

FIG. 2 – Un agent patrouillant un graphe composé de deux noeuds reliés par une arêtede poids 1. La stratégie de l’agent est π = 1, 2, 1, 2, 1, . . .. Après un aller-retour ef-fectué par l’agent (symbolisé par un robot), l’oisiveté de chaque noeud tend vers 2à mesure que l’agent s’en approche, mais n’atteint jamais 2, puisque l’oisiveté d’unnoeud sur lequel l’agent se trouve devient nulle. Donc, lim inf t→2 Idlt(1) = 2, et doncMaxMaxIdlπ(G) = 2.

3 Liens entre le problème du voyageur de commerce et leproblème mono-agent de la patrouille

Dans cette section, après avoir rappelé la définition et quelques propriétés du problèmedu voyageur de commerce (TSP), nous montrerons en quoi ce problème peut être utilepour comprendre et résoudre le problème multi-agents de la patrouille. Nous montreronsen particulier que lorsqu’il n’y a qu’un seul agent, le problème de la patrouille (avecMaxMaxIdl et AvgAvgIdl) est équivalent à une certaine variante du TSP.

Définition 5 Soit G, un graphe complet, et cij un poids associé à chaque couple de som-met (i, j) de G. Le problème du voyageur de commerce consiste à trouver un cycle élé-mentaire s0...sn (c’est à dire ne passant pas deux fois par le même sommet) qui parcouretous les sommets du graphe une fois et une seule, et tel que c(s0...sn) soit minimale.

Le problème du voyageur de commerce ainsi défini suppose que tous les sommets dugraphe sont reliés entre eux (graphe complet). Afin de nous rapprocher du problème de

5


la patrouille, pour lequel les graphes ne sont pas supposés complets, nous utiliserons unevariante du problème du voyageur de commerce, connu sous le nom de graph-TSP [12],qui porte sur des graphes G(V, E) non nécessairement complets : dès lors, il ne s’agitplus de trouver un cycle élémentaire mais un cycle s1...sm passant au moins une fois parchaque sommet tel que ∪m

i=1si = V , et que c(s1...sm) soit minimal. Il est montré dans[13] que toute instance du problème de graph-TSP peut être efficacement réduite à uneinstance d’un problème TSP.

Soulignons l’intérêt de mettre en évidence des liens entre les problèmes qui nous in-téressent et le TSP. D’abord, il existe de très nombreux algorithmes disponibles publique-ment permettant de résoudre des instances du TSP de taille importante. Nous avons pournotre part utilisé le logiciel open-source “Concorde” 1 qui implémente plusieurs algo-rithmes efficaces, dont l’heuristique lin-kernighan [9]. Il est par ailleurs capable de four-nir la solution optimale sur des instances comptant jusqu’à plusieurs centaines de noeuds.Un autre intérêt d’une telle réductions provient des connaissances théoriques accumuléessur le TSP. Ainsi, il est connu que sur des graphes respectant l’inégalité triangulaire, leTSP est 3

2-approximable, ce qui signifie qu’il existe un algorithme (décrit par Christofides

[7] et en O(n3)) capable de générer une solution inférieure à 32

fois la solution optimal.Ce résultat est naturellement valable pour le graph-TSP. Nous montrons ci-après que lors-qu’il n’y a qu’un agent, la stratégie de patrouille optimale pour le critère MaxMaxIdlconsiste à parcourir le cycle correspondant à la solution au graph-TSP sur G.

Mentionnons par ailleurs qu’une variante du TSP, connue sous le nom de “minimumlatency TSP” [4], s’occupe de minimiser le temps moyen d’attente de chaque noeud. Ilsemble donc que cette variante, qui pose des problèmes très différents des TSP classiques,s’approche du problème mono-agent de la patrouille avec le critère AvgAvgIdl. Nousnous focaliserons dans la suite sur le critère MaxMaxIdl, du fait qu’il constitue uneborne supérieure aux autres critères, et qu’il permet d’établir un lien fort avec les TSP.Ce lien peut être formalisé par le théorème 1. Pour montrer ce théorème, nous auronsbesoin du lemme suivant, qui relie dans le cas monoagent le poids d’un cycle parcourutpar l’agent et la valeur de la MaxMaxIdl.

Lemme 1 Soit G = (V, E), un graphe. Soit s1 . . . sm, un cycle sur G. Si ∪mi=1si = V

et s’il existe un sommet x ∈ V présent une seule fois dans le cycle, alors la stratégieπ consistant à faire parcourir ce cycle indéfiniment par un unique agent sera telle queMaxMaxIdlπ(G) = c(s1...sm).

Preuve. (lemme 1). Pour tout sommet y ∈ V , le temps nécessaire pour partir de y et yrevenir au plus égal à c(s1, s2) + c(s2, s3) + . . . + c(sm−1, sm) = c(s1...sm). Quant ausommet x par lequel le cycle ne passe qu’une seule fois, le temps nécessaire à l’agent

1logiciel disponible à l’adresse www.math.princeton.edu/tsp/concorde.html

6


pour partir de x et y revenir est exactement de c(s1...sm). Donc, MaxMaxIdlπ(G) =c(s1...sm). �

Trivialement, pour tout graphe connexe, un cycle ayant les propriétés requises parce lemme existe toujours. En particulier le cycle induit par le graph-TSP ainsi que lecycle obtenu par l’algorithme de Christofides [7] qui approxime le graph-TSP vérifientces propriétés.

Théorème 1 Soit G, un graphe et sopt le cycle qui est une solution optimale au problèmedu graph-TSP sur G. La stratégie consistant pour un seul agent à parcourir indéfinimentce cycle est la stratégie mono-agent optimale au sens du critère MaxMaxIdl.

Preuve. Soit π, une stratégie monoagent quelconque, dont la MaxMaxIdlπ(G) est bor-née2, ce qui implique que chaque noeud de G est visité infiniment souvent. Par définition,il existe un noeud x et un réel tx > 0 tels que Idltx(x) = Idltx+MaxMaxIdlπ(G)(x) = 0et que durant l’interval de temps ]tx, tx + MaxMaxIdlπ(G)[, un ensemble de noeudsVx ⊆ V \{x} soient visités. Montrons par l’absurde que Vx = V \{x}, c’est à dire quetous les noeuds hormi x sont visités durant cet intervalle de temps.

Supposons que Vx ⊂ V \{x}. Forcément, il y aura un noeud z /∈ Vx qui aura été visitéà tz < tx puis3 à t′z > tx+MaxMaxIdlπ(G) et non visité durant ]tx, tx + MaxMaxIdlπ(G)[.Par conséquent, l’oisiveté maximale sur le noeud z sera supérieure à MaxMaxIdlπ(G),ce qui est une contradiction. On a donc par l’absurde Vx = V \{x}.

Nous venons donc de montrer que pour toute stratégie π, il existe un instant tx à partirduquel l’agent positionné sur un noeud x visitera l’ensemble des autres noeuds avant derevenir sur x, et que la durée de cette exploration sera égale à MaxMaxIdlπ(G). Cela re-vient donc à dire que dans toute stratégie π, il existe un cycle (correspondant à l’ensembledes noeuds visités durant[tx, tx + MaxMaxIdlπ(G)]) incluant tous les sommets de G, etdont le poids est égal à MaxMaxIdlπ(G).

Donc, pour toute stratégie monoagent π dont la MaxMaxIdl est bornée, il existe unestratégie π′ consistant à parcourir indéfiniment un cycle s et tel que MaxMaxIdlπ =MaxMaxIdlπ′ = c(s).

Dès lors, une stratégie optimale πopt consistera à parcourir indéfiniment le plus petitcycle incluant tous les sommets du graphe, ce qui correspond exactement à la définitiondu graph-TSP. De plus, par l’application du lemme 1,MaxMaxIdlπopt(G) sera égal aupoids du cycle induit par le graph-TSP. �

2trivialement, une telle stratégie existe toujours3Un noeud est visité lorsqu’un agent sur trouve dessus. Néanmoins, du fait que pour tout noeud i on ait

Idl0(i) = 0, on considère qu’à l’instant zéro, l’ensemble des noeuds sont visités simultanément.

7


4 Quatres classes de stratégies multi-agents pour le pro-blème de la patrouille

Nous avons vu dans la section précédente comment utiliser un algorithme de TSPpour résoudre le problème mono-agent de la patrouille. Comment étendre ce résultat aucas multi-agent ? Notons tout d’abord qu’il existe un grand nombre de variantes du pro-blème du voyageur qui puissent être considérés comme multi-agents. Les plus connusd’entre eux sont les Vehicule Routing Problem (VRP) [10] et le multiple-salesman trave-ling problem (m-TSP) [6]. Ces deux problèmes supposent l’existence d’un “dépot” danslequel les agents doivent revenir après leurs visites, ce qui permet dans certains cas deréduire le problème à un simple TSP [6], mais les rend difficilement utilisables pour notreétude. Un autre problème plus récent, nommé “multi-agent TSP” a récemment été intro-duit dans [17, 16], et traité par des méthodes génétiques dans [14]4. Ce problème est trèsproche du notre, mais il n’existe pas à notre connaissance résultat théorique importantle concernant, ni d’algorithme ayant fait ses preuves sur des graphes importants. Afind’établir des résultats formels sur notre problème, nous introduisons dans cette sectiondes biais importants sur les stratégies envisagées. Plus précisemment, nous définissonsd’abord deux classes de stratégies principales (illustrées par la figure 3), dite “stratégies àcycle unique” et “stratégies régionalisées”, ainsi que quelques résultats préliminaires surces classes. Ces deux classes ont un grand intéret en elles-mêmes, car elles formalisentdes stratégies simples et intuitives. Nous définissons aussi deux autres classes moins inté-ressantes en elles-mêmes mais qui nous serviront pour démontrer par la suite des résultatsd’approximation. En particulier, la dernière stratégie dite “mixte”, permettra d’améliorerles résultats obtenus avec des stratégies à cycle unique.

Définition 6 Soit P , un partitionnement de G en {P1, ..., Pq} régions connexes (avecq ≤ r). Dans la suite de ce papier, on désignera par Gi(Pi, E ∩ P 2

i ) les sous-graphesde G induits par les noeuds de la région i. Toute stratégie multi-agents de parcours deG pour laquelle chaque agent i ne visite les noeuds que d’une région Pj sera appeléestratégie multi-agents régionnalisée selon P . On notera ΠP1...Pq , la classe de toutes lesstratégies régionalisées selon P1...Pq, et Π<P1,r1>...<Pq,rq> la classe des stratégies multi-agents régionnalisées selon P1...Pq, dans lesquelles chaque région Pi est patrouillée parexactement ri agents, avec bien sur r =

∑qi=1 ri. On notera aussi Πq−Regions la classe

des stratégies régionalisées selon un partitionnement en q régions. Enfin, si le nombred’agents est égal au nombre de régions (r = q), on dit que la stratégie est individuelle-ment régionalisée.

4Les auteurs de l’article cité confondent multi-agent TSP et m-TSP : ils traitent le premier et non ledernier.

8


Ainsi, avec les stratégies individuellement régionalisées, chaque noeud n’est visité quepar un seul agent (cf fig. 3). Le lemme suivant nous indique ce qu’est une bonne stratégieindividuellement régionalisée.

Lemme 2 Soit G(V, E), un graphe connexe métrique, et P = {P1, . . . , Pr} un partition-nement de ce graphe en r régions chacune connexe. Soit ΠgTSP

P , la stratégie individuel-lement régionalisée consistant à faire parcourir à chaque agent i le cycle induit par legraph-TSP du sous-graphe Gi. Alors, ΠgTSP

P est la stratégie individuellement régionali-sée selon P qui soit optimale au sens du critère MaxMaxIdl.

Preuve. (lemme 2). Par définition, pour toute stratégie individuellement régionnaliséeΠP = {π1, . . . , πr}, on a MaxMaxIdlΠP

(G) = maxi{MaxMaxIdlπi(Gi)}. Il s’en-

suit que si la stratégie ΠP est composée des stratégies mono-agent πopt1 , ...πopt

r chacuneoptimale sur G1...Gr, alors, ΠP est optimale au sens du critère MaxMaxIdl. D’après lethéorème 1, le cycle induit par le graph-TSP est la stratégie mono-agent optimale, et doncparmi toutes les stratégies de ΠP , celle formée des cycles induits par les graph-TSP surles sous-graphes Gi est optimale. �

Introduisons maintenant une nouvelle classe de stratégies, qui nous permettra d’établirun pont avec les TSP, sans avoir à recourir à un partitionnement.

Définition 7 Soit s0...sm, un cycle (pas nécessairement élémentaire) visitant tous lesnoeuds de G. Une stratégie multi-agents Π = {π1...πr} est dite à cycle unique s0...sm ssiil existe d1...dr ∈ N tels que πi(k) = s(k+di) mod m. On notera ΠCycle la classe de toutesles stratégies à cycle unique.

Intuitivement, une stratégie est à cycle unique si tous les agents parcourent le même cycledans le même sens, mais avec un certain décalage (cf fig. 3). Grâce au lemme suivant, nousmontrons qu’à un terme près, r agents parcourant un cycle aboutiront à une MaxMaxIdlr fois plus petite qu’un seul agent parcourant ce même cycle, à la condition que les agentssoient espacés de manière régulière sur le cycle.

Lemme 3 Soit s0...sm, un cycle passant par tous les sommets de G et tel qu’il existe aumoins un sommet x ∈ V par lequel le cycle ne passe qu’une fois. Il existe alors une stra-tégie Π = {π1...πr} à cycle unique s0...sm telle que MaxMaxIdlπ1 (G)

r− max{cij | (i, j) ∈

ES} ≤ MaxMaxIdlΠ(G) ≤ MaxMaxIdlπ1 (G)

r+max{cij | (i, j) ∈ ES}. Ici, ES représente

l’ensemble des arêtes du cycle s0...sm. Ce résultat peut aussi s’écrire c(s0...sm)r

−max{cij |(i, j) ∈ ES} ≤ MaxMaxIdlΠ(G) ≤ c(s0...sm)

r+ max{cij | (i, j) ∈ ES}.

9


12

3

4

6

5

12

3

4

6

5

FIG. 3 – Exemples de stratégies à cycle unique Πcyc = {πcyc1, πcyc2} (à gauche) et destratégies régionalisées ΠReg = {πreg1, πreg2} (à droite) avec deux agents. On a doncπcyc1 = 1, 2, 3, 4, 5, 6, 1, 2, 3 . . . et πcyc2 = 4, 5, 6, 1, 2, 3, 4, 5, 6, 1 . . .. Quand à la stratégierégionalisée, on a πreg1 = 1, 2, 3, 2, 1, 2, . . . et πreg2 = 4, 5, 6, 5, 4, 5, . . .. Par conséquent,MaxMaxIdlΠcyc(G) = 3 et MaxMaxIdlΠreg (G) = 4. Ici, la stratégie à cycle uniqueest donc meilleure que la stratégie régionnalisée, mais c’est parfois l’inverse.

Preuve. Soit s0...sm, le cycle pas nécessairement élémentaire sur G. Considérons deuxagents parcourant ce cycle et dont les positions à l’instant 0 soient respectivement lesnoeud s0 et sd. Soit l(i, j) =

∑j−1k=i csksk+1

. La valeur l(0, d) est donc le temps nécessaireau premier agent pour rejoindre le noeud sd en partant de s0. Quelle que soit le noeudvisité par l’agent 2 à l’instant t, ce noeud sera au moins visité par l’agent 1 à l’instantt+l(0, d). Par conséquent, nous aurons MaxMaxIdl{π1,π2}(G) ≤ max{l(0, d), l(d, m)}.Par ailleurs, si à l’instant tx, l’agent 2 se trouve sur le noeud x, alors du fait que x n’appa-raît qu’une seule fois dans le cycle et par application du lemme 1, on sait que la prochainevisite de l’agent 2 à ce noeud x surviendra à l’instant tx + l(0, m). Par conséquent, aprèsavoir été visité à l’instance tx, le noeud x ne sera pas visité avant l’instant tx + l(0, d).Donc, MaxMaxIdl{π1 ,π2}(G) = max{l(0, d), l(d, m)}.

Si l’on généralise à r agents, on obtient MaxMaxIdlΠ(G) = max{l(0, d1),l(d1, d2), . . . , l(dr−1, m)}. En choisissant chaque dk afin qu’il soit le plus grand entiervérifiant l(0, dk) ≤ k × l(0,m)

r, on a en particulier d0 = 0 et dr = m, ce qui nous

permet d’écrire MaxMaxIdlΠ(G) = maxk=0..r−1 l(dk, dk+1). Il nous reste à bornerl(dk, dk+1) = l(0, dk+1) − l(0, dk) de la façon suivante :

k × l(0,m)r

− max{cij | (i, j) ∈ ES} ≤ l(0, dk) ≤ k × l(0,m)r

(k + 1) × l(0,m)r

− max{cij | (i, j) ∈ ES} ≤ l(0, dk+1) ≤ (k + 1) × l(0,m)r

En réunissant ces deux équations, on obtient :

10


FIG. 4 – Noeuds d’un cycle s0...sm sur une échelle représentant la distance qu’un agentdoit parcourir pour les visiter.

l(0, m)

r− max{cij | (i, j) ∈ ES} ≤ l(dk, dk+1) ≤ l(0, m)

r+ max{cij | (i, j) ∈ ES}

Le graphique 4 illustre cette situation. Soit Π = {π1 . . . πr}, la stratégie à cycle uniques0...sm suivie par r agents et telle que chaque agent i soit positionné à l’instant t = 0sur le noeud sdi

. Du fait que l(0, m) soit le temps nécessaire à un agent pour parcou-rir le cycle entier, on a pour tout agent i, MaxMaxIdlπi

(G) = l(0, m). Du fait queMaxMaxIdlΠ(G) = maxk=0..m−1 l(dk, dk+1), on aura donc le résultat du lemme.

�

Remarquons que le terme max{cij | (i, j) ∈ ES} présent dans la borne du critèreMaxMaxIdl exposée dans le lemme 3 provient du fait qu’à l’instant 0, chaque agent estobligatoirement positionné sur l’un des noeuds de graphe. Si l’on permettait aux agentsd’etre positionnés à mi-chemin sur les arêtes du graphes au temps 0, alors on aurait natu-rellement MaxMaxIdlΠ(G) =

MaxMaxIdlπ1 (G)

r.

Pour finir, nous définissons deux autres classes de stratégies : tout d’abord, la classedes stratégies d’aller-retour, qui sera utilisées dans les démonstrations de la section sui-vante pour obtenir des résultats d’approximation généraux. Ensuite, la classe des straté-gies mixtes, qui combine les aspects des stratégies à cycle unique et régionalisées.

Définition 8 Une stratégie monoagent π est dite stratégie d’aller-retour selon un chemins1 . . . sm ssi elle consiste à parcourir ce chemin d’avant en arrière. Concrètement, π =s1, s2,..., sm−1, sm, sm−1, ..., s2, s1, s2, .... Dès lors, MaxMaxIdlπ ≤ 2c(s1...sm). Unestratégie multiagents est dite d’aller-retour si elle est composée de stratégies mono-agentsd’aller-retour et que tous les noeuds de G sont visités. La classe correspondante seranotée ΠAR.

11


Lemme 4 Pour toute stratégie multiagents Π, il existe une stratégie Π ′ = {π′1...π

′r} ∈

ΠAR telle que MaxMaxIdlΠ′(G) ≤ 2 maxi c(si0 . . . si

mi) ≤ 2 × MaxMaxIdlΠ(G). Ici,

si0...s

imi

désigne le chemin associé à la stratégie monoagent π ′i.

Preuve. Soit tΠ = MaxMaxIdlΠ(G). Soit si0 . . . si

mile chemin suivi par l’agent i pendant

l’interval de temps [0, tΠ] avec la stratégie Π. Par définition, ∪{sij}i=1..r,j=0..mi

= V . Deplus, tΠ ≤ maxi c(s

i0, . . . , s

imi

). Soit π′i, la stratégie monoagent d’aller-retour définie sur le

chemin si0...s

imi

. La stratégie multiagents Π′ = {π′1...π

′r} effectue un aller-retour complet

(c’est à dire que les agents reviennent à leur position initiale après avoir visité tous lesnoeuds) en un temps égal à deux fois le poids max des chemins si

0 . . . simi

et donc inférieurou égal à 2tΠ. �

Lemme 5 Pour toute stratégie multiagents d’aller-retour Π = {π1...πr}dans laquellechaque stratégie πi est associée aux chemin si

1 . . . simi

, il existe un cycle S couvrant tous

les noeuds de G tel que c(S)2r

≤ maxi c(si1 . . . si

mi) + max{cij | (i, j) ∈ MST (G)}. Ici,

MST (G) désigne le plus petit arbre couvrant de G.

Preuve. Considérons EΠ = ∪ri=1 ∪mi

j=1 {(sij, s

ij+1)}, l’ensemble des arêtes parcourues par

les agents. Du fait que les chemins parcourus par les agents peuvent être disjoints, le sous-graphe (V, EΠ) n’est pas nécessairement connexe : il est au pire composé de r régionsconnexes distinctes. Or, il est connu que pour tout partionnement d’un graphe connexe Gen q régions connexes distinctes, l’ensemble des q−1 plus petites arêtes reliant ces régionsentres elles appartient au MST (G). Donc, il existe TΠ, un sous-ensemble de moins de rarêtes de MST (G) tel que GΠ(V, EΠ ∪ TΠ) soit connexe. Remarquons que

c(EΠ ∪ TΠ) = c(EΠ) + c(TΠ)

≤ r maxi

c(si1 . . . si

mi) + r max{cij | (i, j) ∈ MST (G)}

Il nous reste à construire un cycle à partir des arêtes de GΠ. Soit T = MST (GΠ).Soit S, le cycle défini comme le parcours de T en profondeur d’abord. On a clairementc(S) ≤ 2c(EΠ ∪ TΠ). �

Définition 9 Soit P , un partitionnement de G en {P1, ..., Pq} régions connexes avec q ≤r. Soient q cycles {si

0 . . . simi} visitant chacun tous les noeuds de Gi. Soient r1...rq ∈ N

∗,tels que

∑qi=1 rq = r. Toute stratégie multi-agents de parcours de G telle que dans chaque

Gi, il y ait ri agents parcourant le sous-graphe en suivant une stratégie à cycle uniquesi0 . . . si

mi, sera appelée stratégie mixte, et nous désignerons la classe correspondante par

Π{(s10...s1

m1,r1),...,(sq

0...sqmq ,rq)}. La classe de toutes les stratégies mixtes sera désignée par

ΠMixte.

Notons que ΠCycle ⊂ ΠMixte ⊂ ΠRegions. Par ailleurs, le lemme 2 nous indique que pourun partitionnement P donné, la stratégie régionnalisée optimale est une stratégie mixte.

12


5 Comparaison entre les stratégies individuellement ré-gionalisées et à cycle unique dans le cas métrique

Dans cette section, nous comparons les deux classes de stratégies présentées précé-demment. Le théorème montre que selon le critère MaxMaxIdl et à 3 maxij{cij} près,il existe une stratégie à cycle unique meilleure que toute stratégie régionnalisée. Dansle cas où le graphe est unitaire (cij ∈ {0, 1}), alors la stratégie à cycle unique devientnettement plus intéressante que la stratégie régionalisée.

Dans la suite de l’exposé optΠ(G), optΠr−Regions(G), optΠP

(G), et optΠCycle(G) dési-

gneront les valeur optimale du critère MaxMaxIdl(G) respectivement sur les classes detoutes les stratégies multiagents, des stratégies régionalisées, des stratégies individuelle-ment régionalisées selon P , et des stratégies à cycle unique. Lorsqu’il n’y a pas d’ambi-guité, on omettra de mentionner G.

Le lemme suivant, qui montre comment construire un cycle à partir de stratégies indi-viduellement régionalisées, est un préliminaire au théorème principal.

Lemme 6 Soit G = (V, E), un graphe connexe métrique sur lequel doivent patrouillerr agents. Soit P = {P1, ..., Pr}, un partitionnement de ce graphe en r régions chacuneconnexe. Soit, sur chacune de ces régions Pi, un cycle si = si

1 . . . simi

couvrant l’ensembledes noeuds de Pi et ne passant jamais deux fois dans le même sens par la meme arête5.On peut alors en combinant ces cycles créer un cycle unique S vérifiant :

c(S) ≤r∑

i=1

c(si) + r × maxij{cij}

Preuve. Soit Eintra = {(i, j) ∈ E | ∃x ∈ 1..r, i ∈ Px, j ∈ Px} et soit Einter = {(i, j) ∈E | ∃x, y ∈ 1..r, x = y, i ∈ Px, j ∈ Py}. Soit Einter un plus petit sous-ensemble deEinter, tel que le graphe (V, Eintra∪ Einter) soit connexe. Autrement dit, Einter représenteun arbre reliant les régions entre elles (voir figure 5).

Soit E↑i = ∪mi−1

j=1 (sij, s

ij+1), l’ensemble des arcs (orienté) intervenant dans le cycle si.

Du fait que chaque arc (orienté) n’est présent qu’une fois dans si, le digraphe (grapheorienté) G↑

i (Pi, E↑i ) a la propriété d’etre eulérien, c’est à dire qu’il possède un cycle vi-

sitant tout ses noeuds et passant une seule fois par chaque arete. De plus, c(E ↑i ) = c(si).

Soit E↑inter, l’ensemble des arcs (orientés) obtenu en doublant chaque arete de Einter.

Rappelons qu’un digraphe est eulérien ssi il est connexe et que pour chacun de sesnoeuds, le nombre d’arcs entrants est égal au nombre d’arcs sortants. Par construction,

5Clairement, un tel cycle existe toujours.

13


Procédure visiter(x, i, DejaV isitees)

1. Soit si1...s

imi

, un cycle sur Gi parcourant tous les noeuds de Gi, et ajusté tel quesi1 = si

mi= x.

2. DejaV isitees ← DejaV isitees ∪ {i}3. Pour k = 1 . . .mi − 1 faire

4. Pour toute arête (sik, y) ∈ Einter telle que la région j de y n’appartienne pas à

DejaV isitees faire

5. renvoyer (sik, y)

6. visiter(y, j, DejaV isitees)

7. renvoyer (y, sik)

8. fin pour

9. renvoyer (sik, s

ik+1)

10. fin pour

E↑inter ne vérifie que la deuxième condition, et il lui manque la connexité pour etre eulé-

rien. Par définition, aucun des digraphes G↑1, . . . , G

↑r, E

↑inter n’a d’arc en commun. Donc,

le digraphe G↑(V,∪ri=1E

↑i ∪ E↑

inter) est connexe, et sur chacun de ses noeuds, le nombred’arcs entrants et sortant est égal. Il est donc eulérien. Il existe donc un cycle S parcou-rant l’ensemble des noeuds de V et une seule fois chaque arc de ∪r

i=1E↑i ∪ E↑

inter. Celui civérifie :

c(S) = c(E↑inter) +

∑ri=1 c(E↑

i ) = c(E↑inter) +

∑ri=1 c(si). Du fait que Einter décrit

un arbre reliant les r régions, il n’a que r − 1 aretes, et donc c(E↑inter) = 2 × c(Einter) <

2r × maxi,j{cij | (i, j) ∈ E}. �

Remarquons que le lemme 6 nous montre l’existence d’un cycle S ayant des propriétésintéressantes, sans nous indiquer comment construire ce cycle. Une solution consisteraità extraire du digraphe G↑ un cycle eulérien, par exemple avec l’algorithme de Fleury.Nous proposons un algorithme ad-hoc permettant de construire S : étant donné x, unnoeud quelconque de V et Pi, la région à laquelle x appartient, l’appel à la procédurevisiter(x, i, { }) renverra une suite d’arcs constituant ce cycle S. La figure 5 illustre letype de cycle obtenu par cet algorithme, et la figure 6 montre un exemple de cycle obtenupar l’algorithme.

Théorème 2 Soit G(V, E), un graphe connexe métrique sur lequel doivent patrouiller ragents. on a : optΠCycle

≤ optΠr−Regions+ 3 × maxij{cij}.

Preuve. (Théorème 2). La première étape de cette preuve consiste à montrer que le cycle

14


FIG. 5 – Création par l’algorithme visiter du cycle destiné à parcourir le graphe. A gauche,un graphe partitionné en régions (cercles en pointillés). A droite, le même graphe (sans ledétail des noeuds) dont des arêtes de Einter ont été retirées pour obtenir un arbre reliantles régions entres elles. Les flêches symbolisent le cycle de parcours du graphe, obtenu encombinant les cycles sur chaque région.

induit par le graph-TSP ne passe pas deux fois par la meme arete dans le meme sens, ceciafin de pouvoir utiliser le lemme 6.

Considérons le cycle S = x1, x2, . . . , xi, a, b, xi+1, . . . , xj , a, b, xj+1, . . . , xm qui passedeux fois par (a, b) et dans le meme sens. Ce cycle ne peut pas etre la solution d’un graph-TSP puisque l’on peut construire un cycle S ′ = x1, x2, . . . , xi, a, xj , . . . xi+1, b, xj+1, . . . , xm

qui visite les memes noeuds et dont le poids est inférieur : c(S ′) = c(S)− 2× ca,b. Donc,le cycle induit par le graph-TSP ne passe pas deux fois dans le meme sens sur une memearete.

Soit {P1...Pr}, une partition sur G, et G1..Gr, les sous-graphes associés. NommonsgTSP (Gi) le cycle correspondant au graph-TSP sur Gi. Le lemme 2 nous indique quepour tout partitionnement P , on a optΠP

= maxi∈1..r{c(gTSP (Gi))}. Grâce au lemme 6on sait qu’il existe un cycle visitant tous les noeuds de V et vérifiant :

c(S) ≤r∑

i=1

c(gTSP (Gi)) + 2r × maxij{cij}

≤ r × maxi∈1..r{c(gTSP (Gi))} + 2r × maxij{cij}≤ r × optΠP

+ 2r × maxij{cij} (1)

Utilisons le lemme 3 pour montrer qu’une stratégie à cycle unique Πs construit à partirdu cycle S permet d’obtenir les propriétés suivantes :

15


MaxMaxIdlΠs(G) ≤ c(S)

r+ maxij{cij}

≤ optΠP+ 3 × maxij{cij}

Donc, pour toute partition {P1...Pr}, il existe toujours une stratégie à cycle uniquemeilleure que la meilleure stratégie régionalisée sur P1...Pr, à 3. max{cij} près. �

Corollaire 1 Soit G = (V, E), un graphe connexe métrique sur lequel doivent patrouillerr agents. Soit P = {P1, ..., Pr}, un partitionnement de ce graphe en r régions connexes.On peut calculer en temps O(n3) une stratégie multi-agents à cycle unique ΠChr ∈ ΠCycle

telle qu’on ait MaxMaxIdlΠS≤ 3

2optΠP

+ 4 × maxij{cij}.

Preuve. (Corrolaire 1) Soit SChr, le cycle obtenu en utilisant l’algorithme de Christofides[7] sur G. On sait que c(SChr) ≤ 3

2c(SgTSP ), avec SgTSP désignant le cycle induit par le

graph-TSP sur G. En utilisant l’équation 1, on obtient :

c(SChr) ≤ 3

2c(SgTSP ) ≤ 3r

2× optΠP

+ 3r × maxij{cij}

Avec le lemme 3, on peut donc conclure que la stratégie multiagents à cycle uniqueΠSChr

selon SChr vérifie :

MaxMaxIdlΠsChr(G) ≤ c(SChr)

r+ maxij{cij}

≤ 3

2optΠP

+ 4 × maxij{cij}

�

6 Approximations à partir de stratégies à cycle unique

Dans cette section, nous allons d’abord présenter un premier résultat d’approxima-tion utilisant une stratégie à cycle unique obtenue par un algorithme de graph-TSP. Cerésultat comporte le terme 4.maxij{cij}. Dès lors, si le graphe comporte quelques arêtesde très grand poids, la MaxMaxIdl obtenue par la stratégie à cycle unique sera d’au-tant plus grande. Pour finir, nous obtiendrons un résultat d’approximation indépendant demaxij{cij}, grâce à l’utilisation de la classe des stratégies mixtes.

16


Théorème 3 Soit G = (V, E), un graphe connexe métrique et r, un nombre quelconqued’agents. En O(n3), on peut trouver une stratégie ΠChr ∈ ΠCycle telle que MaxMaxIdlΠChr

≤3×optΠ+4×maxij{cij}. De plus, en O(n log n), on trouve une stratégie ΠMST ∈ ΠCycle

telle que MaxMaxIdlΠMST≤ 4× optΠ + 4×maxij{cij | (i, j) ∈ MST (G)} et que les

agents n’empruntent que les arêtes du plus petit arbre couvrant de G.

Preuve. A l’aide du lemme 4, on sait qu’il existe une stratégie Π = {π1...πr} ∈ ΠAR

dans laquelle chaque stratégie monoagent πi est associée à un chemin si0 . . . si

mi, tel

que maxi{c(si0 . . . si

mi)} ≤ optΠ. De plus, pour toute stratégie Π ∈ ΠAR, le lemme 5

nous informe qu’il existe un cycle S parcourant tous les noeuds de G et tel que c(S)2r

≤maxi{c(si

0 . . . simi

)}+ maxij{cij | (i, j) ∈ MST (G)}. Avec l’algorithme de Christofides[7], on peut obtenir en O(n3) un cycle SChr passant par tous les noeuds et de poids infé-rieur à 3

2du poids minimal. De même, avec l’algorithme du plus petit arbre couvrant, on

obtient en O(n log n) un cycle SMST correspondant à l’exploration en profondeur d’abordde cet arbre, et de poids inférieur à 2 du poids minimal. Dès lors :

c(SChr) ≤ 3

2c(S)

≤ 3r. maxi

{c(si0 . . . ci

mi)} + 3r max

ij{cij | (i, j) ∈ MST (G)}

≤ 3r.optΠ + 3r maxij

{cij | (i, j) ∈ MST (G)}c(SMST ) ≤ 2c(S) ≤ 4r.optΠ + 4r max

ij{cij | (i, j) ∈ MST (G)}

L’application du lemme 3 nous permet de créer à partir du cycle obtenu par l’algo-rithme de Christofides une stratégie à cycle unique ΠChr telle que MaxMaxIdlΠChr

(G) ≤c(SChr)

r+ maxij{cij} ≤ 3.optΠ + 4. maxij{cij}. De même, MaxMaxIdlΠMST

(G) ≤c(SMST )

r+ maxij{cij | (i, j) ∈ MST (G)} ≤ 4.optΠ + 4. maxij{cij | (i, j) ∈ MST (G)}.

�

7 Approximations à partir de stratégies mixtes

Dans cette section, nous utiliserons les stratégies mixtes pour obtenir un résultat d’ap-proximation qui ne dépende pas de maxij{cij}. Rappelons qu’une stratégie mixte se com-pose de partitions dans lesquels un ou plusieurs agents se déplacent en parcourant descycles. Notons que la partition triviale formée d’une seule région ne permet pas d’obtenirun résultat d’approximation ainsi que le suggère le résultat de la section précédente, etque déterminer une partition en r régions “équilibrées” est un problème difficile. Notre

17


1

2

34

5

6

7

8

9

1011

R1

R2

R3

1

2

34

5

6

7

8

9

1011

R1

R2

R3

FIG. 6 – Graphe partitionné en 3 régions. Seuls les arêtes issues du graph-TSP de chaquerégion ainsi que les arêtes de Einter sont visibles. Si l’on fourni à l’algorithm visiter lescycles issus du graph-TSP et les arêtes de Einter, alors l’appel à visiter(1, 1, { }) renverra :(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 11), (11, 10), (10, 11), (11, 7), (7, 8), (8, 9),(9, 4), (4, 3), (3, 1).

approche consistera à définir un critère sur les partitions, dont nous montrerons qu’il suffitpour établir un résultat d’approximation.

Tout d’abord, nous définirons la notions de partition α − propre, et montrerons com-ment on peut construire de telles paritions. Par la suite, nous montrerons que pour toutepartition optΠ − propre, il existe une stratégie mixte qui permette d’obtenir le résultatd’approximation voulu. Bien entendu, nous ignorons la valeur de optΠ. Néanmoins, lelemme 7 et 8 nous montrent comment construire un ensemble d’au plus r partitions parmilesquelles se trouve nécessairement une partition optΠ − propre. Le théorème principalde cette section montre que le problème est 15-approximable. Avant d’en débuter la dé-monstration qui se trouve à la fin de cette section, il nous faut introduire la notion departition α − propre et en obtenir quelques propriétés.

Définition 10 Soit G(V, E), un graphe connexe. Une partition {P1 . . . Pq} de G est diteα − propre ssi :

– Pour chaque sous-graphe Gi, l’arbre couvrant minimal MST (Gi) ne possède pasd’arete de poids supérieur à α.

– Toute arete de G reliant deux régions est toujours de poids strictement supérieur àα.

Remarquons que si l’on choisit α < minij{cij}, la seule partition α − propre est{{1}, {2}, . . . , {n}}. D’autre part, si α ≥ maxij{cij}, seul {V } est α−propre. Le lemmesuivant généralise la construction de partitions pour α quelconque.

18


Lemme 7 Soit G(V, E) un graphe connexe et tel que ∀(i, j) ∈ E, cij > 0. Il existe uneclasse ℘ = {℘0...℘n−1} de partitions de G, telle que chaque partition ℘k comporte krégions et peut etre calculée en O(n log n), et que ∀α ≥ 0, ∃℘k ∈ ℘, ℘k est α − propre.

Preuve. On désigne par MST (G) l’ensemble des aretes du plus petit arbre couvrant de G,et on peut le calculer en O(n logn). Soit a1...an−1, les aretes de MST (G) triées par ordrede poids décroissant. Soit T k

G = MST (G)\{a1, ...ak}. Clairement, le graphe Gk(V, T kG)

possède k composantes connexes. On défini donc ℘k comme étant la partition dont chaquerégion correspond à une composante connexe de Gk. Montrons que pour α ∈ [

cak+1, cak

[,

℘k est α − propre.

D’abord, T kG a été obtenu en éliminant de l’arbre couvrant minimal de G les aretes

de poids supérieur ou égal à cak, ce qui a pour effet de créer des composantes connexes

distantes entres elles d’au moins cak. Autrement dit, toute arete de G reliant deux régions

de ℘k est de poids supérieur ou égal à cak. Ensuite il est clair que le MST de chaque

composante connexe de T kG est inclus dans MST (G), et donc dans T k

G. Cela impliquequ’aucune arete de poids supérieur à cak+1

n’appartient au MST des partitions de ℘k.Cela montre bien que pour α ∈ [

cak+1, cak

[, ℘k est α − propre. Par ailleurs, ℘0 est la

partition comportant une seule région, et est donc α − propre pour α ∈ [0, can−1

[, et

℘n−1 qui est la partition formée de n régions (1 noeud par région) est α − propre pourα ∈ [ca1 ,∞[. Finalement, pour toute valeur de α ≥ 0, il existe une partition de ℘ qui soitα − propre. �

Lemme 8 Soit G(V, E), un graphe et r agents patrouillant ce graphe. Toute partition{P1 . . . Pq} qui soit (optΠ) − propre vérifie q ≤ r.

Preuve. Preuve par l’absurde : supposons qu’on ait une partition {P1 . . . Pq} formée deq > r régions et qui soit (optΠ)−propre. Du fait que le nombre de régions est supérieur aunombre d’agents, à l’instant zéro, il y aura au moins une région inocuppée (“pigeon holeprinciple”). Quelque soit la stratégie multiagents Π suivie, pour atteindre cette région,tout agent mettra un temps supérieur à optΠ(puisque tout arete reliant deux régions a unpoids supérieur à optΠ), ce qui implique que ∀Π, MaxMaxIdlΠ(G) > optΠ, ce qui estune impossibilité. �

Lemme 9 Soit G(V, E), un graphe et r agents patrouillant ce graphe. Pour toute parti-tion {P1 . . . Pq} de G qui soit optΠ − propre, il existe une distribution r1...rq des agentssur les différentes régions et une stratégie Π′ ∈ Π<P1,r1>..<Pq,rq> telle que MaxMaxIdlΠ′(G) ≤2 × optΠ. Il s’ensuit que optΠ<P1,r1>..<Pq,rq>

≤ 2 × optΠ.

Preuve. Soit Πopt, une stratégie multiagents optimale, et soit si1...s

imi

, les noeuds par-courus par l’agent i jusqu’au temps t = optΠ selon la stratégie Πopt. Par définition,

19


V = ∪i=1..r ∪j=1..mi{si

j}. D’après le lemme 4, la stratégie multiagents Π′ obtenue enparcourant ces chemins d’avant en arrière vérifie MaxMaxIdlΠ′(G) ≤ 2.optΠ. De plus,du fait que ∀i ∈ 1..r, c(si

1...simi

) ≤ optΠ, toutes les arêtes figurant dans les cheminssi1...s

imi

sont de poids inférieur ou égal à optΠ. Donc, en suivant la stratégie Π′, les agentsn’emprunteront que des arêtes de poids inférieur ou égal à optΠ. Or, toute arête reliantdeux régions Pi et Pj a un poids nécessairement supérieur à optΠ. Par conséquent, lors-qu’ils suivent la stratégie Π′, les agents ne changent jamais de région. Π′ est donc unestratégie régionalisée en plus d’etre une stratégie d’aller-retours. �

Lemme 10 Soit G(V, E), un graphe et r agents patrouillant ce graphe. Soit {P1 . . . Pq},une partition de G qui soit optΠ − propre. Soit Si

MST , le cycle obtenu en parcourant enprofondeur d’abord l’arbre couvrant minimal du iieme sous-graphe Gi(V, E∩P 2

i ). Alors,

il existe une répartition r∗1...r

∗q ∈ 1..r des r agents telle que la stratégie mixte Π

r∗1 ...r∗qMST

consistant à faire parcourir chaque cycle S iMST par r∗i agents vérifie MaxMaxIdl

Πr∗1 ...r∗qMST

(G) ≤12.optΠ(G).

Preuve. Soit une stratégie à cycle unique Πri

MST (Gi)sur la région Pi faisant suivre le cycle

SiMST par ri agents. D’après le théorème 3, on a alors, pour tout répartition r1...rq des

agents sur les différentes régions :

MaxMaxIdlΠriMST (Gi )

(Gi) ≤ 4optΠri (Gi) + 4. max{cij | (i, j) ∈ MST (Gi)}≤ 4optΠri (Gi) + 4.optΠr(G)

Notons que le passage de max{cij | (i, j) ∈ MST (Gi)} à optΠ provient du fait quela partition est optΠ − propre, et donc qu’aucune arête du MST (Gi) n’excède en poidsla valeur de optΠ.

Selon le lemme 9, il existe une répartition r∗1...r

∗q des agents sur les différentes régions

telle que optΠ<P1,r∗1

>..<Pq,r∗q >≤ 2 × optΠ. On a donc

∀i, optΠr∗

i(Gi) ≤ optΠ<P1,r∗

1>..<Pq,r∗q >

(G) ≤ 2 × optΠ(G)

Par conséquent, pour tout i, on a

MaxMaxIdlΠ

r∗i

MST (Gi)

(Gi) ≤ 8 × optΠ(G) + 4 × optΠ(G)

ce qui implique que MaxMaxIdlΠ

r∗1 ...r∗qMST

(G) ≤ 12 × optΠ. �

20


Remarquons que le lemme ci-dessus utilise les cycles induits par l’arbre couvrantminimal, au lieu d’utiliser les cycles obtenus par l’algorithme de Christofides. Si nousavions opté pour ce dernier choix, nous n’aurions pas été certain que les cycles obtenus nepassaient pas par des arêtes de poids supérieur à optΠ, ce qui aurait rendu la démonstrationimpossible. Notons que si nous avions autorisé aux agents d’être positionnés à l’instantzéro entre deux noeuds, alors nous aurions put utiliser l’algorithme de Christofides, enobtenant les mêmes bornes que ci-dessus.

Le lemme ci-dessus ne nous indique pas comment calculer la répartition des agentsdans chaque région : il nous dit juste qu’il existe une répartition telle qu’en parcourant lesMST des différentes régions, on obtiendra une valeur du critère MaxMaxIdl inférieure à 12fois l’optimale. Le lemme suivant nous montre qu’il est possible de calculer la répartitionr1...rq proche de la répartition optimale.

Lemme 11 Soit G, un graphe parcouru par r agents, et {P1 . . . Pq}, une partition de Gqui soit optΠ − propre. Soit Si

MST , le cycle obtenu en parcourant en profondeur d’abordl’arbre couvrant minimal du iieme sous-graphe Gi = (V ∩ Pi, E ∩ P 2

i ). On peut calcu-ler une répartition r1...rq des agents dans les régions telle que la stratégie mixte Π

br1...brq

MST

consistant à faire parcourir chaque cycle S iMST par ri agents vérifie MaxMaxIdl(G)

Πbr1...brqMST

≤14 × optΠ.

Preuve. Soit r1...rq, la répartition d’agents qui minimise maxi(c(Si

MST )

bri). En appliquant le

lemme 3, et en substituant optΠ à maxij{cij | (i, j) ∈ MST (Gi)}, on obtient :

maxi

(c(Si

MST )

ri) − optΠ ≤ MaxMaxIdl

Πbr1 ...brqMST

(G) ≤ maxi

(c(Si

MST )

ri) + optΠ (2)

On peut appliquer le meme lemme concernant une répartition r1...rq quelconque d’agents

pour obtenir MaxMaxIdlΠr1...rqMST

(G) ≥ maxi(c(Si

MST )

ri) − optΠ. Or, comme r1...rq mini-

mise maxi(c(Si

MST )

bri), on a

∀r1...rq MaxMaxIdlΠr1 ...rqMST

(G) ≥ maxi

(c(Si

MST )

ri) − optΠ (3)

En, fusionnant les équations 2 et 3, on obtient :

∀r1...rq MaxMaxIdlΠ

br1...brqMST

(G) ≤ MaxMaxIdlΠr1 ...rqMST

(G) + 2optΠ (4)

En utilisant le lemme 10, qui indique qu’il existe une répartition d’agents r ∗1...r

∗q telle

que MaxMaxIdlΠ

r∗1 ...r∗qMST

(G) ≤ 12optΠ, en déduit :

21


MaxMaxIdlΠ

br1 ...brqMST

(G) ≤ 14.optΠ (5)

�

Le lemme ci-dessus suppose que l’on peut déterminer les entiers r1...rq qui minimisent

maxi(c(Si

MST )

bri) et tels que

∑qi=1 ri = r. Montrons comment effectuer ce calcul sous la

condition (provisoire) que ∀i, c(S iMST ) > 0. Soit γi = r × c(Si

MST )Pqk=1 c(Sk

MST ). Le problème

revient à maximiser mini(bri

γi). Il est clair que les solutions ri au problème vérifient ri ∈

{�γi� , �γi�}. L’algorithme suivant permet de trouver la solution au problème simplement :

1. On affecte�γi� à chaque variable ri

(a) On calcule le nombre d’agents affectés en trop r+ =∑q

i=1 �γi� − r

(b) On détermine parmi toutes les variables r1...rq les r+ variables qui ont la plusgrande valeur de bri−1

γiet qui vérifient ri ≥ 2

(c) On décrémente chacune de ces r+ variables de 1.

Au début de cette note, on a supposé que ∀i, c(S iMST ) > 0. Pour traiter le cas ou l’un des

cycles SiMST est le poids nul, il suffit d’affecter à ce cycle un agent ri = 1, et de résoudre

le problème d’affectation de r − 1 agents sur tous les autres cycles.

Théorème 4 Soit G(V, E) un graphe connexe. Il existe un algorithme capable de déter-miner en O(r × n log n) une stratégie mixte Π telle que MaxMaxIdlΠ(G) ≤ 15.optΠ.

Preuve. (Théorème 4). A l’aide des lemmes 7 et 8, nous pouvons obtenir en O(r×n logn)un ensemble de r partions P1...Pr, parmi lesquelles il existe au moins une partition(optΠ) − propre. Pour chacune de ces partitions Pk, il faudra

1. calculer les cycles Si,kMST pour chaque région i

2. calculer la meilleure répartition rk1 ...r

kq d’agents sur ces partitions.

3. estimer Mk = maxi(c(Si,k

MST )

brki

+ max{cxy | (x, y) ∈ Si,kMST}) qui est une borne

supérieure sur le critère MaxMaxIdl, selon le lemme 3.

On sait qu’il existe parmi ces r partitions une partition Pk∗ qui soit optΠ − propre. Deslors, la borne-sup de cette partition vérifiera : M k∗ ≤ MaxMaxIdlΠk∗(G) + max{cxy |(x, y) ∈ Si,k∗

MST} et donc en appliquant le lemme 11, M k∗ ≤ MaxMaxIdlΠk∗(G) +optΠ ≤ 15.optΠ. Il est donc clair qu’en sélectionnant partition Pk et la stratégie mixteassociée Πk qui correspondent au Mk minimal sans savoir si cette partition est optΠ −propre ou non, nous sauront néanmoins que :

MaxMaxIdlΠk (G) ≤ Mk ≤ Mk∗ ≤ 15.optΠ

�

22


8 Conclusion

Une étude théorique du problème de la patrouille a été entreprise. En particulier, il aété montré que des biais forts (stratégies à cycle unique) permettait de rapprocher notreproblème à un simple TSP, grâce auquel on pouvait avoir des solutions très efficaces. L’undes problèmes concernant les stratégies à cycle unique vient de la constante maxij{cij}dans le résultat d’approximation ; cela rend en particulier cette approche moins inté-ressante sur des graphes comportant d’importantes variations entre la taille des arêtes.L’utilisation de stratégies mixtes (section 7) a permit de montrer que le problème est 15-approximable sans restriction quant au type de graphe.

Il est probable qu’il existe des liens entre le problème de la patrouille en le “VehicleRouting Problem”, que nous n’avons pas su mettre en évidence. Ce problème est d’ailleurssouvent traité par des approches dites “Route first, Cluster second”, ou “Cluster first,Route second”[11], cette dernière approche ressemblant beaucoup à celle que nous avonsutilisé dans la dernière section.

Récemment, une étude expérimentale a comparé différents algorithmes sur le pro-blème de la patrouille [1]. Des techniques d’apprentissage par renforcement, de négo-ciation, de méthodes multiagents ont été comparées aux stratégies à cycle unique. Il enressort que sur l’ensemble des graphes générés, les stratégies à cycle unique donnent demeilleurs résultats que tous les autres algorithmes, quel que soit le nombre d’agents utili-sés.

Références

[1] Almeida, A., Ramalho, G. L., Santana, H. P., Tedesco, P., Menezes, T. R., Corruble,V., Chevaleyre, Y. (2004). Recent Advances on Multi-Agent Patrolling. In Advancesin Artificial Intelligence ? SBIA 2004 : 17th Brazilian Symposium on Artificial In-telligence, Sao Luis, Maranhao, Brazil. Lecture notes on Artificial Intelligence 3171,Springer-Verlag.

[2] Aydano Machado, Geber Ramalho, Jean-Daniel Zucker, Alexis Drogoul (2002).Multi-Agent Patrolling : an Empirical Analysis of Alternative Architectures. ThirdInternational Workshop on Multi-Agent Based Simulation.

[3] Aydano Machado, Almeida Alessandro, Ramalho Geber, Zucker Jean-Daniel, Dro-goul Alexis (2002). Multi-Agent Movement Coordination in Patrolling. First Work-shop on Agents in Computer Games, at the 3rd International Conference on Com-puters and Games (CG’02), Edmonton, Canada.

[4] Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Ra-ghavan, and Madhu Sudan (1994). The minimum latency problem. In Proceedings

23


of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages163-171, Montréal, Québec, Canada.

[5] Johnston, M. R. (1999). Dynamic Routing with Competition : Foundations and Stra-tegies. PhD Thesis, Massey University, Palmerston North, New Zealand.

[6] Bellmore, A. and Hong, S. (1974). Transportation of multi-salesman problem to thestandard TSP, Journal ACM 21, p.500-504.

[7] Christofides, N. (1976). Worst-case analysis of a new heuristic for the travellingsalesman problem. Tech. Rep. CS-93-13, Carnegie Mellon University, GraduateSchool of Industrial Administration.

[8] Crites and Barto (1996). Improving elevator performance using reinforcement lear-ning. Advances in Neural Information Processing Systems. pp1017-1023. MIT-Press.

[9] R.M. Karp and J.M. Steele (1985). Probabilistic analysis of heuristics, in The trave-ling salesman problem : a guided tour of combinatorial optimization, E.L.Lawler,J.K. Lenstra, A.H.G.Rinnooy Kan and D.B.Shmoys Eds., Wiley.

[10] M. A. Al-Fawzan and K. S. Al-Sultan (1996). The vehicle routing problem : a survey,in Proceedings of the Fifth Industrial Engineering Research Conference, pp. 269 -274.

[11] Laporte G., Gendreau M., Potvin J-Y., Semet F. (2000). Classical and Modern Heu-ristics for the Vehicle Routing Problem, International Transaction in OperationalResearch, vol. 7, pp. 285-300.

[12] D. Naddef and G. Rinaldi (1993), The Graphical Relaxation : A New Framework forthe Symmetric Traveling Salesman Polytope, Mathematical Programming 58, 5388.

[13] Reinelt G., (1994), "The Traveling Salesman : Computational Solutions for TSPApplications," Lectures Notes in Computer Science 840, Springer-Verlag.

[14] Donald Sofge, Alan Schultz, and Kenneth De Jong (2002). Evolutionary Compu-tational Approaches to Solving the Multiple Traveling Salesman Problem Using aNeighborhood Attractor Schema. EvoCOP, EvoWorkshops 2002, Applications ofEvolutionary Computing. LNCS 2279, p. 153.

[15] Tangamchit P., Dolan J., Khosla P. (2000). Learning-Based Task Allocation in De-centralized Multirobot Systems. 5th International Symposium on Distributed Auto-nomous Robotic Systems, October 4-6, 2000, Knoxville, Tennessee, USA.

[16] Andersson, M. and Sandholm, T. (2000). Contract Type Sequencing for ReallocativeNegotiation. International Conference on Distributed Computing Systems (ICDCS),Taipei, Taiwan, April.

[17] Andersson, M. and Sandholm, T. (1999). Time-Quality Tradeoffs in ReallocativeNegotiation with Combinatorial Contract Types. National Conference on ArtificialIntelligence (AAAI), pp. 3-10, Orlando, FL.

24

Documents

Le probleme multi-agents de la patrouillechevaley/papers/anna_patro.pdf · Le probleme multi-agents de la patrouille ... communs avec le problème de la patrouille : citons les Vehicule