Généralisation des jeux de poursuite stochastiques 

Généralisation des jeux de poursuite stochastiques 

Un formalisme généralement simple, mais efficace, pour décrire les interactions entre des agents dans des contextes parfois très complexes est celui de la théorie des jeux. Développé il y a de cela près d’une centaine d’années avec de premiers résultats dus à Zermelo 1 , suivis par une découverte plus formelle et globale due à Newmann et Morgenstern pour finalement aboutir au théorème novateur de Nash 2 , la théorie des jeux est maintenant incontournable dans des domaines aussi éloignés que l’intelligence artificielle et l’économie. Notamment, la théorie des jeux a eu un impact profond dans une branche importante de la recherche opérationnelle qu’est la théorie de la recherche qui étudie des questions pratiques telles que la rescousse d’individus perdus en mer. On parle généralement de jeux pour signifier un contexte précis établi avec des règles régissant les interactions permises entre des agents ainsi que les objectifs que ceux-ci cherchent à accomplir.

Un jeu de poursuite est un problème inspiré par la théorie des jeux visant à retrouver un individu se promenant dans un environnement précis. Déjà, lorsque la première formulation d’un jeu de policier et voleur fut établie par Nowakowski et Winkler [39] en 1983, et indépendamment par Quilliot [46], près de vingt années s’étaient écoulées depuis la première formulation connue d’un jeu de poursuite due à Isaacs avec son jeu homicidal chauffeur . Dans ce jeu, un piéton (l’évadé) est poursuivi par un chauffeur (le poursuivant) avec l’intention de l’écraser. Isaacs cherchait à comprendre sous quelles conditions le chauffeur pourrait atteindre son objectif. Isaacs a continué à travailler dans les jeux de poursuite pour ensuite formuler un autre jeu assez connu, celui du monstre et de la princesse [23] dans lequel un monstre cherche à capturer une princesse dans une chambre complètement sombre. Quoique les jeux de Isaacs se décrivent en temps continu alors que celui du policier et voleur se déroule en temps discret, on peut tracer un parallèle entre les deux via les jeux intermédiaires qui furent étudiés durant ces vingt années. En effet, depuis Isaacs, plusieurs articles et livres ont été écrits sur les jeux de poursuite. Évidemment, les méthodes de résolution de ces deux exemples diffèrent beaucoup : Isaacs a développé les équations différentielles éponymes qui permettent de résoudre le jeu du monstre et de la princesse alors que Nowakowski et Winkler ont élaboré une relation de récurrence .

Dans ce mémoire, nous sommes intéressés par les jeux à temps discret et se déroulant sur des structures discrètes, principalement des graphes, dans lesquels les équations différentielles de Isaacs ne sont pas définies. En 1976, selon la recension de littérature de Fomin et Thilikos [17], fut formulé le premier jeu de poursuite sur graphe. Celui-ci se déroulait toutefois en temps continu. Parson [43] formula ce premier jeu pour décrire le mouvement de spéléologues dans une caverne. Certains jeux différentiels (jeux se décrivant avec des équations différentielles) furent étudiés sous la restriction que l’environnement soit un graphe alors que ces jeux sont typiquement conçus pour des environnements continus. Petrov [44] a indépendamment redécouvert le problème ainsi que certains résultats de Parsons plus tard. Golovach a démontré en 1989 [22, 21] que les modèles de Parsons et Petrov étaient équivalents à un jeu de poursuite à temps discret sur un graphe. Dès lors fut complétée la transition vers les jeux purement discrets (en temps et en espace). L’évadé, dans le jeu de Golovach, est invisible, ce qui complique la tâche des poursuivants. Ce jeu fait encore aujourd’hui partie d’un domaine actif de recherche portant le nom des jeux de fouille de graphes dans lesquels un évadé complètement invisible est recherché sur un graphe.

Jeux de policiers et voleurs :

En 1983, pour mener jusqu’au bout la discrétisation et la simplification des jeux de poursuite, Nowakowski et Winkler [39] et, indépendamment, Quilliot [46], ont défini puis résolu, c’està-dire ont déterminé la stratégie optimale du policier 5 , un premier jeu de policier et voleur. Celui-ci se joue encore une fois à deux joueurs, l’un poursuivant l’autre à information parfaite 6 , sur un graphe et à tour de rôle. Depuis, plusieurs articles ont été publiés concernant ce type de jeux qui, chacun, font varier un paramètre du jeu (vitesse des joueurs, type de graphe, etc.).

