Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-08-07T19:16:02Z No. of bitstreams: 1 DissRSJ.pdf: 7098556 bytes, checksum: 78b5b020899e1b4ef3e1fefb18d32443 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-08-07T19:18:39Z (GMT) No. of bitstreams: 1 DissRSJ.pdf: 7098556 bytes, checksum: 78b5b020899e1b4ef3e1fefb18d32443 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-08-07T19:18:50Z (GMT) No. of bitstreams: 1 DissRSJ.pdf: 7098556 bytes, checksum: 78b5b020899e1b4ef3e1fefb18d32443 (MD5) / Made available in DSpace on 2017-08-07T19:28:30Z (GMT). No. of bitstreams: 1 DissRSJ.pdf: 7098556 bytes, checksum: 78b5b020899e1b4ef3e1fefb18d32443 (MD5) Previous issue date: 2015-05-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Data mining aims at extracting useful information from a Database (DB). The mining process enables, also, to analyze the data (e.g. correlations, predictions, chronological relationships, etc.). The work described in this document proposes an approach to deal with temporal knowledge extraction from a DB and describes the implementation of this approach, as the computational system called S_MEMIS+AR. The system focuses on the process of finding frequent temporal patterns in a DB and generating temporal association rules, based on the elements contained in the frequent patterns identified. At the end of the process performs an analysis of the temporal relationships between time intervals associated with the elements contained in each pattern using the binary relationships described by the Allen´s Interval Algebra. Both, the S_MEMISP+AR and the algorithm that the system implements, were subsidized by the Apriori, the MEMISP and the ARMADA approaches. Three experiments considering two different approaches were conducted with the S_MEMISP+AR, using a DB of sale records of products available in a supermarket. Such experiments were conducted to show that each proposed approach, besides inferring new knowledge about the data domain and corroborating results that reinforce the implicit knowledge about the data, also promotes, in a global way, the refinement and extension of the knowledge about the data. / A mineração de dados tem como objetivo principal a extração de informações úteis a partir de uma Base de Dados (BD). O processo de mineração viabiliza, também, a realização de análises dos dados (e.g, identificação de correlações, predições, relações cronológicas, etc.). No trabalho descrito nesta dissertação é proposta uma abordagem à extração de conhecimento temporal a partir de uma BD e detalha a implementação dessa abordagem por meio de um sistema computacional chamado S_MEMISP+AR. De maneira simplista, o sistema tem como principal tarefa realizar uma busca por padrões temporais em uma base de dados, com o objetivo de gerar regras de associação temporais entre elementos de padrões identificados. Ao final do processo, uma análise das relações temporais entre os intervalos de duração dos elementos que compõem os padrões é feita, com base nas relações binárias descritas pelo formalismo da Álgebra Intervalar de Allen. O sistema computacional S_MEMISP+AR e o algoritmo que o sistema implementa são subsidiados pelas propostas Apriori, ARMADA e MEMISP. Foram realizados três experimentos distintos, adotando duas abordagens diferentes de uso do S_MEMISP+AR, utilizando uma base de dados contendo registros de venda de produtos disponibilizados em um supermercado. Tais experimentos foram apresentados como forma de evidenciar que cada uma das abordagens, além de inferir novo conhecimento sobre o domínio de dados e corroborar resultados que reforçam o conhecimento implícito já existente sobre os dados, promovem, de maneira global, o refinamento e extensão do conhecimento sobre os dados.

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)

Automated Planning is an active area within Artificial Intelligence. With the help of computers we can quickly find good plans in complicated problem domains, such as planning for search and rescue after a natural disaster. When planning in realistic domains the exact duration of an action generally cannot be predicted in advance. Temporal planning therefore tends to use upper bounds on durations, with the explicit or implicit assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false. If we finish cooking too early, the dinner will be cold before everyone is at home and can eat. Simple Temporal Networks with Uncertainty (STNUs) allow us to model such situations. An STNU-based planner must verify that the temporal problems it generates are executable, which is captured by the property of dynamic controllability (DC). If a plan is not dynamically controllable, adding actions cannot restore controllability. Therefore a planner should verify after each action addition whether the plan remains DC, and if not, backtrack. Verifying dynamic controllability of a full STNU is computationally intensive. Therefore, incremental DC verification algorithms are needed. We start by discussing two existing algorithms relevant to the thesis. These are the very first DC verification algorithm called MMV (by Morris, Muscettola and Vidal) and the incremental DC verification algorithm called FastIDC, which is based on MMV. We then show that FastIDC is not sound, sometimes labeling networks as dynamically controllable when they are not.  We analyze the algorithm to pinpoint the cause and show how the algorithm can be modified to correctly and efficiently detect uncontrollable networks. In the next part we use insights from this work to re-analyze the MMV algorithm. This algorithm is pseudo-polynomial and was later subsumed by first an n5 algorithm and then an n4 algorithm. We show that the basic techniques used by MMV can in fact be used to create an n4 algorithm for verifying dynamic controllability, with a new termination criterion based on a deeper analysis of MMV. This means that there is now a comparatively easy way of implementing a highly efficient dynamic controllability verification algorithm. From a theoretical viewpoint, understanding MMV is important since it acts as a building block for all subsequent algorithms that verify dynamic controllability. In our analysis we also discuss a change in MMV which reduces the amount of regression needed in the network substantially. In the final part of the thesis we show that the FastIDC method can result in traversing part of a temporal network multiple times, with constraints slowly tightening towards their final values.  As a result of our analysis we then present a new algorithm with an improved traversal strategy that avoids this behavior.  The new algorithm, EfficientIDC, has a time complexity which is lower than that of FastIDC. We prove that it is sound and complete.

