english version

 

Ph.D. thesis



    Modelowanie i przetwarzanie wiedzy czaso-przestrzennej. Model XCDC - aspekty teoretyczne oraz rozwiązania aplikacyjne

    Abstrakt

    Podstawowym celem rozprawy jest przedstawienie formalizmu XCDC (ang. eXtended Cardinal Direction Calculus), zbadanie jego własności oraz porównanie go pod względem możliwości reprezentacyjnych z innymi, szeroko stosowanymi technikami jakościowymi. Formalizm XCDC służy do modelowania wiedzy czaso-przestrzennej, tj. do tworzenia struktur matematycznych stanowiących reprezentację modelową stanów rzeczy (ze świata przedmiotowego).
    XCDC rozszerza możliwości klasycznego formalizmu CDC, pozwala na większą precyzję w reprezentacji rzeczywistych zależności przestrzennych, a ponadto umożliwia opis relacji czasowych oraz dynamicznych zmian zachodzących w badanym środowisku. Omawiamy szereg aspektów teoretycznych tego podejścia, w tym jego wybrane własności matematyczne. W szczególności definiujemy podstawowe operacje na strukturach modelu XCDC, co pozwala na uzasadnienie pewnych własności algebraicznych tworzonych struktur, m.in. tworzenia przez te struktury algebr Boole'a czy braku ich podzbioru spełniającego warunki relacji JEPD. Opierając się na zdefiniowanych operacjach oraz własnościach rzutów rozważanej przestrzeni euklidesowej R^3 (dwa wymiary przestrzenne, jeden wymiar czasowy) na płaszczyzny dwuwymiarowe (jedną przestrzenną i dwie czaso-przestrzenne), wprowadzamy również w sposób ścisły pojęcia zbiorów poprawnych i niepoprawnych relacji formalizmu XCDC. Omawiamy także kwestię jednoznaczności reprezentacji w modelu XCDC oraz problem tzw. relacji pozornych odpowiadających sytuacjom, w których funkcja przyporządkowująca parze obiektów czaso-przestrzennych strukturę XCDC nie jest różnowartościowa. Rozszerzamy też algorytm składania relacji Skiadopoulosa i Koubarakisa oraz definiujemy wskaźnik Edir pozwalający na porównywanie poziomu precyzji relacji XCDC. Ponadto porównujemy model XCDC z innymi podejściami jakościowymi (m.in. RCC-5 i RCC-8, ICD-5 i ICD-9, czy algebrą Allena i jej pochodnymi) charakteryzującymi się różnorodną formą opisu relacji czasowych, przestrzennych i czaso-przestrzennych oraz wzajemną nieredukowalnością ze względu na opisywanie przez nie innych aspektów tych relacji. W ramach analizy porównawczej, prezentujemy metody konwersji relacji wspomnianych modeli klasycznych do struktur XCDC, co pozwala na ocenę proponowanego przez nas modelu jako rozwiązania o szerokim wachlarzu możliwości reprezentacyjnych i wielu potencjalnych zastosowaniach.
    Następnie zwracamy uwagę na możliwość zastosowania proponowanych technik w systemach opartych na wejściu w języku naturalnym. Przestawiamy trzy opracowane przez nas eksperymenty z udziałem ochotników, których wyniki posłużyły za materiał empiryczny wykorzystany do weryfikacji modelu XCDC (m.in. jego użyteczności w interpretacji wyrażeń języka naturalnego). Ponadto wyniki eksperymentu posłużyły do opracowania zbioru TSREL składającego się z 34 relacji czaso-przestrzennych konceptualizowanych w języku naturalnym oraz do konstrukcji tabel konwersji elementów zbioru TSREL do struktur XCDC i odwrotnie. Pokazujemy także, że zbiór relacji TSREL można częściowo uporządkować relacją zdefiniowaną w oparciu o zależności pomiędzy odpowiednimi polami macierzy kierunkowo-relacyjnych. Uporządkowanie to pozwala ponadto traktować zbiór TSREL jako ontologię pojęć związanych z opisem czasu i przestrzeni (powiązanych relacją hiponimii), co w szczególności umożliwia zaawansowane wnioskowanie o zależnościach czaso-przestrzennych. Opracowaliśmy też algorytm interpretowania względnych relacji kierunkowych z korzystaniem struktury tzw. poczekalni. Zbadaliśmy również zagadnienia związane z jakościowymi relacjami odległościowymi oraz zaproponowaliśmy metodę składania takich zależności opartą na teorii zbiorów rozmytych.
    Wreszcie omawiamy rozwiązania aplikacyjne związane z formalizmem XCDC. W szczególności prezentujemy algorytm budowania mapy rozpatrywanego obszaru w bazie wiedzy systemu interpretowanej jako graf z kliką. Ponadto dyskutujemy zagadnienie wnioskowania czaso-przestrzennego opartego na konstrukcji ścieżki złożeń (stanowiącej rozszerzenie teoriografowego pojęcia ścieżki). Tematem rozważań jest również problematyka wyznaczanie lokalizacji zadanego obiektu (wyznaczenia takiej pozycji, która będzie najbardziej przydatna z punktu widzenia potencjalnego użytkownika), porównywanie relacji, czy weryfikację spójności danej bazy wiedzy, zwłaszcza przy niepełnym zbiorze relacji. Zaproponowane przez nas rozwiązania omawiamy także w kontekście prototypu systemu POLINT-112-SMS, zorientowanego na wspomaganie służb zabezpieczających dużą imprezę masową. W systemie tym model XCDC stanowi podstawę Modułu Czaso-Przestrzennego odpowiadającego za zbieranie, przetwarzanie oraz wnioskowanie na relacjach czaso-przestrzennych. Warto podkreślić, że system POLINT-112-SMS został, z powodzeniem, przetestowany w trakcie eksperymentów symulacyjnych, co wskazuje na realną użyteczność zaproponowanego formalizmu XCDC w praktycznych rozwiązaniach aplikacyjnych.



    Spatio-Temporal Knowledge Modeling and Processing. The XCDC Model - Theoretical Aspects and Applications

    Abstract

    In the Ph.D. thesis we introduce the XCDC (eXtended Cardinal Direction Calculus) formalism and analyze its properties. We also compare the XCDC with other widely used qualitative techniques. The XCDC formalism is designed for spatio-temporal knowledge modeling, i.e. for creating the mathematical structures which provide the model representation of the state of objects (from the real world). The XCDC extends the capabilities of the classical CDC formalism, provides greater precision in the representation of the real-world spatial relations, and also describe temporal relation and the dynamic changes taking place in an analysed environment. We discuss a number of theoretical aspects of this approach, including some of its mathematical properties. In particular, we define the basic operations on the XCDC structures what forms the basis for the proofs of some of their algebraic properties, e.g. being the Boolean algebras or the lack of their subset satisfying the conditions of the JEPD relationships. Based on the defined operations and the properties of the R^3 Euclidean space (two spatial dimensions, one temporal dimension) and its projections on the two-dimensional planes (one spatial and two spatio-temporal) we also introduce a strict notion of correct and incorrect sets of relations of the XCDC formalism. We also discuss the problem of the ambiguity of the representation in the XCDC model recognized as so-called apparent relations corresponding to the situation in which the function mapping a pair of spatio-temporal objects into the XCDC structure is not injective. We also extend the Skiadopoulos and Koubarakis' algorithm for the composition of relations and define the Edir indicator for comparing the precision level between relations. In addition, we compare the XCDC model with other qualitative techniques (such as RCC-5 and RCC-8, ICD-5 and ICD-9, and Allen's algebra and its modifications) characterized by various forms of the description of temporal, spatial and spatio-temporal relations and mutual irreducibility due to the different distinctive features of their basic relations. During the comparative analysis, we present a method for converting the relation of these classical models into the XCDC structures. That allows to evaluate the proposed model as a solution with a wide representation capabilities and many potential applications.
    Then we look at the possibility of applying the proposed techniques in the systems based on natural language input. We describe three experiments developed with the participation of volunteers. The collected empirical material was used to verify the XCDC model (including its usefulness in the interpretation of natural language expressions). Furthermore, the results of the experiments were used to establish the TSREL set consisting of 34 spatio-temporal relations conceptualized in a natural language and to construct the conversion tables from the TSREL patterns into the XCDC structures and vice versa. We also show that the set of the TSREL relations can be partially ordered by the relation based on the relationship between the corresponding fields of the direction-relation matrices. This partial order also allows to recognize the TSREL collection as an ontology of the concepts associated with the description of time and space (connected by hyponymy), what in particular provides an advanced reasoning about spatio-temporal relations. We developed the algorithm to interpret relative relation which uses the system structure called 'waiting room'. We also analyze the problem of qualitative distance relations and suggest the method for composing such dependencies based on the theory of fuzzy sets.
    Finally, we discuss the applications of the XCDC formalism. In particular, we present the algorithm to build in the knowledge base the map of an analyzed area interpreted as a graph with a clique. Then we discuss the problem of spatio-temporal reasoning based on the construction of a composition path (which is the extension of a path in the graph theory). The theme of discussion is also the issue of the calculation of the location of a specified object (understood as a position which would be most useful from the point of view of a potential user), the comparison of relation, also the consistency checking of the knowledge base, especially while the knowledge is incomplete. We also discussed the proposed solutions in the context of the prototype of the POLINT-112-SMS system intended to support security services during a large mass event. In this system the XCDC model is the basis for the Spatio-Temporal Module responsible for collecting, processing and reasoning about the spatio-temporal relations. It is worth noticing that the POLINT-112-SMS system has been successfully tested during simulation experiments what shows the real usefulness of the proposed formalism in the practical applications.