The development of (semi)-autonomous vehicles and communication between vehicles and infrastructure (V2X) will aid to improve road safety and reduce emissions by identifying dangerous traffic scenes based on movement patterns. A key to this is the Local Dynamic Map (LDM), which acts as an integration platform for static, temporary, and dynamic information about traffic in a geographical context. We have semantically enhanced the LDM to allow an elaborate domain model, captured by a mobility ontology, and queries over data streams that allow for semantic concepts and spatial relationships. Our approach is in the context of ontology-mediated query answering (OQA), which features conjunctive queries over DL-LiteA ontologies that allow for window operators over streams having a pulse and for spatial relations between spatial objects. We have introduced in previous work simple aggregate queries over mobility streams, which often do not suffice to capture more complex movement patterns. Based on three scenarios, we define requirements derived from a domain-specific list of features. Further, we present an extension of the previous aggregate functions with statistical and predictive functionality, which allows us to query more complex mobility patterns such as road networks statistics, vehicles maneuvers, and temporal connected events such as (potential) accidents. We also give a more detailed report on our implementation and analyze it regarding the features and requirements.
The development of (semi)-autonomous vehicles needs extensive communication
between vehicles and the infrastructure, which is covered by Cooperative Intelligent
Transport Systems (C-ITS). These systems collect temporal data (e.g., traffic light signal
phases) and geospatial data (e.g., GPS positions), which are exchanged in
vehicle-tovehicle, vehicle-to-infrastructure, and combined communications (V2X). This aids (a) to
improve road safety by analyzing traffic scenes that could lead to accidents (e.g., red light
violations), and (b) to reduce emissions by optimizing traffic flow (e.g., dissolve traffic
jams). A key technology for this is the Local Dynamic Map (LDM) [
We have semantically enhanced the LDM towards an elaborate domain model, captured by a mobility ontology, with conjunctive queries (CQs) over data streams that allow for semantic concepts and spatial relationships to address safety applications, such as detection of red light violations on complex intersections managed by a roadside C-ITS station. To realize query answering (QA) over mobility streams, spatial and streaming data were lifted to ontology-mediated QA (OQA) with the ontology language DLLiteA . However, for monitoring more complex actions such as vehicle maneuvers (e.g., overtaking), this query language is too limited and needs to be extended with temporal, statistical, and predictive functions. To this end, we start with the three important scenarios “intersection statistics”, “mobility patterns”, and “event detection” and derive requirements for a suitable query language, which are based on a domain-specific set of features. Our contributions are briefly summarized as follows: - we define our desired scenarios, features, and requirements (Section 2); - we outline the field of V2X integration using LDMs and provide details on our LDM ontology that incorporates the features/requirements (Section 3); - we present our current data model, query language, and outline the evaluation techniques with extensions regarding the features/requirements (Section 4); - we give a detailed description of our query platform and analyze it regarding the implemented features and requirements (Section 5).
In Section 6, we discuss related work and conclude with ongoing and future work. 2
In this section, we give three application scenarios that are used to define the features and derived the requirements. All scenarios are related to roadside C-ITS stations deployed on either a single road intersection or a network of intersections. The C-ITS stations receive any V2X message and can send signal phases and a local intersection topology messages, to inform other participants on its current state. The other participants such as vehicles (or pedestrians) might share their states such as their current speed, acceleration, and position using V2X messages or an IoT-based protocol (e.g., ZigBee, Bluetooth, or Z-Wave).3 Furthermore, the C-ITS could have access to auxiliary streams providing news, public transport, and weather data.
S1: Intersection and Network Statistics. The focus of this scenario is on the collection of statistical data concerning stops, throughput, traffic distribution, or types of participants by aggregating the streaming data on specific intersections. Regarding this scenario, we have identified the following use cases and measurements: 1. Object level: for a single vehicle, the average speed, acceleration, number of stops, or on a sensor level average temperature or rainfall could be calculated ; 2. Road/Lane level: on the road/lane level, important measures could be the average throughput, waiting time, the amount of stops, but also traffic light related measurements such as the average signal phase length; 3. Intersection level: on this level, besides calculating a summary of road/lane level indicators, matrices regarding transfers (e.g. how many cars head straight on), modality, and type mix (e.g. relation between public/private transport, or car/truck) could be determined; 4. Network level: on the network level, intersections are represented by nodes connected by roads. In this setting, we could calculate summary of each intersections, but also transfer times and traffic flow between intersections could be calculated.
S2: Vehicle Maneuvers. This scenario is concerned with the detection of maneuvers performed by a single car or a group of cars. The detection of maneuvers can be used for statistics (e.g., number of cars turning left), or as a basic pattern for event detection as defined below (e.g., crossing a double line). The following maneuvers could be extracted from the trajectories of vehicles: 1. Slow down/speed up: the detection of these maneuvers could be done by aggregating the acceleration; 2. Drive straight on, turn left, turn right: for the detection of turns, the geometry of a vehicle trajectory could be matched to geometries representing all types of turns. 3. Stop, load/unload, park: to determine whether a car has stopped is straightforward, but distinguishing the reason for the stop needs contextual information such as the location of the stop, e.g., parking; 4. Lane change: this maneuver requires the combination of trajectory-based geometries and spatial relations that are evaluated w.r.t. the trajectories; 5. Overtake: this maneuver is an extension of a “change lane”, but needs additionally trajectory predictions.
Note that the calculation of the trajectory needs a preprocessing step of correcting frequent GPS errors in position data.
S3: Event Detection. An important C-ITS application is “road safety” [
Features and Requirements. The eight resp. nine central requirements, e.g., volume,
velocity, variety, incompleteness, complex domain models, etc. identified by [
We have derived the requirements (shown in Table 1) by analyzing each scenario and use case regarding the necessary features. In case of a single feature, e.g., trajectory computation, we only distinguish between “Y” for required, “N” for not required, and “P” possibly required. For instance in S3.1, a point-based time model suffices, however, intervals might be helpful to represent signal phases of traffic lights. In case of longer timed queries (such as S3.5), intervals are needed to process aggregations in combination with long-term temporal relations. Further in S3.1, both pull- or bushed-based queries are desired, and the “standard” features like spatial relations, aggregations, and predictions (including trajectories) are all necessary. 3
The base communicate technologies (i.e., the IEEE 802.11p standard) allow wireless
access in vehicular environments, which enables messaging between vehicles themselves
and the infrastructure, also called V2X communications. The messages are broadcast
every 100ms by traffic participants (e.g. vehicles, roadside ITS stations) to update other
participants about their current state [
Local Dynamic Map. The V2X technology does not yet consider the integration of the
different types of messages. As a comprehensive integration effort, the EU SAFESPOT
project [
Recent research ([
/LocalDynamicMapITS-v0.4-Lite.owl ontology-agnostic; hence other mobility ontologies could be used as well. We follow a layered approach starting with a simple separation between the following classes: - V 2XF eature: is the spatial representation of V2X objects, such as details of an intersections including lanes and traffic lights; - GeoF eature: represents the GIS aspects of the LDM including POIs, areas like parks, and road networks with Geometry as the geometrical representation of features; - Actor: is the class that includes persons, vehicles, as well as roadside ITS stations. Its objects have autonomous behavior and are the main generator of streamed data; - Event: describes prototypical events that happen in a mobility scene, an important subclass of Event is M aneuver that captures possible maneuver such as left-turns, U-turns, or stops by vehicles; - StatisticalV alues: describes possible measurements such as the average speed or throughput that could be collected on an intersection for a lengthy period of time; - CategoricalV alues: specify the different categories such as signal phases, or vehicle roles used in the domain. Vehicle roles are crucial for emergency detection, since it informs the type of an emergency vehicle (e.g., police).
Further, we also introduced the following properties: - properties for partonomies, e.g., isP artOf ; - spatial relations, e.g., intersects; - connectivity, e.g., connected; and - standard properties, e.g., isAllowed, hasRole, isM anaged, or positions.
The sub-classes of GeoF eature are linked to GeoOWL and GeoNames for embedding it into existing ontologies.5 V 2XF eature is the domain specific modeling of the MAP (Map Data Message) topology and describes the details of an intersection including its lanes, allowed maneuvers, and traffic lights. 4
The QA component is central to the usage of a semantically enriched LDM, since it allows us to access the streamed data in the LDM. We focus on pull-based queries that evaluate a query at a single point in time called the query time Ti.
Example 1. The following query detects red-light violations on intersections by searching for vehicles y at speed above 30km/h on lanes x whose signals will turn red in 4s: q1(x; y) : LaneIn(x) ^ hasLocation(x; u) ^ intersects(u; v) ^ pos(line; 4s)(y; v) ^ V ehicle(y) ^ speed(avg; 4s)(y; r) ^ (r > 30) ^ isM anaged(x; z) ^ SignalGroup(z) ^ hasState(first; 4s)(z; Stop) Query q1 exhibits the different dimensions which need to be combined: – V ehicle(y) and isM anaged(x; z) are ontology atoms, which have to be unfolded in respect to the ITS domain modelled in the LDM ontology; – intersects(u; v) and hasLocation(x; u) are spatial atoms, where the first checks spatial intersection and the second the assignment of a geometry to an object; – speed[avg; 4s](y; v) resp. pos[line; 4s](y; r) defines a window operator that aggregates the average speed resp. positions (as points) of the vehicles over the streams
ontology/ speed and pos; hasState[f irst; 4s](z; Stop) gives us the traffic lights, which switch in 4s to the state “Stop”.
For query evaluation, we have adapted OQA to handle spatial and streaming data,
which standard approaches as [
Example 2. For the timeline T = [0; 100], we have the stream FCAM = (T; v; 1) of vehicle positions and speed at the assigned time points for the individuals c1, c2 and b1: v(0) = fspeed(c1; 30); pos(c1; (5; 5)); speed(c2; 10); pos(c2; (4; 4)); speed(b1; 10); pos(b1; (1; 1))g, v(1) = fspeed(c1; 29); pos(c1; (6; 5)); speed(c2; 0); pos(c2; (5; 4)); speed(b1; 5); pos(b1; (2; 1))g, and v(2) = fspeed(c1; 34); pos(c1; (7; 5)); speed(c2; 0); pos(c2; (5; 4))g.
A “slower” stream FSP aT = (T; v; 5) captures the next signal state of a traffic light: v(0) = fhasState(t1; Red)g and v(5) = fhasState(t1; Green)g. Further, the static ABox contains assertions Car(c1), Car(c2), Bike(b1), and SignalGroup(t1).
Our query language is based on CQs and adds spatial-stream capabilities (see Example 1). A spatial-stream CQ q(x) is a formula:
Vli=1 QOi (x; y) ^ Vn k=1 QFk (x; y)
j=1 QSj (x; y) ^ Vm
(1)
where x are the distinguished (answer) variables, y consists of non-distinguished
(existentially quantified) variables, objects, and constant values:
- each QOi (x; y) has the form A(z) or P (z; z0), where A is a class name, P is a property
name of the LDM ontology, and z; z0 are from x [ y;
- each atom QSj (x; y) is from the vocabulary of spatial relations and of the form
S(z; z0), where z; z0 is as before and S is one of the following spatial relation rel 2
fintersects ; contains; nextTo; equals; inside; disjoint ; outsideg;
- QFj (x; y) is similar to QOi (x; y) but adds the vocabulary for stream operators, which
are taken from [
The window [agr; b; e] is derived from the work of [
Example 3. The following query counts the vehicles y that speed above 40km/h in the
last 12 hours on intersection x and compares the count of vehicles z to the previous day:
q2(x; y; z) : Intersection(x) ^ hasLocation(x; u) ^ intersects(u; v) ^
pos(line; 60s)(y; v) ^ V ehicle(count;12h)(y) ^ speed(max; 60s)(y; r) ^
(r > 40) ^ pos(line; 60s)(z; v) ^ V ehicle(count;36h;24h)(z) ^
speed(line; 60s)(z; s) ^ (s > 40)
Query Rewriting by Stream Aggregation. We aim at answering pull-based queries at
a single time point Ti with stream atoms that define aggregate functions on different
windows sizes relative to Ti. For this, we consider a semantics based on epistemic
aggregate queries (EAQ) over ontologies [
For normal objects and constant values, we allow three aggregate functions such as count; f irst; last on the data items of a stream. In case of objects, e.g. vehicle c1 other functions such as sum are not meaningful. For last and f irst, we need to search the bag of data items, as the sequence of time points is lost. This is achieved by iteratively checking if we have a match at one of the time points. In the implementation, the first and last match can be simply cached while processing the stream.
Similar to [
The DS and the predictions can be performed on the bag of data items or the result of a previous aggregations. For predictions and DS, we need to keep the temporal information as the order is lost using bags, as the prediction functions need the time dimension. Hence we tag the exact timestamp to each data item, e.g., speed(c1; 50)[10:05] and speed(c1; 45)[10:07] states that c1 had a speed of 50 (resp. 45) at 10:05 (resp. 10:07). Aggregation of Spatial Objects. For spatial objects, geometric aggregate functions are applied to the bag of data items that represent geometries. As with f irst or last, we must rearrange them to create a valid geometry g(s), i.e., a sequence p = (p1; : : : ; pn) of points pi. We allow the following aggregate functions to derive new geometries: - point: we evaluate last to get the last available position p1; - line: we create p = (p1; : : : ; pn), where p1 6= pn and determine a total order on the bag of points, such that we have a starting point using last and iterate backwards finding the next point by Euclidean distance; - line angle: this aggregate function determines angles (in degrees) in a geometry by (1) applying the function line, (2) obtaining a simplified geometry using smoothing, and (3) calculating the angles between the lines of the simplified geometry; - polygon: similar to line, but we create a polygon (p1; : : : ; pn), where p1 = pn by: (1) determining the convex hull of the bag of points, and (2) extracting all pairs of points representing the convex hull; - traject: The simplest approach to calculate trajectories is by using the function line. However, this is often not sufficient, and more complex smoothing and map matching functions are needed. For the prediction of the future paths, we allow different projections such a linear or curvature-based models. As an additional information, we need to include the maximal distance and step size for each time point. In a simple approximation the current speed can be taken, but also more elaborate models using velocity profiles could be applied.
Example 4. This query returns all vehicles y that will pass the crossing C1 in 10s: q3(x; y) : Crossing(x) ^ hasLocation(x; u) ^ intersects(u; v) ^
pos(traject; 10s)(y; v) ^ V ehicle(y) ^ (x = "C1")
Query Evaluation by Hypertree Decomposition. The main challenge is to handle
three types of query atoms that need different evaluation techniques over possibly
separate databases. Ontology atoms are evaluated over the static ABox A using a
“standard” DL-LiteA query rewriting, i.e., PerfectRef [
In [
The main steps of our query evaluation strategy is as follows. First, we construct the acyclic hypergraph Hq from q and label each hyperedge in Hq with lO (ontology edge), lS (spatial edge), and lF (stream edge), where lF gets the window size assigned. Then, we build the join tree Jq of Hq and extract the subtrees J i in Hq, such that each node is covered by the same labels, so we have sub-CQs that share the same aggregation/prediction functions and same window size l. For each subtree J i , we perform the detemporalization of the stream CQ q i by extracting and computing the results, which are stored in a virtual relation R i (a temporary table). Finally, we traverse Jq bottom up, left-to-right, to evaluate q i for each subtree J i (without stream atoms) and keep the results in memory for caching in future queries.
Example 5. The following query returns all lane change of vehicles z by checking if two lanes were crossed in the last 4s. The coloring distinguishes between ontology (orange), spatial (blue), and stream (green) atoms: q4(z) : LaneIn(x) ^ hasLoc(x; u) ^ intersects(u; w) ^ LaneIn(y) ^ hasLoc(y; v) ^ intersects(v; w) ^ pos(line; 4s)(z; w) ^ V ehicle(z) In Figure 2, we show the derived hypergraph that leads to the following decomposition and evaluation order: (1) qF 1(z; w) : V ehicle(z) ^ pos(line; 4s)(z; w) (2) qN1(x; u) : LaneIn(x) ^ hasLoc(x; u); (3) qN2(y; v) : LaneIn(y) ^ hasLoc(y; v) (4) q4(z) : qF 1(z; w) ^ intersects(u; w) ^ qN1(x; u) ^ intersects(v; w) ^ qN2(y; v) 5
We have implemented a prototype for our spatial-stream QA approach in JAVA 1st.r8eaumsinRgDtBheMPSI.PWELeIpNrEesDenBt t9h.e6s.1y7staemsthare- ihnatseLrsoeccts x chitecture in Figure 3 and give the details on the components below. pos PipelineDB. We chose the open-source LaneIn u w stream RDBMS PIPELINEDB 9.6.1, as it V ehicle is built on top of PostgreSQL and PostGIS,8 and allows us to support spatial data. PIPELINEDB distinguishes between y v z streams and continuous views, where streams are write-only, so the query evalu- Fig. 2: Hypergraph of q4 ator has to access the read-only continuous views. The database is modeled such that there are one-to-one mappings from streams to continuous views, and further to the TBox classes and properties; e.g., vehicle positions are fed into the stream stream pos that is accessed via the continuous view view pos, which is mapped to the property pos.
We also provide a simple integration framework that constantly receives V2X messages and adds the raw message data either to normal tables of the static database, to spatial tables of the GIS database, or the streams of the stream database.
Query Parser and Decomposer. After parsing the input spatial-stream CQ, the
hypertree is decomposed using Gottlob et al.’s implementation [
Spatial evaluator: the spatial evaluator is responsible for handling the spatial relations
such as intersects. As mentioned in [
Stream evaluator: this evaluator is responsible for detemporalizing the streams by
grouping and aggregating the data items. For a stream sub-CQ qi, we perform the
following steps:
(1) extract the data items according to the window size derived from l, b, and e;
(2) evaluate the query qi without rewriting and store the “known solutions” in memory
as Ri;1;
(3) evaluate the rewritten query qi0 over qi and store it in memory as Ri;2;
(4) apply the prediction function on Ri;2 and add the newly predicted data items;
(5) apply the grouping and aggregation function on Ri;2, and produce the outcome Ri;3.
In our current evaluator, the prediction function is a preprocessing step for the
aggregation, and is not yet considered as an independent step. If we would consider predictions
independently, the prediction atoms could be considered as streams themselves, which
generate new data points. However this would change the query evaluation process and
would need to be investigated further. The function traject is designed with the same
intention; we take the existing points (as coordinates) and project a single path into the
future. Currently, we ignore the curvature and use a simple straight-line projection to
create new points. However, taking the curvature into account is a desired extension.
Evaluation of Features. We evaluate our platform regarding the list of features and rely
in the evaluation on our previous results of [
Data stream management systems (DSMSs) such as STREAM [
This work is sparked by the need of detecting mobility patterns based on the LDM for V2X communications, where the LDM serves as an integration effort for streaming data (e.g., vehicle movements) in a spatial context (e.g., intersections) over a complex domain (e.g., a mobility ontology). In previous work, we have introduced simple aggregate queries over mobility streams, which often do not suffice to capture more complex movement patterns. Hence, we present an extension of the previous aggregation functions with statistical and predictive functionality, which allows us to query more complex mobility patterns such as road networks statistics, vehicles maneuvers, and temporal connected events such as (potential) accidents. The extension is based on the newly developed scenarios traffic statistics, vehicle maneuvers, and event detection. We have defined a set of domain-specific features such as trajectory computation and spatial matching, which are matched with the use cases and scenarios to define the requirements.
Given by the new features, we extend our previous LDM ontology, the current spatial-stream query language, and adjust our methods to take the features into account. Further, we redesigned our system architecture and give insights in the new components used for prediction and trajectory calculation.
Future work. Currently, we are implementing the platform thoroughly and will provide benchmarks based on a set of queries related to the three scenarios. As discussed in the previous section, our ongoing and future research is directed to extend our language, methods, and the platform to fulfill the defined requirements, which will allow to use the platform in the mentioned scenarios.