The concept of proximity is an important aspect of human reasoning. Despite the diversity of applications that require proximity measures, the most intuitive notion is that of spatial nearness. The aim of this thesis is to investigate the underpinnings of the notion of nearness, propose suitable formalisations and apply them to the processing of GIS data. More particularly, this work offers a framework for spatial proximity that supports the development of more intuitive tools for users of geographic data processing applications. Many of the existing spatial reasoning formalisms do not account for proximity at all while others stipulate it by using natural language expressions as symbolic values. Some approaches suggest the association of spatial relations with fuzzy membership grades to be calculated for locations in a map using Euclidean distance. However, distance is not the only factor that influences nearness perception. Hence, previous work suggests that nearness should be defined from a more basic notion of influence area. I argue that this approach is flawed, and that nearness should rather be defined from a new, richer notion of impact area that takes both the nature of an object and the surrounding environment into account. A suitable notion of nearness considers the impact areas of both objects whose degree of nearness is assessed. This is opposed to the common approach of only taking one of both objects, seen as a reference to assess the nearness of the other to it, into consideration. Cognitive findings are incorporated to make the framework more relevant to the users of Geographic Information Systems (GIS) with respect to their own spatial cognition. GIS users bring a wealth of knowledge about physical space, particularly geographic space, into the processing of GIS data. This is taken into account by introducing the notion of context. Context represents either an expert in the context field or information from the context field as collated by an expert. In order to evaluate and to show the practical implications of the framework, experiments are conducted on a GIS dataset incorporating expert knowledge from the Touristic Road Travel domain.

Autonomous systems require a lot of information about the environment in which they operate in order to perform different high-level tasks. The information is made available through various sources, such as remote and on-board sensors, databases, GIS, the Internet, etc. The sensory input especially is incrementally available to the systems and can be represented as streams. High-level tasks often require some sort of reasoning over the input data, however raw streaming input is often not suitable for the higher level representations needed for reasoning. DyKnow is a stream processing framework that provides functionalities to represent knowledge needed for reasoning from streaming inputs. DyKnow has been used within a platform for task planning and execution monitoring for UAVs. The execution monitoring is performed using formula progression with monitor rules specified as temporal logic formulas. In this thesis we present an analysis for providing spatio-temporal functionalities to the formula progressor and we extend the formula progression with spatial reasoning in RCC-8. The result implementation is capable of evaluating spatio-temporal logic formulas using progression over streaming data. In addition, a ROS implementation of the formula progressor is presented as a part of a spatio-temporal stream reasoning architecture in ROS. / Collaborative Unmanned Aircraft Systems (CUAS)

Real-time strategy (RTS) games constitute one of the largest game genres today and have done so for the past decade. A central feature of real-time strategy games is opponent AI which is suggestively the “last frontier” of game development because the focus of research has primarily been on other components, graphics in particular. This has led to AI research being largely ignored within the commercial game industry but several methods have recently been suggested for improving the strategic ability of AI agents in real-time strategy games. The aim of this project is to evaluate how a method called qualitative spatial reasoning can improve AI on a tactical level in a selected RTS game. An implementation of an AI agent that uses qualitative spatial reasoning has been obtained and an evaluation of its performance in an RTS game example monitored and analysed. The study has shown that qualitative spatial reasoning affects AI agent’s behaviour significantly and indicates that it can be used to deduce a rule-base that increases the unpredictability and performance of the agent.

In the last two decades, qualitative spatial representation and reasoning, and in particular spatial logics, have been the subject of an increased interest from the Artificial Intelligence community. By a spatial logic, we understand a formal language whose variables range over subsets of a fixed topological space, called regions, and whose non-logical primitives have fixed geometric meanings. A spatial logic for reasoning about regions in a Euclidean space is called a Euclidean spatial logic. We consider first-order and quantifier-free Euclidean spatial logics with primitives for topological relations and operations, the property of convexity and the ternary relation of being closer-than. We mainly focus on the computational properties of such logics, but we also obtain interesting model-theoretic results. We provide a systematic overview of the computational properties of firstorder Euclidean spatial logics and fill in some of the gaps left by the literature. We establish upper complexity bounds for the (undecidable) theories of logics based on Euclidean spaces of dimension greater than one, which yields tight complexity bounds for all but two of these theories. In contrast with these undecidability results, we show that the topological theories based on one-dimensional Euclidean space are decidable, but non-elementary. We also study the computational properties of quantifier-free Euclidean spatial logics, and in particular those able to express the property of connectedness. It is known that when variables range over regions in the Euclidean plane, one can find formulas in these languages satisfiable only by regions with infinitely many connected components. Using this result, we show that the corresponding logics are undecidable. Further, we show that there exist formulas that are satisfiable in higher-dimensional Euclidean space, but only by regions with infinitely many connected components. We finish by outlining how the insights gained from this result were used (by another author) to show the undecidability of certain quantifier-free Euclidean spatial logics in higher dimensions.

