Soutenance mémoire
Généralités
De nos jours, quand nous évoquons la communication, il nous faut préciser à quoi nous faisons référence. D’une part, la communication peut être vue comme un moyen de transmettre des données, ce qui est un sujet très complexe et sophistiqué. Les moyens de communication modernes sont utilisés mondialement pour transmettre de manière quasi instantanée via la télévision, internet, ou les smartphones, des contenus très variés tels que les informations (souvent illustrées par des photos et des vidéos, ce qui peut faire beaucoup de données), des documents professionnels (de plus en plus de personnes travaillent à distance de nos jours), des films, de la musique, voire même des quantités insoupçonnées de photos de chats. Pour ce faire, et avec l’augmentation des flux de données, de nombreux outils théoriques et pratiques sont développés pour permettre ces échanges. D’autre part, la communication peut être vue comme un « simple » échange entre deux personnes. C’est un moyen de transmettre des connaissances. Il y a ce besoin de compréhension mutuelle : si les personnes qui échangent ont un objectif commun, il est évident que communiquer peut être bénéfique pour l’atteindre. Dans le cas d’intérêts conflictuels, communiquer ses intentions peut également être utile d’un point de vue stratégique pour arriver à ses fins. Certains grands conflits historiques tels que la crise de Cuba (1962) n’auraient sans doute pas eu la même issue sans communication. Que les objectifs des différents agents soient alignés ou non, l’absence de communication peut entraîner des conséquences désastreuses. Un des exemples les plus insolites, tiré de [37] est le suivant : sur une petite route de montagne en Italie, une petite section a été réduite à une voie. Les voitures arrivant de directions opposées passaient donc tour à tour via un accord implicite. Jusqu’à ce que deux voitures s’engagent en même temps et se bloquent mutuellement le passage. Refusant de reculer, et les voitures s’accumulant derrière, il fallut trois jours aux autorités italiennes pour faire disparaître cet embouteillage ! Communiquer est donc primordial dans bon nombre de situations, et peut prendre plusieurs formes :
• une forme explicite, comme par exemple fixer le lieu et la date d’un rendez vous, ce qui de nos jours est grandement simplifié par les moyens de communication modernes, ou encore répartir les tâches dans un travail de groupe, et ce via un échange en face à face, téléphonique, de SMS ou par mail. Selon le contexte, ces deux exemples peuvent rendre compte d’objectifs communs ou non pour les agents : deux personnes qui ont pour objectif commun de passer du temps ensemble chercheront juste un accord sur l’heure et l’activité qu’ils feront 1 ; en revanche, dans une entreprise, chaque individu peut avoir un objectif personnel plus ou moins éloigné de l’objectif général de son entreprise. Dans ce cas, la communication peut amener à réduire partiellement ou complètement le biais entre les objectifs. Un autre exemple de communication explicite est l’action de freiner en voiture. En effet, l’appui sur la pédale de frein actionne instantanément les feux stop, qui signalent aux automobilistes situés derrière le véhicule que ce dernier freine et qu’il faut probablement freiner aussi pour éviter la collision. Bien que cet exemple fasse partie de la communication explicite, l’information « cette voiture est en train de freiner » n’est pas envoyée telle quelle, elle est codée en un message (les feux stop sont allumés). Comme nous le verrons dans ce manuscrit, coder l’information est primordial. Un dernier exemple de conflit où la communication a un rôle central est l’ultimatum. Nous pouvons citer l’un des plus célèbres, celui du 23 juillet 1914 2 de l’Autriche-Hongrie à la Serbie, qui entraînera, par le jeu des diverses alliances militaires de l’époque, la Première Guerre mondiale. Cet ultimatum est un exemple où le résultat de l’échange aboutit à la meilleure solution pour aucune des parties ;
• une forme implicite. Nous l’utilisons quotidiennement sans même nous en rendre compte. Un exemple basique est le simple fait de marcher dans la rue. En effet, quand deux personnes se retrouvent face à face, faire un mouvement pour indiquer de quel côté la personne va éviter l’autre est une forme de communication implicite : l’échange n’est pas verbal, il se fait via un mouvement, une action. Dans ce cas précis, l’action est interprétée de manière claire par la personne en face, qui pourra à son tour choisir le « bon » côté, celui qui permet d’éviter la collision. Il est important de souligner ici que nous avons supposé que la communication explicite à voix haute « Je vous évite par ce côté ! » n’est pas une option, car dans les faits, personne ne l’envisage. La communication n’a pas toujours pour but d’améliorer la connaissance de celui qui reçoit le message. Parfois, c’est l’effet inverse et la communication amène à une plus grande incertitude sur l’information détenue par celui qui envoie le message, ce qui peut lui être bénéfique. Au football lorsqu’un tir au but s’apprête à être effectué, la position du gardien, la course d’élan du tireur ou encore la position de son pied font autant office d’actions que de messages, aboutissant à de la communication implicite. Par exemple, en 2002, Mickaël Landreau, alors gardien du FC Nantes, s’est positionné sur la gauche de son but 3 (et non au milieu comme habituellement), envoyant alors un message qui perturba le tireur brésilien du Paris Saint-Germain Ronaldinho. Ce qui fonctionna puisque Landreau arrêta le tir au but. D’autres exemples peuvent se retrouver au poker, où le temps de réflexion et le montant des mises sont des actions ainsi que des messages aux adversaires. Le choix de communiquer de manière explicite ou implicite n’est souvent pas libre et dépend très fortement du contexte et des possibilités de communication. Dans certaines situations, des moyens de communication explicite sont disponibles, rendant nul le coût de la communication : la signalisation du freinage a par exemple un coût nul. Dans d’autres situations, le seul moyen de communiquer est de manière implicite, ce qui peut avoir un coût, comme nous le verrons plus loin, notamment en Section 1.2 et au Chapitre 2. L’un des points centraux de cette thèse est l’étude théorique de problèmes d’optimisation à préférence commune ou non 4 où la communication se fait via certaines structures d’information, ce qui nous amènera à caractériser la manière « optimale » de se coordonner. Ici, nous considérerons que l’information à transmettre est une connaissance privée sur l’état (aléatoire) du système en question. Comme nous le verrons, il ne suffit pas d’envoyer l’information telle quelle (le système considéré ne permet pas toujours de le faire), il faut parfois la compresser, la coder en un certain nombre de messages.
La théorie de l’information
Nota Bene : les définitions de bases ainsi que les lemmes, propositions, et théorèmes de la théorie de l’information utiles pour cette thèse sont proposés en Annexe A. La théorie de l’information modélise la communication au sens technique du terme. La signification du message que nous voulons transmettre n’a que peu d’importance. La sémantique est exclue de cette théorie, l’essentiel étant de transmettre des messages de manière fiable. Pour ce faire, la communication est modélisée par différentes composantes : sources d’information, émetteurs, récepteurs, canaux de transmission (possiblement bruités), relais, etc. Grâce à cette modélisation, nous sommes en mesure de connaître les capacités théoriques de transmission d’information d’un certain nombre de systèmes. Par exemple, nous savons que le taux minimal de compression d’une source est égale à l’entropie de la variable aléatoire correspondant à cette source (Proposition A.13), et qu’il existe un code qui atteint ce taux minimal. Nous connaissons aussi la capacité maximale d’un canal de transmission point à point (Proposition A.14). De nos jours, avec l’augmentation du nombre d’échanges d’information, il est très important de savoir comment transmettre une information de la manière la plus concise possible, tout en gardant une grande fiabilité (typiquement une probabilité d’erreur au décodage proche de zéro). D’autre part, ce genre de résultats, ainsi que les techniques de codage de source et de codage canal, nous seront très utiles dans cette thèse, que ce soit pour la communication implicite ou explicite. En effet, lorsque nous sommes dans une configuration où la communication est faite de manière explicite, l’information est codée, compressée en un certain nombre de messages qui seront envoyés au récepteur. Nous ferons ici des liens avec la quantification, lorsque le nombre de messages qui peuvent être transmis est bien plus petit que le nombre d’états de la source. Il nous faudra créer un codage de la source d’information pour utiliser le système de manière optimale. Dans le cas de la communication implicite, les actions prises par un agent deviennent des messages, qui seront interprétés par un autre agent. Les messages sont donc codés en actions. Le nombre d’actions pouvant être plus petit que le nombre de messages à transmettre, il y a un besoin de compression des messages de la source. Grâce à la théorie de l’information, nouspouvons savoir comment coder ces messages de manière optimale. La théorie de l’information a en fait des liens avec beaucoup d’autres domaines [26] :
• La théorie des communications, notamment parce que la croyance 5 selon laquelle il était impossible d’envoyer de l’information à un taux positif avec une probabilité d’erreur négligeable, a été démentie par Shannon [79] ;
• La physique, tout particulièrement la seconde loi en thermodynamique ;
• Les mathématiques, notamment les statistiques et la théorie des probabilités ;
• L’économie, via la théorie des portefeuilles ainsi que le critère de Kelly, relatif aux systèmes de paris et d’investissements.
Ici, nous contribuons à la théorie de l’information en renforçant les liens de cette théorie avec la théorie des jeux, qui est l’objet de la section suivante
État de l’art
Dans une grande partie de la littérature sur la coordination entre agents, qui inclue les problèmes de décision collective 13 [6], une des hypothèses est la possibilité pour les agents d’accéder à un canal dédié à la communication pour coordonner leurs actions. Ces canaux sont dédiés car ils permettent aux agents de communiquer entre eux sans affecter directement la fonction d’utilité. Les travaux sur la coordination avec canaux dédiés les plus proches des travaux de ce chapitre sont [29, 30]. Dans ces travaux, les auteurs introduisent les notions de coordination empirique et de coordination forte pour mesurer la capacité des agents à coordonner leurs actions dans un réseau composé de canaux dédiés sans bruit. La coordination empirique mesure un comportement moyen de coordination au cours du temps et impose à la distribution empirique conjointe des actions d’être proche asymptotiquement en distance de variation totale (voir la Définition A.1 disponible en Annexe A) d’une distribution cible. Cette notion est liée à des travaux précédents sur la communication de distribution de probabilité [57], et est analysée via des outils de théorie taux-distorsion 14. La coordination forte est quant à elle plus contraignante et impose que les distributions des séquences d’actions soient asymptotiquement indiscernables (également en distance de variation totale) des séquences d’actions tirées grâce à une distribution cible. Cette notion est quant à elle liée au concept de « channel resovability » [49]. Dans les deux cas, le but est d’établir la capacité de coordination, qui lie les distributions conjointes d’actions atteignables aux contraintes sur le taux fixé des canaux dédiés non bruités. Les résultats de [29, 30] ont été étendus à un certain nombre de réseaux avec canaux dédiés [11, 13, 14, 48], et des codes optimaux ont été conçus pour des configurations particulières [12, 15]. En revanche, beaucoup moins de choses sont connues sur le problème de coordination via les actions (la communication implicite) en l’absence de canaux dédiés à la communication. Le travail le plus proche est celui de [46], dans lequel les auteurs caractérisent l’ensemble des utilités moyennes possibles, en supposant que l’Agent 2 observe parfaitement les actions passées de l’Agent 1. Ils établissent l’ensemble des distributions atteignables, qui sont en fait les distributions empiriques conjointes des actions que l’on peut atteindre via la structure d’information imposée au système. En particulier, cet ensemble est caractérisé par une contrainte d’information qui traduit la structure d’observation des actions entre les agents. Cet article [46] s’appuie en grande partie sur des arguments de type combinatoire, alors que [32] utilise une approche via des outils de la théorie de l’information pour la coordination via les actions. Nous utiliserons nous aussi des outils issus de la théorie de l’information. Concernant l’application développée dans ce chapitre, ce travail apparaît comme le premier à établir une relation entre le problème d’optimisation distribuée étudié ici et le problème de contrôle/d’allocation distribué(e) de ressources dans les réseaux sans fil. Spécifiquement, nous nous focalisons sur un problème de contrôle de puissance distribué pour un canal avec interférence, ainsi qu’un cas particulier de ce canal, le canal à accès multiple (voir la définition en Section A.5). Dans la littérature, un point de vue souvent adopté est d’utiliser des outils de théorie des jeux pour concevoir des schémas de contrôle de puissance et pour analyser leur performance. Un de ces outils est l’algorithme itératif de « water-filling » [87], qui est un cas particulier de la dynamique de meilleure réponse (un algorithme de la théorie des jeux, voir la section B.3 en Annexe B), qui est appliqué sur un horizon de temps sur lequel l’état du canal est constant. Un des principaux inconvénients des implémentations diverses de la dynamique de meilleure réponse pour des problèmes de contrôle de puissance (voir par exemple, [58][88][5]) sont qu’ils induisent (après convergence) des stratégies de contrôle de puissance amenant à des équilibres de Nash non efficace au sens de Pareto. C’est-à-dire qu’il existe des stratégies qui permettraient à tous les agents d’augmenter leur utilité individuelle par rapport à la stratégie de « contrôle de puissance Nash ». Un des autres inconvénients est que ce genre de stratégies itératives ne convergent pas toujours. Il existe seulement des conditions suffisantes de convergence (voir par exemple [78] pour le cas « entrées multiples, sorties multiples » 15), et ces conditions peuvent être très restrictives à tel point qu’elles peuvent ne pas être vérifiées du tout dans certains cas importants tels que le canal à accès multiple parallèle [69]. D’autre part, un des buts du contrôle de puissance codé, qui est le nouveau concept développé dans ce chapitre (et en particulier en Section 2.5), et d’obtenir un point de fonctionnement efficace pour le réseau. Ceci est rendu possible en échangeant de l’information entre les émetteurs à propos de l’état du canal. Une observation clé que nous faisons est que l’échange d’information peut être fait via des quantités observées telles que le rapport signal sur interférence plus bruit (RSIB) 16. C’est-à-dire que ces rapports, pour les différents utilisateurs, peuvent être eux-mêmes vus comme les sorties d’un canal par lequel les émetteurs peuvent communiquer pour coordonner leurs actions, à condition qu’ils encodent ces rapports de manière appropriée, ce qui n’est pas fait dans la littérature actuelle. L’aspect de codage apparaît ici car un émetteur va prendre plusieurs réalisations de l’état du canal pour les mettre en correspondance avec une séquence de niveaux de puissance. Les autres émetteurs exploitent alors la séquence d’observations associée (par exemple les valeurs de leur RSIB) pour sélectionner leurs niveaux de puissance. L’avantage d’utiliser du codage est qu’aucune procédure itérative n’est nécessaire (les livres de codes et les fonctions de codage et de décodage se font hors ligne, avant l’utilisation du réseau), nous évitant donc des problèmes de convergence.
Discussion en dimension supérieure
Pour étudier ce modèle en dimension quelconque T ≥ 1, de nouveaux problèmes se posent. Pour commencer, les objets à manipuler sont bien plus complexes, notamment les stratégies (et les espaces dans lesquels elles vivent) qui sont des vecteurs de vecteurs (voir par exemple les équations (3.9) et (3.10)). Les théorèmes d’existence d’équilibres de Nash ainsi que ceux de convergence de la dynamique de meilleure réponse ne s’étendent pas de manière triviale. De plus, [52] est un des seuls articles qui traite de la dimension T quelconque, et ce pour une unique fonction d’utilité, donc un cas particulier de jeu. Le fait que les utilités soient les mêmes pour les deux agents permet d’avoir un jeu de potentiel et d’utiliser les propriétés de ce jeu, ce qui n’est plus possible lorsque les deux agents ont chacun leur utilité propre. Enfin, d’un point de vue numérique, trouver les cellules de la partition (qui sont des polytopes convexes) n’est pas un problème compliqué 29, en revanche calculer leur volume pour pouvoir connaître la valeur de l’utilité des agents est un problème difficile [53] [59] . Il existe cependant des algorithmes pratiques se basant sur des méthodes de Monte-Carlo pour estimer avec une précision arbitrairement faible ces volumes [35] [41]. Ces méthodes pratiques convergent de plus en temps polynomial. Nous les utilisons pour notre application numérique lorsque T > 1.
Conclusion et perspectives
« Nobody ever figures out what life is all about, and it doesn’t matter. Explore the world. Nearly everything is really interesting if you go into it deeply enough. »
– Richard P. Feynman.
Le but principal de cette thèse était l’étude de différentes structures d’information et des moyens d’optimiser l’utilisation des ressources d’information en fonction de ces structures. Pour cela, plusieurs modèles ont été étudiés : un modèle à deux agents, intérêts communs et communication coûteuse ; un modèle à deux agents, intérêts divergents et communication sans coût ; ainsi qu’un modèle avec un nombre d’agents quelconques où l’essentiel pour les agents est d’avoir l’observation parfaite des actions passées des autres agents. Dans ces modèles, nous avons supposé une asymétrie d’information : un agent a de l’information sur l’état du système qu’un autre agent n’a pas. Nous avons donc caractérisé, pour ces modèles, la manière optimale de coordonner les différents agents du système. Pour cela, nous avons utilisé des outils de la théorie de l’information et en particulier nous avons fait du codage de source. En plus du challenge théorique de ces problèmes, nous avons appliqué nos résultats à des cas pratiques de communication sans fil, notamment au problème de contrôle de puissance. Notre nouvelle approche, le contrôle de puissance codé, est complètement générale et nous montrons qu’elle permet d’obtenir le bon compromis entre transmission d’information et maximisation de l’utilité. Elle apparaît comme très prometteuse par rapport à des algorithmes classiques utilisés jusqu’alors.Nous avons également développé une application aux réseaux de véhicules électriques. Notre approche sur un modèle de base permet de bien comprendre les enjeux et amène des pistes de réflexion pour une gestion intelligente de l’information dans ces réseaux. Ces modèles sont relativement simples mais sont essentiels à la compréhension des mécanismes d’optimisation des ressources de communication, et permettent d’avoir une vision de base pour étudier des modèles plus généraux. En effet, en plus d’amener une nouvelle approche de résolution de problème d’optimisation et de théorie des jeux via des outils de théorie de l’information, cela permet de penser d’une manière différente les algorithmes et codes qui seront implémentés en pratique pour des problèmes de communication sans fil. Les perspectives de cette thèse sont d’étudier des modèles plus généraux pour pouvoir se rapprocher au mieux de modèles pratiques réalistes et renforcer un peu plus les liens entre deux des théories scientifiques les plus importantes de ces dernières décennies. Nous pouvons par exemple considérer les extensions suivantes :
• Augmenter le nombre d’agents pour les modèles des chapitres 2 et 3 paraît essentiel. En augmentant ce nombre, il faudra redéfinir l’asymétrie d’information et préciser la connaissance qu’ont les agents sur l’état du réseau ;
• Pour les modèles avec deux agents puis dans un deuxième temps pour des modèles à K ∈ N agents, nous pouvons supposer que chaque agent possède une information partielle sur l’état du système et étudier une structure d’information bidirectionnelle. Le modèle de théorie de l’information de Shannon [80] ainsi que les modèles de théorie des jeux [73],[77],[7] ou [9] pourront servir de base de travail ;
• Nous pouvons également considérer un modèle avec un espion et caractériser la nouvelle contrainte qui permettra d’être robuste à l’espionnage ;
• Ajouter plusieurs phases de communication plutôt que l’envoi d’un unique message pourra également être une extension à considérer. Ceci permettra de réduire au moins partiellement le biais entre les utilités des agents ;
• Enfin, passer d’espaces discrets à des espaces continus est un axe de travail qui est à l’étude et qui donnera lieu à une soumission à la conférence de contrôle européenne (ECC 2015).
Le passage du discret au continu doit être fait avec attention, à commencer par la définition des entropies différentielles. Cet article permet de faire le lien entre discret et continu. Nous appliquons de plus ces résultats au problème bien connu de Witsenhausen. D’un point de vue pratique, en plus des applications en communication sans fil et aux Smart Grids correspondant aux extensions théoriques ci-dessus, nous pensons qu’il est possible d’appliquer ces modèles à d’autres contextes notamment pour la transmission d’information en économie ou au sein d’une entreprise pour optimiser la gestion de l’information. En conclusion, nous pouvons affirmer que ce domaine qui regroupe des problèmes à la croisée de deux théories n’en est qu’à ses débuts et est très prometteur.
|
Table des matières
Chapitre I Introduction
1.1 Contexte de la thèse
1.1.1 Généralités
1.1.2 La théorie de l’information
1.1.3 La théorie des jeux
1.1.4 Le contrôle de puissance dans les réseaux sans fil
1.1.5 Les réseaux de véhicules électriques
1.2 Structure et objectifs du manuscrit
1.2.1 Exemple introductif : Le « Big Online Matching Game »
1.2.2 Exemple introductif : les cas de référence
1.2.3 Structure de la thèse
1.3 Contributions et publications
1.3.1 Contributions
1.3.2 Publications
Chapitre 2 Coordination via la communication implicite dans les réseaux distribués
2.1 Motivation et état de l’art
2.1.1 Un problème d’optimisation distribuée
2.1.2 État de l’art
2.1.3 Contributions principales
2.2 Description du problème étudié
2.2.1 Formulation mathématique
2.2.2 Discussion
2.3 Contraintes d’information sur les distributions atteignables
2.3.1 Une condition nécessaire d’atteignabilité
2.3.2 Conditions suffisantes d’atteignabilité
2.4 Problème d’optimisation sous contraintes
2.4.1 Cas général
2.4.2 Le cas de l’observation parfaite Y = X1
2.5 Application : le contrôle de puissance codé
2.5.1 Description du cadre proposé
2.5.2 Influence de la fonction d’utilité
2.5.3 Influence de la structure d’observation
2.5.4 Influence de la connaissance sur l’état
2.5.5 Influence du schéma de coordination
2.6 Conclusion du chapitre
Chapitre 3 Communication stratégique pour les smart grids
3.1 Motivation et état de l’art
3.1.1 Introduction
3.1.2 État de l’art
3.2 Modèle de jeu de signaux et exemple introductif
3.2.1 Modèle de jeu de signaux
3.2.2 Discussion
3.2.3 Un exemple illustratif
3.3 Résultats théoriques
3.3.1 Le cas de la dimension 1
3.3.2 Discussion en dimension supérieure
3.4 Application numérique
3.4.1 Influence du biais b
3.4.2 Exemple de partitions et actions associées
3.5 Conclusion du chapitre
Chapitre 4 Transformation d’une structure d’observation arbitraire à l’aide d’un encodeur
4.1 Motivation et état de l’art
4.1.1 Introduction
4.1.2 Etat de l’art
4.2 Description du modèle
4.2.1 Structure d’observation avec assistance d’un encodeur
4.2.2 Source aux variations arbitraires et observation parfaite virtuelle
4.2.3 Lien avec les jeux répétés
4.3 Contraintes d’information pour retrouver l’observation parfaite
4.3.1 Graphe auxiliaire et coloriage
4.3.2 Condition suffisante pour l’observation parfaite virtuelle
4.3.3 Condition nécessaire pour l’observation parfaite virtuelle
4.4 Application aux jeux répétés
4.5 Conclusion du chapitre
Chapitre 5 Conclusion et perspectives
Annexes
Télécharger le rapport complet
