La prédiction de séquence comporte plusieurs applications en traitement du langage naturel, en bioinformatique, et en vision numérique. La complexité de calcul requise pour trouver la séquence optimale parmi un nombre exponentiel de possibilités limite cependant l’utilisation de tels algorithmes. Dans ce mémoire, nous proposons une approche permettant de résoudre cette recherche efficacement pour deux types de problèmes différents. Plus précisément, nous adressons le problème de pré-image en prédiction de structure nécessitant de trouver la séquence associée à une entrée arbitraire, et le problème consistant à trouver la séquence qui maximise la fonction de prédiction de plusieurs classificateurs et régresseurs à noyaux. Nous démontrons que ces deux problèmes se réduisent en un même problème combinatoire valide pour plusieurs noyaux à séquences. Pour ce problème, nous proposons une borne supérieure sur la fonction de prédiction pouvant être utilisée dans un algorithme de recherche branch and bound pour l’obtention de solutions optimales. Sur les tâches de reconnaissance de mots et de prédiction de phonèmes, l’approche proposée obtient des résultats compétitifs avec les algorithmes de prédiction de structure de l’état de l’art. De plus, la solution exacte du problème de pré-image augmente de manière significative les performances de prédiction en comparaison avec une approximation trouvée par l’heuristique la plus connue. Pour les tâches consistant à trouver la séquence maximisant la fonction de prédiction de classificateurs et régresseurs, nous montrons que des méthodes existantes peuvent être biaisées à prédire de longues séquences comportant des symboles répétitifs. Nous soulignons que ce biais est enlevé lorsque le noyau est normalisé. Finalement, nous présentons des résultats en conception de médicaments sur la découverte de composés principaux. Le code source peut être téléchargé à https://github.com/a-ro/preimage. / Sequence prediction algorithms have many applications in natural language processing, bioinformatics, and computer vision. However, the computational complexity required to find the optimal sequence among an exponential number of possibilities limits the use of such algorithms. In this thesis, we propose an approach to solve this search efficiently for two types of sequence prediction problems. More precisely, we address the pre-image problem encountered in structured output prediction, which consists of finding the sequence associated with an arbitrary input, and the problem of finding a sequence maximizing the prediction function of various kernel-based classifiers and regressors. We demonstrate that these problems reduce to a common combinatorial problem valid for many sequence kernels. For this problem, we propose an upper bound on the prediction function which has low computational complexity and which can be used in a branch and bound search algorithm to obtain optimal solutions. On the practical tasks of optical word recognition and grapheme-to-phoneme prediction, the proposed approach is shown to be competitive with state-of-the-art structured prediction algorithms. Moreover, the exact solution of the pre-image problem is shown to significantly improve the prediction accuracy in comparison with an approximation found by the best known heuristic. On the task of finding a sequence maximizing the prediction function of kernelbased classifiers and regressors, we highlight that existing methods can be biased toward long sequences that contain many repeated symbols. We demonstrate that this bias is removed when using normalized kernels. Finally, we present results for the discovery of lead compounds in drug discovery. The source code can be found at https://github.com/a-ro/preimage.

Suite à l'échec du behaviorisme, une nouvelle forme d'explication des états mentaux qui pouvait tenir compte du caractère subjectif de l'expérience phénoménale devenait nécessaire. Les progrès en mathématique et en logique symbolique ont permis, en grande partie grâce aux travaux du britannique Alan Turing vers la fin des années 30, de développer un modèle du cerveau auquel participe ce que l'on nomme l' « intelligence artificielle ». Une pléiade de sciences se sont alors regroupées autour de cette nouvelle discipline pour former la « science cognitive ». De cette union est née la théorie computationnelle de l'esprit ou« cognitivisme ». D'après cette théorie, le cerveau serait un ordinateur digital qui traite de l'information, et l'esprit ne serait qu'un programme informatique. Dans cette perspective, la relation corps-esprit correspond à l'approche « fonctionnaliste » et fait abstraction de la nature du cerveau et de sa neurophysiologie. Tout comme des ordinateurs aux architectures différentes arrivent à produire les mêmes résultats, on suppose que deux systèmes ayant des états fonctionnels isomorphes se trouvent nécessairement dans des états cognitifs identiques. Ainsi, le cerveau et l'ordinateur seraient deux systèmes physiques de calculs sur des représentations symboliques. Cependant, l'ordinateur digital et l'intelligence artificielle ne fournissent qu'un modèle qu'il ne faut pas confondre avec la réalité de notre spécificité. Ni la conscience ni l'intentionnalité ne peuvent être expliquées par une simple métaphore et, en ce sens, le cerveau n'a rien d'un ordinateur digital.