Le livre de Bonato et Nowakowsi, [8], recensant l’histoire de ce type de jeux et son intérêt en mathématiques et en informatique est d’ailleurs une très bonne référence sur le sujet. Il est coutume en mathématiques de vouloir simplifier un problème ardu pour plus aisément le résoudre. C’est possiblement ce qui a mené Nowakowski et Winkler, et Quilliot, à décrire un jeu dans lequel l’évadé est complètement visible pour contribuer à résoudre d’autres jeux de poursuite comme celui de Golovach.

Ces jeux, de par leurs formulations simples, suscitent aussi beaucoup d’intérêt à différents niveaux d’abstraction. Certains y voient des modèles de caractérisation de paramètresimportants de graphes tels que la largeur d’arbre ou de chemin (on renvoie à l’article de Fomin et Thilikos [17] pour plus d’explications sur les liens entre les jeux de poursuite et les paramètres de graphes ainsi qu’au livre de Diestel [16] pour plus d’information sur ces paramètres). C’est d’ailleurs une des raisons pour laquelle on classe les graphes selon les solutions qu’il produisent sous certains jeux : l’ensemble des graphes sur lesquels k policiers peuvent capturer un voleur sous telles règles, l’ensemble des graphes sur lesquels l voleurs peuvent se sauver sous telles règles, etc. D’autres utilisent certaines variantes pour modéliser des intrusions de virus dans des systèmes informatiques [2]. Finalement, d’autres encore, tels que dans le présent travail, utilisent la proximité de ces jeux avec des applications connues en théorie de la recherche pour aider à résoudre des problèmes de fouilles de graphes qui sont difficiles au niveau computationnel (NP-difficiles [58], par exemple).

L’intérêt pour les jeux de policiers et voleurs est donc bien présent, ce qui justifie l’étude des différentes variantes formulées dans les dernières années.

Le point de vue de la théorie des jeux

Un aspect souvent négligé des jeux de policiers et voleurs est leur proximité avec la théorie des jeux en général, aspect qui pourrait être utile pour résoudre des problèmes complexes apparaissant dans ces jeux tels que le problème du traitement des jeux  information partielle. En effet, malgré que les jeux de policiers et voleurs soient en général traité comme des problèmes distincts naissant naturellement de la théorie des graphes, et donc n’utilisant en général pas le même langage que la théorie des jeux, on peut aisément trouver de grandes similarités entre les deux formalismes. On peut faire de beaux rapprochements entre la manière dont sont résolus typiquement les jeux de policiers et voleurs et les méthodes classiques de la théorie des jeux. En effet, on peut remarquer qu’une méthode assez classique pour déterminer la stratégie optimale des policiers peut être réécrite comme une variante d’une méthode connue de la théorie des jeux.

D’un autre côté, un des aspects les plus importants de ce mémoire est l’intégration d’éléments aléatoires dans les jeux de policiers et voleurs. En effet, ceux-ci sont typiquement purement déterministes, c’est-à-dire ils ne supposent aucun aspect stochastique. Cependant, une partie de la recherche sur les jeux de policiers et voleurs se dirige depuis quelques années vers des jeux dans lesquels, par exemple, un voleur se déplace aléatoirement [25, 28]. De tels jeux ne peuvent être résolus à l’aide de la même méthode de résolution utilisée dans les jeux de policiers et voleurs déterministes. Il est donc nécessaire de développer de nouveaux outils pour inclure ces nouvelles éventualités. Une certaine branche de la théorie des jeux, dite des jeux stochastiques, présente un cadre adéquat et élégant pour intégrer ces éléments aléatoires. Il semble donc naturel d’exposer cette théorie dans ce mémoire. On verra au chapitre 3 que celle-ci n’a cependant pas été appliquée directement dans nos travaux, elle est donc présentée simplement à des fins d’exposition.

En finir avec les jeux de policiers et voleurs

