Context Graphs as an Efficient and User-Friendly Method of Describing and Recognizing a Situation in AAL

2.1. AmI Platforms for AAL

The development of software and hardware platforms specifically directed to ambient assisted living is a relatively recent endeavor. Most platforms are based on research in ambient intelligence environments and smart homes, but, this time, customized for use by a single (usually) assisted individual [9–11].

One of the things that is easy to see is that most proposed platforms have a very complex architecture that is meant to bring information from a large number of sensors, which communicate using various protocols. Furthermore, most platforms are centralized, relying on a central server in the home that does all of the processing, relying mostly on rules to decide upon the appropriate action. The environment and the user's context are many times represented as tuples of values from sensors, and sometimes ontologies are used to define situations. What is often times missing, though, is intelligence itself [12]. Usually, action is decided based on large amounts of information (including various smart devices, such as smart cups, showers, floors, etc.) that would be normally difficult or intrusive to obtain [13–15]. However, there is a strong lack of support for changing situations, for temporal sequences of situations and for easy understanding of how the system works by a less informed caretaker. While research on multi-protocol, multi-device architectures is extremely useful for the case of the smart home, reasoning and true intelligence is always necessary in AAL. We will look into some individual examples.

Lyons et al. [13] present an important corpus of use cases for single-inhabitant smart homes, using case-based reasoning to decide on the severity of the case (if any). While the scenarios are very useful, the authors assume that the system is composed of largely smart appliances (including small ones, such as a blender) able to detect the length of the person's shower, the phases of tea-making and the position of various small objects. While this can technically be done, it would be overly complicated and expensive. The Ambient Home Care System (AHCS) [1] proposes a large number of sensors as well: motion detectors, smart carpets, wrist devices and smart walking aids. As stated further on, we try to obtain intelligent behavior using a smaller number of sensors, leading to less intrusiveness and a lower cost of the system. A relevant study on the perception on wearable devices, namely a smart wrist device, has been done by Holzinger et al. [16]. Similarly, Sun et al. [6] propose an interesting interface to be used for elders in order to interconnect with each other and their carers, but the system is purely reactive, and there is no activity recognition involved; participants must explicitly declare their needs.

We find that reasoning in many AAL applications is lacking, not exploiting at the fullest the information brought by sensors and through communication. For instance, Tapia et al. [11] present several agent-based AAL applications and projects that rely on various sensors and protocols (RFID, WiFi, ZigBee) to assist the person. The architecture and the presented infrastructure are valuable, but the system works only as a gatherer of information. Context-aware reasoning by the agents would greatly improve the performance and the features of the system.

Klein et al. [17] present the results of the SOPRANO European project (Service-Oriented Programmable Smart Environments for Older Europeans) featuring the SOPRANO Ambient Middleware (SAM). The project features a complex architecture built around a context manager, reasoning using relations between various elements of context, much like in our work, and ontologies. As ontologies do not perform well in the case of dynamic context, we claim that using context matching would improve the performance of reasoning.

The work of Blasco et al. [18] presents a complex platform, encompassing a large number of devices and protocols and an interesting architecture for the core of the system. The Context Manager uses a fixed set of rules that are specific to the appliances in the system. While useful as a platform for controlling and gathering information from devices, there is room for improvement in the reasoning and intelligence of the system.

For further implementations, we refer the reader to more complete surveys [10,15], from which one can see that, where intelligent behavior, using AI methods and mechanisms, is implemented, it is done so in a manner that is not easy to adjust or update by a less-informed carer. We address this by proposing mechanisms that use representations that are easier to understand and to use.

2.2. Context Awareness and Context Modeling

In context awareness for pervasive computing, infrastructures for the processing of context information [19,20] contain several layers, going from sensors to the application. There are several challenges in building infrastructures for context awareness [21], related, on the one hand, to managing data formats and protocols, and on the other hand, to splitting responsibilities (processing) between devices. Middleware proposed for context-aware services [22,23] are hierarchical, separating context providers from context consumers. This type of infrastructure is useful when the context information comes from the environment and refers to environmental conditions, such as location, temperature, light or weather, also having a simpler representation [24]. Our approach is directed towards an infrastructure that is decentralized, in which each entity/agent has knowledge about the context of its user, and applications are also able to create context information and insert it into the system, combining the features of context providers and consumers [7].

