Dans cette thèse nous montrons que le raisonnement symbolique associé à la vérification de la consistance d'arc avec propagation de contraintes est un outil efficace pour interpréter les images. Nous montrons dans un premier temps que ce cadre théorique permet de vérifier l'organisation spatiale de différentes composantes d'un objet complexe dans une image. Nous proposons ensuite d'étendre l'utilisation de celui-ci à la reconnaissance sélective des formes décrites par des équations mathématiques, grâce à la notion de consistance d'hyper-arc à deux niveaux de contraintes. La pertinence et la faisabilité de cette approche ont été validées par de multiples tests. En outre, les résultats obtenus sur des images sur-segmentées montrent que la méthode proposée est résistante au bruit, même dans des conditions où les humains (dans certains cas d'agnosie visuelle) peuvent échouer. Ces résultats soutiennent l'intérêt du raisonnement symbolique dans la compréhension de l'image. / In this thesis we show that symbolic reasoning associated with arc consistency checking is an efficient tool for images interpretation. We first show that this theoretical framework makes it possible to verify the spatial organization of different components of a complex object in an image. We then propose to extend the use of this framework to the selective recognition of shapes described by mathematical equations, thanks to the notion of hyper-arc consistency with bi-levels constraint. The relevance and feasibility of this approach have been validated by multiple tests. In addition, the results obtained on over-segmented images show that the proposed method is noise-resistant, even under conditions where humans (in some cases visual agnosia) may fail. These results support the interest of symbolic reasoning in image understanding.

Pour l’apprentissage automatisé de données régulières comme des images ou des signaux sonores, les réseaux convolutifs profonds s’imposent comme le modèle de deep learning le plus performant. En revanche, lorsque les jeux de données sont irréguliers (par example : réseaux de capteurs, de citations, IRMs), ces réseaux ne peuvent pas être utilisés. Dans cette thèse, nous développons une théorie algébrique permettant de définir des convolutions sur des domaines irréguliers, à l’aide d’actions de groupe (ou, plus généralement, de groupoïde) agissant sur les sommets d’un graphe, et possédant des propriétés liées aux arrêtes. A l’aide de ces convolutions, nous proposons des extensions des réseaux convolutifs à des structures de graphes. Nos recherches nous conduisent à proposer une formulation générique de la propagation entre deux couches de neurones que nous appelons la contraction neurale. De cette formule, nous dérivons plusieurs nouveaux modèles de réseaux de neurones, applicables sur des domaines irréguliers, et qui font preuve de résultats au même niveau que l’état de l’art voire meilleurs pour certains. / Convolutional neural networks have proven to be the deep learning model that performs best on regularly structured datasets like images or sounds. However, they cannot be applied on datasets with an irregular structure (e.g. sensor networks, citation networks, MRIs). In this thesis, we develop an algebraic theory of convolutions on irregular domains. We construct a family of convolutions that are based on group actions (or, more generally, groupoid actions) that acts on the vertex domain and that have properties that depend on the edges. With the help of these convolutions, we propose extensions of convolutional neural netowrks to graph domains. Our researches lead us to propose a generic formulation of the propagation between layers, that we call the neural contraction. From this formulation, we derive many novel neural network models that can be applied on irregular domains. Through benchmarks and experiments, we show that they attain state-of-the-art performances, and beat them in some cases.

La télémédecine est une approche nouvelle de la pratique médicale qui est particulièrement porteuse d'espoir face à l'enjeu sociétal posé par l'incidence croissante des maladies chroniques. Le développement de la télésurveillance médicale réalisée grâce au recueil de données physiologiques ou biologiques au domicile du patient implique de développer nos capacités à analyser un volume important de données. Le problème auquel s'intéresse cette thèse est d'établir ou d'apprendre automatiquement la fonction qui lie les données fournies par les capteurs à l'état de santé du patient. La difficulté principale tient à ce qu'il est difficile d'établir de manière sûre l'état de santé d'un patient, la seule référence disponible étant alors celle que peut donner le médecin traitant. Nous montrons dans cette thèse que la modélisation stochastique et plus particulièrement le formalisme graphique bayésien permet d'aborder cette question sous trois angles complémentaires. Le premier est celui de la représentation explicite de l'expertise médicale. Cette approche est adaptée aux situations dans lesquelles les données ne sont pas accessibles et où il est donc nécessaire de modéliser directement la démarche du médecin. La seconde approche envisagée est celle de l'apprentissage automatique des paramètres du modèles lorsque suffisamment de données sur les sorties attendues sont disponibles. Nous nous intéressons enfin à la possibilité d'apprendre les actions pertinentes par renforcement sous les contraintes de la problématique médicale à savoir d'après l'observation de l'expert dans sa pratique normale / Telemedicine is a new approach of medical practice that is expected to be one of the answers for facing the challenge of chronic diseases management. Development of remote medical surveillance at home relies on our capacity to interpret a growing amount of collected data. In this thesis, we are interested in defining the function that connects the state of the patient to the data given by the different sensors. The main difficulty comes from the uncertainty when assessing the state of the patient. The only reference available is the one that can be given by the medical doctor. We show in this thesis that stochastic modelling and more specifically graphical bayesian formalism allows to treat this question in three ways. The first one consists in representing explicitly the medical expertise. This approach is adapted to the cases in which data is not accessible, and as a consequence, where it is necessary to model directly the diagnosis rules. The second approach that we study is the automatic learning of model parameters that can be performed when enough information is available concerning the expected outputs of the system. Finally, we propose the use of reinforcement for learning medical actions from the observation of the human expert in its everyday practice. Considering the specificity of the medical domain, we study the likelihood criterion for learning an efficient representation of the state space

Pouvoir se déplacer intelligemment dans un environnement inconnu est primordial pour des robots mobiles (Évitement d’Obstacle (EO)). Ceci est nécessaire pour explorer et construire une carte de l’environnement (CArtographie Active (CAA)), carte qui servira à d’autres tâches comme la patrouille (COuverture Active (COA)). Cette thèse se focalise sur la prise de décision pour planifier les déplacements de robots autonomes afin de naviguer, couvrir ou explorer l’environnement. Ainsi, nous nous basons sur la Prise de Décision Séquentielle (PDS) en Intelligence Artificielle et proposons deux contributions concernant : (1) les processus décisionnels de CAA et COA, et (2) la planification à long terme pour la COA. De plus, récemment, les robots mobiles ont commencé à partager l’espace physique avec les humains en fournissant des services comme du ménage à la maison. Dans ces cas, le comportement du robot doit s’adapter à la dynamique du monde. Par conséquent, nous proposons deux autres contributions pour : (3) la CAA en environnements de foule, et (4) l’EO par chemin clairsemé en environnements ambiants / The ability to intelligently navigate in an unknown environment is essential for mobile robots (Obstacle Avoidance (OA)). This is needed to explore and build a map of the environment (Active Mapping (AM)); this map will then support other tasks such as patrolling (Active Coverage (AC)). In this thesis, we focus on decision-making to plan the moves of autonomous robots in order to navigate, cover, or explore the environment. Therefore, we rely on the framework of Sequential Decision-Making (SDM) in Artificial Intelligence to propose two contributions that address: (1) decision processes for AC and AM and (2) long-term planning for AC. Furthermore, mobile robots recently started sharing physical spaces with humans to provide services such as cleaning the house. In such cases, robot behavior should adapt to dynamic aspects of the world. In this thesis, we are interested in deploying autonomous robots in such environments. Therefore, we propose two other contributions that address: (3) short-term AM in crowded environments and (4) clearest path OA in ambient environments

Dans cette thèse, nous nous intéressons à l'étude d'un modèle dédié à l'exploration et à la structuration d'espaces d'apprentissage sensorimoteur pour des systèmes artificiels. Nous appuyons notre démarche sur les notions de corps et de développement propre, auxquelles se greffe un troisième processus dit motivationnel. Cette forme de curiosité artificielle se base sur le progrès en compétence et repose ainsi sur les contraintes physiques naturelles directement issues de l'encorporation de l'agent. L'objectif de la motivation est de réguler un développement à long terme, dédié à l'apprentissage de nouvelles compétences non prévues par le concepteur. Nous inscrivons nos travaux dans la continuité de l'approche du babillage sensorimoteur dans l'espace des buts, qui consiste à déterminer un ensemble de techniques permettant à un agent de générer, selon une métrique d'intérêt, une configuration sensorielle qu'il va essayer d'atteindre par des actions motrices. Nos contributions viennent améliorer et complexifier un modèle motivationnel existant, en proposant des alternatives au processus de structuration de l'espace d'exploration. Certaines de ces propositions théoriques ont été validées expérimentalement grâce à la plateforme FIMO, que nous avons développée dans cette optique, et qui est disponible en ligne. / In this thesis, we study a motivational model for artificial systems, which aims at exploring and structuring sensorimotor learning spaces. Our approach relies on some essential notions, including the body, the development, and the motivation. This particular kind of artificial curiosity is based on the competence or learning progress, and thus depends on the physical natural constraints originating from the agent's embodiment. We follow the Goal-Babbling Exploration approach which consists in determining a set of techniques allowing an agent to self-generate goals, i.e. sensory configurations, and try to reach them using motor actions. Our contributions improve the SAGG-RIAC motivational model, by proposing alternative ways of structuring the exploration of the goal space. Some of our contributions have been experimentally validated within the FIMO framework we developed to this purpose.

Dans cette thèse, nous nous intéressons au problème d'interrogation de bases de connaissances composées de données et d'une ontologie, qui représente des connaissances générales sur le domaine d'application. Parmi les différents formalismes permettant de représenter les connaissances ontologiques, nous considérons ici un fragment de la logique du premier ordre appelé règles existentielles (aussi connues sous le nom de ``tuple generating dependencies'' et Datalog+/-). Le problème fondamental de conséquence logique au cœur de cette thèse demande si une requête conjonctive est conséquence d'une base de connaissances. Les règles existentielles étant très expressives, ce problème est indécidable. Toutefois, différentes restrictions sur les ensembles de règles ont été proposées afin d'obtenir sa décidabilité.La contribution de cette thèse est double. Premièrement, nous proposons un outil qui nous permet d'unifier puis d'étendre la plupart des classes de règles connues reposant sur des notions d'acyclicité assurant la finitude du chaînage avant. Deuxièmement, nous étudions la compatibilité des classes décidables de règles existentielles connues avec un type de connaissance souvent nécessaire dans les ontologies: la transitivité de relations binaires. Nous aidons à clarifier le paysage des résultats positifs et négatifs liés à cette question et fournissons une approche permettant de combiner la transitivité avec les règles existentielles linéaires. / In this thesis we investigate the issue of querying knowledge bases composed of data and general background knowledge, called an ontology. Ontological knowledge can be represented under different formalisms and we consider here a fragment of first-order logic called existential rules (also known as tuple-generating dependencies and Datalog+/-).The fundamental entailment problem at the core of this thesis asks if a conjunctive query is entailed by an existential rule knowledge base. General existential rules are highly expressive, however at the cost of undecidability. Various restrictions on sets of rules have been proposed to regain the decidability of the entailment problem.Our specific contribution is two-fold. First, we propose a new tool that allows to unify and extend most of the known existential rule classes that rely on acyclicity conditions to tame infinite forward chaining, without increasing the complexity of the acyclicity recognition. Second, we study the compatibility of known decidable rule classes with a frequently required modeling construct, namely transitivity of binary relations. We help clarifying the picture of negative and positive results on this question, and provide a technique to safely combine transitivity with one of the simplest, yet useful, decidable rule classes, namely linear rules.

L'objectif du problème appelé "Ontology-based data access" (OBDA) est d'améliorer la réponse à des requêtes en prenant en compte des connaissances d'ordre général durant l'évaluation des requêtes. Ces connaissances générales sont représentées à l'aide d'une ontologie, qui est exprimée dans cette thèse grâce à des formules logiques du premier ordre, appelées règles existentielles, et aussi connues sous le nom de "tuple-generating dependencies" et Datalog+/-. L'expressivité des formules utilisées est telle que l'évaluation de requêtes devient un problème indécidable, et cela a conduit la communauté à définir de nombreux cas décidables, c'est-à-dire des restrictions sur les ensembles de règles existentielles considérés. La contribution de cette thèse est double : tout d'abord, nous proposons une vue unifiée sur une grande fraction des cas décidables connus, et fournissons par là même une analyse de complexité et un algorithme optimal dans le pire des cas. Nous considérons également l'approche couramment utilisée de réécriture de requêtes, et proposons un algorithme générique qui permet de surmonter certaines causes évidentes d'explosion combinatoire qui rendent les approches classiques pratiquement inapplicables. / Ontology-based data access (OBDA) aims at enriching query answering by taking general background knowledge into account when evaluating queries. This background knowledge is represented by means of an ontology, that is expressed in this thesis by a very expressive class of first-order formulas, called existential rules (sometimes also tuple-generating dependencies and Datalog+/-). The high expressivity of the used formalism results in the undecidability of query answering, and numerous decidable classes (that is, restrictions on the sets of existential rules) have been proposed in the literature. The contribution of this thesis is two-fold: first, we propose a unified view of a large part of these classes, together with a complexity analysis and a worst-case optimal algorithm for the introduced generic class. Second, we consider the popular approach of query rewriting, and propose a generic algorithm that overcomes trivial causes of combinatorial explosion that make classical approaches inapplicable.

Cette thèse traite de l'adaptation du niveau de cohérence locale au cours de la résolution d'un problème de satisfaction de contraintes (CSP). En particulier, nous nous intéressons à l'utilisation des propriétés de cohérence locale plus fortes que la cohérence d'arc (AC) pour gagner en efficacité de résolution d'un CSP. Les cohérences plus fortes que AC sont généralement coûteuses à maintenir dans un réseau de contraintes. Par conséquent, elles sont rarement utilisées en pratique. Cette thèse apporte plusieurs contributions qui permettent de bénéficier de la puissance de filtrage de ces cohérences fortes tout en évitant le coût élevé de les maintenir dans tout le réseau de contraintes. Premièrement, nous introduisons la cohérence locale paramétrée (p-LC), une approche originale qui permet de définir des niveaux de cohérence intermédiaires entre AC et une de cohérence locale LC, plus forte que AC. Puis, nous présentons l'instanciation de cette approche à maxRPC et SAC, deux cohérences plus fortes que AC. Il en découle deux cohérences paramétrées, à savoir p-maxRPC et p-SAC. Ensuite, nous présentons l'algorithme p-maxRPC3, qui réalise p-maxRPC et l'algorithme p-SAC1, pour réaliser p-SAC dans un réseau de contraintes. Deuxièmement, nous montrons expérimentalement que maintenir un niveau de cohérence intermédiaire p-LC, peut donner un bon compromis entre puissance de filtrage et coût de calcul nécessaire pour maintenir ce niveau de cohérence. En outre, nous montrons que pour chaque instance de CSP il est possible de trouver un paramètre adéquat qui donne ce bon compromis. L'approche de cohérence paramétrée ne précise pas comment le paramètre peut être choisi a priori. Nous proposons donc deux techniques qui permettent d'ajuster automatiquement le niveau de cohérence paramétrée p-LC. Ces deux techniques utilisent plusieurs paramètres à la fois. Chaque paramètre est associé à une partie du problème et s'adapte automatiquement et localement au cours de la résolution. Finalement, nous proposons POAC1, le premier algorithme pour établir partition-one-AC (POAC) dans un réseau de contraintes. Puis, en comparant POAC à SAC nous constatons que POAC converge au point fixe plus rapidement que SAC. Sur la base de ce constat, nous proposons APOAC, une version adaptative de POAC qui contrôle le nombre de variables sur lesquelles POAC est appliqué. / This thesis deals with adapting the level of consistency during solving a constraint satisfaction problem (CSP). It focuses on the use of local consistency properties stronger than arc consistency (AC) to improve the CSP solving efficiency. Local consistency properties stronger than arc consistency are generally expensive to maintain in a constraint network. Therefore, these local consistencies are seldom used in practice. This thesis gives several contributions to benefit from the filtering power of local consistencies stronger than AC while avoiding the high cost of maintaining them in the whole constraint network and throughout the search. First, we introduce the parameterized local consistency (p-LC), an original approach that allows us to define intermediate levels of consistency between AC and a local consistency LC stronger than AC. Then, we present the instantiation of the parameterized local consistency approach to maxRPC and SAC, two consistencies stronger than AC. This leads to two parameterized consistencies, namely p-maxRPC and p-SAC. After giving the definitions of p-maxRPC and p-SAC, we present the algorithm p-maxRPC3, that achieves p-maxRPC and the algorithm p-SAC1, for achieving p-SAC in a constraint network. We show experimentally that maintaining an intermediate level of consistency p-LC, can give a good compromise between filtering power and the computational cost of maintaining this level of consistency. We also show that for each instance of CSP we can find a parameter that gives this good compromise. The parameterized local consistency approach does not specify how the parameter can be chosen a priori. Hence, we propose two techniques to automatically adjust the parameter p. In fact, both techniques don't use a single parameter, but several parameters. Each parameter is mapped to a part of the problem and it is automatically and locally adjusted during search. Finally, we propose POAC1, the first algorithm achieving partition-one-AC (POAC) in a constraint network. We compare POAC to SAC and we found that POAC converges faster than SAC to the fixed point due to its ability to prune values from all variable domains when being enforced on a given variable. Based on this observation, we proposed APOAC, an adaptive version of POAC, that monitors the number of variables on which to enforce POAC.

Les besoins de l'industrie des jeux vidéo sont en constante évolution. Dans le domaine de l'intelligence artificielle, nous identifions dans le chapitre 1, les différents besoins de l'industrie dans ce domaine. Nous pensons que la conception d'une solution d'apprentissage de comportements par imitation qui soit fonctionnelle et efficace permettrait de couvrir la plupart de ces besoins. Dans le chapitre 2, nous montrons que les techniques d'extraction de données peuvent être très utiles pour offrir une telle solution. Cependant, ces techniques ne sont pas suffisantes pour construire automatiquement un comportement complet qui serait utilisable dans les jeux vidéo modernes. Dans le chapitre 3, nous proposons un modèle générique pour apprendre des comportements en imitant des joueurs humains : Orion. Ce modèle est composé de deux parties, un modèle structurel et un modèle comportemental. Le modèle structurel propose un framework généraliste d'exploration de données, fournissant une abstraction des différentes méthodes utilisées dans ce domaine de recherche. Ce framework nous permet de construire un outil d'usage général avec de meilleures possibilités de visualisation que les outils d'extraction de données existants. Le modèle comportemental est conçu pour intégrer des techniques d'exploration de données dans une architecture plus générale et repose sur les Behavior Trees. Dans le chapitre 4, nous illustrons comment nous utilisons notre modèle en mettant en oeuvre le comportement des joueurs dans les jeux Pong et UT3 en utilisant Orion. Dans le chapitre 5, nous identifions les améliorations possibles, à la fois de notre outil d'extraction de données et de notre modèle comportemental. / The video game industry's needs are constantly changing. In the field of artificial intelligence, we identify inchapter 1, the different needs of industry in this area. We believe that the design of a learning behavior through imitation solution that is functional and efficient would cover most of these needs. In chapter 2, we show that data mining techniques can be very useful to provide such a solution. However, for now, these techniques are not sufficient to automatically build a comprehensive behavior that would be usable in modern video games. In chapter 3, we propose a generic model to learn behavior by imitating human players: Orion.This model consists of two parts, a structural model and a behavioral model. The structural model provides a general data mining framework, providing an abstraction of the different methods used in this research. This framework allows us to build a general purpose tool with better possibilities for visualizing than existing data mining tools. The behavioral model is designed to integrate data mining techniques in a more general architecture and is based on the Behavior Trees. In chapter 4, we illustrate how we use our model by implementing the behavior of players in the Pong and Unreal Tournament 3 games using Orion. In chapter 5,we identify possible improvements, both of our data mining framework and our behavioral model.

Dans cette thèse nous étudions le rôle de la motivation intrinsèque dans l’émergence et le développement des systèmes communicationnels. Notre objectif est d’explorer comment des populations d’agents artificiels peuvent utiliser un système de motivation computationnel particulier, appelé l’autotelic principle, pour réguler leur développement linguistique et les dynamiques qui en résultent au niveau de la population.Nous proposons d’abord une mise en œuvre concrète de l’autotelic principle. Le noyau de ce système repose sur l’équilibre des défis, des tâches à accomplir afin d’atteindre un objectif, et des compétences, les capacités que le système peut utiliser pour accomplir les différentes tâches. La relation entre les deux éléments n’est pas stable mais se déstabilise régulièrement lorsque de nouvelles compétences sont acquises, ce qui permet au système de tenter des défis de plus grande complexité. Ensuite, nous testons l’utilité de ce système de motivation dans une série d’expériences sur l’évolution du langage. Dans le premier ensemble d’expériences, une population d’agents artificiels doit développer une langue pour se référer à des objets ayant des caractéristiques discrètes. Ces expériences se concentrent sur la façon dont les systèmes communicatifs non ambigus peuvent émerger lorsque l’autotelic principle est utilisé pour réguler le développement du langage en étapes de difficulté croissante. Dans le deuxième ensemble d’expériences, les agents doivent créer un langage artificiel pour communiquer sur des couleurs. Dans cette partie, on explore comment le système de motivation peut contrôler la complexité linguistique des interactions pour un domaine continu et on examine aussi la validité de l’autotelic principle en tant que mécanisme permettant de réguler simultanément plusieurs stratégies linguistiques de difficulté similaire. En résumé, nous avons démontré à travers de notre travail que l’autotelic principle peut être utilisé comme un mécanisme général pour réguler la complexité du langage développé de manière autonome en domaines discrets et continus. / This thesis studies the role of intrinsic motivation in the emergence and development of communicative systems in populations of artificial agents. To be more specific, our goal is to explore how populations of agents can use a particular motivation system called autotelic principle to regulate their language development and the resulting dynamics at the population level.To achieve this, we first propose a concrete implementation of the autotelic principle. The core of this system is based on the balance between challenges, tasks to be done to achieve a goal, and skills, the abilities the system can employ to accomplish the different tasks. The relation between the two elements is not steady but regularly becomes destabilised when new skills are learned, which allows the system to attempt challenges of increasing complexity. Then, we test the usefulness of the autotelic principle in a series of language evolution experiments. In the first set of experiments, a population of artificial agents should develop a language to refer to objects with discrete values. These experiments focus on how unambiguous communicative systems can emerge when the autotelic principle is employed to scaffold language development into stages of increasing difficulty. In the second set of experiments, agents should agree on a language to communicate with about colour samples. In this part, we explore how the motivation system can regulate the linguistic complexity of interactions for a continuous domain and examine the value of the autotelic principle as a mechanism to control several language strategies simultaneously. To summarise, we have shown through our work that the autotelic principle can be used as a general mechanism to regulate complexity in language emergence in an autonomous way for discrete and continuous domains.