Depuis les trente dernières années, une grande variété de jeux de policiers et voleurs a été énoncée et résolue. Comme on peut le remarquer dans les revues de littérature sur le sujet telles que le livre de Bonato et Nowakowski [8], la quantité de variantes du jeu original de Nowakowski et Winkler est très impressionnante. Cependant, chaque variante a historiquement été étudiée en vase clos et on peut aisément justifier le désir de vouloir unifier les jeux de policiers et voleurs sous un même modèle. D’autant plus qu’en 2012, après quelque trente années de recherche, Clarke et MacGilivray [12] ont résolu le jeu à k policiers, essentiellement une des variantes les plus importantes de ce type de jeux, avec les mêmes outils que ceux utilisés pour résoudre le jeu à un seul policier. On peut donc flairer en lisant l’article de Clarke et MacGillivray qu’il devrait exister une manière de réunir tous les jeux de policiers et voleurs sous un même modèle et les résoudre une fois pour toutes.

Très récemment, Bonato et MacGillivray décrivaient un modèle en affirmant qu’il généralisait tous les jeux de policiers et voleurs [6]. À l’aide d’un formalisme très simple, ils y résolvaient l’ensemble des jeux de policiers et voleurs en généralisant la méthode de Nowakowski et Winkler. Un aspect n’était pas couvert cependant : depuis quelques années est étudié dans la littérature [28, 25] un jeu de policier et voleur, dit du policier et voleur saoul, dans lequel le voleur se déplace de manière aléatoire et donc sans réagir optimalement aux actions du policier. Ce jeu, résolu dans notre article de CP 2015 [52], n’entrait pas dans le cadre de Bonato puisque celui-ci n’y introduisait que des jeux totalement déterministes tels qu’ils furent toujours conçus avant qu’advienne le jeu de policier et voleur saoul.

Ainsi, la contribution principale de ce mémoire, au chapitre 3, est une généralisation de l’article de Bonato et MacGillivray à des contextes plus généraux où différents événements aléatoires pourraient se produire. Non seulement les voleurs sont-ils libres de bouger aléatoirement, mais après chaque action entreprise par les joueurs peut survenir un événement aléatoire venant, par exemple, contrecarrer les actions de ceux-ci. Le chapitre 3 répond donc à la problématique suivante : Suite à la présentation du modèle général de jeux de poursuite de Bonato et MacGillivray, il appert que les jeux intégrant des composantes stochastiques ne sont pas pris en compte. Est-il possible, et si oui comment, de concevoir un nouveau cadre général incluant le premier ainsi que les aspects aléatoires n’ayant pas été considérés ?

Le problème de l’information

Un aspect fondamental des jeux de poursuite, et de tout jeu en général, est la question de la quantité d’information disponible aux protagonistes. Plus particulièrement, on s’intéresse généralement à la quantité d’information que possèdent les poursuivants. Aux deux extrêmes d’un large spectre on retrouve les jeux à information nulle et les jeux à information parfaite : d’une part lorsque l’information est nulle les poursuivants n’ont aucune information sur la position des évadés, on parle par exemple des jeux d’Optimal Search Path ou de fouille de graphe, d’autre part dans un jeu à information parfaite les poursuivants ont en tout temps connaissance de la position des évadés tels que dans les jeux de policiers et voleurs. Entre ces deux bornes se compte une vaste quantité de jeux différents tels que les jeux avec témoins, caméras, radars, etc. qui diffusent une quantité limitée et ponctuelle d’information sur la position des évadés.

Naturellement, dans un même jeu plus la quantité d’information disponible aux poursuivants augmente, plus élevée est la probabilité que ceux-ci en viennent à capturer leur adversaire. Ceci est en particulier vrai pour les jeux de policiers et voleurs : on peut montrer qu’un problème de recherche opérationnelle dénommé le Optimal Search Path (OSP) dans lequel un individu cherche un évadé lui étant invisible sur un graphe se traduit en un jeu de policier et voleur lorsque la position de l’évadé est révélée au chercheur. C’est cette association qui a été exploitée dans l’article présenté à la conférence « 21st International Conference on Principles and Practice of Constraint Programming (CP 2015)» .

Organisation de ce mémoire 

