Qualitative Spatio-Temporal Representation and Reasoning for robotic applications

Janusz Będkowski

Institute of Automatic Control and Robotics, Warsaw

Abstract: This paper discusses the methodology of Qualitative Spatio-Temporal Representation and Reasoning (QSTRR) for robotic applications. The goal is to develop reasoning mechanism that will allow modelling the environment and performing spatio-temporal decisions. A new approach is related to environment modelling based on robot’s perception, therefore new concepts (spatial entities) are obtained automatically, and then used in reasoning. This paper presents the results of the three experiments. Each experiment focuses on different robotic applications, such as mobile spatial assistive intelligence for spatial design, spatial design used for robotic arm integration with the environment and supervision of a teleoperated robot. Each of the experiments is considered as the proof of concept of the proposed methodology. Thus, it can be efficiently used for developing sophisticated robotic application where human-robot interaction and integration are considered as an important goal.

Keywords: qualitative reasoning, mobile robot, industrial robot, semantic modelling

1. Introduction

Qualitative representation and reasoning, applied not only to robotic applications, is an important research direction [1, 5–7]. It is a very promising methodology to build robotic systems able to perform dialog-based interaction [2]. In [3], conceptual spatial representations are used for indoor mobile robot navigation. The sophisticated HRI (Human Robot Interface) based on Combinatory
Categorial Grammar (CCG) parser of OpenCCG 1 is proposed in [4]. The problem of providing intelligent spatial decision-making (spatial reasoning) is related to the framework of Multi-Modal Data Access for Spatial Assistance Systems [8]. This framework shows a key concept of spatial assistance systems by focusing on multi-perspective semantics, qualitative and artefactual
abstractions, industrial conformance and interoperability. The author also provided examples of the use for distinct application domains, which was an important input for developed QSTRR methodology. An important aspect is to choose a proper calculi to model spatial entities and spatio-temporal relations. Therefore, for topological spatial relations (qualitative) the Region Connected Calculus (RCC) [9] is proposed. RCC is a formalism for spatial reasoning that takes regions of space (shapes) instead of points of classical geometry as the primitives. An efficient approach is a system of topological relations called RCC-8 [10].
This paper discusses some aspects of semantic modelling, therefore it is important to emphasize that semantic mapping in mobile robotics has already been well studied and it offers many robust approaches. In [11] the authors proposed a methodology for building semantic maps based on robot’s observations, and in [12] further developments related to 6D SLAM (Simultaneous Localization and Mapping) are demonstrated. This paper proposes a new Qualitative Spatio-Temporal Representation and Reasoning methodology dedicated for robotic applications. The goal was to develop methods able to build semantic models of the environment and to perform integration and interaction with humans. Figure 1 illustrates such an idea.

Fig. 1. Mobile robot equipped with 3D laser can build a semantic model of the environment based on conceptualization and ontology. Integration (semantic models) and interaction (human-machine) form the core concept of Mobile Spatial Assistive Intelligence that creates virtual modified environment

Rys. 1. Robot mobilny wyposażony w laserowy system pomiarowy 3D buduje model semantyczny środowiska przy pomocy konceptualizacji na bazie przyjętej ontologii; integracja (semantycznych modeli) oraz interakcja (człowiek-maszyna) są rdzeniem opracowanej Mobilnej Przestrzennej Inteligencji Asystującej, za pomocą której tworzy się modyfikację wirtualnego środowiska

2. Qualitative Spatial Representation

The main element of Qualitative Spatial Representation is an ontology. As a representation vocabulary, it is specialized to the domain of physical/functional entities in a real structured environment. It allows building a model of an environment using qualitative spatio-temporal or quantitative representation. An ontology (O) is composed of several entities: a set of concepts (C), a set of relations (R), a set of axioms (A), a concepts’ hierarchy (CH), a relations’ hierarchy (RH) and a set of spatio-temporal events (Est). It is illustrated by the following definition:

O = <C; R; A; CH; RH; Est> (1)

The concept is defined as a primitive spatial entity described by a shape (S) composed of polygons in 3D space, associated with a semantic label (SL). Ontology distinguishes two different types of attributes that can be assigned to the concept: quantitative (Aqn) and qualitative (Aql). Four values of a qualitative attribute (entity function) are listed: real physical object, functional space, operational space, range space. Functional, operational and range spaces are related with spatial artifacts that describe the environment and robotic devices, such as sensors and actuators. The following quantitative attributes are related with physical properties of spatial entities: location, mass, centre of mass, moment of inertia (how much resistance there is to change the orientation about an axis) and material (friction, restitution). Therefore, a definition of the concept (C) is formulated as follows:

C = <S; Aqn; Aql; SL> (2)