No description available.

Um sistema artificial pode usar raciocínio espacial qualitativo para inferir informações sobre seu ambiente tridimensional a partir de imagens bidimensionais. Inferências realizadas com base em raciocínio espacial qualitativo devem ser capazes de lidar com incertezas. Neste trabalho investigamos a utilização de técnicas probabilísticas para tornar o raciocínio espacial qualitativo mais robusto a incertezas e aplicável a agentes móveis em ambientes reais. Investigamos uma formalização de raciocínio espacial com lógica de descrição probabilística em um subdomínio de tráfego. Desenvolvemos também um método que combina raciocínio espacial qualitativo com um filtro Bayesiano para desenvolver dois sistemas que foram aplicados na auto localização de um robô móvel. Executamos dois experimentos de auto localização; um utilizando a teoria de relações qualitativas percebíveis sobre sombra com filtro Bayesiano; e outro utilizando o cálculo de oclusão de regiões e o cálculo de direção com filtro Bayesiano. Ambos os sistemas obtiveram resultados positivos onde somente o raciocínio espacial qualitativo não foi capaz de inferir a localização do robô. Os experimentos com dados reais mostraram robustez aos ruídos e à informação parcial. / An artificial system can use qualitative spatial reasoning to obtain information about its tridimensional environment, from bi-dimensional images. Inferences produced by qualitative spatial reasoning must be able to deal with uncertainty. This work investigates the use of probabilistic techniques to make qualitative spatial reasoning more robust against uncertainty, and better applicable to mobile agents in real environments. The work investigates a formalization of spatial reasoning using probabilistic description logics in a traffic domain. Additionally, a method is presented that combines qualitative spatial reasoning with a Bayesian filter, to develop two systems that are applied to self-localization of mobile robots. Two experiments are described; one using the theory of perceptual qualitative relations about shadows; the other using occlusion calculus and direction calculus. Both systems are combined with a Bayesian filter producing positive results in situations where qualitative spatial reasoning alone cannot infer robot location. Experiments with real data show robustness to noise and partial information.

El objetivo de esta tesis es proponer mejoras en modelos existentes de razonamiento espacial cualitativo con relaciones cardinales, y proponer nuevos modelos y técnicas de razonamiento utilizando algunos resultados previos del razonamiento temporal cualitativo. Los modelos propuestos se basan en dos formalismos muy utilizados para razonamiento cualitativo: los Problemas de Satisfacción de Restricciones y las Lógicas Modales. / The main goal of this PhD Thesis is to propose improvements to existing models for qualitative spatial reasoning with cardinal direction relations, and to propose new models and reasoning techniques using some previous results from qualitative temporal reasoning. The proposed models are based on two widely used formalisms for Qualitative Reasoning: Constraint Satisfaction Problems and Modal Logics.

Um sistema artificial pode usar raciocínio espacial qualitativo para inferir informações sobre seu ambiente tridimensional a partir de imagens bidimensionais. Inferências realizadas com base em raciocínio espacial qualitativo devem ser capazes de lidar com incertezas. Neste trabalho investigamos a utilização de técnicas probabilísticas para tornar o raciocínio espacial qualitativo mais robusto a incertezas e aplicável a agentes móveis em ambientes reais. Investigamos uma formalização de raciocínio espacial com lógica de descrição probabilística em um subdomínio de tráfego. Desenvolvemos também um método que combina raciocínio espacial qualitativo com um filtro Bayesiano para desenvolver dois sistemas que foram aplicados na auto localização de um robô móvel. Executamos dois experimentos de auto localização; um utilizando a teoria de relações qualitativas percebíveis sobre sombra com filtro Bayesiano; e outro utilizando o cálculo de oclusão de regiões e o cálculo de direção com filtro Bayesiano. Ambos os sistemas obtiveram resultados positivos onde somente o raciocínio espacial qualitativo não foi capaz de inferir a localização do robô. Os experimentos com dados reais mostraram robustez aos ruídos e à informação parcial. / An artificial system can use qualitative spatial reasoning to obtain information about its tridimensional environment, from bi-dimensional images. Inferences produced by qualitative spatial reasoning must be able to deal with uncertainty. This work investigates the use of probabilistic techniques to make qualitative spatial reasoning more robust against uncertainty, and better applicable to mobile agents in real environments. The work investigates a formalization of spatial reasoning using probabilistic description logics in a traffic domain. Additionally, a method is presented that combines qualitative spatial reasoning with a Bayesian filter, to develop two systems that are applied to self-localization of mobile robots. Two experiments are described; one using the theory of perceptual qualitative relations about shadows; the other using occlusion calculus and direction calculus. Both systems are combined with a Bayesian filter producing positive results in situations where qualitative spatial reasoning alone cannot infer robot location. Experiments with real data show robustness to noise and partial information.

