Spatio-temporal reasoning is the area of automated reasoning about space and time and is important in the field of robotics. It is desirable for an autonomous robot to have the ability to reason about both time and space. ST0 is a logic that allows for such reasoning by, among other things, defining a formalism used to describe the relationship between spatial regions and a calculus that allows for deducing further information regarding such spatial relations. An extension of ST0 is ST1 that can be used to describe the relationship between spatial entities across time-points (inter-temporal relations) while ST0 is constrained to doing so within a single time-point. This allows for a better ability of expressing how spatial entities change over time. A major obstacle in using ST1 in practise however, is the fact that any observations made regarding spatial relations between regions is constrained to the time-point in which the observation was made, so we are unable to observe inter-temporal relations. Further complicating things is the fact that deducing such inter-temporal relations is not possible without a frame of reference. This thesis examines one method of overcoming these problems by considering the concept of rigid regions which are assumed to always be unchanging and using them as the frame of reference, or as landmarks. The effectiveness of this method is studied by conducting experiments where a comparison is made between various landmark ratios with respect to the total number of regions under consideration. Results show that when a high degree of intra-temporal relations are fully or partially known, increasing the number of landmark regions will reduce the percentage of inter-temporal relations to be completely unknown. Despite this, very few inter-temporal relations can be fully determined even with a high ratio of landmark regions.

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)

Les relations spatiales entre les différentes régions dans une image sont utiles pour la compréhension et l'interprétation de la scène représentée. L'analyse Spatio-temporelle d'une scène implique l'intégration du temps dans des relations spatiales entre les objets en mouvement. Les relations spatio-temporelles sont définies dans un intervalle de temps utilisant la géométrie 3D ou l'extension de la géométrie 2D à la dimension temporelle. La modélisation des relations spatiales dynamiques prend en compte la position relative des objets et leurs relations directionnelles, ceci implique les relations topologiques, directionnelles et de distance. Ces relations sont étendues au domaine temporel. Dans notre travail, on décrit une méthode de combinaison d’information topologique et directionnelle où les relations d'Allen floues 1D sont appliquées au domaine spatial. La méthode proposée intègre le flou au niveau des relations. La méthode très gourmande initialement en temps de calcul en raison de l’approximation des objets ainsi qu'à l'algorithme de fuzzification des segments des sections longitudinales est améliorée en utilisant une approximation polygonale adaptée sur les objets considérés. L'algorithme du fuzzification des segments d'une section longitudinale inclut des opérateurs d'agrégation floue. Dans la méthode proposée, Les relations topologiques 2Dsont représentées par un histogramme. Les relations floues n'étant pas exhaustives, un algorithme de défuzzification des relations spatiales a été proposé pour réaliser un ensemble JEPD de relations spatiales. Cet ensemble de relations spatiales est représenté par un graphe de voisinage où chaque nœud du graphe représente la relation topologique et directionnelle. Cette méthode définit des relations spatio-temporelles en utilisant le modèle de données Espace-Temps. Un ensemble de relations spatio-temporelles est également fourni à l'aide de la stabilité topologique. Afin de valider le modèle, nous avons développé des applications fondées sur le raisonnement spatio-temporel proposé. Celui-ci a permit la création de tables de composition pour les relations spatiales topologiques structurées en sous-tables. Les entités de ces sous-tables sont liées les unes aux autres par des relations spatiales. Dans une seconde application, nous avons proposé une méthode de prédiction des évènements entre objets en mouvement fondée sur le même raisonnement spatio-temporel. Les objets en mouvement changeant de position à chaque instant, la prédiction de la nouvelle position spatiale d'un objet tient compte des états de relations spatiales calculées précédemment. / Spatial relations between different image regions are helpful in image understanding, interpretation and computer vision applications. Spatio-temporal analysis involves the integration of spatial relations changing over time between moving objects of a dynamic scene. Spatio-temporal relations are defined for a selected time interval using 3D geometry or extension of 2D object geometry to the time dimension with sequence occurrence of primitive events for each snapshot. Modeling dynamic spatial relations takes into account the relative object position and their directional relations; this involves the topological, directional and distance relations and their logical extension to the temporal domain. In this thesis, a method for combining topological and directional relations information is discussed where 1D temporal fuzzy Allen relations are applied in spatial domain. Initially, the method has a high computational cost. This computing cost is due to the object approximation and the fuzzification algorithm of segments. The computing time has been using polygonal object approximation. Fuzzification algorithm is replaced with fuzzy aggregation operators for segments of a longitudinal section. In this method, two dimensional topological relations are represented in a histogram. The representation method for two dimensional spatial relations has been changed. These fuzzy relations are not Jointly Exhaustive and Pairwise Disjoint (JEPD). An algorithm for defuzzification of spatial relations is proposed to realize JEPD set of spatial relations, these JEPD spatial relations are represented in a neighborhood graph. In this neighborhood graph, each node represents the topological and directional relation. This method is further extended for defining spatio-temporal relations using space and time data model, a set of spatio-temporal relations are also elaborated using the stability property in topology. In an application, a method for spatio-temporal reasoning based on this new model is developed. Spatio-temporal reasoning consists of developing the composition tables for spatial relations. Composition table for topological relations are rearranged into sub-tables. Entities in these sub-tables are related to each other and mathematical rules are defined for composition of spatial relations which elaborate the relation between entities of sub-tables. In another application, we propose a method for motion event predictions between moving objects. It is a similar process to the spatio-temporal reasoning. Dynamic objects occupy different places at different time points, these objects have multiple choices for subsequent positions and a unique history. Prediction about motion events take into account the history of a moving object and predict about the semantics of a motion event.

