One of the main problems in software development for service robots is to create systems that reliably behave as intended, even though the real eld of application and the concrete user requirements are unknown during design time. Consequently, the software controlling service robots has to be aware of its environment and has to adapt its behavior accordingly. A model representing environmental data is called a context model. Appropriate context models currently lack means for modeling temporal and spatial information simultaneously. While it is important to reason about historical context data for most of the SelfAdaptive Systems, there is an increasing need for treating the temporal dimension of context models as rst-class-citizen. In this paper, we propose a graph- and role-based context model (GRoCoMo), which includes expressive means for describing time and location. A query language enables for reasoning on current and historical data, as well as future trends. A manipulation language enables the speci cation of rewrite rules for updating context models based on situations detected within the context.
A service robot is a reprogrammable, sensor-based, mechatronic device which
performs useful services to support human activities [
T Route 2 Shortest Path Near Wall
Crowded Area
S Start
T Target
lines), calculates the shortest route from the starting location (S) to the target
location (T) and provides two di erent alternatives. The other strategy, Near
Wall (dashed lines), calculates routes that lead along walls. The grey dashed
area is usually used by many persons and therefore, marked as \crowded". When
the navigation algorithm decides to use the upper oor, the Near Wall
strategy is the better option, since the probability to get in the way of humans is
decreased. On the other hand, it might be disadvantageous on the lower oor,
where the robot potentially has to drive around many open doors. Hence, the
decision should be made at runtime. An inherent property of all SAS is that they
are implementing a variant of the MAPE-K loop, rst introduced by IBM [
This paper is structured as follows. In Section 2, we give an overview on context modeling and outline important properties of context models. In Section 3, we discuss relevant context modeling approaches and their suitability w.r.t. the identi ed properties. We present our approach in Section 4 and discuss our prototypical implementation in Section 5. Finally, Section 6 presents our conclusion and future work. 2
To enable an application to adapt itself to changing environmental conditions,
information about the environment must be gathered and analyzed. For this
purpose, a variety of approaches have been developed, to tackle the speci c
requirements in di erent application domains of SAS [
Z4 - Activities: The activities dimension encompasses any information about an entity's past, present and future needs, goals, tasks and plans. Z5 - Time: Statements in a context model often have a temporal dimension.
Time can be expressed using time zones (e.g., Central European Time) or virtual times (e.g., milliseconds after system start). Furthermore, overlay models can be used for abstraction (e.g., working hours, weekends, etc.). Z6 - Location: Since most of a context model's elements represent objects from the physical world, which are arranged spatially, location is a major aspect of context information. The location dimension can include real or virtual locations (e.g., IP address in a network). Those locations can use absolute, relative, or symbolic location models.
Strang et al. [
The research area of SAS is still very popular, resulting in thousands of
publications each year. This is also true for research on context modeling and
management. For our related work research, we searched for papers published between
2000 and 2013 and containing the words \context model " in their title, using
Google Scholar1. The result of the indicated query was a set of 3469 papers. We
ltered the result-set manually to exclude publications that were not intended for
the application in SAS. The result was a reduced set of 1228 manually ltered
papers. Among them, we investigated ve context model survey papers [1{3, 6, 13].
We have chosen six representative context model publications, which consider
the dimensions time (Z3) and/or location (Z4). Four of those papers [
In 2003 Strang et al. proposed the ontology-based context model CoOL
(Context Ontology Language) [
Gu et al. presented an ontology-based context model for their service-oriented
context-aware middleware SOCAM in 2004 [
Wang et al. proposed the CONtext ONtology (CONON) [
(Z1) Entities (Z2) Individuality (Z3) Relationships (Z4) Activities
(Z5) Time (Z6) Location
CoOL (+) + + ({) ({) ({) + + + + ({) (+) + + + + ({) + (+) + + ({) ({) ({) + + + + { + + + + + { + SOCAM
CONON
MUSIC
ERMHAN
CACOnt explain how those locations can be related to each other, to create hierarchical location models.
Reichle et al. described an ontology-based context model for the MUSIC
project in 2008 [
In 2011, Paganelli and Giuli presented a context model for the ERMHAN
service platform for Ambient Assisted Living (AAL) scenarios [
In 2013, Xu et al. presented the Context-Aware Computing Ontology CACOnt. It prede nes several types of entities, properties, relationships and activities (Z1 - Z4 ). The authors extensively investigate the location dimension (Z6 ), by providing di erent levels of abstraction for the speci cation of an entities location (e.g., GPS, location hierarchies). They do not consider the time dimension (Z5 ). Thus, a CACOnt model only provides information on the current context state. However, like in every model with extensible attributes, it is possible to express time information using attributes with a custom interpretation logic.
As shown in Table 3, the presented context models provide means for modeling the dimensions of entities, individuality, and relationships (Z1-Z3). The activity dimension (Z4) is either provided, directly or can be modeled separately, using an extensible entity-model. The most recent works consider the location (Z6) as an essential part of a context model, and, thus, provide means Vis6ual Paradigm CoTmmouwnityaErdditiosn [nCot oforncotmemxertcial Museo] deling in Space and Time for handling spatial information as a rst-class-element of context models. The time dimension (Z5), however, is considered important in state-of-the-art literature, but current context models do not provide explicit modeling elements to handle time appropriately. 4
In this section, we present our Graph- and Role-based Context-Model (GRoCoMo), a context model supporting all modeling dimensions stated in Section 2. 4.1
As depicted in Figure 2, the context model consists of Nodes and Relations. Both, Node and Relation inherit from the abstract type Modeling Element. Each element has a name, a sensorId to identify values created by the same sensor and a unique resource identi er (URI), to identify the individual element. A Relation connects exactly one Source Element to exactly one Target Element. Both, source and target, are of the type Modeling Element. Hence, it dt1 : DateTime dateTime = 25.05.2014 14:10 da start
ts 1: Timespa dt1 : DateTime dateTime = 25.05.2014 14:10 example Robot
: Device start
end ts 1: Timespan
Located At
Located At Predecessor
Room 1 : Location Floor 1 : Location
Located At
Office Building :
Location
Located At ts2 : Timespan is possible to de ne relations on relations. A node represents an entity of the context model. The model provides prede ned node types (e.g., Person). However, the metamodel can be extended with domain-speci c node types by subclassing. A Relation represents a typed, complex relationship between two entities. Furthermore, each relationship can contain several directly assigned attributes. 4.2
To cover temporal aspects, Timespans can be assigned to each modeling element (i.e., nodes and relations), to state when the validity of a modeling element started and stopped. Each modeling element with a validity timespan that has no associated end-time, is considered valid at the current time. By default the validity of a modeling element starts when it is created and can be invalidated by assigning an invalidation time. Because each element can have multiple validity times, a previously invalidated node or relation can be re-validated again. Each modeling element may have a Predecessor Relation to another modeling element of the same type that was replaced by the respective element w.r.t. its validity. In the scenario described in Section 1, the robot moves from a starting location S to a target location T. While the robot moves, a node, representing the robot, contains an outgoing LocatedAt relation. As shown in Figure 3, when the robot moves from room1 to floor1 the rst LocatedAt relation is invalidated and replaced by a new relation. Because the invalidated relation is not deleted from the model, it is still accessible and can later be analyzed (e.g., by creating motion pro les). Furthermore, di erent representations of \time" can be modeled. As shown in Figure 3, date and time combinations can be represented as absolute timestamps in a given calendar. Hence, it is important to have an associated location to every timestamp representation, which is inferred in the provided example, because the timespan is assigned to a LocatedAt relation. Furthermore, other representations of time (e.g., weekdays or holidays) can be modeled and assigned to nodes and relations. 4.3
Locations are represented by special Location nodes (see Figure 2). The model separates physical (e.g., the main station) or logical locations (e.g., a folder in a le system). Physical locations can further be divided into sub-symbolic (e.g., GPS coordinates) or symbolic (e.g., Dresden Main Station) locations. To relate an entity to a location node, the GRoCoMo metamodel provides a generic LocatedAt relation. The target of such a relation must always be a location node. When the source node is a location node as well, the relation represents a partof relation for a speci ed point in time (e.g., Dresden Main Station Is Located At Dresden). The LocatedAt relation is transitive. Lets consider for example a person is located in a car and this car is located in the city of Dresden. In this case, the person is located in Dresden as well. While the car changes its location when it is moving, the driver will not change its position relative to the car, but its location relative to the geographical location. The part-of relation on locations forms a graph that has no cycles. 4.4
In order to query the context model, we have created a rst prototype for a query language (GRoCoMo-QL) based on pattern matching in graphs. Listing 1.1 shows an example. Each query starts with a de nition of roles. Each role has an id (e.g., node1) and represents a node with an optional type constraint (e.g., Location). Then, relations can be de ned. Each relation has an id, an optional type constraint, a source and a target role, as well as a temporal constraint. The last part of the query is a restriction clause, where any restrictions on the structure of the previously de ned roles and relations can be speci ed. The query from Listing 1.1 will return all tuples (node1, node2, rel1), where node1 is a location node, node2 is a device node and the name attribute of node2 has the value ``Example Robot''. Furthermore, both nodes must be connected by a LocatedAt relation from node1 to node2. As a temporal constraint, within all results it is guaranteed, that all nodes and relations were/are valid at the same time and only nodes and relations are considered, that were valid within the last 5 minutes. 1 nodes { 2 node1 : Location [ valid within last 5 min ]; 3 node2 : Device [ valid within last 5 min ]; 4 } 5 relations { 6 rel1 : LocatedAt ( node2 , node1 ) [ valid within last 5 min ]; 7 } 8 where node2 . name = " Example_Robot ";
Listing 1.1. A GRoCoMo-QL example. 4.5
The context model can be changed using a sequence of the following basic graph rewrite operations: Add Node/Relation: This operation adds a node/relation to the graph. The concrete type is speci ed on the client side.
Remove Node/Relation: This operation takes the id of a node/relation as an input and will remove the corresponding node. In contrast to the invalidation operation, a deletion will irreversibly remove the node.
Invalidate Element: The invalidation operation of a modeling element (i.e., nodes and relations) sets the end time of the corresponding element to the current time. Hence, it will be considered invalid.
Validate Element: Analogously to the invalidation, the validation operation will create a new valid timespan and sets the start time to either the current or the provided time.
Set Property: Some of the GroCoMo meta-classes (cf. Figure 2) de ne built-in properties (e.g., name). Those properties can be changed using this operation. The changes of built-in properties are not tracked (w.r.t. historical data).
From those basic operations, complex operations can be composed (e.g., replace node, set attribute, set location). The context model can be manipulated by (a) sensors, (b) inference-, and (c) cleanup units. Sensors observe the environment (physical or virtual) and update the context model accordingly. Inference units enrich the context model with new nodes and/or relations based on analysis of the available data in the context model. Cleanup units remove nodes and relations based on application- and hardware-speci c rules in order to avoid memory overloads. To express the manipulation of those di erent manipulation units, we have created a prototypical manipulation language (GRoCoMo-ML), based on the Query Language sketched in Section 4.4. Listing 1.2 shows an example. A manipulation script consists of a set of labeled situations, where each situation contains exactly one query. Then, conditions on the results of the corresponding queries can be stated. The match/mismatch of situations can be combined using logical operators (e.g., and, or, etc.), as well as aggregation operations stated on the number of matches. In the provided example, the corresponding sequence of manipulation operations is executed, when the pattern, described in the situation "PersonInRoom1", is matched more than 5 times.
The presented context model GRoCoMo provides a prede ned set of nodetypes (e.g., Person, Activity, Location, Time), representing contextual entities (supporting modeling dimension Z1 ). The core model introduces speci c nodes (i.e., Attribute Node) and speci c relations (i.e., HasAttribute relation) to model the individuality of entities (dimension Z2 ). Through this approach dynamic complex types can be modeled by creating nested attributes. Relations represent relationships either between entities or between other relations (dimension Z3 ). Activities can be modeled using special Activity nodes (dimension Z4 ). In order to express temporal and historic data (dimension Z5 ), valid times by means of Timespans can be assigned to each node and relation, to express when the validity of a modeling element started and ended. Beside the represented timestamps, it is also possible to assign symbolic representations of 1 Situation " PersonInRoom1 "{ 2 nodes { 3 room1 : Location ; 4 person : Person ; 5 } 6 relations { 7 rel1 : LocatedAt ( person , room1 ); 8 } 9 where room1 . name == " kitchen "; 10 } 11 ON Count ( PersonInRoom1 ) > 5 { 12 an = new AttributeNode ( name = " is crowded " , value = true ); 13 rel = new AttributeRelation ( source = room1 , target = an ); 14 }
Listing 1.2. A GRoCoMo-ML Example time (e.g., Monday, Holiday etc.). Finally, spatial information is captured by Location nodes (dimension Z6 ).
To investigate the feasibility of the presented approach, we have created a
prototypical implementation using the role-based self-adaptive system Smart
Application Grids (SMAGs) [
The domain of service-robots highly requires software systems that adapt their
behavior based on past, present and potential future situations of the involved
system. The MAPE-K loop represents the adaptation process from data
acquisition, to system recon guration, based on data stored in a shared knowledge
base. An important part of this knowledge base is the context model, capturing
environmental data. It was observed, that structured knowledge representations
(e.g., ontologies) are best suited for modeling open and unknown environments.
Current approaches, however, fail to support context data analysis over time
and location simultaneously. In this paper, we have proposed the context model
GRoCoMo (Graph- and Role-Based Context Model), using a typed, attributed
and directed graph as a foundation. The model supports di erent prede ned
entities and relations, which can be extended for speci c domains. The model
treats activities, time and location as rst-class-citizens. For temporal
information, validity-timespans are attached to each modeling element, representing the
timespan when an element is/was valid (w.r.t. a speci c location). To model
locations, the model provides specialized location nodes and relations, as well
as a transitive semantics for those relations. We have outlined a rst version
of a pattern-based Query Language, as well as a Manipulation Language using
pattern-based situation detection and a set of prede ned manipulation
operations, to change the context model. For future work, the provided prototypical
implementations of the API and the corresponding languages have to be nished,
stabalized and published. In addition, the presented approach has to be
evaluated in real-world examples. Bettini et al. [
This work is supported by the German Research Foundation (DFG) within the Cluster of Excellence \Center for Advancing Electronics Dresden" and the Collaborative Research Center 912 \Highly Adaptive Energy-E cient Computing".