En premier lieu, le chapitre 1 présente des définitions de base d’objets mathématiques qui seront utilisés dans ce mémoire. Plus précisément, on y présente la théorie des graphes, la théorie des processus aléatoires ainsi que la programmation par contraintes. Ensuite sont présentées au chapitre 2 les méthodes généralement utilisées pour trouver la stratégie optimale des policiers dans les jeux de policiers et voleurs ou, autrement dit, pour résoudre ces jeux. Ce chapitre présente en quelque sorte les outils de base utilisés dans les jeux de policiers et voleurs, outils qui se retrouvent dans les chapitres qui suivent. Ce chapitre présente aussi comment la méthode de résolution des jeux de policiers et voleurs se compare à la méthode de résolution de jeux généraux de la théorie des jeux. Finalement, une branche de la théorie des jeux, la théorie des jeux stochastiques, est exposée de manière plus formelle. Au chapitre 3 est présentée une des contributions majeures de ce mémoire. Celle-ci fera d’ailleurs l’objet d’un article de journal à être soumis. Dans ce chapitre sont développés un modèle générique de jeu de policiers et voleurs ainsi qu’une méthode récursive permettant de résoudre une infinité de jeux de policiers et voleurs différents. Ce chapitre, quoique s’inspirant d’un article déjà soumis de Bonato et MacGillivray, représente un progrès important dans la théorie des jeux de policiers et voleurs puisqu’il permet l’étude d’une infinité de jeux différents à l’aide d’un seul modèle en plus d’étendre la méthode de résolution classique des jeux de policiers et voleurs au cas stochastique. Le chapitre 4 présente notre contribution à l’avancement de la recherche sur un problème connu de fouille de graphes, le problème OSP. Cette contribution est originale dans sa manière d’aborder le problème de l’OSP. À la lecture de l’état de l’art sur le sujet, il semble que la relaxation du problème en un jeu à information parfaite n’ait jamais été formellement établie. Cette publication ouvre la voie à l’application de cette méthode à d’autres problèmes du type OSP dont celui avec plusieurs chercheurs. Les deux chapitres principaux de ce mémoire sont donc les chapitres 3 et 4. Comme ceux-ci traitent de deux problématiques distinctes, les revues de littérature concernant ces deux sujets seront directement incluses dans ceux-ci.

Objets et définitions de base

Certaines définitions d’objets mathématiques de base sont présentées dans ce chapitre, ceci dans le but de faciliter la lecture du reste du manuscrit. Les définitions présentées dans ce chapitre se divisent en trois grands thèmes : la théorie des graphes, les processus aléatoires et la programmation par contraintes. Il n’est nullement prétendu dans ce mémoire que ces définitions couvrent l’entièreté de leurs domaines respectifs et nous encourageons le lecteur intéressé à consulter les références recommandées pour obtenir de plus amples informations. Certaines sections utilisent des notations propres à leurs domaines respectifs, celles-ci sont résumées dans la table de notation située en page viii .

Théorie des graphes

Les définitions présentées dans cette section peuvent toutes être retrouvées dans un livre de théorie des graphes. Les références classiques dans ce domaine sont les ouvrages de Diestel [16], Bondy et Murty [9] et Bollobás [5]. Un graphe G = (V, E) s’écrit comme un ensemble dénombrable V d’éléments appelés sommets, ainsi qu’une relation symétrique E ⊆ V × V dont les élément sont nommés arêtes. On écrit [u, v] ∈ E l’arête formée par les sommets u, v ∈ V . On représente visuellement les sommets par des points et les arêtes par des liens entre ceux-ci. Sauf indication contraire, on ne dessine qu’une seule arête par paire de sommets, pour simplifier. On écrit souvent V (G) et E(G) pour préciser de quel graphe on regarde l’ensemble de sommets ou d’arêtes, surtout lorsqu’il y a possibilité d’ambiguïté. Trois graphes sont présentés à la figure 1.1. Le premier, un exemple de graphe célèbre présenté à la figure 1.1(a), est le graphe de Petersen. Le second, à la figure 1.1(b) est parfois appelé le petit frère de Petersen pour des raisons apparentes. On écrit généralement n et m pour les cardinalités de l’ensemble de sommets et celle de l’ensemble d’arêtes. On parle de sommets adjacents lorsque deux sommets sont liés par une arête.

