La modélisation de la dynamique des piétons, des cyclistes et des conducteurs de véhicules est d'un grand intérêt théorique et pratique. Au cours des deux dernières décennies, la Recherche dans un large éventail de domaines tels que l'infographie, la physique, la robotique, les sciences sociales, la sécurité et les systèmes de formation a créé des simulations impliquant des individus de type hétérogènes. Deux grands types de simulation d'individus dans un univers virtuel peuvent généralement être distingués selon qu'elles cherchent à atteindre : un haut niveau de réalisme de comportement (simulation pour la sécurité ou les sciences sociales) ou une visualisation de haute qualité (productions de films, de jeux vidéos, d'outils de réalité virtuelle). Dans la première catégorie, les résultats de simulation sont généralement cohérents avec les observations réalisées sur la population réelle et peuvent servir de base à des études théoriques pour l'évaluation et la prévision du comportement des individus. Dans la seconde catégorie, les modèles de comportement ne sont pas la priorité et ne correspondent pas quantitativement au monde réel. Cependant, les individus sont des personnages en 3D entièrement animés et les utilisateurs de l'application peuvent avoir un degré élevé d'interaction avec les éléments de la simulation. Les recherches et les applications récentes tendent à unifier ces deux domaines, en particulier dans le domaine des systèmes de formation où les deux aspects sont nécessaires pour une formation efficace. Dans ce cadre, les systèmes multiagents sont utilisés pour modéliser les populations d'individus. Ils forment un paradigme prometteur pour la conception de logiciels complexes. En effet, ce paradigme propose de nouvelles stratégies pour analyser, concevoir et implémenter de tels systèmes. Les systèmes multiagents sont considérés comme des sociétés composées d'entités autonomes et indépendantes, appelées agents, qui interagissent en vue de résoudre un problème ou de réaliser collectivement une tâche. Les systèmes multiagents peuvent être considérés comme un outil viable pour la modélisation et la simulation de systèmes complexes, et notamment les systèmes de simulation d'individus dans un univers virtuel. Nous proposons un métamodèle organisationnel et holonique permettant de modéliser ces systèmes multiagents. L'approche organisationnelle permet de décomposer le système en unités comportementales appelées rôles. L'approche holonique permet de composer le système en un ensemble d'agents, eux-mêmes, pouvant être décomposés en un ensemble d'agents, et ainsi de suite. Ce métamodèle est utilisé comme la base de notre processus méthodologique, appelé ASPECS, qui guide les scientifiques et les experts d'un domaine dans la modélisation et la construction d'un modèle d'un SMA représentant un système complexe. Sur la base du métamodèle organisationnel et holonique, nous proposons des modèles d'environnement et de groupes d'individus constituant un système de grande échelle spatiale et avec une large population d'individus. Ces modèles sont utilisés pour la simulation d'individus et de foules dans des univers virtuels. L'une des particularités intéressantes de nos modèles est leur conception multiniveau. Nous proposons des modèles de décomposition hiérarchique dynamique pour l'environnement et pour la population. Durant le processus de simulation, il devient alors possible de sélectionner les niveaux permettant d'atteindre le meilleur compromis entre la qualité des résultats produits par la simulation et les performances de calculs pour obtenir ces résultats. Les modèles présentés dans ce mémoire ont été appliqués à la simulation de foule et de trafic dans le cadre de contrats de recherche dont certains sont abordés dans ce document : simulation du réseau urbain de bus de Belfort, simulation de foules dans un centre ville de Belfort, simulation du covoiturage dans les Flandres.

The World Wide Web (WWW) is a huge information network within which searching for relevant quality contents remains an open question. The ambiguity of natural language is traditionally one of the main reasons, which prevents search engines from retrieving information according to users' needs. However, the globalized access to the WWW via Weblogs or social networks has highlighted new problems. Web documents tend to be subjective, they mainly refer to actual events to the detriment of past events and their ever growing number contributes to the well-known problem of information overload. In this thesis, we present our contributions to digest information in real-world heterogeneous text environments (i.e. the Web) thus leveraging users' efforts to encounter relevant quality information. However, most of the works related to Information Digestion deal with the English language fostered by freely available linguistic tools and resources, and as such, cannot be directly replicated for other languages. To overcome this drawback, two directions may be followed: on the one hand, building resources and tools for a given language, or on the other hand, proposing language-independent approaches. Within the context of this report, we will focus on presenting language-independent unsupervised methodologies to (1) extract implicit knowledge about the language and (2) understand the explicit information conveyed by real-world texts, thus allowing to reach Multilingual Information Digestion.

Dans ce mémoire de synthèse d'habilitation à diriger des recherches, je présente les travaux en simulation multi-agents que j'ai menés au sein de l'équipe SMAC (LIFL, Université Lille 1) depuis le début de ma carrière d'enseignant-chercheur en 2002. Ceux-ci portent sur la conception et la mise en application de méthodes et d'outils de simulation destinés à faciliter la modélisation de systèmes complexes à large échelle. Dans ce but, j'ai développé avec mes collègues une approche " orientée interactions " caractérisée par une unification des concepts utilisés dans le domaine des SMA. Elle a donné lieu à une importante élaboration méthodologique et algorithmique (la méthode IODA) dans laquelle toute entité du modèle est représentée par un agent, et tout comportement par une règle appelée interaction. Cette méthode s'appuie sur une séparation entre déclaratif et procédural qui facilite l'acquisition de l'expertise auprès des thématiciens. Par ailleurs de nombreux outils logiciels sont nés de ces recherches (dont la plateforme JEDI et une extension IODA pour la plateforme NetLogo), ainsi que diverses applications dans des domaines variés (biologie cellulaire, serious games, marketing, cartographie). Pour conclure, je présente mon projet de recherche pour les prochaines années qui se propose d'articuler des problématiques issues de travaux récents, d'une part sur la simulation multi-niveaux (qui vise à définir un cadre opérationnel permettant le changement d'échelle d'observation ou de point de vue sur les sous-systèmes d'un système complexe), et d'autre part sur la recherche automatique d'informations dans des données réelles pour augmenter le réalisme comportemental des populations d'agents. Par ailleurs une collaboration avec l'IGN sur l'utilisation de ces techniques pour la généralisation cartographique permet également d'envisager la transposition de ces méthodes de simulation à la résolution de problèmes.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d'origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d'ordonnancement cumulatif. Un problème d'ordonnancement consiste à déterminer les dates de débuts et de fins d'un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l'on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l'on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l'aide d'algorithmes dédiés et de métaheuristiques. Par exemple, l'utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d'ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l'idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d'accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appe- lées à chaque noeud de l'arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d'un million de tâches et 64 resources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes de placement et d'ordonnancement.