A large number of AmI platforms rely on software agents [25] to handle distributed configurations. However, in doing so, context awareness generally remains centralized, as agents use context servers or centralized context services to store and to provide context information and to perform context-aware reasoning (detection of situations). Here, we can refer platforms such as iDorm [26], LAICA (Laboratory of Ambient Intelligence for a Friendly City) [27] or AmbieAgents [28]. We propose mechanisms to distribute context-aware reasoning and context information, such that each agent handles the information relevant to its activity.

Modeling of context information uses representations that range from tuples to logical, case-based and ontological representations [15,19,29–31]. The most popular approaches are ontologies for representing situations and rules for reasoning, coupled with propositional or predicate logic to represent current context information.

Rules are used to specify the action to perform when a particular set of conditions are met [32,33]. However, rules are not easy to adapt, and their formalisms cannot be easily used by a less informed carer. Defeasible rules are an interesting formalism to define implications that are not necessarily true, accounting for uncertainty and erroneous context information [34].

Ontologies are used in many projects to define situations and to establish the relations among the elements of the context. Several ontologies have been created specifically for use in context-aware computing (e.g., SOUPA [35]). The main criticism regarding ontologies is a lack of support for temporal relations, the lack of dynamicity and the large space and temporal complexity required for ontological reasoning [30]. Solutions have been proposed for integrating temporal information into ontologies [36], for reducing the footprint on resource-constrained devices [37] and for distributing ontologies across devices [38]; however, ontologies remain more appropriate for centralized approaches, where reasoning is performed by powerful devices. The mechanisms we propose are directed towards system distribution, the local storage of context information and local reasoning.

The work of Turner et al. shows how context-mediated behavior (CMB) [39] can be used to adapt behavior to cases that have not been encountered before, but share similarities with existing cases, much like we use patterns for context recognition. Their work extends case-based reasoning and is applied in AUV (Autonomous Underwater Vehicles) control [40]. Our research is somewhat similar in behavior, but we use structures that are easy to represent graphically and to visualize.

Another mechanism that can be used for activity recognition is Event Calculus [41], a logic formalism relying on fluents (variables) that can be changed by the occurrence of events at various times. While using this formalism can give good results for small cases [42], the constraints and the situation recognition algorithm make it impractical for situations with a large number of variables.

As we attempt to use graphs for the representation of context information, the work of Sowa [43] on conceptual graphs is especially interesting with respect to our research, but, in our work, we define a textual and graphical representation that is easier to use, and we focus on graph matching for situation detection.

In the field of time-aware graph-based representations, the body of research is small. Ontologies do not handle temporal relations very well, and more work has been done in time-aware RDF (Resource Description Format) or similar representations. We mention the work of Pollack [2] in terms of tagging graph nodes with information on realization intervals and the works on temporal queries on RDF (e.g., [44]). Our work, however, is based more on graph features, integrated with context matching, and easier to visualize. We do not focus only on the validity of relations, but also on graphs that represent a sequence of events.

We find the work of Storf et al. [45] very interesting from the point of view of aggregating events into temporal trends. While our work draws from theirs, we are building upon it by coupling temporal awareness with the graph-based representation of context.

Similarly, Fernández-Llatas et al. [46] aggregate the recognition of context into workflows to detect outliers and deviation from the normal situation. However, the system only has a unidirectional perception of context, and context information is limited to location. We propose a representation that encompasses not only other types of perceptions, but also associations between facts and the ability of applications to generate context information themselves.

The research group of Diane Cook working on activity detection proposes a method that bears much similarity to our own, in the sense that textual pattern detection is used to detect behavioral patterns in activity data recorded as text [47,48]. By comparison, this work is directed towards activity recognition (rather than detection) and proposes a representation for context/situation information that is easier to read and handle by the carer of the assisted person.