Aujourd’hui, de plus en plus de cours se donnent en ligne. En revanche, ceux-ci restent marginaux et très peu d’entre eux permettent d’obtenir des certifications valables et reconnues. Or l’accès à ces contenus est une ressource incroyable, et de plus en plus d’efforts sont mis dans la numérisation de l’apprentissage. Le but de cette maîtrise est donc d’améliorer la supervision d’examens à distance. En effet, un des points forts d’internet est l’anonymat, et attester de la réussite et des compétences d’une personne devient rapidement non trivial. De plus, les seuls outils couramment disponibles à disposition pour la surveillance sont la caméra et le clavier/souris de l’utilisateur, ce qui donne une information très clairsemée. Pour ce faire, les techniques les plus à jour de tracking, reconnaissance, génération de données, et analyse ont été utilisées afin d’amener de l’automatisation et de «l’intelligence» dans la surveillance. Notons que même pour un humain cette tâche est difficile et décider ou non d’un comportement anormal n’est pas déterministe. Le but est donc d’apporter une aide, un support, pour pouvoir sécuriser les examens à grande échelle. La méthode décrite se base sur les avancées en intelligence artificielle, notamment des réseaux génératifs adversaires (generative adversials networks GANs), de l’apprentissage par renforcement (reinforcement learning RL), des réseaux récurrents (recurrent neurals networks RNN) et de réseaux convolutionels (Convolutional neural networks CNN). / Nowadays, more and more courses are available online. On the other hand, they remain marginal and few of them have given valid and recognized certifications. Yet, those lessons have incredible content, and are an amazing resource. Furthermore, more and more, efforts are made toward numerising learning. The goal of this thesis is to improve online exam monitoring. Indeed, one of the strong points of the internet is anonymity, and attesting the success and skills of someone quickly becomes non-trivial. Moreover, the only commonly accessible tools available for surveillance are the camera, and the user’s keyboard / mouse which gives very sparse information. To do so, we used the most up-to-date tracking, recognition, generation and analysis techniques to introduce automation and «intelligence» in the surveillance. Note that even for a human this task is difficult and that to decide if a behavior is abnormal is not deterministic. The goal is therefore to provide help and support to bring large-scale examination monitoring to a safer level. The method described is based on the advances in artificial intelligence, particularly generative adversials network (GANs), reinforcement learning (RL) convolution neural networks (CNN) and recurrent neural networks (RNN).

Quantité de réflexions et de discussions sont en cours au sujet de ce qu'est au juste l'intelligence artificielle et de ce qu'il adviendra de nous, les humains, dans la foulée de son émergence. Tout comme les nanotechnologies, les biotechnologies, la robotique et les autres technologies émergentes, souvent regroupées sous le néologisme technosciences, l'intelligence artificielle est source de spéculation et d'inquiétude concernant la nature de la technique et son impact sur la nature de l'homme. Certains humanistes romantiques pensent que ce que nous sommes pourrait être diminué ou perdu, que la subjectivité humaine est et continuera d'être érodée par la prolifération de processus artificiels de plus en plus autonomes. Certains transhumanistes, de leur côté, provoquent et invoquent ces transformations, les considérant comme des explorations légitimes et souhaitables de nouvelles possibilités et optimisations. L'exercice que ce mémoire propose est de superposer à une présentation de l'IA contemporaine une exploration théorique plus large des notions de technosciences, d'humanisme et de posthumanisme. Pour ce faire, nous présenterons les thèses de trois auteurs qui partagent la crainte de la diminution et de la dénaturation de l'humain dans la foulée de l'émergence des théories cybernétiques et de la recherche et développement technoscientifique. Nous explorerons ensuite un éventail de pensées et réflexions qui nuancent ou contredisent ces thèses. Car si les technologies émergentes nous poussent à mettre en doute notre propre importance et pointent vers notre potentielle obsolescence, elles rendent aussi possibles un éventail d'expériences et de manifestations nouvelles. À travers l'exploration de la notion d'anthropocentrisme chère à l'humanisme, à celle de la co-évolution humain-technologie mise de l'avant par les théoriciens posthumanistes, l'objectif de ce mémoire est d'exposer et d'expliciter les éléments théoriques qui nous semblent centraux à l'exploration de la relation entre l'humain et les technologies émergentes. / There is a great deal of thought and discussion about what exactly artificial intelligence is and what will happen to us humans in the wake of its emergence. As for nanotechnology, biotechnology, robotics, and other emerging technologies, often grouped under the neologism technoscience, artificial intelligence is a source of speculation and concern about the nature of technology and its impact on the nature of man. Some romantic humanists believe that who we are could be diminished or lost, that human subjectivity is and will continue to be eroded by the proliferation of increasingly autonomous artificial processes. Some transhumanists, on the other hand, provoke and invoke these transformations, seeing them as legitimate and desirable explorations of new possibilities and optimizations. The exercise that this dissertation proposes is to superimpose on a presentation of contemporary AI a broader theoretical exploration of the notions of technoscience, humanism and posthumanism. To do so, we will present the theses of three authors who share the fear of the diminution and denaturation of the human in the wake of the emergence of cybernetic theories and technoscientific research and development. We will then explore a range of thoughts and reflections that nuance or contradict these theses. For while emerging technologies cause us to question our own importance and point to our potential obsolescence, they also make possible a range of new experiences and manifestations. Through the exploration of the notion of anthropocentrism dear to humanism, to that of human-technology co-evolution put forward by posthumanist theorists, the objective of this dissertation is to expose and explain the theoretical elements that seem to us central to the exploration of the relationship between the human and emerging technologies.