La dénombrabilité de V permet de traiter G comme une structure discrète, par opposition à un ensemble non dénombrable, ou continu, tel que R. Un graphe peut être fini ou infini selon la cardinalité de son ensemble de sommets. On suppose toujours qu’il n’existe qu’une seule arête entre deux sommets (autrement on parlerait de multigraphe). Un graphe H est un sous-graphe de G, noté H ⊆ G, si V (H) ⊆ V (G) et E(H) ⊆ E(G). Autrement dit, H est formé à l’aide d’une partie des sommets du graphe G et de certaines de ses arêtes. On voit par exemple que le graphe présenté à la figure 1.2(a) est un sous graphe du graphe présenté à la figure 1.2(b), lui-même sous-graphe de celui illustré à la figure 1.2(c). Plusieurs graphes simples ont leurs noms propres tels que le chemin, le cycle ainsi que le graphe complet (aussi appelé clique). Un chemin dans un graphe G =  (V, E) est formé par une suite (vi)i∈{1,…,n} , n ≥ 1 de sommets distincts tels que chaque sommet est lié par une arête à son suivant, c’est-à-dire [vi , vi+1] ∈ E pour tout i ∈ {1, . . . , n − 1}. On définit la longueur d’un chemin par le nombre d’arêtes le composant. On note P l’ensemble des chemins de longueur finie d’un graphe et Pu l’ensemble des chemins de longueur finie débutant en u. Un cycle est un chemin contenant l’arête [vn, v1]. Le graphe complet est un graphe dont tous les sommets sont adjacents. On dénote par Pn, Cn, Kn respectivement le chemin (P venant du terme anglais « path »), le cycle et la clique à n sommets. Les figures 1.2(a), 1.2(b), 1.2(c) présentent respectivement les graphes P4, C4 et K4 On dit qu’un graphe G est connexe lorsque entre chaque paire (u, v) de sommets de G il existe un sous-graphe de G formant un chemin P débutant en u et se terminant en v 1 . Autrement dit, un graphe est connexe s’il est possible de le parcourir en entier en partant de n’importe quelle position et en suivant seulement les arêtes.

Processus aléatoires 

Cette section présente quelques notions de base de processus aléatoires qui peuvent sans difficulté être retrouvées et approfondies dans un bon livre de probabilités avancées tel que ceux de Ross [48, 49]. En particulier, on définit les deux notions principales utilisées dans ce mémoire, soit la chaîne de Markov et son cas particulier, la marche aléatoire. On utilise dans ce mémoire le terme général de processus aléatoire (ou processus stochastique) pour décrire une suite de variables aléatoires (Xi)i∈N dont l’hypothèse i.i.d. (indépendantes et identiquement distribuées) n’est pas supposée. Ainsi, un processus aléatoire peut décrire une suite de variables dépendantes. Ces processus sont généralement utilisés pour décrire l’évolution, par exemple dans le temps ou l’espace, d’une variable aléatoire X. Notamment, le cours de la bourse peut se décrire à l’aide d’un processus aléatoire : si la valeur de la bourse (disons du Dow Jones) au temps t est donnée par Xt , alors chaque paire de variables Xt , Xt+1 doit donc être dépendante. En effet, la valeur de la bourse au temps t doit influer sur la valeur de celle-ci au temps t+ 1. Formellement, si P [Xi = xi ] est la probabilité qu’une variable aléatoire Xi prenne la valeur xi , alors un processus aléatoire vise généralement à décrire la probabilité conditionnelle P [Xt = xt | Xt−1 = xt−1, . . . , X0 = x0], soit la probabilité qu’une variable prenne une certaine valeur étant donné l’ensemble des informations connues.

Théorie des jeux et jeux de poursuite

Résolution de jeux finis

On dit qu’un jeu de policiers et voleurs est résolu lorsque la stratégie optimale des policiers est déterminée, en supposant que les voleurs jouent eux-mêmes optimalement. Ces jeux sont résolus à l’aide de deux méthodes distinctes, l’une algébrique et l’autre graphique. La première méthode est détaillée plus bas.

Résolution par relation d’ordre
Le jeu de policier et voleur classique est décrit dans l’article de Nowakowski et Winkler [39] ainsi que dans la thèse de doctorat de Quilliot [46]. Ceux-ci présentent un jeu se déroulant sur un graphe connexe fini (le cas infini est aussi étudié, on en trouve une description dans le livre de Bonato et Nowakowski [8]). Deux joueurs s’y opposent : un policier et un voleur. Ceux-ci, à tour de rôle, se déplacent de sommet en sommet le long des arêtes du graphe. Le jeu se déroule à temps discret. De plus, le policier est toujours le premier à jouer. Pour initialiser le jeu, le policier choisit un sommet de départ avant que le voleur ne choisisse le sien. Les joueurs se déplacent ensuite sur le graphe avec comme objectif pour le policier de capturer le voleur et pour ce dernier d’échapper à cette capture. Le policier remporte la partie lorsqu’il partage le même sommet que le voleur, peu importe le moment où ceci se produit.