Dans cette thèse, nous étudions la robustesse dans le contexte de la modélisation de systèmes complexes par les automates cellulaires. En effet, si l'on cherche à reproduire un comportement émergent à partir d'un modèle d'automate cellulaire, il nous semble nécessaire de se demander si les comportements observés sont bien le résultat d'interactions entre entités constituantes, ou bien s'ils dépendent d'une définition particulière du modèle. Nous allons ainsi être amenés à considérer la robustesse du modèle, à savoir la résistance de son comportement à de petites variations sur les attributs de sa définition. Dans un premier temps, nous montrons la pertinence de cette approche en considérant plusieurs définitions possibles d'une perturbation de la mise à jour globale et en les appliquant à une classe simple et représentative de modèles d'automates cellulaires, les Automates Cellulaires Elémentaires. Nous observons que, malgré le fait que nos perturbations soient proches et qu'une majorité des modèles considérés ne change pas de comportement, quelques cas particuliers montrent des changements qualitatifs du comportement que nous étudions plus en détail. Dans un second temps, nous appliquons cette approche en nous penchant sur un modèle particulier d'automate cellulaire, qui simule le phénomène de formation d'essaim à partir d'un modèle évolué d'automate cellulaire, le gaz sur réseau. Nous explorons la robustesse du comportement du modèle en considérant la perturbation de deux attributs du modèle, la forme de la grille cellulaire et la mise à jour globale, et en tirons les conclusions sur la relation entre l'observation du comportement et la définition précise du modèle.

Le formalisme des MDP, comme ses variantes, sert typiquement à contrôler l'état d'un système par l'intermédiaire d'un agent et de sa politique. Lorsque l'agent fait face à des informations incomplètes, sa politique peut eff ectuer des actions pour acquérir de l'information typiquement (1) dans le cas d'une observabilité partielle, ou (2) dans le cas de l'apprentissage par renforcement. Toutefois cette information ne constitue qu'un moyen pour contrôler au mieux l'état du système, de sorte que la collecte d'informations n'est qu'une conséquence de la maximisation de la performance escomptée. Cette thèse s'intéresse au contraire à des problèmes de prise de décision séquentielle dans lesquels l'acquisition d'information est une fin en soi. Plus précisément, elle cherche d'abord à savoir comment modi fier le formalisme des POMDP pour exprimer des problèmes de collecte d'information et à proposer des algorithmes pour résoudre ces problèmes. Cette approche est alors étendue à des tâches d'apprentissage par renforcement consistant à apprendre activement le modèle d'un système. De plus, cette thèse propose un nouvel algorithme d'apprentissage par renforcement bayésien, lequel utilise des transitions locales optimistes pour recueillir des informations de manière e fficace tout en optimisant la performance escomptée. Grâce à une analyse de l'existant, des résultats théoriques et des études empiriques, cette thèse démontre que ces problèmes peuvent être résolus de façon optimale en théorie, que les méthodes proposées sont presque optimales, et que ces méthodes donnent des résultats comparables ou meilleurs que des approches de référence. Au-delà de ces résultats concrets, cette thèse ouvre la voie (1) à une meilleure compréhension de la relation entre la collecte d'informations et les politiques optimales dans les processus de prise de décision séquentielle, et (2) à une extension des très nombreux travaux traitant du contrôle de l'état d'un système à des problèmes de collecte d'informations.