Résumé Internet est devenu un moyen de diffusion de l’information géographique par excellence. Il offre de plus en plus de services cartographiques accessibles par des milliers d’internautes à travers le monde. Cependant, la qualité de ces services doit être améliorée, principalement en matière de personnalisation. A cette fin, il est important que la carte générée corresponde autant que possible aux besoins, aux préférences et au contexte de l’utilisateur. Ce but peut être atteint en appliquant les transformations appropriées, en temps réel, aux objets de l’espace à chaque cycle de génération de la carte. L’un des défis majeurs de la génération d’une carte à la volée est la résolution des conflits spatiaux qui apparaissent entre les objets, essentiellement à cause de l’espace réduit des écrans d’affichage. Dans cette thèse, nous proposons une nouvelle approche basée sur la mise en œuvre d’un système multiagent pour la génération à la volée des cartes et la résolution des conflits spatiaux. Cette approche est basée sur l’utilisation de la représentation multiple et la généralisation cartographique. Elle résout les conflits spatiaux et génère les cartes demandées selon une stratégie innovatrice : la génération progressive des cartes par couches d’intérêt. Chaque couche d’intérêt contient tous les objets ayant le même degré d’importance pour l’utilisateur. Ce contenu est déterminé à la volée au début du processus de génération de la carte demandée. Notre approche multiagent génère et transfère cette carte suivant un mode parallèle. En effet, une fois une couche d’intérêt générée, elle est transmise à l’utilisateur. Dans le but de résoudre les conflits spatiaux, et par la même occasion générer la carte demandée, nous affectons un agent logiciel à chaque objet de l’espace. Les agents entrent ensuite en compétition pour l’occupation de l’espace disponible. Cette compétition est basée sur un ensemble de priorités qui correspondent aux différents degrés d’importance des objets pour l’utilisateur. Durant la résolution des conflits, les agents prennent en considération les besoins et les préférences de l’utilisateur afin d’améliorer la personnalisation de la carte. Ils améliorent la lisibilité des objets importants et utilisent des symboles qui pourraient aider l’utilisateur à mieux comprendre l’espace géographique. Le processus de génération de la carte peut être interrompu en tout temps par l’utilisateur lorsque les données déjà transmises répondent à ses besoins. Dans ce cas, son temps d’attente est réduit, étant donné qu’il n’a pas à attendre la génération du reste de la carte. Afin d’illustrer notre approche, nous l’appliquons au contexte de la cartographie sur le web ainsi qu’au contexte de la cartographie mobile. Dans ces deux contextes, nous catégorisons nos données, qui concernent la ville de Québec, en quatre couches d’intérêt contenant les objets explicitement demandés par l’utilisateur, les objets repères, le réseau routier et les objets ordinaires qui n’ont aucune importance particulière pour l’utilisateur. Notre système multiagent vise à résoudre certains problèmes liés à la génération à la volée des cartes web. Ces problèmes sont les suivants : 1. Comment adapter le contenu des cartes, à la volée, aux besoins des utilisateurs ? 2. Comment résoudre les conflits spatiaux de manière à améliorer la lisibilité de la carte tout en prenant en considération les besoins de l’utilisateur ? 3. Comment accélérer la génération et le transfert des données aux utilisateurs ? Les principales contributions de cette thèse sont : 1. La résolution des conflits spatiaux en utilisant les systèmes multiagent, la généralisation cartographique et la représentation multiple. 2. La génération des cartes dans un contexte web et dans un contexte mobile, à la volée, en utilisant les systèmes multiagent, la généralisation cartographique et la représentation multiple. 3. L’adaptation des contenus des cartes, en temps réel, aux besoins de l’utilisateur à la source (durant la première génération de la carte). 4. Une nouvelle modélisation de l’espace géographique basée sur une architecture multi-couches du système multiagent. 5. Une approche de génération progressive des cartes basée sur les couches d’intérêt. 6. La génération et le transfert, en parallèle, des cartes aux utilisateurs, dans les contextes web et mobile. / Abstract Internet is a fast growing medium to get and disseminate geospatial information. It provides more and more web mapping services accessible by thousands of users worldwide. However, the quality of these services needs to be improved, especially in term of personalization. In order to increase map flexibility, it is important that the map corresponds as much as possible to the user’s needs, preferences and context. This may be possible by applying the suitable transformations, in real-time, to spatial objects at each map generation cycle. An underlying challenge of such on-the-fly map generation is to solve spatial conflicts that may appear between objects especially due to lack of space on display screens. In this dissertation, we propose a multiagent-based approach to address the problems of on-the-fly web map generation and spatial conflict resolution. The approach is based upon the use of multiple representation and cartographic generalization. It solves conflicts and generates maps according to our innovative progressive map generation by layers of interest approach. A layer of interest contains objects that have the same importance to the user. This content, which depends on the user’s needs and the map’s context of use, is determined on-the-fly. Our multiagent-based approach generates and transfers data of the required map in parallel. As soon as a given layer of interest is generated, it is transmitted to the user. In order to generate a given map and solve spatial conflicts, we assign a software agent to every spatial object. Then, the agents compete for space occupation. This competition is driven by a set of priorities corresponding to the importance of objects for the user. During processing, agents take into account users’ needs and preferences in order to improve the personalization of the final map. They emphasize important objects by improving their legibility and using symbols in order to help the user to better understand the geographic space. Since the user can stop the map generation process whenever he finds the required information from the amount of data already transferred, his waiting delays are reduced. In order to illustrate our approach, we apply it to the context of tourist web and mobile mapping applications. In these contexts, we propose to categorize data into four layers of interest containing: explicitly required objects, landmark objects, road network and ordinary objects which do not have any specific importance for the user. In this dissertation, our multiagent system aims at solving the following problems related to on-the-fly web mapping applications: 1. How can we adapt the contents of maps to users’ needs on-the-fly? 2. How can we solve spatial conflicts in order to improve the legibility of maps while taking into account users’ needs? 3. How can we speed up data generation and transfer to users? The main contributions of this thesis are: 1. The resolution of spatial conflicts using multiagent systems, cartographic generalization and multiple representation. 2. The generation of web and mobile maps, on-the-fly, using multiagent systems, cartographic generalization and multiple representation. 3. The real-time adaptation of maps’ contents to users’ needs at the source (during the first generation of the map). 4. A new modeling of the geographic space based upon a multi-layers multiagent system architecture. 5. A progressive map generation approach by layers of interest. 6. The generation and transfer of web and mobile maps at the same time to users.

