The development of (semi)-autonomous vehicles requires extensive communication between vehicles and the infrastructure called V2X communication. This should allow to increase road safety, which is a major objective of Cooperative Intelligent Transport Systems (C-ITS), and can be achieved by analyzing tra c scenes in real-time and detecting events that could lead to accidents, e.g., red light violations [2]. Roadside C-ITS stations will support V2X communication with cars and the infrastructure such as tra c lights, but also could be extended for more complex tasks as tra c scene analysis. We illustrate the necessity of analyzing tra c scenes by two real-world scenarios, which are known problems in the eld of C-ITS regarding safety and optimization [2]. The rst scenario, called road intersection safety, was identi ed in [2], where the authors consider \road intersection monitoring" as an important application to improve road safety. For this scenario, we assume a complex intersection with a sensor-based roadside C-ITS stations, where tra c accidents happen frequently. The second scenario, called changing tra c situations, concerns the deployment and maintenance of these stations. Currently, a roadside station is con gured once at deployment, hence it cannot react dynamically on a changing environment such as road construction or tra c jams due to a miscon guration of signal phases. Smart roadside stations could become autonomous by dynamically adapting to the changing environment and tra c situations. For instance, they could recognize unoptimized signal phases and adjust the phases according to the new situation. Enabling the analysis of tra c scenes as in the above scenarios, includes more general characteristics such as dealing with the complex C-ITS domain, as well as handling large quantities of message-based and spatio-temporal data. This characteristics are not only relevant fo the C-ITS domain, but also exits in other elds such as robotics or geospatial analysis. Primarily, we have identi ed two di erent abstract levels of understanding for the analysis, each of them poses its own challenges as: 1. How do we e ciently analyze C-ITS streams for detecting short-term problems as (complex) events, e.g., accident detection; This thesis research is conducted within the project LocTra Log (http://www.kr.tuwien.ac.at/research/projects/loctra og/) funded by the industrial PhD program of the FFG, in cooperation with Siemens AG Austria.
2. How do we diagnose complex problems, e.g., tra c-jams, which need a long-term observation span.
Each level can be seen independently and poses the additional challenge of intervening event detection and diagnosis in an e cient way. Another challenge arises from the nature of roadside C-ITS stations, which are (a) designed with limited memory and processing resources; (b) deployed in a distributed manner as a mesh network with a particular (spatial) topology. For enabling tra c scenes analysis, we aim to investigate tractable (lightweight) Knowledge Representation & Reasoning (KRR) methods for event detection and model-based diagnosis. The methods, namely rule- and ontology-based reasoning, have to be extended to streaming and spatial data taking a C-ITS domain model into account.
Section 2 describes state-of-the-art. Section 3 outlines the problem description, which is addressed by the research question and goals of Section 4 using the methods described in Section 5. Section 6 concludes with results and future work. 2
V2X Communication and Integration. The base communication
technologies (i.e., the IEEE 802.11p standard) allow wireless access in vehicular
environments, which enables messaging between vehicles themselves and the
infrastructure, called V2X communication. Tra c participants and roadside C-ITS stations
broadcast every 100ms messages for informing others about their current state
such as position, speed, and tra c light signal phases [
The Local Dynamic Map (LDM)
is a comprehensive integration
e ort of V2X messages; the
SAFESPOT project [
The LDM has the following four layers (see Fig. 1): Permanent static (static
information from GIS maps); Transient static (detailed local information such as
intersection features); Transient dynamic (temporary regional information like
weather); Highly dynamic (dynamic information such as V2X messages). Current
research, e.g., [
Stream-Processing, Complex Event Detection, and Stream-Reasoning.
Stream reasoning studies how to introduce reasoning processes into scenarios
that involve streams of continuously produced information. In that, domain
models provide background knowledge for the reasoning and lift streams to
a \semantic" level. Particular aspects of stream reasoning are incremental and
repeated evaluation, either push-based, i.e. on data arrival, or pull-based at
given points in time, and using data snapshots (called windows) to reduce
the data volume. Windows can be obtained by selecting e.g. data based on
temporal conditions (time-based windows), or data counts (tuple-based windows).
Besides the seminal Continuous Query Language (CQL) [
Diagnosis. In A.I., diagnosis is one of the classical application areas and evolved
around expert systems such as MYCIN. It can roughly be divided in the
datadriven [
The motivating scenarios road intersection safety and changing tra c situations
provide the setting, where we have identi ed theoretical and related technical
problems. The problems are in the scope of lightweight systems with limited
processor and memory resources. Hence, we limit ourselves to tractable KRR
methods and techniques. We already have de ned in [
Event Detection. Event detection is crucial to lter safety relevant events like vehicle collisions, or tra c patterns like a tra c jam. It is closely tied to stream processing, since the events are ltered from di erent C-ITS data streams, where the integration layer allows us to map the streams to the ontology. Since, there is no query and ontology language yet suited for querying the streams that include spatial data, we face the following problems: Which data model and query language is suited for our streams and what \features"this language should include. For instance, what kind of window operators and aggregate functions could be applied. In case of DL-Lite, our extension might a ect its computational properties as First-Order-Rewritability (FO-Rewritability). Further, how can we deal with missing and inconsistent data inside a window. Simple events might be detected by this new query language, but complex events (e.g., multiple-vehicle collisions), which are a chain of simple events satisfying speci c temporal and spatial relations, are not captured. This might require more powerful methods related to stream reasoning.
Diagnosis. With event detection, we cannot nd the cause for a tra c jam, merely the observations and aggregated facts are captured. Since we only consider model-based diagnosis, we aim to nd a minimal set of multiple diagnosis models, where di erent combinations of faulty components might occur. Creating multiple diagnoses models could be computationally expensive, hence we need a techniques of iteratively calculating these models. Furthermore, we need to investigate how the quality of a model can be determined by allowing preferences. Another challenge arises from the complex domain model of C-ITS, which adds temporal, spatial, and ontological aspects to the diagnosis. For instance, one diagnosis model might be valid now, but already invalided at the next time point. For event detection a query answering based approach might su ce, but for diagnosis a rule-based language like ASP or Datalog might be better suited. However the mentioned languages have to be adapted according to the desired features, e.g., streaming data, but keeping desired computational properties as tractability. Interaction between Event Detection and Diagnosis. Since the calculation of a diagnosis step is slower than updates in the C-ITS data streams, a two-level approach has to be applied, where the input data is rst fed into event detection component for shallow reasoning to determine whether the changed data needs deeper reasoning on the second level, i.e. the full diagnosis. However, an e cient and simple interaction needs to been thoroughly investigated. 4
Research Questions. The overall research question is whether lightweight KRR methods and techniques are suitable for C-ITS applications such as tra c scene analysis. This question can be divided into the following sub-topics: - Which tractable methods and techniques are suitable to extract (complex) events from C-ITS data streams having an elaborate domain model? - Based on the detected events, how can model-based diagnosis be applied to nd long-term problems in roadside C-ITS stations? - How is an e cient interaction between both components feasible? Following from the research questions, the goals of this thesis are as follows: 1. Goal: Event Detection for C-ITS. Based on the integration layer with an LDM ontology, we aim to work out an event detection component by extending DL-Lite for query answering over C-ITS streams. For this, we aim (a) to de ne a data model and query language suited for spatial data streams; (b) to extend the semantics for query answering with DL-Lite including window operators and aggregates over streams and spatial relations over spatial objects; (c) to provide a technique for query rewriting taking the above into account. The above results might not su ce for complex event detection, hence the language has to be extended to capture temporal relations as in LTL. 2. Goal: Model-based Diagnosis for C-ITS. We aim to develop a modelbased diagnosis component that includes a clear de nition and encoding of observations O, a (fault) model S, and a list of system components C applied to the C-ITS domain and in particular to roadside stations. The encoding has to capture the temporal, spatial, and ontological aspects of C-ITS. Based on the encoding, we aim to apply or extend standard rule-bases evaluation with an ASP or Datalog solver. We might encounter technical limitations, e.g., tractability, with standard techniques and might need an iterative approach for evaluation. 3. Goal: Component Integration. Since the event detection part must communicate changes in the requirements to the diagnosis component, a suitable interface and sharing of the domain is required. We aim to de ne the bidirectional interface between the event detection and diagnosis component, and design methods and techniques to realize the 2-level approach for shallow and deep reasoning, such that unnecessary diagnosis computations are avoided while necessary ones are correctly initiated.
Since our overal goal regards lightweight KRR methods and techniques, our
focus is on tractable rule- and ontology-based reasoning. As already mentioned,
we start with DL-LiteA for the LDM ontology, which is the main language for
ontology-based data access [
Example 1. The following query illustrates the component as it detects red-light violations on intersections by searching for vehicles y with speed above 30km/h on lanes x whose signals will turn red in 4s: q(x; y) : LaneIn(x) ^ hasLocation(x; u) ^ intersects(u; r) ^ pos[line; 4s](y; r)^ Vehicle(y) ^ speed[avg; 4s](y; v) ^ (v > 30) ^ isManaged(x; z)^
SignalGroup(z) ^ hasState[ rst; 4s](z; s) ^ (s = Stop) Query q exhibits the di erent dimensions that need to be combined: Vehicle(y) and isManaged(x; z) are ontology atoms that have to be unfolded with respect to the LDM ontology; intersects(u; v) and hasLocation(x; u) are spatial atoms, where the rst checks spatial intersection and the second the assignment of geometries to objects; speed[avg; 4s](y; v) resp. pos[line; 4s](y; r) de nes a window operator that aggregates the average speed resp. positions (as points) of the vehicles over the streams speed and pos; hasState[ rst; 4s](z; Stop) gives us the tra c lights that switch in 4s to the state \Stop".
For the evaluation of this query, we have to extend OBDA to handle spatial
and streaming data, which is not considered in the standard approaches as [
We introduce a bag-based epistemic semantics for the queries, so that we locally close our world for A and avoid \wrong" aggregations due to the open world semantics of DL-LiteA. For normal objects and constant values, we allow di erent aggregate functions such as min; max; sum on the data items of a stream. For spatial objects, geometric aggregate functions such as point; line; poly are applied, which create new geometries based on the aggregates.
Model-based Diagnosis. As already outlined, we will support model-based
diagnosis as our method of choice. First, we need to de ne our roadside station
and the related problems (e.g. the model of an accident) as a formal diagnosis
problems with O, S and C. Observations O are taken from the detected events
3 http://vision-tra c.ptvgroup.com/de/produkte/ptv-vissim/
via the bidirectional interface; C is de ned as the list of system components
that includes details on the actors involved in tra c scene such as tra c lights,
vehicles, and the topological de nition of an intersections. Further S is the model
of a real system's behavior, which includes a de nition of correct signal plans
for tra c lights, driving behavior of cars, and tra c properties like accidents
and tra c ow. A diagnosis D is then a subset of C, which is consistent with S
and combined with S entails O. Then, we could compile the resulting diagnosis
problem into a standard encoding for an ASP or Datalog solver. The results of
Beck et al. [
In this paper, we have presented a framework for allowing tra c scene analysis in C-ITS systems based on tractable KRR methods and techniques such as ruleand ontology-based reasoning. For the scene analysis, we have identi ed that we need a fast event detection and a model-based diagnosis component that have a common vocabulary based on an LDM ontology. Then, we have shown that event detection is feasible by extending OBDA with query answering over streams of spatial data. Further, the model-based diagnosis component was outlined, so we will be able to identify faulty components of a C-ITS system.
The rst two steps are almost nished, however results regarding correctness and handling possible inconsistencies in query answering are desired. An initial prototype needs further development including optimizations and complex spatial aggregates. The third step is ongoing work that currently involves a clear de nition and encoding of the model-based diagnosis problem including all involved components, which should allow us to encode and compute it with a ASP/Datalog solver. At the same time, we need to specify the bidirectional interface and work out the information ow between the components. Finally, we aim at evaluating and testing the integrated components using a tra c simulation under real conditions.