In this paper we discuss the adoption of a formal approach to correlation of heterogeneous information based on qualitative spatial reasoning to contribute to some relevant aspects that stream reasoning need to face in Urban Computing. The approach is based on the adoption of Commonsense Spatial Hybrid Logics to reason about events and infer higher-level scenarios of interest. This paper therefore extends previous work of the authors in the context of pervasive computing systems in order to take into account an urban-scale application context. In order to discuss the advantages of the approach a real-world application devoted to control and monitor different phenomena occurring in urban environments is described. Finally, some issues related to the exploitation of the approach in Semantic Web frameworks are discussed.
The large availability of sensing technologies, connectivity, mature data analysis
algorithms and ubiquitous access to information opened the door to a new application
scenario that has been recently referred to as Urban Computing [
In this scenario, a great deal of the available information concern specific parts of
the environment and has a temporal reference. The continuous nature of the information
management process tightly connects the problem of interpreting and reason about this
kind of information to the problem of analysing and reasoning about data streams [
Modern applications in Urban Computing require not only monitoring of specific phenomena e.g. traffic, but an integrated monitoring of the heterogeneous information produced by different information acquisition devices and different subsystem (e.g. concerning traffic, pollution, occurrence of special events, and so on) in order to govern complex urban phenomena, interpret and infer critical situation, and possibly take on suitable control actions. In particular, there is an increasing need of relating computation to the spatial context in which it takes place, and models managing spatially related information are necessary to correlate local information, to coordinate devices and to supply context aware services.
In this paper we discuss the adoption of a formal approach to correlation of
heterogeneous information based on qualitative spatial reasoning to contribute to some of the
crucial aspects that stream reasoning need to face in Urban Computing. The approach is
based on previous work where these techniques have been applied to home-scale
pervasive computing applications [
In Section 2 we discuss the application context, which consists of a real-world
platform for monitoring and control of an urban area; the platform integrates
domainspecific subsystems and different kind of information and knowledge sources. Section
3 introduces a four-layered conceptual architecture for information management, on
which the above mentioned platform and other similar monitoring and control
systems [
Supercentro is an ongoing project carried out by Project Automation S.p.A. for the development of a platform integrating different subsystems producing and storing information about phenomena related to mobility (or relevant to it) in the City of Milan. The aim of the platform is to support qualified operators in monitoring such phenomena in order to take suitable actions, to diffuse relevant information to citizens and to eventually select retroactive actions autonomously.
At the bottom level, data are collected by a number of technologies and devices including traffic and environmental sensors (monitoring air pollution, noise and other weather reports), traffic violation detectors, closed circuits televisions (CCTV), and so on. A calendar containing extraordinary or periodic events occupying part of the road network (e.g. roadworks, demonstrations, local markets, and so on) provides another information source. The information collected are processed and interpreted at the local level by a number of softwares and algorithms that take raw data as input and produce aggregate information, represented as events, that are stored in a repository; as an example, data about traffic flows are aggregated with statistical techniques to associate a qualitative measure of traffic both to road sections where sensors are not available and to wider areas. Information can then be diffused through multiple channels, among which mobile services providing context aware functionalities: messages about traffic congestions should be filtered on the basis of the agent location and proactive suggestions need to be delivered on the basis of the overall context. Other control actions that need to be taken on the basis of the context concern the management of traffic regulators, Variable Message Panels (VMP), CCTV, and so on.
An event correlation manager is needed in the Supercentro platform in order to make sense of the great amount of events populating the repository at any time, providing human and software agents with meaningful high level information about the environment they are and move in. The event manager needs to consider (i) the urban spatial environment, and (ii) a high degree of heterogeneity of the events to be correlated. Consider that some of these correlations need to produce information which can be referred to the spatial environment in a global perspective (e.g. heavy traffic affects all the trade fare area and its neighborhood); however, it would be also useful to model correlations on a local perspective (e.g. heavy traffic occurs on all the areas that are reachable from the current location x) because these correlations should provide information to be delivered to users’ mobile devices, or, in the future, could be even performed by the mobile devices themselves. 3
The approach described in this paper is based on a four-layered conceptual architecture
for information processing in control and monitoring systems. The general
characteristic of the architecture and the covered domains have been discussed in [
Where much of the processing at the local interpretation level is usually performed
by targeted and domain specific efficient algorithms (e.g. neural-networks for the first
analysis of camera streams), model and knowledge-driven correlation approaches are
effective at the correlation level [
The key aspect of the spatial and temporal-based approach to correlation consists in exploiting the spatial and temporal representation as the substratum that allows to correlate otherwise heterogeneous information (e.g. a air pollution detection and a traffic measure detection have in common that they can be interpreted both as events occurring on a portion of space and time). In order to map the above described approach to what has been defined as “stream reasoning”, data in the streams we focus on consist of events as representational units, which are usually outputs of preliminary processing. From our perspective stream reasoning is interpreted as a knowledge based event correlation problem.
In this paper we focus on space for two main reasons. On the one hand, the extension
of a spatial modal logic in order to a logic considering also the temporal dimension is
quite intuitive because of the well known axiomatizations of temporal modal logics
and of some spatio-temporal modal logics [
We therefore focus on spatial-based correlation of events assuming to reason about
what is known within an observation window, considering this window as time unit.
Different possible representations and interpretations of temporal event sequences are
represented on the left side of Figure 1; our approach assumes the regular and discrete
interval-based interpretation of regular timestamp-based event sequences, according to
the model adopted in [
The approach to information correlation as spatial reasoning consists therefore in
defining: (i) a spatial model representing the environment; (ii) a logic that allows to talk
and reason about events referenced w.r.t. the adopted spatial model; (iii) the domain
correlation axioms. In particular, as for the models, we defined the class of
Commonsense Spatial Models (CSMs), and as for the logic, we defined a family of Hybrid
Commonsense Spatial Logics (HCSLs), whose semantic is given by CSMs as underlying
but is based on correlations taking into account heterogeneous pieces of information and/or
information coming from different sources [
The CSHLs are based on a class of models for commonsense spatial reasoning based on the notions of “place” and “commonsense spatial relation”. We call Commonsense Spatial Models these kinds of graph-like models, which are defined as follows:
A Commonsense Spatial Model CSM = hP, RLi is a relational structure, where P = {p1, ..., pk} is a finite set of places, and RL = {R1, ..., Rn} is a finite non-empty set of binary conceptual spatial relations labeled by a set of labels L ⊂ N, and where, for each i ∈ L, Ri ⊆ P × P .
A place can be any entity identifiable by a set of properties or information, and relations in the structure are intuitively interpreted as spatial relations between places. Standard Commonsense Spatial Models are a class of models identified by three kinds of spatial relations, namely proximity, containment, and orientation.
All the formal properties of proximity and containment relations, and the main
properties of orientation relations are represented in Table 1 (abbreviated respectively as
P,C and O). Two more properties specific to orientation relations are provided later
on, in Definition 3. Intuitively, proximity relations represent the possibility of reaching
one place from another one (in both a physical and a metaphorical sense), establishing
connections among spatial entities. Containment relations define location and physical
inclusion between places, allowing to define hierarchies among places possibly with
different shapes, dimensions and nature (e.g. a room and a printer are both places).
Finally, relative orientation relations are introduced. Orientation relations are strict
partial orders of places w.r.t. some reference points: cardinal points are particular reference
points, and a relation such as “north of” defines an order on places such that north is
northern than any other place, that is, it is the top element of the order. Properties of
orientation relations include therefore the existence and uniqueness of a top element
for any orientation relation (axioms EX and UNI top element in Definition 3). This
approach allow to define special orders of interest in particular domains, as shown in the
next sections (e.g. the Trade Fair of a city). We refer to [
Let assume that {R1p, ..., Rkp} is a set of proximity relations, {R1c, ..., Rmc} is a set of containment relations, and {R1o, ..., Rno} is a set of orientation relations each one with its top element topi. A Standard Commonsense Spatial Model SCSM is a CSM p p with R = {R1, ..., Rk, R1c, ..., Rmc, R1o, ..., Rno} and {top1, ..., topn} ⊆ P .
Modal languages already proved to be very useful to reason about relational
structures, and have been exploited for temporal and spatial logics, for logic of necessity and
possibility and many others [
M, w
ϕ , where w′ is the denotation of i
Hybrid logics allow to express in the language itself, by means of nominals and satisfaction operators, sentences about the satisfiability of formulas; formulas preceded by satisfaction operators allow in fact to represent statements about specific states of the model, e.g. states of affairs occurring at certain places in our spatial interpretation of modalities.
A spatial hybrid logic is defined introducing a specific set of modal operators interpreted as spatial operators. The SCSMs then define the class of relational structures that provide the semantics, e.g. the spatial interpretation, of specific spatial operators.
Adjacency among places is represented by the somewhere near hPi and everywhere near [P] operators, interpreted over proximity relations; containment among places is represented by the somewhere inside hINi and everywhere inside [IN] operators, and the respective inverse hNIi and [NI] interpreted over containment relations; orientation in space is represent with cardinal direction operators interpreted over orientation relations; as an example, for North, we have somewhere north hNi and everywhere north [N].
Intuitively, a formula such as hPialarm means that an alarm is occurring somewhere near the place the formula is evaluated at (more literally: there is a place proximal to the current one where the proposition alarm is true). A formula such as [P]alarm means that an alarm is occurring everywhere near the place the formula is evaluated at (in every place proximal to the current one the proposition alarm is true). Nominals can be exploited to refer to specific places: @schoolalarm means that an alarm is occurring at the school (at the place named school the proposition alarm is true). Formulas can be arbitrarily combined with standard logical operators and modal operators can be nested: a formula such as @school(alarm ∧ [P][IN]¬smoke) means that everywhere inside every place that is close to the school is free of smoke (the proposition smoke is not true).
Formally, we introduce the notion of Standard Commonsense Spatial Logic, defined as follows.
Definition 3. (Basic Standard Commonsense Spatial Logic, SLbasic).
Language. SLbasic is a hybrid multimodal language containing the modal operators hNi, hEi, hSi, hWi, hINi, hNIi and hPi, the respective boxes ([N], and so on), and where {north, east, south, west} ∈ N OM .
Semantics. Formulas of Lb are interpreted over a SCSM : hINi, hNIi are interpreted over containment accessibility relations, hPi over a proximity relation, and hNi, hEi, hSi, hWi over orientation relations, whose top elements are respectively the denotation of “north”, “east”, “south”, “west”.
Calculus. A sound and complete calculus for SCM Sbasic is given by H +ΦS +XS
where:
– H is the standard tableau system for Hybrid logic [
@i ([N]hSii ∧ [S]hNii) @i ([E]hWii ∧ [W]hEii) @i ([IN]hNIii ∧ [NI]hINii) @i (hNIihPihNIij → hPij)
3⋆i → [IN]3⋆i where ⋆ = (N |E|S|W )
Finally, the interpretation of “north” is bound by the formula @north¬hNii, and analogous formulas are introduced for the other top elements.
As for the represented cross-properties, the first three axioms specify that the
relations RS /RN , RE /RE and RIN /RNI , are reciprocally one the inverse of the other one.
The fourth axiom represent that if two places are proximal, the places that contain them
are proximal as well. The last axiom represent that if a place has a specific orientation
with respect to another place, then every place contained in it inherits such an
orientation. Observe that each SCSM is a frame; therefore, classes of SCSMs characterized
by specific constraints on their relations identify classes of frames. On the basis of the
above axiomatization, in [
We want to stress here at least some peculiarities of the tableau based calculi for Hybrid Logic that will turn out to be very important for commonsense spatial reasoning. – First, Hybrid Logic’s pure formulas, i.e. formulas that do not contain propositional variables, allow defining more properties than normal modal formulas (see Table 1).
We will refer to this property of Hybrid Logic as frame definability. – Secondly, Hybrid Logic allows us to fully exploit frame definability for reasoning purposes. In fact, consider that the tableau rules given by Blackburn provide a sound and complete calculus for Hybrid Logic in this sense: a formula ϕ is tableau provable iff it is valid, that is, iff it is true in every frame. It has been proved that it is sufficient to add a set of pure formulas defining the desired frame to the tableaux to obtain a sound and complete calculus with respect to that frame. We will refer to this property as to modularity. As an example of how one can exploit modularity, see the introduction of the RtF≻ relation and of the corresponding htF≻i modal operator, in Section 5.
Given the application scenario described in Section 2, here we discuss (i) the extension of SCMSs introduced in order to model the urban spatial environment of interest, (ii) the hybrid logic to talk about these models, and (iii) some formulas defining the interesting scenarios that can be inferred. To show the expressiveness of hybrid commonsense spatial logics for modelling context aware reasoning in this paper we focus on traffic-related aspects of the correlation. 5.1
CSMs for the Urban Context Different cartographic and spatial representation levels are considerd in the Supercentro project. The first level relevant to event correlation consists of an undirected graph where nodes are intersections and edges are road sections with no driving direction3. A second level of representation can be defined on top of this last undirected graph, considering area-level entities as specific clusters of roads. An area consists of a set of edges and intersections, that is, a set of undirected arcs and nodes of the higherlevel cartographic representation. Each edge belongs to one and only one area, while intersections can belong to more than one area. 3 Edges of the directed graph are the main entities of the road network while intersections are pure connectors; a square, e.g. in such cartographic models is represented by a set of edges; location is referred to edges.
As for the scenario of the Supercentro project, areas, mobile and static agents are a first set of spatial entities (i.e. places of the CSM) that need to be considered. Mobile and static agents represent mobile and static devices, that is, sensors (e.g. CCTV, traffic violation detectors, and so on) and actuation devices such as information clients and providers (e.g. Virtual Message Panels, PDA-based software agents, control central), and control systems (e.g. traffic regulators).
Since in the following we focus on traffic-related aspects, an important issue that needs to be considered is the connection between areas interpreted as the possibility for drivers to move from an area A to an area B. This new connection relation that must be introduced is not a “proximity relation” of a SCSM essentially because it cannot be considered symmetric. In fact, the possibility to move from an area A to an area B depends on the existence of an intersection belonging to A and B, but also on the Administrative Code (in fact, it can be the case that two areas would be topologically connected, but the Administrative Code prevent drivers from moving from A to B because of, e.g. one ways or forbidden turns). In an urban context, it is possible to define interesting relative orientation relation w.r.t. to significant reference points in the city. As an example, we introduce an order toward the Trade Fair, a place of the city of Milan that often attracts many visitors inducing traffic congestions. These relations, together with those of SCSM, will be considered as accessibility relations (in the sense of Modal Logic) of the resulting model. 5.2
Reasoning about Traffic Scenarios We recall that area-level traffic measures can be estimated on the basis of local interpretation carried out with statistic algorithms (see Section 3). As a consequence, in correspondence to each area-level entity in the model we have an inferred qualitative measure of its traffic density and condition, namely: heavy congestion, congestion, dense, fluid-dense, fluid, very fluid. The system is also able to map location on the arealevel spatial representation; these mapping will be exploited to show the capability of our approach to define context-aware scenarios. The hybrid multimodal language for representing event correlation at the area-level for the Supercentro project results from an extension of the SLbasic language.
Definition 4. (Supercentro Area-level Commonsense Spatial Logic, SLarea).
Language. SLarea is a hybrid multimodal language containing the modal operators hNi, hEi, hSi, hWi, hINi, hNIi, hPi, hRi and htF≻i, the respective boxes ([N], and so on), and where {north, east, south, west, tradeF air} ∈ N OM .
Semantics. Formulas of SLarea are interpreted over a specialization of the SCSM , that is devoted to “area-level” of the Supercentro project. In particular: hINi, hNIi, hPi, hNi, hEi, hSi, hWi are interpreted over the relations introduced in Section 4, hRi is interpreted over a reflexive reachability relation defined among areas, and htF≻i is interpreted over the relation RtF≻ , that is an orientation relation whose reference point is tradeFair.
The definition of the formal properties of the reachability relation R through axioms
defined on hRi is given by the pure formula defining reflexivity: @ihRii. Formally this
means that the frame capturing the spatial representation needed in this scenario is
defined by pure formulas of SLarea. Therefore, Theorem 1 of [
In order to represent interesting scenarios in the domain of the Supercentro project,
we equipped the SLarea language with the following set of propositional symbols
representing traffic density on the areas: heavy congestion, congestion, dense,
fluid-dense, fluid, very fluid. Finally, highway access is a
propositional symbol that is used to qualify specific peripheral areas of the city, with the
obvious meaning. The satisfiability of the formulas, that have to be considered as scenario
descriptions depends on: (i) the place of the CSM the formula is evaluated at ; (ii) the
contextual information provided by the model, concerning the topological structure and
the information referred to each place (e.g. traffic density, ontological qualifications of
the areas, and so on). Such information is provided by formulas of type @ip, with p
being a propositional variable. In what follows, we present some examples of interesting
scenarios, defined by means of SLarea formulas. An intuitive description of their
satisfiability conditions explains the meaning of the formulas and how they can be exploited
in deductions. For each formula ϕ defining a scenario one should think of introducing
a formula ϕ ↔ ScenarioID, where ScenarioID is a propositional variable naming the
scenario. Then deduction can be performed on the names of the scenarios defined. For
formal details about deductions based on the tableaux we refer again to [
Scenario 1. (Everywhere Outgoing Fluent).
[R](fluid ∨ veryFluid) “Every area I can reach from here is characterized by fluid or very fluid traffic”. Scenario 2. (Somewhere Outgoing Slow).
hRi(heavycongestion ∨ congestion) “Some area I can reach from here is characterized by heavy congestion or congestion”.
The satisfiability of the above two formulas is context dependent in the sense that it depends on the place from where the formula satisfiability is checked. As a consequence, if one suppose that the task of verifying the presence of specific scenario is performed by a mobile agent, the outcomes of this task may be different according to the current location of the agent itself.
Scenario 3. (Somewhere Outgoing Towards Trade Fair Fluent).
(hRi(fluid ∨ veryFluid) ∧ i) ∧ htF≻ii “There exists at least an area that I can reach from here in the direction of the Trade Fair, where traffic is fluid or very fluid”. 3 Note that this choice strictly depends on the nominals that immediately follow the first satisfaction operators in a formula but also, where there is no satisfaction operator in the head of a formula, on the specific locations the reasoning task takes place.
Scenario 4. (Somewhere Inside Somewhere Outgoing Towards Trade Fair Fluid.
hINi((htF≻ii ∧ fluid) ∧ hRii) “There exists at least an area inside the one I am in, from which I can reach an area in the direction of the Trade Fair that is, where traffic is fluid”.
The scenario above provides useful information in the case the satisfiability check is performed on a non atomic area of the model. As an example, the following formula stating that the area “Sempione” contains the areas “Sempione Cerchia East” and “Sempione Cerchia West” is a valid in the area-level model of the Supercentro project: @sempionehINisempioneCerchiaEast ∧ hINisempioneCerchiaW est Therefore, checking the satisfiability of the formula describing Scenario 4 at the Sempione macro-area, may provide useful contextual information about light regulation plans for the Sempione macro-area can be activated to make the traffic flow out better.
Scenario 5. (Everywhere Outgoing from Trade Fair Slow).
@tradeF air[R](heavycongestion ∨ congestion) “All the areas reachable from the Trade Fair, are characterized by heavy congestion or congestion”.
Note that a satisfaction operator in the head of a formula can be introduced, and exploited, as integral part of the definition of a specific scenario (as suggested in the above example), or can be dynamically added to the formula, possibly with different nominals, according to the current location of the mobile agent requiring the outcomes of the reasoning task.
Scenario 6. (Somewhere at North of Trade Fair Fluent Highway Outgoing).
@tradeF airhNi((fluid ∨ veryFluid) ∧ hRihighwayAccess) “There exists at least an area at north of the Trade Fair, at which it is the case that the traffic condition is qualified as fluid or very fluid and from which it is reachable an area characterized by the presence of a highway access point”.
Due to the semantics of the satisfaction operators, these last formulas provide a “global” perspective on what is going on in term of traffic conditions at the area-level model. The presence of the satisfaction operators, in fact, indicate that the satisfiability of these formulas, regardless of the current location of the mobile agent, starts from the area denoted by the nominal tradeFair. 6
Here we briefly introduce some pointers to previous papers of the same authors that
provide an accurate comparison of our approach to correlation and spatial reasoning
with related work. [
We refer to this last work and to [
As for the consideration of spatio-temporal events, an example of spatio-temporal
correlation (but where spatial representation is simplified up to the 1D) is presented
in [
The approach to stream reasoning based on event correlation presented in this paper aims at providing a controlled modeling framework to define and reason on event patterns (the scenario). As for modeling capabilities, the approach has a number of advantages.
First, the combination of the modal and the hybrid perspective available in CSHL allows for the representation of global and context aware scenarios (scenarios whose definition with a CSHL formula is satisfiable depending on the place it is evaluated); the last feature is interesting to model correlation tasks for mobile agents.
Second, the approach is flexible enough due to the expressive power of hybrid logics: also within the new scenario described in this paper, we exploited the hybrid logic approach to spatial representation and reasoning, with some slight modifications and extensions of the language introduced in Section 4. In particular, we almost kept containment and direction relations basic properties (with some constraints related to typing) and we modified connection relations.
Third, we took advantage from both the characteristics stressed out in Section 4: frame definability and modularity. In fact, the hybrid language introduced allowed to model quite specific conditions defining the frame of reference (the road network), and this would have not been possible within plain modal logic. On the other hand, we have been able to adapt and modifying single operators still not loosing the logical calculus defined in Section 4 (it is sufficient to replace the rules for binary operators with their generalization for operators of arbitrary arity).
In the past a subset of the possible correlation definable through our logic has been
implemented through production rule-based systems, via non formal mappings of a set
of significant logic-based correlation axioms to rules. However, this approach is not
formal and is domain dependent. The calculus defined here and based on [
Nowadays Semantic Web technologies and languages such as RDF, RDFS and OWL are becoming more and more popular for knowledge, information and data exchange on the Web. In the following we discuss some preliminary ideas on how to bridge the gap between the HCSL as modeling framework and Semantic Web technologies and languages to implement the approach.
As a matter of fact, hybrid logics are logics to talk about graph structures, which are also at the basis of RDF and OWL. Basic hybrid logics (standard modal semantics plus nominals and satisfaction operators) easily map to SHOIQ constructs. Assume to focus on Abox statements since events are represented as assertions. The more straightforward mapping between Abox statements and CSHL formulas is given by interpreting SHOIQ nominals as CSHL nominals, concepts as propositional variables, type assertions and role assertions as hybrid pure formulas as depicted in Table 2. 4 Available at http://www.luigidragone.com/hlmc/ tween CSHLs and Semantic Web-related languages such as the Description Logics, we discuss two main questions related to the application of the approach discussed here to event correlation in a Semantic Web context.
Question 1. Assuming to represent events as RDF triples or molecules, are the
CSHLs enough expressive to reason about such events? Two main features of
OWLDL (via mapping to SH OI QD) that are not covered by the CSHLs presented here
are cardinality restrictions and an explicit treatment of datatype properties and concrete
domains. As for the first issue, extension of modal logics to represent cardinality
constraints on accessibility relations are called graded modal logics; graded hybrid logics
and tableaux to reason about them are introduced in [
Question 2. To what extent it is possible to exploit available Semantic Web technologies to perform event correlation as modeled in CSHLs? Many of the axioms described in Definition 3 cannot be translated in SH OI QD axioms and therefore OWL-DL reasoners are not able to handle them. The more promising strategy is therefore to exploit rules for Semantic Web languages or combining rules and query answering. Suppose to be able to represent all the axioms characterizing S Larea according to Defition 4, or in alternative, at least an important core of them; then, is it possible to codify the scenarios described in Section 5.2 in SPARQL queries? This question can be also interpreted as follows: given some kind of algorithms that is able to complete the spatial information in the model according to the semantics of the spatial relationships, is it possible to exploit query answering for SPARQL to perform model checking on available information? The answer to this question is “no” in the general case. The formulas that can be straightforwardly translated into SPARQL queries are the formulas built only from propositional variable, nominals, conjunction and diamond operators (e.g. Scenario 4 of Section 5.2). In particular, a script-based strategy to handle conjunction, disjunction and box operators (e.g. [I N ]) is needed. SPARQL extensions that allow to quantify on variables in the query graph could provide support at least for the treatment of box operators and therefore the detection of scenarios including “everywhere” conditions5. 5 The RDF Gateway 3.0 triple store provides a query engine that seems to be able to treat a SPARQL extension including provide quantification and negation; cf. http://www.intellidimension.com/developers/library/sparql-extensions.aspx
Our current research focus on the above two questions, inquiring extensions of the SCHLs to explicitly treat concrete domains and datatype-like relations, and exploring the combination of rule-based reasoning and script-based SPARQL query answering.
Special thanks go to Alessandro Mosca for its previous contribution, and for the recent inspiring exchange of ideas on these topics.