Ce travail s'inscrit dans la recherche en acquisition des connaissances et en apprentissage automatique pour la modélisation et la validation incrémentale de connaissances de résolution de problème. Nous proposons un modèle simple de représentation des connaissances opératoires qui s'appuie sur la notion de situation, et présentons un outil de modélisation incrémentale et de révision coopérative pour les Bases de Connaissances (BC) exprimées dans cette représentation. Cet outil a été mis au point dans le cadre d'un projet de conception de dialogues télématiques personnalisés. Dans notre modèle, chaque étape intermédiaire de résolution du problème est représentée explicitement dans le SBC sous la forme d'un objet simple et compréhensible appelé "nodule de situation". Les corrections et enrichissements de la BC sont effectués de manière incrémentale, c'est-à-dire au fur et à mesure de la découverte de cas mal résolus, et coopérative, c'est-à-dire en s'appuyant sur un utilisateur / concepteur de la BC compétent dans le domaine. Les caractéristiques de notre approche, que nous proposons de baptiser "révision située", sont les suivantes : l'objectif est de faire en sorte que le processus de révision de la BC soit facile pour l'utilisateur, basé sur des cas concrets, et opérant des corrections "prudentes" et validées. L'outil REVINOS a été développé dans cette optique. Chaque phase de révision coopérative contient une étape de modélisation ou de réutilisation d'objets de la BC, à la charge du concepteur, puis une étape de correction proprement dite, effectuée de manière semi-automatique. REVINOS guide le concepteur tout au long du processus de révision et propose des généralisations à des cas concrets similaires. REVINOS offre l'originalité de chercher à valider les répercussions des corrections proposées, en soumettant au concepteur des exemples abstraits qui correspondent à des ensembles de cas concrets de résolution.

Les problèmes d'optimisation spatialisés font intervenir des entités (clients, demandes, trafic) réparties sur une étendue (la donnée) et des dispositifs physiques (antennes, véhicules) qui doivent leur être associés de manière optimale. Il en résulte de nombreux problèmes d'optimisation combinatoire difficile à résoudre (NP-hard). Pour résoudre ce type de problème, nous proposons des algorithmes à structure intermédiaire, des recherches locales et des approches de résolution collective selon des métaphores de systèmes naturels et biologiques. Le but est par exemple de prendre en compte dès le départ la potentialité d'application à des problèmes dynamiques, de fournir un canevas à la mise en œuvre distribuée possible des algorithmes, et de résoudre des problèmes de grandes tailles.

This thesis is concerned with multi-objective sequential decision making (MOSDM). The motivation is twofold. On the one hand, many decision problems in the domains of e.g., robotics, scheduling or games, involve the optimization of sequences of decisions. On the other hand, many real-world applications are most naturally formulated in terms of multi-objective optimization (MOO). The proposed approach extends the well-known Monte-Carlo tree search (MCTS) framework to the MOO setting, with the goal of discovering several optimal sequences of decisions through growing a single search tree. The main challenge is to propose a new reward, able to guide the exploration of the tree although the MOO setting does not enforce a total order among solutions. The main contribution of the thesis is to propose and experimentally study two such rewards, inspired from the MOO literature and assessing a solution with respect to the archive of previous solutions (Pareto archive): the hypervolume indicator and the Pareto dominance reward. The study shows the complementarity of these two criteria. The hypervolume indicator suffers from its known computational complexity; however the proposed extension thereof provides fine-grained information about the quality of solutions with respect to the current archive. Quite the contrary, the Pareto-dominance reward is linear but it provides increasingly rare information. Proofs of principle of the approach are given on artificial problems and challenges, and confirm the merits of the approach. In particular, MOMCTS is able to discover policies lying in non-convex regions of the Pareto front, contrasting with the state of the art: existing Multi-Objective Reinforcement Learning algorithms are based on linear scalarization and thus fail to sample such non-convex regions. Finally MOMCTS honorably competes with the state of the art on the 2013 MOPTSP competition.

Depuis les premiers travaux de Moreno en 1934, l'analyse de réseaux sociaux s'est toujours accompagnée de diagrammes représentant les relations entre individus. Depuis, la visualisation de graphes n'a cessé de se développer au sein des communautés de visualisation d'information et de dessin de graphes. Au-delà des travaux se concentrant sur les problèmes combinatoires et algorithmiques posés par les dessins de graphes on parle désormais de fouille visuelle de réseaux et plus généralement de visual analytics en intégrant l'utilisateur au coeur de l'analyse. Dans cette thèse nous nous concentrons sur les supports visuels interactifs stéréoscopiques qui permettent de piloter le processus de fouille. En utilisant un environnement expérimental ad hoc, nous essayons d'en évaluer l'impact dans une tâche très populaire de détection de structures en communautés. A travers différentes expériences, nous montrons que pour une classe de graphes particulière la 2D semble plus adapté pour les graphes simples tandis que la 3D stéréo est bénéfique pour les graphes les plus complexes. Nous identifions également des différences dans l'usage des interactions entre la mono et la stéréo, ce qui semble illustrer des différences de comportement caractérisant des différences de stratégie d'utilisation entre ces deux conditions. Nos travaux se prolongent sur le plan technologique par le développement d'une bibliothèque permettant des interactions "mains-libres" adaptées à la fouille visuelle debout devant un grand écran.