2.3. Graph Matching

Graph matching (finding an isomorphism between two graphs) has been used for a great variety of domains, prominently for image analysis, chemistry, document processing and ontology matching, but less in context recognition [49]. Graph matching is an NP-complete problem. In our specific situation, what is needed is the exact and potentially incomplete matching of labeled, directed graphs. Most matching algorithms [49] are focused on unlabeled graphs, meant especially for image recognition. We have taken inspiration from several popular algorithms, such as the ones created by Bron-Kerbosch [50], Larossa [51] and Cordella [52], and we have found that dedicated matching algorithms can be created that, for the specific problem of context matching, offer very satisfactory performance [8].

Kirsch-Pinheiro et al. [53] use graph matching for context-aware service selection in order to handle dynamic context; however, they actually match taxonomical graphs and not graphs representing the current situation.

Chein et al. [54] use graph matching for visual reasoning (not necessarily context-awareness) using generalization and specialization operations to find if a graph can be transformed into the other. Their research is very useful from the point of view of graph transformation; however, finding matches based on trying various sequences of operations seems far from an efficient method for matching.

3.1. Physical Environment and Sensors

This research integrates with our AmIciTy initiative [55] to build a context-aware, agent-based platform for AmI and AAL applications. The platform is in the course of being deployed in the Ambient Intelligence Laboratory in our faculty [56,57], funded by the ERRIC FP7 European Project [58]. The laboratory contains various sensors, among which, the most interesting to this research are Microsoft Kinect^TM RGB-D cameras, capable of tracking a user's skeletal approximation and position relative to the camera. If only the depth information from the sensor is used, we consider that the privacy of the subject is respected.

The choice of sensor equipment has been guided by our perspective on AAL. Wearable sensors are felt by the person as an intrusion to their privacy, and it may be that the person will dissent, will refuse or will avoid wearing them. Moreover, in a social environment, wearable devices (such as sensors or tracking bracelets) may attract stigmatization, as they show that the person is indeed in need of assistance and cannot fully care for themselves [14,45]. Devices that require action from the assisted person, on the other hand (such as panic buttons), may not be activated in time or at all when there is an emergency. In our view, the solution lies in using only a few, less intrusive sensors that the person can easily adapt to, such as depth cameras and microphones, used to detect the location and posture of the person, and, occasionally, RFID tags, used to detect object use [59]. This way, there is no direct interaction between the person and the sensors, and issues regarding the acceptability of technology by the person are minimized. In the future, when the system will need to interact with the assisted person, usability and acceptance studies will need to be conducted [60].

3.2. A Brief Overview of the System Architecture

The AmIciTy platform is an agent-based platform for AmI and AAL applications [7]. It is oriented towards a fully distributed functionality, using few or no centralized components. The platform relies on a context-aware layer that handles locally-stored context information and deals with recognizing situations, integrating interesting information received from other agents and disseminating potentially interesting information to other agents. Each agent resides on a machine close to where its function is needed and maintains only context/situation information that is relevant to its own function. Some agents may receive perceptions from simple devices and do only simple processing; other agents may reside on powerful workstations and handle complex detection tasks, featuring large context graphs and many patterns.

Figure 1 presents a layered perspective on the components of the system (based on the work of Seghrouchni [61]), in which agents reside in a layer dealing with application-specific behavior, but containing a sublayer—the context-awareness middleware—which is generalized so as to be used by any AmI application.

In this paper, we concentrate on describing how context matching can be useful for AAL applications, and the multi-agent system aspect of the platform will not be discussed, as it has been done so in previous work [7]. The presentation will focus on the functionality of only one agent, keeping in mind that the design of the context graphs has been done so that the representation is easy to distribute among multiple agents.

3.3. Situation Recognition