Les premiers robots sont apparus dans les usines, sous la forme d'automates programmables. Ces premières formes robotiques ont le plus souvent un nombre très limité de capteurs et se contentent de répéter une séquence de mouvements et d'actions. De nos jours, de plus en plus de robots ont à interagir ou coopérer avec l'homme, que se soit sur le lieu de travail avec les robots coéquipiers ou dans les foyers avec les robots d'assistance. Mettre un robot dans un environnement humain soulève de nombreuses problématiques. En effet, pour évoluer dans le même environnement que l'homme et comprendre cet environnement, le robot doit être doté de capacités cognitives appropriées. Au delà de la compréhension de l'environnement matériel, le robot doit être capable de raisonner sur partenaires humains afin de pouvoir collaborer avec eux ou les servir au mieux. Lorsque le robot interagit avec des humains, l'accomplissement de la tâche n'est pas un critère suffisant pour quantifier la qualité de l'interaction. En effet, l'homme étant un être social, il est important que le robot puisse avoir des mécanismes de raisonnement lui permettant d'estimer également l'état mental de l'homme pour améliorer sa compréhension et son efficacité, mais aussi pour exhiber des comportements sociaux afin de se faire accepter et d'assurer le confort de l'humain. Dans ce manuscrit, nous présentons tout d'abord une infrastructure logicielle générique (indépendante de la plateforme robotique et des capteurs utilisés) qui permet de construire et maintenir une représentation de l'état du monde à l'aide de l'agrégation des données d'entrée et d'hypothèses sur l'environnement. Cette infrastructure est également en charge de l'évaluation de la situation. En utilisant l'état du monde qu'il maintient à jour, le système est capable de mettre en oeuvre divers raisonnements spatio-temporels afin d'évaluer la situation de l'environnement et des agents (humains et robots) présents. Cela permet ainsi d'élaborer et de maintenir une représentation symbolique de l'état du monde et d'avoir une connaissance en permanence de la situation des agents. Dans un second temps, pour aller plus loin dans la compréhension de la situation des humains, nous expliquerons comment nous avons doté notre robot de la capacité connue en psychologie développementale et cognitive sous le nom de “théorie de l'esprit” concrétisée ici par des mécanismes permettant de raisonner en se mettant à la place de l'humain, c'est à dire d'être doté de “prise de perspective”. Par la suite nous expliquerons comment l'évaluation de la situation permet d'établir un dialogue situé avec l'homme, et en quoi la capacité de gérer explicitement des croyances divergentes permet d'améliorer la qualité de l'interaction et la compréhension de l'homme par le robot. Nous montrerons également comment la connaissance de la situation et la possibilité de raisonner en se mettant à la place de l'homme permet une reconnaissance d'intentions appropriée de celui-ci et comment nous avons pu grâce à cela doter notre robot de comportements proactifs pour venir en aide à l'homme . Pour finir, nous présenterons une étude présentant un système de maintien d'un modèle des connaissances de l'homme sur diverses tâches et qui permet une gestion adaptée de l'interaction lors de l'élaboration interactive et l'accomplissement d'un plan partagé. / The first robots appeared in factories, in the form of programmable controllers. These first robotic forms usually had a very limited number of sensors and simply repeated a small set of sequences of motions and actions. Nowadays, more and more robots have to interact or cooperate with humans, whether at the workplace with teammate robots or at home with assistance robots. Introducing a robot in a human environment raises many challenges. Indeed, to evolve in the same environment as humans, and to understand this environment, the robot must be equipped with appropriate cognitive abilities. Beyond understanding the physical environment, the robot must be able to reason about human partners in order to work with them or serve them best. When the robot interacts with humans, the fulfillment of the task is not a sufficient criterion to quantify the quality of the interaction. Indeed, as the human is a social being, it is important that the robot can have reasoning mechanisms allowing it to assess the mental state of the human to improve his understanding and efficiency, but also to exhibit social behaviors in order to be accepted and to ensure the comfort of the human. In this manuscript, we first present a generic framework (independent of the robotic platform and sensors used) to build and maintain a representation of the state of the world by using the aggregation of data entry and hypotheses on the environment. This infrastructure is also in charge of assessing the situation. Using the state of the world it maintains, the system is able to utilize various spatio-temporal reasoning to assess the situation of the environment and the situation of the present agents (humans and robots). This allows the creation and maintenance of a symbolic representation of the state of the world and to keep awareness of each agent status. Second, to go further in understanding the situation of the humans, we will explain how we designed our robot with the capacity known in developmental and cognitive psychology as "theory of mind", embodied here by mechanisms allowing the system to reason by putting itself in the human situation, that is to be equipped with "perspective-taking" ability. Later we will explain how the assessment of the situation enables a situated dialogue with the human, and how the ability to explicitly manage conflicting beliefs can improve the quality of interaction and understanding of the human by the robot. We will also show how knowledge of the situation and the perspective taking ability allows proper recognition of human intentions and how we enhanced the robot with proactive behaviors to help the human. Finally, we present a study where a system maintains a human model of knowledge on various tasks to improve the management of the interaction during the interactive development and fulfillment of a shared plan.