Dans ces travaux, nous tentons d’améliorer l’aspect comportemental dans les jeux vidéo en utilisant le raisonnement par cas (Case Based Reasoning - CBR), qui simule le comportement humain. Cette technique, provenant du domaine de l’intelligence artificielle, résout de nouveaux problèmes en retrouvant des expériences analogues dans sa base de cas et en les adaptant au nouveau problème considéré. Nous utilisons le CBR pour l’automatisation de décisions prises par des composantes d’un jeu. La construction d’un module CBR nécessite l’accumulation de plusieurs épisodes de jeu pour former la base de cas du module. Cependant, lorsqu’un grand nombre d’épisodes sont emmagasinés dans la base de cas, la réponse en temps du système s’alourdit. Nous sommes alors confrontés au défi d’améliorer le temps de réponse du module CBR tout en gardant un niveau de performance acceptable du système. Dans ce mémoire, nous utilisons le jeu de Tetris pour mener notre étude. Ce jeu présente un intérêt particulier car les décisions à prendre sont contraintes dans le temps. Nous proposons dans ce mémoire de répondre aux questions suivantes : Comment formuler un système CBR pour jouer au jeu Tetris. Quelle est la performance attendue par un système CBR appliqué à ce jeu. Quel est le niveau du jeu qui peut être atteint par l’estimation de la valeur des cas obtenus par apprentissage par renforcement. Comme Tetris est un jeu contraint par le temps, quel est le niveau de dégradation de performances qui peut être perçue par la réduction de la taille de la base de cas. / In this work, we try to improve the behavioral aspects of video games using Case Based Reasoning (CBR), which can reproduce human behavior as reasoning by similarity, as well as remembering and forgetting previous experiences. This technique, coming from the Artificial Intelligence field, solves new problems by retrieving similar past experiences in the case base and adapting solution to solve new problems. We use CBR for the automation of decisions made by the game engine. The construction of a CBR system needs to accumulate many episodes from the gaming environment to create the case base of the CBR engine. However, as the number of episodes being saved in the case base increases, the response time of the CBR system slows down. We are then facing a dilemma: reducing the size of the case base to improve the response of the CBR system while keeping an acceptable level of performance. In this master thesis, we use the game of Tetris to conduct our case studies. This game presents some particular interests, as decisions to be made are limited by time constraints. We propose in this thesis to answer the following questions: How to construct a CBR system to play the game of Tetris. What is the expected performance of the system applied to this game? Wich game level can be reached by estimating case value through reinforcement learning? As time response constraints are inherent to Tetris, which degradation of performance can be expected by removing cases from the case base?

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2008-2009 / L'augmentation dans les dernières décennies du nombre de véhicules présents sur les routes ne s'est pas passée sans son lot d'impacts négatifs sur la société. Même s'ils ont joué un rôle important dans le développement économique des régions urbaines à travers le monde, les véhicules sont aussi responsables d'impacts négatifs sur les entreprises, car l'inefficacité du ot de traffic cause chaque jour d'importantes pertes en productivité. De plus, la sécurité des passagers est toujours problématique car les accidents de voiture sont encore aujourd'hui parmi les premières causes de blessures et de morts accidentelles dans les pays industrialisés. Ces dernières années, les aspects environnementaux ont aussi pris de plus en plus de place dans l'esprit des consommateurs, qui demandent désormais des véhicules efficaces au niveau énergétique et minimisant leurs impacts sur l'environnement. évidemment, les gouvernements de pays industrialisés ainsi que les manufacturiers de véhicules sont conscients de ces problèmes et tentent de développer des technologies capables de les résoudre. Parmi les travaux de recherche en ce sens, le domaine des Systèmes de Transport Intelligents (STI) a récemment reçu beaucoup d'attention. Ces systèmes proposent d'intégrer des systèmes électroniques avancés dans le développement de solutions intelligentes conçues pour résoudre les problèmes liés au transport automobile cités plus haut. Ce mémoire se penche donc sur un sous-domaine des STI qui étudie la résolution de ces problèmes gr^ace au développement de véhicules intelligents. Plus particulièrement, ce mémoire propose d'utiliser une approche relativement nouvelle de conception de tels systèmes, basée sur l'apprentissage machine. Ce mémoire va donc montrer comment les techniques d'apprentissage par renforcement peuvent être utilisées afin d'obtenir des contrôleurs capables d'effectuer le suivi automatisés de véhicules. Même si ces efforts de développement en sont encore à une étape préliminaire, ce mémoire illustre bien le potentiel de telles approches pour le développement futur de véhicules plus \intelligents". / The impressive growth, in the past decades, of the number of vehicles on the road has not come without its share of negative impacts on society. Even though vehicles play an active role in the economical development of urban regions around the world, they unfortunately also have negative effects on businesses as the poor efficiency of the traffic ow results in important losses in productivity each day. Moreover, numerous concerns have been raised in relation to the safety of passengers, as automotive transportation is still among the first causes of accidental casualties in developed countries. In recent years, environmental issues have also been taking more and more place in the mind of customers, that now demand energy-efficient vehicles that limit the impacts on the environment. Of course, both the governments of industrialized countries and the vehicle manufacturers have been aware of these problems, and have been trying to develop technologies in order to solve these issues. Among these research efforts, the field of Intelligent Transportation Systems (ITS) has been gathering much interest as of late, as it is considered an efficient approach to tackle these problems. ITS propose to integrate advanced electronic systems in the development of intelligent solutions designed to address the current issues of automotive transportation. This thesis focuses on a sub-field ITS since it studies the resolution of these problems through the development of Intelligent Vehicle (IV) systems. In particular, this thesis proposes a relatively novel approach for the design of such systems, based on modern machine learning. More specifically, it shows how reinforcement learning techniques can be used in order to obtain an autonomous vehicle controller for longitudinal vehiclefollowing behavior. Even if these efforts are still at a preliminary stage, this thesis illustrates the potential of using these approaches for future development of \intelligent" vehicles.