We view situation/context as a set of associations between different concepts, a view somewhat inspired by the work of Henriksen and Indulska [62]. The context is formed by the elements that are relevant to the user's activity and can act as the ‘dressing’ of the user's focus [63,64]. Using associations is an improvement over using tuples or properties of context elements and is similar to logical representations, but easier to understand and visualize.

Let us have an example scenario, featuring the fictional character, Emily, who we will use throughout the paper. She is aged 87 and lives alone. We address situations in which Emily is alone in her home. If Emily needs to go out of the house to do some shopping, normally she gets dressed, she takes her wallet, her keys and a shopping bag with her. The situation of “Emily is going out for shopping” is defined by four associations: Emily is dressed in her city clothes; Emily has her wallet with her; Emily has her keys with her; and Emily has a shopping bag with her (see Figure 2). If only some associations are detected (e.g., all, except for the wallet), the user may be in the situation, but something may be wrong (the situation is not complete); Emily has forgotten her wallet. As a result, the system may issue a notification to remind Emily of the missing association.

The above works for instantaneous context, where a situation is detected in the moment when all or most of the associations are present. However, there are cases in which time and sequence play a role. For example, in Emily's home there are RGB-D cameras in every room, except for the bathroom (for privacy concerns), but the system cannot detect Emily anywhere in the house. It may be that Emily is in the bathroom or that Emily has gone out of the house. However, if Emily has been near the bathroom door exactly before disappearing, it is most likely that she went to the bathroom. Another example: if Emily goes to the bathroom and does not come out for one hour, there may be a problem, and the carer must be notified or (if the system has the possibility) the system may try to obtain a response from Emily that she is alright.

From the point of view of ease of use, a situation described as associations is easier to define and understand by a carer. Instead of describing rules, the carer just has to describe the situation, which potentially includes actions from the part of the system (e.g., notifications). When the situation is represented as a graph, it becomes even easier. Moreover, if identifying a situation relies on identifying associations between the present context and the desired situation, it is easy for someone to see what exists and what is missing (see, for instance, Figure 3).

For sequences and time-related situations, the easiest for someone is to visualize time as flowing along an axis and various events happening at the right times on this axis. Alternative sequences of events can start from the same starting point, but have different outcomes, depending on what happens along the way. If laid out on an axis, temporal distance (time passed between events) is easy to picture. This is how we have developed the concepts of timelines, presented in Section 4.6 (see Figure 4).

From the point of view of artificial intelligence, describing possible complete situations instead of rules can be interpreted as having a goal-driven, cognitive behavior instead of a reactive behavior. Once a situation is sufficiently matched by the current context, the agent can set itself a goal to complete the situation as it is defined, instead of just reacting to perceptions.

Following the reasoning above, we have decided that, especially in the context of an AAL system, used both by the assisted person and by the caregiver(s), the current context would be best represented as a graph of associations/relations between concepts (the context graph). Known situations are represented also as graphs, possibly featuring some generic elements, which can be matched against the context graph to detect the current situation(s). This formal representation is described in depth in Section 4.

4.1. Current Situation Represented as the Context Graph

In order to represent its beliefs about the current situation, each agent A has a context graph CG_A = (V, E) that contains the information that is currently relevant to its function.

We consider a global set of concepts to be present in the graph:

• Concepts = Strings ∪ URIs

In this definition, Strings stands for the set of all strings and URIs for the set of all valid Universal Resource Identifiers. Nodes must have a non-empty label. There is no taxonomy for the concepts and no way to generalize a concept to another concept (as in the work of Chein et al. [54]). However, complex ontologies (or even taxonomies) are not absolutely needed in an environment covering one habitation and the activity of one person. In this case, having a name and a class for each item and activity is enough. For instance, it is sufficient to have $\mathit{\text{Sleeping}}\stackrel{\mathit{\text{isa}}}{\to }\mathit{\text{Activity}}$ to say what is the class of a node. This can be matched in a pattern? $\stackrel{\mathit{\text{isa}}}{\to }\mathit{\text{Activity}}$ or, in short, ? Activity. If more complexity is needed, taxonomies can be defined in the context graph using multiple $\stackrel{\mathit{\text{isa}}}{\to }$edges and can be matched using regular expression pattern edges.