Le paysage numérique de la culture française et mondiale subit de grands bouleversements depuis une quinzaine d’années avec des mutations historiques des médias, de leur format traditionnel au format numérique, tirant avantageusement parti des nouveaux moyens de communication et des dispositifs mobiles aujourd’hui popularisés. Aux côtés de formes culturelles ayant achevé, ou étant en passe d’achever, leur transition vers le numérique, la bande dessinée tâtonne encore pour trouver sa place dans l’espace du tout dématérialisé. En parallèle de l’émergence de jeunes auteurs créant spécifiquement pour ces nouveaux supports de lecture que sont ordinateurs, tablettes et smartphones, plusieurs acteurs du monde socio-économique s’intéressent à la valorisation du patrimoine existant. Les efforts se concentrent autant sur une démarche d’adaptation des œuvres aux nouveaux paradigmes de lecture que sur celle d’une indexation de leur contenu facilitant la recherche d’informations dans des bases d’albums numérisés ou dans des collections d’œuvres rares. La problématique est double, il s’agit premièrement d’être en mesure d’identifier la structure d’une planche de bande dessinée en se basant sur des extractions de primitives, issues d’une analyse d’image, validées et corrigées grâce à l’action conjointe de deux ontologies, la première manipulant les extractions d’images bas-niveau, la deuxième modélisant les règles de composition classiques de la bande dessinée franco-belge. Dans un second temps l’accent est mis sur l’enrichissement sémantique des éléments identifiés comme composants individuels d’une planche en s’appuyant sur les relations spatiales qu’ils entretiennent les uns avec les autres ainsi que sur leurs caractéristiques physiques intrinsèques. Ces annotations peuvent porter sur des éléments seuls (place d’une case dans la séquence de lecture) ou sur des liens entre éléments (texte prononcé par un personnage). / Since the beginning of the twenty-first century, the cultural industry, both in France and worldwide, has been through a massive and historical mutation. They have had to adapt to the emerging digital technology represented by the Internet and the new handheld devices such as smartphones and tablets. Although some industries successfully transfered a piece of their activity to the digital market and are about to find a sound business model, the comic books industry keeps looking for the right solution and has not yet produce anything as convincing as the music or movie offers. While many new young authors and writers use their creativity to produce specifically digital designed pieces of art, some other minds are focused on the preservation and the development of the already existing heritage. So far, efforts have been concentrated on the transfer from printed to digital support, with a special attention given to their specific features and how they can be used to create new reading conventions. There has also been some concerns about the content indexing, which is a hard task regarding the large amount of data created since the very beginning of the comics history. From a scientific point of view, there are several issues related to these goals. First, it implies to be able to identify the underlying structure of a comic books page. This comes through the extraction of the page's components, their validation and their correction based on the representation and reasoning capacities of two ontologies. The first one focus on the representation of the image analysis concepts and the second one represents the comic books domain knowledge. Secondly, a special attention is given to the semantic enhancement of the extracted elements, based on their spatial relations to each others and on their own characteristics. These annotations can be related to elements only (e.g. the position of a panel in the reading sequence), or to the bound between several elements (e.g. the text pronounced by a character).