Les mathématiques offrent un cadre convenable pour raisonner rigoureusement sur les systèmes et phénomènes réels. Par exemple, en génie logiciel, les méthodes formelles sont parmi les outils les plus efficaces pour détecter les anomalies dans les logiciels. Plusieurs systèmes réels sont stochastiques par nature dans le sens où leur comportement est sujet à un aspect d'incertitude. La représentation de ce genre de systèmes requiert des modèles stochastiques comme les processus de Markov étiquetés (LMP), les processus de Markov décisionnels (MDP), etc. Cette thèse porte sur la quantification de la différence entre les systèmes stochastiques. Les contributions majeures sont : 1. une nouvelle approche pour quantifier la divergence entre les systèmes stochastiques basée sur l'apprentissage par renforcement, 2. une nouvelle famille de notions d'équivalence qui se situe entre l'équivalence par trace et la bisimulation, et 3. un cadre plus flexible pour la définition des notions d'équivalence qui se base sur les tests. Le résultat principal de la thèse est que l'apprentissage par renforcement, qui est une branche de l'intelligence artificielle particulièrement efficace en présence d'incertitude, peut être utilisé pour quantifier efficacement cette divergence. L'idée clé est de définir un MDP à partir des systèmes à comparer de telle sorte que la valeur optimale de cet MDP corresponde à la divergence entre eux. La caractéristique la plus attrayante de l'approche proposée est qu'elle est complètement indépendante des structures internes des systèmes à comparer. Pour cette raison, l'approche peut être appliquée à différents types de systèmes stochastiques. La deuxième contribution est une nouvelle famille de notions d'équivalence, que nous appelons moment, qui est plus forte que l'équivalence par trace mais plus faible que la bisimulation. Cette famille se définit naturellement à travers la coïncidence de moments de variable aléatoires (d'où son nom) et possède une caractérisation simple en terme de tests. Nous montrons que moment fait partie d'un cadre plus grand, appelé test-observation-equivalence (TOE), qui constitue la troisième contribution de cette thèse. Il s'agit d'un cadre plus flexible pour la définition des notions d'équivalence basé sur les tests. / Modelling real-life systems and phenomena using mathematical based formalisms is ubiquitous in science and engineering. The reason is that mathematics offer a suitable framework to carry out formal and rigorous analysis of these systems. For instance, in software engineering, formal methods are among the most efficient tools to identify flaws in software. The behavior of many real-life systems is inherently stochastic which requires stochastic models such as labelled Markov processes (LMPs), Markov decision processes (MDPs), predictive state representations (PSRs), etc. This thesis is about quantifying the difference between stochastic systems. The main contributions are: 1. a new approach to quantify the divergence between pairs of stochastic systems based on reinforcement learning, 2. a new family of equivalence notions which lies between trace equivalence and bisimulation, and 3. a refined testing framework to define equivalence notions. The important point of the thesis is that reinforcement learning (RL), a branch of artificial intelligence particularly efficient in presence of uncertainty, can be used to quantify efficiently the divergence between stochastic systems. The key idea is to define an MDP out of the systems to be compared and then to interpret the optimal value of the MDP as the divergence between them. The most appealing feature of the proposed approach is that it does not rely on the knowledge of the internal structure of the systems. Only a possibility of interacting with them is required. Because of this, the approach can be extended to different types of stochastic systems. The second contribution is a new family of equivalence notions, moment, that constitute a good compromise between trace equivalence (too weak) and bisimulation (too strong). This family has a natural definition using coincidence of moments of random variables but more importantly, it has a simple testing characterization. moment turns out to be part of a bigger framework called test-observation-equivalence (TOE), which we propose as a third contribution of this thesis. It is a refined testing framework to define equivalence notions with more flexibility.

Dans le secteur de la défense, la majorité des processus de combat soulèvent des problèmes complexes, comme l'allocation de ressources. Le projet NEREUS cherche des méthodologies de planification et d'exécution de stratégies pour le centre de commandement et de contrôle (C2) d'une frégate canadienne. L'approche par apprentissage proposée dans ee mémoire permet de constater que de nouvelles stratégies découvertes par expérimentation peuvent se comparer à des doctrines préalablement conçues. Les processus de decision de Markov ont été utilisés pour construire un cadre de développement et modéliser des agents capables d'agir dans des environnements en temps réel. Un agent basé sur l'apprentissage par renforcement a donc été évalué dans un environnement de simulation de combat maritime et un formalisme issu du Weapon-Target Assignment a été utilisé pour définir le problème en temps réel.

Dans cette thèse, nous proposons une méthode générique de développement d‘applications de géosimulation, en 2D et 3D, de divers phénomènes ou comportements complexes (exp. comportements humains) dans des environnements géographiques. Notre travail vise à résoudre quelques problèmes dans le domaine de la simulation informatique et, plus particulièrement, dans le domaine de la simulation multiagent. Les principaux problèmes que nous visons à résoudre dans cette thèse sont: - Absence de méthodes génériques de développement de simulations multiagent de phénomènes ou comportements dans des environnements géographiques. - Manque de techniques de collecte et d’analyse des données spatiales et non-spatiales : (1) données en entrée de la géosimulation multiagent (qui sont utilisées pour alimenter la simulation) ou (2) données en sortie de la géosimulation (qui sont générées par cette simulation). - Absence d’un prototype de géosimulation qui peut être, à la fois, ‘réaliste’ et ‘utile’ pour simuler le comportement du magasinage des êtres humains dans un environnement georéférencé représentant un centre commercial. L’idée principale de notre thèse consiste en: (1) la création d’une méthode générique de développement de géosimulations multiagents, en 2D et 3D, des phénomènes complexes (impliquant par exemple des êtres humains) dans des environnements géographiques et (2) l’application de cette méthode en utilisant le comportement de magasinage dans un centre commercial comme cas d’illustration. Cette méthode contient dix étapes qui sont résumées comme suit : Les trois premières étapes ont pour objectifs de (1) définir les besoins des utilisateurs finaux de la géosimulation, (2) d’identifier les caractéristiques du phénomène à simuler ainsi que celles de son environnement, et (3) de créer un modèle à base d’agents représentent le phénomène à simuler ainsi que son environnement. La quatrième étape vise à sélectionner l’outil de simulation qui va être utilisé pour exécuter les modèles de simulation. Dans la cinquième étape, nous collectons les données spatiales et non-spatiales qui doivent servir à alimenter les modèles de géosimulation. Dans cette étape nous effectuons quelques analyses des données collectées afin de déterminer quelques patrons de comportement du phénomène à simuler. Dans la sixième étape, nous développons le prototype de géosimulation en exécutant les modèles de géosimulation dans la plateforme sélectionnée tout en utilisant les données qui ont été collectées et analysées. Dans la septième étape, nous utilisons une autre fois la technologie multiagent afin de collecter des données spatiales et non-spatiales en sortie de la géosimulation. Ces données contiennent des informations pertinentes concernant le déroulement de la géosimulation. Dans cette étape nous utilisons diverses techniques d’analyse de données spatiales et non-spatiales afin d’analyser ces données. Dans l’illustration de notre méthode nous avons proposé l’utilisation de techniques d’analyse suivantes: techniques/outils statistiques et mathématiques traditionnelles (ou classiques), notre propre technique/outil et d’analyse des données spatiales et non-spatiales, les techniques d’analyse OLAP (On Line Analytical Processing) et SOLAP (Spatial On Line Analytical Processing). Afin d’assurer la fiabilité des modèles de simulation, nous proposons dans notre méthode une huitième étape qui vise à vérifier et valider les modèles de géosimulation. Dans la neuvième étape, nous testons et nous documentons le prototype de géosimulation. Finalement, dans la dixième étape, les utilisateurs finaux peuvent utiliser la géosimulation multiagent comme outil d’aide à la décision. Ces décisions peuvent concerner le phénomène à simuler ou la configuration spatiale de son environnement. Les principales contributions de cette thèse sont : - Une nouvelle méthode de développement d’applications de géosimulation multiagent, en 2D et 3D, des phénomènes complexes (tels que ceux qui impliquent des comportements humains) dans des environnements géographiques. - Quelques modèles représentant le comportement du magasinage dans un centre commercial qui se basent sur une recherche bibliographique solide dans divers domaines de recherche: Une version intégrée du modèle du comportement du magasinage dans un centre commercial, Deux versions du modèle multiagent du comportement du magasinage (la première est indépendante de la plate-forme qui va être utilisée pour exécuter la simulation et la deuxième est dépendante). - Une application de la méthode proposée en utilisant le comportement du magasinage dans un centre commercial comme cas d’illustration. Le cas de test qui a servi pour développer le prototype de simulation est le centre commercial Square One (Toronto). Ce prototype ‘réaliste’ et ‘utile’ est intitulé Mall_MAGS. - Une technique à base de questionnaire pour collecter des données spatiales et non-spatiales qui servent à alimenter des géosimulations. - Un outil qui permet de saisir, simultanément, des données spatiales et non-spatiales qui vont alimenter des géosimulations. - Une technique à base d’agents qui sert à collecter des donnees spatiales et non-spatiales en provenance de la géosimulation en utilisant le paradigme d’agents, ainsi qu’un outil d’analyse de ces données. - Un couplage des techniques d’analyse et d’exploration de données OLAP (On Line Analytical Processing)/SOLAP (Spatial On Line Analytical Processing) et de notre prototype de géosimulation du comportement du magasinage des êtres humains dans un centre commercial. Ce couplage sert à analyser et à explorer les données générées par ce prototype. / In this thesis, we propose a generic method to develop 2D and 3D multiagent geosimulation of complex behaviors (human behaviors) in geographic environments. Our work aims at solving some problems in the field of computer simulation in general and the field of multiagent simulation. These problems are are: - The absence of methods to develop 2D-3D multiagent simulation of phenomena in geographic environments. - The absence of gathering and analysis techniques that can be used to collect and analyze spatial and non-spatial data to feed the geosimulation models (input data) and to analyze data generated by geosimulations (output data). - The absence of a ‘realistic’ and ‘useful’ geosimulation prototype of customer’s shopping behavior in a mall. The main idea of our work is to create a generic method to develop 2D and 3D multiagent geosimulations of phenomena in geographic environments. This method contains ten steps, which are summarized as follows: The first three steps of the method aim to (1) define the geosimulation users’ needs, (2) identify the characteristics of the phenomenon to be simulated, as well as its environment, and (3) create the geosimulation models using the multiagent paradigm. The fourth step aims to select the simulation tool/environment/language that is used to develop the geosimulation. In step five, we collect the data which feeds the geosimulation models. In this step, we analyze the collected information in order to define some patterns of the behaviors of the phenomenon to be simulated. In the sixth step, we develop the geosimulation prototype, on the selected simulation platform, using the collected data. In step seven, we collect information about the course of the simulation, once again using the multiagent paradigm. In this step, we deal with the non-spatial and spatial data, generated by the simulation using several analysis techniques: Classical or traditional analysis techniques, our own analysis technique/tool, and the OLAP (On Line Analytical Processing) and SOLAP (Spatial On Line Analytical Processing) technique. In order to ensure the correctness of the simulation models, as well as to enhance the confidence of the simulation users, we need to verify and validate the simulation models. The verification and validation are the purpose of the eighth step of our method. In the ninth step, we test and document the simulation, while in the last step users can use the multiagent geosimulator in order to make efficient spatial decisions about the phenomenon to be simulated or about the configuration of the simulated environment. The main contributions of this thesis are: - A new method to develop 2D-3D multiagent geosimulations of complex behaviors (human behaviors) in geographic environments. - Some models dealing with the shopping behavior in a mall: an initial version of the shopping behavior model based upon a large literature review, an initial version of the multiagent model which is independent of the tool used to execute the simulation, and an agent-based model created according to the selected platform used to develop the geosimulation. All these models are related to the individual shoppers and to the simulated environment representing the mall. - An illustration of the method using the shopping behavior in a mall as a case study and the Square One mall in Toronto as a case test. This gave birth to a ‘realistic’ and ‘useful’ geosimulation prototype called Mall_MAGS. - A new survey-based technique to gather spatial and non-spatial data to feed the geosimulation models. - A tool to digitalize the spatial and non-spatial gathered data. - A new agent-based technique to collect output data from the geosimulation prototype. - A new analysis technique and tool to analyze spatial and non-spatial data generated by the geosimulation. - A coupling of the OLAP (On Line Analytical Processing) and SOLAP (Spatial On Line Analytical Processing) analysis techniques with the shopping behavior geosimulation prototype in order to explore and analyze the geosimulation outputs.