La modélisation de la dynamique des objets spatio-temporels fait partie des sujets de recherche pour le suivi et l'interprétation des changements affectant le globe terrestre. Pour cela, l'exploitation des images satellitaires se présente comme un moyen efficace qui aide à l'étude de la dynamique des phénomènes spatio-temporels qui peuvent se produire sur la surface de la Terre notamment l'urbanisation, la déforestation, la désertification, etc. Divers modèles et approches ont été proposés pour modéliser les évolutions des objets spatio-temporels. Toutes fois, chaque modèle présente une capacité limitée pour capturer l'évolution des différentes caractéristiques de l'environnement, en plus la structure de représentation utilisée par chaque modèle ne permet pas de saisir complètement la sémantique de l'évolution d'un objet spatio-temporel. Les travaux de notre thèse s'intéressent à la modélisation de la dynamique des objets spatio-temporels pour l'interprétation des changements en imagerie satellitaire. En conséquence, nous avons proposé dans un premier temps une architecture ontologiques multi-niveaux pour la représentation et la modélisation des objets et des processus spatio-temporels dynamiques. Également, nous avons présenté une nouvelle stratégie d'interprétation sémantique de scènes d'images satellites pour l'interprétation de changements. Le cadre applicatif concerne l'interprétation sémantique d'une scène d'images satellites pour l'interprétation des phénomènes de changements, tels que l'urbanisation et la déforestation. Le résultat obtenu est une carte de changements qui pourra guider une meilleure gestion de l'utilisation/couverture des sols. / Modeling the dynamics of spatio-temporal objects is part of the research subjects for monitoring and interpretation of the changes affecting the Earth. Satellite images are an effective way for studying the dynamics of spatio-temporal phenomena, including urbanization, deforestation, flooding, desertification, and so on, that can occur on the surface of the Earth. Various models and approaches have been proposed to model the evolution of the spatio-temporal objects. However, each of these models has a limited ability to capture the evolution of the different characteristics of the environment, and the representation structure used by each model does not fully capture the semantics of the evolution of a spatio-temporal object. The works of our thesis interested in modeling the dynamics of spatio-temporal objects for changes interpretation in satellite imagery. Therefore, we proposed initially a multi-level ontological architecture for representation and modeling the dynamic of spatio-temporal objects and process. Also, we have presented a new semantic scene interpretation strategy for change interpretation in remote sensing imagery. The application Framework concerns the semantic interpretation of a satellite images scenes for change interpretation of phenomena, such as urbanization and deforestation. The result is a change map that can guide better management of the land use/cover.