From the Motivation: „Description Logics (DLs) are a family of formalisms well-suited for the representation of and reasoning about knowledge. Whereas most Description Logics represent only static aspects of the application domain, recent research resulted in the exploration of various Description Logics that allow to, additionally, represent temporal information, see [4] for an overview. The approaches to integrate time differ in at least two important aspects: First, the basic temporal entity may be a time point or a time interval. Second, the temporal structure may be part of the semantics (yielding a multi-dimensional semantics) or it may be integrated as a so-called concrete domain. Examples for multi-dimensional point-based logics can be find in, e.g., [21;29], while multi-dimensional interval-based logics are used in, e.g., [23;2]. The concrete domain approach needs some more explanation. Concrete domains have been proposed by Baader and Hanschke as an extension of Description Logics that allows reasoning about 'concrete qualities' of the entities of the application domain such as sizes, length, or weights of real-worlds objects [5]. Description Logics with concrete domains do usually not use a fixed concrete domain; instead the concrete domain can be thought of as a parameter to the logic. As was first described in [16], if a 'temporal' concrete domain is employed, then concrete domains may be point-based, interval-based, or both. ...”

We consider a number of temporal logics, some interval-based and some instant-based, and the choices that have to be made if we need to construct a computational framework for such a logic. We consider the axiomatisation of the accessibility relations of the underlying temporal structures when we are using a modal language as well as the formulation of axioms for distinguishing concepts like actions, events, processes and so on for systems using first-order languages. Finally, we briefly discuss the fields of application of temporal logics and list a number of fields that looks promising for further research. / Computer Science & Information Systems / M.Sc.(Computer Science)

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.

We consider a number of temporal logics, some interval-based and some instant-based, and the choices that have to be made if we need to construct a computational framework for such a logic. We consider the axiomatisation of the accessibility relations of the underlying temporal structures when we are using a modal language as well as the formulation of axioms for distinguishing concepts like actions, events, processes and so on for systems using first-order languages. Finally, we briefly discuss the fields of application of temporal logics and list a number of fields that looks promising for further research. / Computer Science and Information Systems / M.Sc.(Computer Science)

Les travaux de recherche développés dans cette thèse concernent la mise en oeuvre d'un système de vidéo surveillance intelligente en milieu hospitalier. Dans le contexte d'une application en unité de soins intensifs médicale, nous introduisons la notion originale de Boite Noire Médicale et nous proposons un nouveau système de monitoring visuel de Détection Automatique de Situations à risque et d'Alerte (DASA) basé sur un système de vidéosurveillance multi-caméra intelligent. L'objectif étant d'interpréter les flux d'informations visuelles et de détecter en temps réel les situations à risque afin de prévenir l'équipe médicale et ensuite archiver les évènements dans une base de donnée vidéo qui représente la Boite Noire Médicale. Le système d'interprétation est basé sur des algorithmes de reconnaissance de scénarios qui exploitent les Modèles de Markovs Cachés (MMCs). Une extension du modèle MMC standard est proposé afin de gérer la structure hiérarchique interne des scénarios et de contrôler la durée de chaque état du modèle markovien. La contribution majeure de ce travail repose sur l'intégration d'un raisonnement de type évènementiel, pour gérer la décision de reconnaissance en tenant compte des imperfections des informations disponibles. Les techniques de reconnaissance de scénarios proposées ont été testées et évaluées sur une base de séquences vidéo médicales et comparés aux modèles de Markov cachés probabilistiques classiques. / This thesis focuses on the study and the implementation of an intelligent visual monitoring system in hospitals. In the context of an application for patient monitoring in mediacal intensive care unit, we introduce an original concept of the Medical Black Box and we propose a new system for visual monitoring of Automatic Detection of risk Situations and Alert (DASA) based on a CCTV system with network smart camera. The aim is to interpret the visual information flow and to detect at real-time risk situations to prevent the mediacl team and then archive the events in a video that is based Medical Black Box data. The interpretation system is based on scenario recognition algorithms that exploit the Hidden Markov Models (HMM). An extension of the classic model of HMM is proposed to handle the internal reporting structure of the scenarios and to control the duration of each state of the Markov model. The main contribution of this work relies on the integration of an evidential reasoning, in order to manage the recognition decision taking into account the imperfections of available information. The proposed scenarios recognition method have been tested and assessed on database of medical video sequences and compared to standard probabilistic Hidden Markov Models.

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.