The set of relations (R) is composed of quantitative and qualitative spatial relations. For topological spatial relations (qualitative) the Region Connected Calculus (RCC) is proposed. RCC is a formalism for spatial reasoning that takes regions of space (shapes) instead of points of classical geometry as primitives. One particular prominent reasoning system is a system of topological relations called RCC-8 (the relations of RCC-8 calculus and conceptual neighbourhood is shown in figure 2, therefore ontology includes eight different topological relations between two regions (in this case, shapes): disconnected (DC), externally connected (EC), partial overlap (PO), equal (EQ), tangential proper part (TPP) and its inverse (TPPi), non-tangential proper part (NTPP) and its inverse (NTPPi).

Fig. 2. The relations of RCC-8 calculus (conceptual neighbourhood)
Rys. 2. Relacje w RCC-8, sąsiedztwo

Quantitative spatial relations are a way to constrain the way entities move relative to another. Ontology defines the following constraints: origins locked, orientations locked; origins locked, orientations free; free rotation around one axis; sliding. Ontology provides a mechanism for building world models that assume spatio-temporal relations in different time intervals (in other words, world models that can capture changes) for the representation of spatio-temporal knowledge used for spatiotemporal reasoning. Chosen temporal representation takes temporal intervals as a primitive, therefore ontology defines qualitative spatio-temporal events (Est) related with topological spatial relations RCC-8:

onEnter (DC → EC → PO),

onLeave (PO EC → DC),

onStartInside (PO → TPP →->NTPP),

onStopInside (NTPP → TPP → PO).

These four qualitative spatio-temporal events can be used to express the most important spatio-temporal relationships that can be hold between two concepts in different intervals of time. To store the instances of ontology-based elements (defined on the conceptual level) an instance base (IBO) is defined:

IBO = <IOC; IOR; IOEst> (3)

where: IOC contains instances of concepts C, IOR contains instances of relations R, and IOEst contains instances of spatio-temporal events. A semantic model is defined as a pair:

SM = <O; IBO> (4)

where: O is an ontology and IBO is an instance base related to ontology O. Ontology is known a-priori but an instance base is being updated during semantic modelling based on robot’s observations. A semantic model is a core concept for the support system. A projection of the semantic model onto 3D space is defined as a 3D semantic map, and a projection of the semantic model onto 2D space is defined as a 2D semantic map. Semantic maps are useful visualization tools that are going to be used in robot applications as interactive HMI (Human Machine Interface).

3. Qualitative Spatial Reasoning

The semantic model is obtained based on robot’s observation assuming the Ontology, the qualitative spatial reasoning can be obtained, and it has been the subject of several studies. An important approach is shown in [13]. The author developed a qualitative reasoner called PelletSpatial, that is a qualitative spatial reasoning engine implemented on top of Pellet. PelletSpatial provides consistency checking and query answering over spatial data represented with the Region Connection Calculus (RCC). It supports all RCC-8 relations, as well as standard RDF/OWL semantic relations, both represented in RDF/OWL. It is a very promising reasoning engine, since it translates RCC relations to OWL-DL class axioms and performs reasoning based on the RCC composition table that implements a path-consistency algorithm. Instead of the existing path-consistency algorithm, proposed QSTRR methodology offers natural dialog-based human-robot interaction. It is obtained by the usage of spatial artifacts (virtual robotic sensors – range spaces). For a detailed discussion see [2].

4. Experiments

4.1. Mobile spatial assistive intelligence for design support

Proposed Qualitative Spatio-Temporal Representation methodology and reasoning can be used in Spatial Design applications. Figures 3–4 show an experiment where a mobile robot built the semantic model of the classroom. A spatial design task consisted of checking what kind of workspaces’ configuration (fig. 3) could be applied.
Figure 4 demonstrates a problem (the shape of workspace is in relation PO-partially overlap with the shape of the wall). The intelligent system provides the qualitative reasoning that helps eliminating spatial conflicts between spatial entities.

4.2. Spatial design used for integration of the robotic arm with the environment

Proposed QSTRR methodology can be efficiently used in applications where there is a need to integrate an industrial robot with the existing environment [14]. Figures 5–6 show a real experiment where the goal was to integrate an industrial robot with the existing production machine. Qualitative reasoning mechanism was used to obtain the spatial conflicts within the interval of the production cycle.

An interesting application field for QSTRR is surgical robotics. Such an approach aims not only to help integrating the robotic platform with the surgery room (figs. 7–9) but also provide a qualitative mechanism to monitor qualitative spatio-temporal events (fig. 10) for surgical documentation.

4.3. Supervision of the teleoperated robot

Supervision of the teleoperated robot is an important task. It can be stated that current applications do not efficiently support a human operator to control the robot, therefore there is the need to provide artificial techniques to achieve better performance. Proposed QSTRR framework can be efficiently used to perform supervision tasks. Figure 11 shows an experiment where environment model was build based on 3D laser measurement data. The goal and robot path are defined as 3D spaces. An additional object of a virtual camera (range space, see figure 12) is used for supervision of robot’s spatio-temporal activities.
Another experiments focus on HMI (Human Machine Interface); Figure 13 demonstrates the goal assigned to the robot, while figure 14 demonstrates the supervision of the robot’s spatio-temporal activities to achieve this goal.

5. Conclusions

This paper discussed the Qualitative Spatio-Temporal Representation and Reasoning Framework methodology, in terms of several robotic applications/experiments that can be considered as a proof of concept. In the paper three experiments are shown, each one related to different robotic applications, such as mobile spatial assistive intelligence for spatial design, spatial design used for robotic arm integration with the environment and supervision of the teleoperated robot. It is obvious that the presented approach has important disadvantages such as limited RCC-8 calculi that cannot model sophisticated spatio-temporal relations. However, it can be efficiently used for developing robotic applications, where robotic actions are simple spatio-temporal activities.

Acknowledgements

The project was funded by the Polish National Centre of Science under grant agreement DEC-2011/03/D/ST6 /03175.

References

1. Jochen R., Bernhard N., Efficient Methods for
Qualitative Spatial Reasoning, “Journal of Artificial Intelligence Research”, 15 (2001), 289–318.

2. Będkowski J., Intelligent Mobile Assistant for Spatial Design Support, “Journal of Automation in
Constrution” 2012, DOI http://dx.doi.org/10.1016/j.autcon.2012.09.009.

3. Zender H., Martinez Mozos O., Jensfelt P., Kruijff G.J.M. and Burgard W., 2008. Conceptual spatial representations for indoor mobile robots, “Robotics and Autonomous Systems”, 56, 6 (2008), 493–502. DOI=10.1016/j.robot.2008.03.007, http://dx.doi.org/10.1016/j.robot.2008.03.007.

4. Baldridge J., Kruijff G.J.M., Multi-modal combinatory categorial grammar, [in:] Conference of the European Chapter of the Association for Computational Linguistics (EACL 2003), Budapest, 2003,
211–218.

5. Cohn A., Qualitative spatial representation and
reasoning techniques, [in:] Lecture Notes in Computer Science, Vol. 1303/1997, Springer, 1997, 1–30.

6. Cohn A., Bennett B., Gooday J., Gotts N.M.,
Qualitative spatial representation and reasoning with the region connected calculus, “GeoInformatica”, 1 (1997) 275–316.

7. Cohn A., Renz J., Qualitative spatial representation and reasoning an overview, “Fundamenta
Informatica”, 46 (2001), 1–2.

8. Schultz C., Bhatt M., A multi-modal data access framework for spatial assistance systems: use-cases with the building information model (bim/ifc), [in:] ISA, [in:] Proceedings of the 2nd ACM SIGSPATIAL
International Workshop on Indoor Spatial Awareness, 2010, 39–46.

9. Galton A.P., Towards an integrated logic of space, time and motion, [in:] Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93), 1993, 1550–1557.