Le point de vue de la théorie des jeux, le théorème de Kuhn
Dans les années 1930, Zermelo (aussi immortalisé pour avoir contribué aux axiomes ZermeloFrankel-axiome du choix) démontra que, sous certaines hypothèses, dans le jeu des échecs, soit il existe assurément une stratégie gagnante pour les blancs, soit cela est vrai pour les noirs, soit les joueurs peuvent toujours faire partie nulle [55]. Ce résultat allait quelques années plus tard être la pierre angulaire de ce qu’on nomme aujourd’hui les jeux combinatoires, dont font partie les jeux de policiers et voleurs [6]. Cependant, la théorie des jeux en général aussi allait profiter de ce résultat et Harold Kuhn, vers 1950 [41, 53], démontra une généralisation de celui-ci dans le cadre général de la théorie des jeux. La démonstration de Kuhn repose sur une méthode aujourd’hui connue sous le nom d’induction à rebours et qui est d’une importance capitale dans plusieurs domaines. Le théorème de Kuhn est présenté avec une esquisse de sa démonstration.

La formulation typique de ce théorème est quelque peu altérée pour simplifier l’exposé et pour garder un vocabulaire accessible. On note qu’un jeu fini est un jeu dans lequel chaque joueur n’a accès qu’à un nombre fini de positions et ne faire qu’un nombre fini de mouvements par tour (comme le Tic-Tac-Toe). Un jeu alterné se joue à tour de rôle et un jeu à information parfaite, encore comme le Tic-Tac-Toe, a la propriété que chaque joueur possède toute l’information nécessaire à sa prise de décision, incluant les règles complètes du jeu ainsi que l’information sur les coups précédemment joués par les autres joueurs.

Les jeux stochastiques

La théorie des jeux stochastiques vient consolider une partie de la théorie des jeux traditionnels en permettant de modéliser l’ajout d’événements aléatoires dans des jeux. Cette branche de la théorie des jeux est attribuable à Shapley [50] qui la décrivait dans les années 1950. Shapley décrivait des jeux simultanés (les joueurs jouent en même temps) et répétés (les joueurs s’affrontent dans une suite de parties). Dans ces jeux, chaque partie se compose d’une action simultanée de chaque joueur, après quoi les joueurs reçoivent un certain gain, valeur qu’ils doivent maximiser, puis le jeu transite aléatoirement vers une autre partie.

Valeurs et stratégies optimales
On dit d’une stratégie qu’elle est optimale si elle maximise ce qu’on nomme la valeur d’un jeu. Cette valeur pour le joueur i, notée valG i , est la probabilité maximale que ce joueur gagne une partie G en s’opposant à un ou plusieurs adversaire(s) jouant eux-mêmes de manière optimale. Pour simplifier, on ne définit que cette notion pour les jeux à deux joueurs puisque seuls ceux-ci nous intéressent.

Généralisation des jeux de poursuite stochastiques :

Les jeux de policiers et voleurs sont étudiés comme exemples de jeux de poursuite à temps discret sur des graphes depuis la publication de la thèse de doctorat de Quiliot [46] en 1978 et, indépendamment, de l’article de Nowakowski et Winkler [39] en 1983. Les deux publications décrivent un jeu se déroulant à tour de rôle et dans lequel un seul policier poursuit un voleur sur les sommets d’un graphe. Le tout se déroule à temps discret et avec information parfaite. Le policier gagne s’il en vient éventuellement à partager le même sommet que le voleur, autrement ce dernier remporte la partie. Ce jeu est complètement déterministe puisqu’on y suppose que les joueurs jouent de manière optimale. Ainsi, puisque le jeu se déroule à information parfaite, il est toujours vrai qu’au moins un des joueurs a une stratégie gagnante déterministe. Ce point, qui a déjà été présenté au chapitre 2 avec quelques définitions et résultats de la théorie des jeux, sera réexaminé plus tard.

Depuis la première description du jeu de policiers et voleurs, plusieurs variantes ont fait surface. Aigner et Fromme [1] ont notamment présenté en 1984 le nombre de policiers (que l’on nomme par la suite par son appellation anglaise cop number ) comme un paramètre de graphes décrivant le nombre minimal de policiers requis sur un graphe pour capturer le voleur. À partir de là, plusieurs variantes ont été décrites, chacune modifiant un ou plusieurs paramètres du jeu tels que la vitesse des joueurs, le nombre de policiers, le rayon de capture des policiers, etc. On renvoie au livre de Bonato et Nowakowski [8] pour une description de ces différentes variantes. La revue de littérature de Fomin et Thilikos [17] est aussi une bonne source traitant des problèmes de fouilles de graphe garanties, dont les jeux de policiers et voleurs font partie. Dans les problèmes de fouille de graphes, l’objectif est toujours de retrouver un objet perdu sur un graphe. Les problèmes dits de fouille garantie sont ceux dans lesquels l’objet est toujours retrouvé avec probabilité 1 lorsque celui-ci est observé par le(s) chercheur(s).