Parmi les différentes formes de raisonnement étudiées dans le contexte de l'intelligence artificielle, le raisonnement qualitatif permet d'inférer de nouvelles connaissances dans le contexte d'informations imprécises, incomplètes et dépourvues de valeurs numériques. Il permet par exemple de déduire de nouvelles informations à partir d'un ensemble d'informations spatiales telles que « la France est frontalière de l'Allemagne », « la Suisse est à l'est de la France », « l'Italie est en Europe » et « le Luxembourg est proche de la France ». Il peut également être utilisé pour résoudre des abstractions de problèmes quantitatifs difficiles à résoudre, afin par exemple d'accélérer la résolution de ces problèmes.De nombreux formalismes de raisonnement qualitatif ont été proposés dans la littérature. Ils ne se focalisent cependant que sur un seul aspect du monde, alors que la majorité des applications requièrent la prise en compte d'informations hétérogènes. Afin de répondre à ces besoins, plusieurs combinaisons et extensions de formalismes qualitatifs, comme le raisonnement spatio-temporel et le raisonnement multi-échelle, ont récemment été proposées dans la littérature. Le raisonnement spatio-temporel permet de raisonner dans le contexte d'informations spatiales et temporelles interdépendantes. Le raisonnement multi-échelle permet de raisonner avec des informations de précisions différentes, et en particulier de lever des incohérences apparentes.Dans cette thèse, nous nous intéressons au raisonnement multi-échelle, au raisonnement spatio-temporel et aux combinaisons de formalismes qualitatifs.Nous proposons d'étendre le raisonnement qualitatif temporel multi-échelle pour prendre en compte le fait que les intervalles de temps peuvent être perçus comme des instants à certaines échelles de précision, de formaliser intégralement ce raisonnement et d'étudier la décision de la cohérence dans ce contexte ainsi que sa complexité. Nous montrons en particulier que ce formalisme permet de décider la cohérence et que le problème de décision de la cohérence est NP-complet, même dans le cas le plus simple.En outre, nous proposons un cadre général permettant de raisonner sur les séquences temporelles d'informations qualitatives, une forme de description spatio-temporelle. Ce cadre permet notamment de raisonner dans le contexte d'évolutions complexes. Par exemple, les entités considérées peuvent avoir des caractéristiques préservées au cours du temps, évoluer de manière dépendante les unes par rapport aux autres, tout en ayant un comportement potentiellement irréversible et différent selon leur nature. De plus, dans ce cadre, le raisonnement est plus performant computationnellement que les approches de l'état de l'art. Nous étudions en particulier la décision de la cohérence dans le contexte spécifique de régions mobiles de taille constante, et montrons que ce cadre permet effectivement de décider la cohérence.De surcroît, nous proposons un cadre formel unifiant plusieurs formes d'extensions et de combinaisons de formalismes qualitatifs, incluant le raisonnement multi-échelle et les séquences temporelles. Ce cadre permet de raisonner dans le contexte de chacune de ces combinaisons et extensions, mais également d'étudier de manière unifiée la décision de la cohérence et sa complexité. Nous établissons en particulier deux théorèmes complémentaires garantissant que la décision de la cohérence est polynomiale, et nous les utilisons pour prouver que plusieurs fragments de séquences temporelles sont traitables.Nous généralisons également la définition principale de formalisme qualitatif afin d'inclure des formalismes qualitatifs exclus des définitions de la littérature, importants dans le cadre des combinaisons. / In this thesis, we are interested in qualitative multi-scale reasoning, qualitative spatio-temporal reasoning and combinations of qualitative formalisms.We propose to extend the multiscale temporal reasoning to take into account the fact that time intervals can be perceived as instants at certain scales of precision, to fully formalize this reasoning and to study its consistency problem. We show in particular that this formalism decides consistency and that the consistency problem is NP-complete, even in the simplest case.In addition, we propose a general framework for reasoning on temporal sequences of qualitative information, a form of spatio-temporal description. This framework allows for reasoning in the context of complex evolutions. For example, the considered entities may have characteristics preserved over time, evolve in a dependent manner with respect to each other, while having a potentially irreversible and different behavior depending on their nature. Moreover, in this context, reasoning is computationally more efficient than state-of-the-art approaches. In particular, we study the consistency problem in the specific context of constant-size moving regions, and show that this framework actually decides consistency.Furthermore, we propose a formal framework unifying several forms of extensions and combinations of qualitative formalisms, including multi-scale reasoning and temporal sequences. This framework allows one to reason in the context of each of these combinations and extensions, but also to study in a unified way the consistency problem. In particular, we establish two complementary theorems guaranteeing that the consistency problem is polynomial, and we use them to prove that several fragments of temporal sequences are tractable.