10. Randell D.A., Cui Z., Cohn A.G., A spatial logic based on regions and connection, [in:] Proceedings of 3rd International conference on knowledge representation and reasoning, 1992.

11. Nuchter A., Hertzberg J., Towards semantic maps for mobile robots, “Robotics and Autonomous Systems”, 56, 2008, 915–926.

12. Nuchter A., Elseberg J., Schneider P., Paulus D., Study of Parameterizations for the Rigid Body Transformations of The Scan Registration Problem, “Journal Computer Vision and Image Understanding” (CVIU) 114, 8, 2010, 963–980.

13. Stocker M., Sirin E., PelletSpatial: A hybrid RCC-8 and RDF/OWL reasoning and query engine, 2009.

14. Bedkowski J., Masłowski A., Middleware for production robotic system modeling, integration and control, “Management and Production Engineering Review”, Vol. 1, No. 2, July 2010, 4–10.

Jakościowa przestrzenno-czasowa reprezentacja oraz rozumowanie dla aplikacji robotycznych

Streszczenie: W artykule przedstawiono metodykę jakościowej przestrzenno-czasowej reprezentacji oraz rozumowania dla aplikacji robotycznych. Celem jest opracowanie mechanizmu podejmowania decyzji, które umożliwi także modelowanie środowiska oraz rozumowanie w sensie jakościowym. Nowym zagadnieniem badawczym jest budowanie modelu środowiska na bazie obserwacji robota mobilnego, przy czym nowe koncepty (podstawowe elementy przestrzenne) są generowane automatycznie. Przedstawiono trzy eksperymenty, każdy skojarzony z inną aplikacją robo tyczną, między innymi mobilna przestrzenna inteligencja asystująca dla projektowania przestrzennego, projektowanie przestrzenne dla integracji robota przemysłowego z istniejącym środowiskiem pracy oraz nadzorowanie pracy robota zdalnie sterowanego. Każdy z tych eksperymentów dowodzi słuszności proponowanej metodyki. W związku z tym metodyka może znaleźć zastosowanie w projektowaniu
zaawansowanych aplikacji robotycznych, gdzie interakcja oraz integracja człowiek-robot są zasadniczym zagadnieniem funkcjonalnym oraz użytkowym.

Słowa kluczowe: rozumowanie jakościowe, robot mobilny, robot przemysłowy, modelowanie semantyczne

Janusz Będkowski, PhD

PhD in Automation and Robotics, Assistant Professor in Institute of Automatic Control and Robotics – Warsaw University of Technology; adjunct in Industrial Research Institute for Automation and Measurements as well as Institute of Mathematical Machines. The scope of research: inspection and intervention robot systems, semantic mapping, virtual training with AR techniques.

e-mail: januszbedkowski@gmail.com