En 2014, Bonato et MacGillivray [6] ont présenté une première généralisation des jeux de policier et voleur qui inclut la majorité de ses variantes. En effet, tous les jeux de poursuite à deux joueurs, à tour de rôle, temps discret, information parfaite et dans lesquels est supposé que les joueurs jouent optimalement, sont inclus dans le modèle de Bonato et MacGillivray. De même, ce modèle inclut tous les jeux de poursuite dits combinatoires (on renvoie au livre de Conway On Numbers and Games [15] pour une introduction sur le sujet des jeux combinatoires). Ceux-ci incluent l’ensemble des jeux se jouant à tour de rôle, à information parfaite, sur une structure discrète, tel qu’un graphe, et sans aucun élément de chance. L’exemple typique de jeu combinatoire est le jeu des échecs. Par opposition, le jeu de Stratégo [59], bien qu’il soit totalement déterministe et discret n’est pas considéré comme un jeu combinatoire dû au fait qu’il se joue à information imparfaite. De même, les jeux de chance comme le poker ne sont pas considérés, entre autres de par le manque d’information disponible aux joueurs, mais aussi de par la stochasticité impliquée. Les jeux combinatoires ne comprennent donc aucun élément probabiliste.

Récemment, certains chercheurs tels que Pralat et Kehagias [25] et Komarov et Winkler [27] ont décrit un jeu, le policier et voleur saoul, dans lequel le voleur se promène sur le graphe d’une manière aléatoire : chacun de ses mouvements est décrit par une marche aléatoire uniforme sur les sommets du graphe. Autrement dit, chaque fois que celui-ci veut faire un mouvement, soit sortir d’un sommet, il choisit aléatoirement le prochain sommet parmi l’ensemble des sommets voisins. En général, cette stratégie est sous optimale. Toutefois, cette description forme la base d’une vaste classe de jeux intéressants supposant chacun que le voleur agisse d’une certaine manière aléatoire. En effet, ce comportement aléatoire ne forme pas seulement l’exemple de base de tout bon livre d’introduction sur les marches aléatoires (le problème de l’ivrogne qui veut rentrer chez lui) [5, 48], le fait de permettre du hasard dans les jeux de policiers et voleurs permet aussi de prendre en considération des situations plus réalistes que les jeux de policiers et voleurs classiques. Un bon exemple de ceci sera étudié au chapitre 4 lors de la résolution du problème dit de l’OSP. Bref, comme ces jeux ne peuvent être décrits par le modèle de Bonato et MacGillivray, il est naturel de songer à étendre ce modèle pour incorporer les jeux comportant des éléments stochastiques.

Ainsi, ce chapitre présente un modèle de jeux de policiers et voleurs qui est plus vaste que celui de Bonato et MacGillivray. L’objectif principal de ce modèle est d’inclure les jeux tels que le policier et voleur saoul où le voleur joue aléatoirement. Étant donné la nature probabiliste de ce jeu, notre modèle ne réutilise pas le même cadre théorique que celui de Bonato et MacGillivray, celui des jeux combinatoires.

Concept de solutions dans les jeux de poursuite
Dans les jeux de policiers et voleurs, on s’intéresse généralement à savoir comment résoudre un jeu. Cette question est universelle à la théorie des jeux ; on devrait typiquement définir un concept de solution tel que l’équilibre de Nash pour s’assurer que cette question soit bien définie. Dans le cas des jeux de policiers et voleurs, on adopte typiquement le point de vue du policier et on ne s’intéresse qu’à la question de savoir s’il est possible, et si oui comment, que celui-ci capture le voleur. Dans notre cadre, cette question se traduit par la détermination de la probabilité de capture du voleur par le policier. On remarque que la solution de plusieurs jeux de policiers et voleurs prend essentiellement la même forme puisqu’ils peuvent être résolus à l’aide d’une expression récursive logique. En effet, Nowakowski et Winkler [39] en 1983 ont défini un premier préordre x  y signifiant que lorsque le policier se place en y il peut assurément capturer le voleur en x. Cette relation a été étendue 30 ans plus tard par Clarke et MacGillivray [12] pour résoudre les jeux à k-policiers en les définissant sur des produits forts de graphes, c’est-à-dire y est élément de V k 1 . Il apparaît donc qu’en transformant le graphe sur lequel le jeu se déroule, on peut toujours définir une relation  de manière à résoudre le jeu.