We also define a global set of Relations between concepts:

• Relations = Strings ∪ URIs ∪ {λ}

In the relation set, we also have the empty label in order to express unnamed relationships, with no special semantics, except just the association between two concepts.

Using the two sets defined above, we define the context graph as:

• CG_a = (V, E), where

• V ⊆ Concepts and

• E = {(from, to, value, validity) | from, to ∈ V, value ∈ Relations, validity ∈ (0,1] ∪ {permanent}}.

First, it is easy to see that two nodes cannot have the same label. One concept will be present in the graph as only one node. Second, we note that the edges have an additional attribute, which is the validity of the edge. We will discuss this in Section 4.5. Multiple edges with the same label may exist in the graph, but not between the same two nodes.

4.2. Recognized Situations Represented As Context Patterns

In order to detect relevant information or to find potential problems, an agent has a set of patterns that it matches against its context graph CG_A. These patterns describe situations that are relevant to its activity (we will note with the superscript “^P” the support for generic elements, such as nodes labeled with a question mark):

• Patterns = {( $G_s^P$, persistence) | s ∈ PatternNames, $G_s^P$a graph pattern, persistence ∈ (0,1] ∪ {permanent}}

That is, a pattern s is defined by a graph pattern $G_s^P$ and a persistence property that gives the validity of edges that are inserted in the context graph as a result of actions (we will talk about actionability a bit later). A graph pattern has the following properties:

• $G_s^P=(V_s^P,E_s^P)$

A graph pattern is just a graph with some generic elements (labeled with a question mark), namely vertices that can match any vertex in the context graph and edges that that can match edges with any label.

• $V_s^P$ = {(label, index), label ∈ Concepts ∪ {?}, index ≥ 0, label = ? ⊕ index = 0}, with ∀(label_i, index_i), (label_j, index_j). label_i ≠ label_j ⊕ (label_i = label_j = ? Λ index_i = index_j), where ⊕ stands for logical exclusive disjunction.

That is, vertices either have labels from Concepts (no two nodes with the same label) or have question marks as labels and are differentiated by an index.

• $E_s^P$ = {(from, to, label, characteristic, actionable) | from, to ∈ $V_s^P$,

  label ∈ Relations ∪ {?}, characteristic ∈ (0,1], actionable ≥ 0}

Edges in the pattern have some additional properties, namely characteristic—the weight of the edge in the quality of a match (see next subsection)—and actionable, indicating whether the agent is able to decide to add the edge in case of a match and in what conditions (see Section 4.4).

4.3. Recognizing Situation through Context Matching

By using graph matching algorithms—matching a pattern from the agent's set of patterns against the agent's context graph—an agent is able to detect interesting information or problematic situations and is able to decide on appropriate action to take (Section 4.4).