Malgré tout, de telles relations ne peuvent être définies que pour des jeux déterministes, soit des jeux dans lesquels on suppose que les joueurs peuvent jouer optimalement. Dans les jeux à composantes stochastiques, ces relations peuvent être reproduites autrement. En effet, dans un article récemment publié sur le problème de l’OSP [52] est présentée une fonction de récurrence wn(x, y) donnant la probabilité qu’en n pas ou moins un voleur situé sur le sommet x se fasse capturer par un policier situé en y. Cette relation, définie dans le jeu du policier et voleur saoul, est similaire à la relation x  n y de Nowakowski et Winkler tout en étant plus générale puisqu’elle permet de modéliser des événements aléatoires. Un aspect intéressant de celle-ci, comme des relations   d’ailleurs, est sa calculabilité en temps polynomial. On peut donc s’interroger à savoir jusqu’où peut-on étendre la définition des jeux de policiers et voleurs pour inclure des éléments aléatoires tout en permettant à ceux-ci d’être résolubles en temps polynomial par une récurrence wn.

Conclusion :

Dans ce mémoire ont été présentés deux aspects atypiques de la théorie des jeux de policiers et voleurs. D’un premier côté, un modèle avec sa méthode de résolution a été proposé pour englober l’ensemble des variantes possibles dans une seule formulation mathématique pour, on le souhaite, faciliter l’étude et l’étendue des jeux de policiers et voleurs. D’un autre côté, il a été montré que les jeux de policiers et voleurs peuvent être utilisés de manière assez simple pour contribuer à résoudre un problème très concret qu’est le problème de l’OSP qui provient de la théorie de la recherche.

Table des matières

Introduction 
1 Objets et définitions de base 
1.1 Théorie des graphes
1.2 Processus aléatoires
1.3 Optimisation par Contraintes (CP)
2 Théorie des jeux et jeux de poursuite 
2.1 Résolution de jeux finis
2.1.1 Résolution par relation d’ordre
2.1.2 Le point de vue de la théorie des jeux, le théorème de Kuhn
2.2 Les jeux stochastiques
2.2.1 Valeurs et stratégies optimales
3 Généralisation des jeux de poursuite stochastiques 
3.1 Introduction
3.1.1 Concept de solutions dans les jeux de poursuite
3.2 Un jeu de poursuite abstrait à information parfaite
3.2.1 Stratégies
3.2.2 Conditions de victoire dans les jeux de policiers et voleurs
3.2.3 Résolution des jeux de policiers et voleurs
3.3 Complexité de calcul dans les jeux de poursuite
3.3.1 La complexité de calcul de la fonction wn
3.3.2 Un résultat de difficulté pour les jeux de poursuite
3.4 Un résultat de stationnarité
3.5 Un modèle concret pour les jeux de policiers et voleurs
3.6 Exemples
3.7 Conclusion et travaux futurs
3.7.1 Jeux à information imparfaite
3.7.2 En conclusion
4 Applications des jeux de poursuite en recherche opérationnelle 
4.1 Introduction
4.2 Théorie de la recherche et OSP
4.3 Le problème de l’OSP, ou le jeu du perdu
4.4 L’OSP en programmation par contraintes (CP)
4.4.1 Modélisation en CP
4.4.2 Le problème du perdu résolu par branch and bound
4.5 La borne DMEAN
4.6 Le jeu du policier et du voleur saoul et évasif
4.6.1 Le jeu du policier et du voleur saoul
4.6.2 La récurrence wn
4.6.3 Le jeu du policier et voleur en processus de Markov décisionnel (MDP)
4.6.4 Quelques concepts de MDP
4.6.5 Retour au MDP du policier et voleur saoul
4.7 La borne COPWIN
4.8 Expérimentations et résultats
4.8.1 Résultats de la comparaison entre COPWIN et DMEAN
4.8.2 Résultats sur l’efficacité de COPWIN
4.9 Conclusion et travaux futurs
Conclusion

Télécharger le rapport complet