The pattern $G_s^P$ matches the subgraph $G_A^{\prime }=(V^{\prime },E^{\prime })$ (presumably $G_A^{\prime }\subseteq C{G}_A$, iff there exists an injective function f_υ : $V_s^P\to V^{\prime }$, so that the conditions (1) and one of (2a) and (2b) are met simultaneously:

(1)

∀_υ^P = (label, index) ∈ $V_s^P$ · υ^P = ? ⊕ f(υ^P) = label

(2a)

∀( ${\upsilon }_i^P$, ${\upsilon }_j^P$, label,…) ∈ $E_s^P$. (f ( ${\upsilon }_i^P$), f( ${\upsilon }_j^P$), label ∈ E′, for label ∈ Relations

(2b)

∀( ${\upsilon }_i^P$, ${\upsilon }_j^P$, ?) ∈ $E_s^P$. ∃label ∈ Relations. (f( ${\upsilon }_i^P$), f( ${\upsilon }_j^P$), label) ∈ E′

That is, every vertex in the pattern matches a different vertex from $G_A^{\prime }$ (f_υ is injective), which has the same label for non-generic pattern vertices; and every edge in the pattern matches (has the same label and the adjacent vertices match) an edge from $G_A^{\prime }$. Subgraph G′ should be minimal: it contains no edges or nodes that are not matched by elements in the pattern.

We allow partial matches. A pattern $G_s^P$ k-matches (matches except for k edges) a subgraph G′ of G, if conditions (2a) and (2b) above are fulfilled for m_s − k edges in $E_s^P$, with k ∈ {1..m_s − 1}, $m_s=\Vert E_s^P\Vert$, and G′ remains connected and minimal.

The same pattern may match various subgraphs of the context graph. A match i between a context pattern $G_s^P$ and the context graph CG_A of an agent A is defined as:

• M_A−si( $G_A^{\prime }$, $G_m^P$, $G_x^P$, f_υ, k_f) $G_A^{\prime }$ , $G_m^P$, $G_x^P$are graphs: $G_A^{\prime }\subseteq C{G}_A$is the subgraph (partially) matched by the pattern, $G_m^P=(V_m^P,E_m^P)\subseteq G_s^P$ (matched or solved part) is the part of the pattern that matches $G_A^{\prime }$ and $G_x^P=(V_x^P,E_x^P)$ is the rest of the pattern, which is unmatched. There is no intersection (common nodes or edges) between $G_m^P$ and $G_x^P$ (it is therefore possible for $G_x^P$ to contain edges without containing both of their adjacent vertices). In the case of a partial match, function f_υ is defined as f_υ : $V_m^P\to V^{\prime }$. The quality of the match is measured by k_f, calculated as:

  • $k_f=\frac{\text{∑}_{e_i^P\in E_m^P}{e}_i^P\cdot \mathit{\text{characteristic}}}{\text{∑}_{e_j^P\in E_s^P}{e}_j^P\cdot \mathit{\text{characteristic}}}$

  The quality of the match improves with every matched edge and improves more if the matched edge has a high characteristic factor.

4.4. Deciding on the Appropriate Action

When a partial match occurs between one of the patterns of the agent and the context graph, with a k_f above a certain threshold, it means that the situation corresponding to the pattern has been detected, but it is incomplete. For instance, the person is preparing to leave, but has not taken the keys to the house; or, an emergency situation occurs, but a notification has not yet been sent. Missing edges may lead to creating the edge, in case the system is able/allowed to create the edge, to taking action, in case the system is able to perform an action that results in the creation of the edge; or to notifying the user, in case the system is not able to perform such an action (see Section 6.1 for some examples).

Whether the edge can be inferred/acted upon by the system depends on the k_f value of the match and on the actionable property of the edge in question. Namely, if actionable ≥ k_f, then the system is able to add the edge to CG_A. The more complete the match (especially if no characteristic edges are missing), the more able the system to action upon actionable edges. The less actionable an edge (lower actionable value), the more complete a match must be in order to lead to the inference of the edge. An edge with zero actionability cannot be acted upon, except if the match is complete, in which case, the edge is already matched.

As an agent may have several actionable edges (across various patterns), choosing which action should be taken at a moment of time, if any, is done using the partial matches of the patterns. When an actionable edge, in a pattern that is otherwise matched, is missing from the context graph, an action will be taken. This is how context patterns can be used to select the action to be performed by the agent.

4.5. Time in the Context Graph

Context is dynamic. The user's context changes with the user's activity and other changes in the environment, which are relevant to the user's activity. In order to account for these changes, an agent/a system may probe the environment continuously to get the exact current situation, but this may not be always possible or tractable. However, one agent can assume that some things remain true for a certain amount of time during which they qualify as beliefs (the agent cannot now for sure if they are true).

This mechanism is implemented in the context graph using the validity property for edges. For edges that will expire, the property indicates when they will expire. The context graph is associated with a clock, providing a value for the current moment of time (e.g., milliseconds passed since January 1, 1970). Whenever an edge expires, it is removed from the graph.

An edge acquires validity either by being added manually by a user or by being inferred by the system as a result of a match with a k_f larger than the edges' actionability (see Section 4.4). When an edge is inferred, it is added to the graph with a validity equal to the persistence property of the pattern.

4.6. Recognizing Sequences of Events with Timelines

In a context-aware application, and in AAL in particular, there has been a great deal of research in the field of recognizing sequences of activities [45,46,65]. These works show the difficulties in managing temporal sequences. For example, if the system knows just that Emily is in the bathroom, it cannot tell if any problem has occurred. If Emily has been in the bathroom for five minutes, it is alright; if she has been in there for one hour, then it may be likely that there is a problem; conversely, if she goes to the bathroom too often, that should be equally noted.

To this end, we have included in our model a new element—the timeline. Timelines integrate with the current framework for graph matching and allow the user to describe sequences of events that should be recognized and the appropriate action to take, if any.

A timeline is a second-order graph pattern (see also Figure 4):

• $T_s^P=(V^P,E^P,\mathit{\text{state}})$, with V^P ⊆ Patterns, state ∈ {active, inactive} and

• E^P = {(from, to, label, state) | from, to ∈ $V_s^P$, label ∈ Labels, state ∈ {disabled, enabled, active}}, with

• Labels = {(λ), (‘next’)}

  • ∪{(relation, quantum) | relation ∈ { ‘sooner-than’, ‘later-than’}, quantum > 0}

  • ∪{(‘interval’, quantum1, quantum2) | quantum1, quantum2 > 0, quantum1 < quantum2}

  • ∪{(‘time’, quantum) | quantum > 0}

A node in a timeline is a pattern in Patterns. The label of an edge can take values that are time lengths (e.g., “5 minutes”, “more than 1 hour”, etc.), special values (e.g., next) or the empty string. Once a timeline is activated, its nodes and edges describe a sequence in which patterns should be matched. It is required that the timeline has one root, which is a single node with no incoming edges.

Initially, a timeline is inactive and all edges in it are disabled. A timeline becomes active when the pattern in the root of the timeline is matched. As a result, the edges going out from the root become enabled. Enabled edges can become active depending on their label (see below). When the pattern in the node at the destination of an active edge is matched, all edges in the timeline become disabled and the edges outgoing from the matched node become enabled. The process continues, until no edges are enabled or active, in which case the timeline becomes inactive.

Edges that are enabled become active as follows:

• edges with an empty label are activated immediately after they are enabled and remain so indefinitely (until they are disabled by an active node being matched);

• edges labeled with next are activated when the pattern in the source node of the edge is not matched anymore and activate their destination node only if the pattern in the destination node becomes matched at the same time (in the same sequence; for the definition of sequence, see Section 5.1);

• edges labeled with ‘sooner than time’ are activated immediately and are disabled after time;

• edges labeled with ‘later than time’ are activated after time passes and remain so indefinitely;

• edges labeled with ‘interval time₁time₂’ are activated after time₁ passes and are disabled after time₂ has passed since the timeline became active;

• edges labeled with ‘time time’ are activated after time has passed and are disabled at the next sequence.

The matching of context patterns works in the same way for timelines as with usual patterns from Patterns, with the exception that patterns in the nodes of the timeline are tested if they match only when the node is active. If a matched pattern has actionable edges, the corresponding action will be taken.

5.1. Efficient Persistent Context Matching

In our previous work, we have developed an algorithm that matches a context pattern against a context graph by first creating single-edge matches (one edge from the pattern to one edge from the graph) and then growing them to achieve maximal matches. The gist of the algorithm is that edge and node labels are compared only when creating the initial matches. Subsequently, a set of correct merge candidates is maintained for each match, so that matches can be merged just by uniting them and aggregating their merge candidate sets.

In the CCM platform, the difference from the previous case is that, in time, the context graph changes only slightly; therefore, a full matching process, against each pattern, is unnecessary. A second aspect deals with sequence. Edges may be added to or removed from the graph in rapid sequence, but it is necessary that the matching is done against a graph that stays constant through the matching process.

The CCM platform (see Figure 5) completely deals with the matching of a set of patterns (timelines or not) against a context graph. At any time, the context graph can be modified. Edges in the context graph may have limited or unlimited persistence.

The CCM platform uses, internally, a component that is called a Graph Matching Platform (GMP). The GMP is capable of obtaining all matches of a set of patterns against a context graph. Note that we treat patterns independently, not as a library. The similar, but very different, case would be to match a new graph every time, against a fixed set of patterns [66]. This is done sequentially. Every time the CG changes, the change is recorded as a transaction in a queue of transactions. A transaction can also contain multiple changes to the graph. If all matching is done, the sequence of the GMP is incremented, and the patterns are matched against the context graph with the next transaction applied. In fact, the GMP works on a graph that is a shadow of the current CG. In the CCM, the thread registering modifications to the graph is different from the thread in which the GMP runs, so that the GMP has time to perform the matching. Applications can register notification receivers with the CCM, and when a match is found, the receiver is notified, asynchronously. When the match occurs, the CCM also manages any modifications related to actionable items.

Beside the shadow of the CG, the GMP contains the list of patterns, each one having attached to it a Matching Process. Whenever a transaction is applied to the CG shadow, the Matching Processes are notified of each individual change. A Matching Process holds two indexes of matches: for each edge in the graph, the list of matches containing that edge, and for each in the pattern, the list of matches containing it. When an edge in the graph is removed, all matches containing that edge are declared invalid and will be removed whenever they are iterated over. When an edge is added to the graph, initial matches are created (against matching edges from the pattern), and merge candidates are added from among the matches of the neighbor pattern edges. This way, removing an edge is done in O(1) (per pattern) and the addition of an edge is done in O(m̅), where m̅ is the mean number of neighbor edges for an edge in the pattern, plus the time to grow any new matches (as per the normal graph matching process).

6.1. Studied Scenarios

All presented scenarios happen in the simulated context of Emily's apartment, a small studio with one room, a hall, the bathroom and the kitchen. In the apartment there are three Kinect^TM sensors (room, hall and kitchen) and some RFID readers (apartment door, fridge, kitchen door). A plan is displayed in Figure 7. We present the following scenarios, which have been used to test the platform, in order to give insight into how context graphs can be used in AAL applications.

7. Conclusion and Future Work

In the field of ambient assisted living, as in ambient intelligence, context awareness is vital in situation detection and reasoning. Context is not only instantaneous, but also temporal, depending on situations that have been detected before.

This work advocates the use of context graphs, context patterns and continuous, persistent context matching as efficient mechanisms for situation detection in AAL, also allowing for a user-friendly interface directly to the core of the system and a reasoning process that is easy to understand.

Context graphs have a solid foundation in graph theory, and graph matching has been researched for a long time. The algorithms and CCM platform that we have developed make context graphs an efficient solution that balances computational effort with memory usage and has a reduced footprint that depends directly on the complexity of the graph and, therefore, on the function of the agent.

The current limitations of the context graph and pattern formalism are related to its structural simplicity, on the one hand, and to temporal relations, on the other. The tradeoff of simplicity is that context patterns cannot account for a model of the environment; therefore, no true anticipation is yet possible. Temporal relations need to be advanced to account for absolute time intervals and coordinates, the frequency of actions, and so on.

Future work for the medium term involves improving the representation, so as to allow working with negative matches (“there is no match for the pattern”) and to make it easier to deal with numbers. Simultaneously, the platform will be tested in the Ambient Intelligence Laboratory, using both single-and multi-user scenarios.

An interesting subject related to context patterns is that of activity detection, learning and the automated discovery of context patterns. Here, previous work by the authors and other research groups can draw from the fields of data mining and behavioral patterns in order to grow patterns as they are recognized. Knowledge may also be discovered by using measures of graph entropy [67] applied to both existing patterns and the current context graph.