Online event recognition from moving vessel trajectories

Abstract

We present a system for online monitoring of maritime activity over streaming positions from numerous vessels sailing at sea. The system employs an online tracking module for detecting important changes in the evolving trajectory of each vessel across time, and thus can incrementally retain concise, yet reliable summaries of its recent movement. In addition, thanks to its complex event recognition module, this system can also offer instant notification to marine authorities regarding emergency situations, such as suspicious moves in protected zones, or package picking at open sea. Not only did our extensive tests validate the performance, efficiency, and robustness of the system against scalable volumes of real-world and synthetically enlarged datasets, but its deployment against online feeds from vessels has also confirmed its capabilities for effective, real-time maritime surveillance.

1 Introduction

Maritime surveillance systems have been attracting considerable attention for economic as well as environmental reasons [18, 39, 40]. For instance, accidents at sea may cause ecological disasters (e.g., oil spill) and shipping companies may be fined to pay billions of dollars. In the past decade, monitoring vessel activity has emerged as a precious tool for preventing such risks, thanks to the Automatic Identification System (AIS)¹. By integrating a VHF transceiver with positioning and navigational devices (e.g., GPS, gyrocompass), AIS can be used to track vessels at sea in real-time through data exchange with other ships nearby, coastal stations, or even satellites. The initial purpose of AIS was to prevent collisions; yet, the amount and precision of the collected data and its real-time availability can be used by a broader spectrum of maritime monitoring applications. International regulations require AIS to be aboard cargo ships of at least 300 gross tonnage, as well as all passenger ships, regardless of size. Considering that AIS data is continuously emitted from over 580,000 vessels worldwide², maritime surveillance systems certainly demand capabilities of highly scalable, continuous, spatiotemporal processing over transient data streams.

To address this requirement, we have been developing a maritime surveillance system that consists of two main components. A trajectory detection component accepts a positional stream of AIS messages and tracks major changes along each vessel’s movement. Given that vessels normally follow planned routes (except for accidents, storms, etc.), this process can instantly identify “critical points” along each trajectory, such as a stop, a turn, or slow motion. Therefore, we may discard redundant locations along a “normal” course, and approximately reconstruct each vessel’s trajectory from such a synopsis consisting of critical points only. But, apart from archiving or displaying it on maps, this derived stream of critical points is mostly useful in recognizing complex maritime phenomena that involve interaction among vessels or spatiotemporal relationships between vessels and geographical areas of interest. This is handled by our complex event recognition component, which can efficiently detect suspicious or potentially dangerous situations, such as fast approaching vessels or package picking at open sea, and accordingly issue alert notifications to marine authorities. In this system, we have set the following major objectives:

• Timeliness. Event detection must be carried out in real-time. Critical points concerning trajectories of vessels and alerts regarding suspicious maritime situations must be issued within seconds in order to enable immediate action if necessary.

• Compression. We wish to extract trajectory synopses per vessel from the incoming AIS positions retaining salient movement features only. This online data reduction can yield huge space savings (empirically, up to 98 % compared with the raw data), but it is also advantageous for effective complex event recognition.

• Quality. Such compressed representations should be reliable enough in reconstructing trajectories with very small deviations (i.e., tolerable approximation error) from original traces, also coping with inherent imperfections in AIS streams.

• Scalability. The system must be able to manage frequently updated, streaming AIS positions from large fleets of vessels moving over a large area. Not only do we verify that a centralized system can handle scalable volumes of incoming data at varying arrival rates, but we also demonstrate that both components are parallelizable, thus offering even higher gains in efficiency.

Several platforms and monitoring applications have been proposed for managing and analyzing data streams. For instance, the system in [11] focuses on recency-probing pattern queries against both live and archived streams. The UpStream platform [29] offers low latency response to continuous queries over massively updated data, but it lacks support for the specific demands of trajectory detection. Besides, automating ingestion of streaming data feeds from various sources into a data warehouse is also important [17], but does not pay attention to complex event recognition. Our particular interest is on geostreaming data [21] from sailing vessels acquired continuously over time, which must be processed on-the-fly in order to recognize important phenomena regarding their movement and their interaction with the maritime environment. In [37] an approach for anomaly detection and classification of vessel interactions is presented. Patterns of interest are expressed as left-to-right Hidden Markov Models and classified using Support Vector Machines, also taking into account contextual information via first-order logic rules. However, this work focuses more on predictive accuracy rather than real-time performance in a streaming scenario. To the best of our knowledge, no streaming framework has been specifically tailored for maritime surveillance over fluctuating, noisy, intermittent, geostreaming AIS messages from large fleets, as the one we present in this work.

This paper is an extended and revised version of previous works presented in [2, 33], and developed in the context of the AMINESS project³. It now offers heuristics for coping with noisy situations, improved algorithms for better capturing important events related to vessel mobility and interaction, as well as a more thorough empirical validation. In particular, our contributions are:

• We introduce single-pass heuristics to drastically reduce noisy AIS positions, much to the benefit of the resulting trajectory synopses (in size and quality).

• We provide a detailed account of online spatiotemporal filters that can detect important changes in each vessel’s mobility and also incrementally maintain succinct, reliable representations of their evolving trajectories.

• We analyze in depth several rules and conditions for efficiently recognizing complex maritime events, which may also involve topological relationships between vessels and geographical zones of interest.

• We empirically validate our methodology in terms of performance and quality of results against a large AIS dataset of real vessel traces. Moreover, we extensively investigate the robustness, efficiency, and timeliness of the system against scalable volumes of synthetically enlarged datasets, as well as its capacity to recognize complex events related to sensitive environmental zones.

• Finally, we outline a deployment of the system in a real-world scenario, against streaming AIS data feeds that are being collected across the Aegean Sea.

The remainder of the paper is organized as follows. In Section 2, we present the architecture of the proposed maritime surveillance system. Sections 3 and 4 respectively present the two main components for online trajectory detection and complex event recognition, respectively. Experimental results are reported in Section 5. In Section 6, we discuss a deployment of this system against real-time AIS data. Finally, in Section 7 we summarize our approach and outline directions for future work.

2 System architecture

Next, we outline the processing flow of the proposed maritime surveillance system. As illustrated in Fig. 1, this system consumes a geospatial stream of AIS tracking messages from vessels, it continuously detects important features that characterize their movement and recognizes complex events such as suspicious vessel activity. Table 1 presents the types of events that can be monitored by the proposed system. This list covers important events that characterize vessel movement according to domain experts (our partners in the AMINESS project).

Fig. 1

Processing flow of streaming AIS data for online maritime surveillance

Table 1 Taxonomy of monitored events over moving vessels at sea

In order to meet the real-time requirements of the geostreaming paradigm [21], this online process necessitates the use of a sliding window [23, 34]. Typically, such a window abstracts the time period of interest by focusing only on phenomena that occurred in a recent range ω (e.g., positions received during past 10 minutes). This window slides forward to keep in pace with newly arrived stream tuples, so it gets refreshed at a specific slide step every β units (e.g., each minute). For instance, an aggregate query could report at every minute the distancparticular AIS messagese traveled by a ship over the past 10 minutes. Typically, β < ω, hence successive window instantiations may share positional tuples over their partially overlapping ranges across time.

As input, we consider particular AIS messages (specifically, of types 1, 2, 3, 18, or 19 according to AIS regulations) and extract position updates. Each message specifies the M M S I (Maritime Mobile Service Identity) of the reporting vessel. For a given M M S I, each of its successive positional samples p consists of geographical coordinates (L o n, L a t) observed at discrete, totally ordered timestamps τ (e.g., at the granularity of seconds). Without loss of generality, we abstract vessels as 2-dimensional point entities moving across time, because our primary concern is to capture their motion features. By monitoring the timestamped locations from a large fleet of N vessels, the system must deal with a positional stream of tuples 〈M M S I, L o n, L a t, τ〉. A Data Scanner decodes each AIS message, identifies those four attributes (the rest are ignored in our analysis), and cleans them from distortions caused during transmission (e.g., discard corrupt messages with bad checksum). This constitutes an append-only data stream, as no deletions or updates are allowed to already received locations.

But it is the sequential nature of each vessel’s trace that mostly matters for capturing movement patterns en route (e.g., a slow turn), as well as spatiotemporal interactions (e.g., ships traveling together). Such a trajectory is approximated as an evolving sequence of successive point samples that locate this vessel at distinct timestamps (e.g., every few seconds). Our system accounts for stream imperfections, i.e., the noise inherent in vessel positions due to sea drift, delayed arrival of messages, or discrepancies in GPS signals. Indeed, prior to any processing, all incoming AIS positions are filtered through the Noise Reduction module by applying heuristics against a velocity vector maintained per vessel⁴. Afterwards, the Mobility Tracker module accepts clean data and checks when and how velocity changes with time. Working entirely in main memory and without any index support, it can detect two kinds of trajectory movement events (ME) as shown in Table 1:

• Instantaneous trajectory events involve individual time points per route, by simply checking potentially important changes with respect to the previously reported location (e.g., a sharp change in heading).

• Long-lasting trajectory events are deduced after examining a sequence of instantaneous events over a longer (yet bounded) time period in order to identify evolving motion changes. For example, a few consecutive changes in heading may be very small if each is examined in isolation from the rest, but cumulatively they could signify a notable change in the overall direction.

At each window slide, those events are compiled by a Compressor and a sequence of “critical” points (such as a stop) are emitted, which are much fewer compared to the originally relayed positions. Accordingly, the current vessel motion can be characterized in real time with particular annotations (e.g., stop, turn). Once new trajectory events are detected per vessel upon each window slide, the annotated critical points can be readily emitted and visualized on maps through a Trajectory Exporter, e.g., as KML polylines (for trajectories) and placemarks (for vessel locations).

Not surprisingly, detecting trajectory events from positional streams essentially performs a kind of path simplification. In the literature, some strategies like [7, 25, 27] specify an error tolerance for the resulting approximation. The memory footprint occupied by the compressed trajectory may also be a constraint in a single-pass evaluation [35]. Mainly focusing on savings in communication cost, dead-reckoning policies like [41] may be employed on board of the moving objects to relay positional updates only upon significant deviation from the course already known to a centralized server. However, this does not hold for AIS data, as maritime control centers wish to locate ships as frequently as possible. Most importantly, a major advantage of our proposed scheme is that it annotates the simplified representations according to particular trajectory events (turn, stop, etc.), thus adding rich semantic information all along each compressed trace.

Moreover, the derived critical points are propagated to the Complex Event Recognition module, which combines this event stream with static geographical data, such as protected areas. The objective of this process is to detect potentially suspicious or dangerous situations, such as illegal shipping and vessel rendezvous, as detailed in Table 1. This list contains a subset of events that could be of interest; for a more complete list, see [10, 24]. We have chosen to implement only those that were deemed most important, after communicating with the domain experts of the AMINESS project. As with the trajectory movement events, complex events are also categorized either as instantaneous or long-lasting (durative). Moreover, complex events can be also classified according to the following criteria:

• Single-vessel events keep track of a single vessel only (e.g., i l l e g a l s h i p p i n g).

• Dual-vessel events must take into account all possible combinations of two vessels when we need to detect some form of interaction between them.

• Area-based events, like s u s p i c i o u s a r e a, do not aim to report the specific vessels involved, but only the geographic region in which such an activity takes place.

All recognized complex events are eventually pushed in real-time to the marine authorities for decision-making.

3 Detecting trajectory events

As illustrated in Fig. 1, the system accepts fresh AIS messages from ships and extracts positional tuples 〈M M S I, L o n, L a t, τ〉. With the possible exception of local manoeuvres near ports, marine regulations, or harsh weather conditions, vessels are normally expected to follow almost straight, predictable routes. In terms of vessel mobility, what matters most is to detect when and how the general course has changed, e.g., identify a stop, a turn, or slow motion. Such instantaneous and long-lasting trajectory movement events (ME) can indicate “critical points” along the trace of each vessel and thus offer a concise, yet quite reliable representation of its course.

In order to identify significant motion changes, we employ an instantaneous velocity vector $\overrightarrow {v}_{now}$ over the two most recent positions reported by each vessel M M S I. In addition, we maintain a mean velocity $\overrightarrow {{v}_{m}}$ per ship over its previous m positions (m is a small integer) so as to abstract its short-term course. With our heuristics, it turns out that a large portion of the raw positional reports can be suppressed with minimal loss in accuracy, as they hardly contribute any additional knowledge.

In this Section, we first present simple, yet quite effective filters as a means of eliminating noise inherent in the streaming AIS data. Next, we describe how the sequence of vessel positions can be processed online in order to detect trajectory movement events and thus maintain a lightweight synopsis of each vessel’s course.

3.1 Online noise reduction

Despite its high value in maritime surveillance, AIS data is not error-free. In fact, there are several sources of error that render a portion of this data noisy and inadequate for monitoring. First, no precise timestamp value is present in AIS messages relayed by the transponders on board; instead, they only report a lag value (in seconds) from the previously transmitted message. Obviously, this value cannot be used for establishing a temporal order, since positional updates from a single vessel may come from a series of base stations (those within range of its antenna along the route).

Therefore, a transaction timestamp marking the arrival of each AIS message at a station has to be used instead. Inevitably, transmission delays may frequently occur between the original message and its arrival. Successive positional messages from a single vessel may often arrive intermingled at a distorted order. Figure 2a illustrates such out-of-sequence messages, where numbers signify timestamp values since the beginning of this trajectory. Had those positions been retained according to their order of arrival, the vessel would occasionally appear in a state of sudden agility, moving back and forth very rapidly at a quite unusual speed. To make matters worse, AIS networks do not have synchronized clocks. Hence, if a vessel is within range of two stations, then a broadcasted message may be received by each one and possibly assigned with a different transaction timestamp. It may also happen that the same timestamp is assigned to different locations (maybe of considerable distance) of the same vessel. Therefore, duplicate or contradicting positions of a vessel may be present in the collected data. Noise might not always be caused by technical issues or the inherent errors and discrepancies in the GPS positions. It may be also due to deliberate, suspicious actions, e.g., switching off the transponder or emitting “spoofed” coordinates in order to avoid surveillance in a sensitive area. To the extent possible, such intermittent or falsified positions should be detected and cleared.

Fig. 2

Noise-related situations along a vessel’s course

Coping with noisy situations over AIS data is particularly challenging and has attracted significant research interest. As argued in [31], noise reduction should not be confused with anomaly detection, because data must be cleaned in advance, before performing any analysis. In that particular work, the well-known DBSCAN clustering algorithm [15] was used to identify outlier positions, which could then be removed from the dataset. With respect to time delays, an adaptive filtering strategy was suggested in [28], which employed Kalman filters and Monte-Carlo simulations to sequentially detect such delays and probabilistically rearrange a “correct” timestamp order. Besides, a stochastic method can be used to cope with position spoofing [19] by exploiting auxiliary data from radars or comparing it with previously tracked information. A common characteristic of all such methods is that they work in offline fashion employing expensive, iterative filters over archived AIS datasets.

In contrast, in this work we wish to apply online, single-pass filters over the incoming stream of AIS positions. Besides, given that trajectory compression is one of our principal objectives, we can afford to lose garbled, out-of-sequence positions and not consider correcting their timestamps. After all, except for cases of malicious activity, a fresh noise-free location will be soon received from a vessel, effectively compensating for the removal of any erroneous preceding one(s). In order to effectively and efficiently eliminate noise in timestamped AIS positions, we resort to applying a series of simple heuristics that examine the instantaneous velocity vector $\overrightarrow {v}_{now}$ of each vessel as computed by its two most recent observations. A noisy situation is identified if at least one of the following conditions apply:

• Off-course positions incur an abrupt change both in speed and heading of velocity $\overrightarrow {v}_{now}$. Such an outlier can be easily detected since it signifies an abnormal, yet only temporary, deviation from the known course as abstracted by mean velocity $\overrightarrow {{v}_{m}}$ of the ship over its previous m positions. Figure 2b illustrates such a case with a vessel that is unexpectedly located far away from its anticipated route.

• When vessels are on the move, they normally take their turns very smoothly (especially larger ships), so a series of AIS locations are transmitted, each marking a small change in heading as in Fig. 3f. However, if the latest position update indicates that a vessel has suddenly made a very abrupt turn (e.g., over 60^o) with respect to its known course (even though its speed may not be altered significantly), then this message should better be ignored altogether. Note that in case of adverse weather conditions (e.g., a storm) a vessel’s route may appear as a ‘zig-zag’ polyline with a series of such abrupt turns as shown in Fig. 2c. Dropping those consecutive points as noise is not typically correct; yet, in terms of data reduction this is quite desirable, as the vessel does not make any intentional turn and generally follows its planned course.

• When a vessel appears to accelerate too much, i.e., at a rate that it is not usual for a ship, this is another indication of noise. This is typical for out-of-sequence messages with twisted timestamps, as the three red spots in Fig. 2a. Each of these three locations is along the course of the ship, but due to their late arrival to the base station, the vessel is seen as suddenly retracting backwards. The location at timestamp t=438 seconds is 270 meters back from the position at t=433 seconds, resulting in a speed of 105 knots, quite unrealistic for any vessel.

• If an identical location from the same vessel has been already recorded before, then this might be a sign of error. Note that even if a vessel remains anchored, its successive GPS measurements usually differ by a few meters. In that case, instantaneous velocity $\overrightarrow {v}_{now}$ is infinitesimal, but not exactly zero. Instead, coincidental coordinates in succession should be deemed as almost certain duplicates, possibly concerning position reports that arrived at slightly different times at more than one AIS stations within range of the vessel’s antenna.

• A similar problem occurs with conflicts in timestamping, when the same timestamp is assigned to two distinct messages from a given vessel, even though they may be probably reporting different coordinates. In this case, instantaneous velocity $\overrightarrow {v}_{now}$ cannot be computed, signifying that these messages are contradictory (if not violating previous rules, we arbitrarily retain the latest one).

Fig. 3

Instantaneous and long-lasting trajectory events

As we experimentally verified (cf. Section 5), as much as 20 % of the raw AIS positions may be qualifying as noise, falling in one of the aforementioned cases. Most importantly, accepting noisy positions would drastically distort the resulting trajectory synopsis, as the red dashed line in Fig. 2b illustrates. Even worse, noise may affect proper detection of movement events, as we will discuss next. Hence, although based in empirical heuristics, such noise reduction has proven certainly beneficial in terms of performance without sacrificing accuracy in the resulting approximation.

3.2 Online tracking of moving vessels

Once potentially noisy positions are cleared, the mobility tracker can promptly deduce instantaneous events by examining the trace of each vessel alone. In particular:

• i) Pause indicates that a vessel is temporarily halted, once its instantaneous speed v _{n o w} is below a suitable threshold v _{m i n} . For example, if v _{n o w} is currently less than v _{m i n} = 1 knot, then the ship seems idle. For the vessel shown in Fig. 3a, the red bullets indicate several pause events; apparently, the ship is anchored at the port and such small displacements may be due to GPS errors or sea drift.

• ii) Speed change occurs once current v _{n o w} deviates by more than α % from the previously observed speed v _{p r e v} . Given a threshold α, the formula $|\frac {v_{now}-v_{prev}}{v_{now}}| > \frac {\alpha }{100}$ indicates whether the vessel has just decelerated or accelerated. This normally happens when approaching to or departing from a port, as depicted in Fig. 3b.

• iii) Turn is spotted when heading in $\overrightarrow {v}_{now}$ has just changed by more than a given angle Δ𝜃; e.g., if there is a difference of ≥15^o from the previous direction.

No critical point gets immediately issued upon detection of any such simple events. An instantaneous pause or turn may be haphazard only; these are not meaningful out of context, because a series of such events may signify that the ship is stopped for some time. To avoid iteratively probing these locations later, we simply attach a bitmap to each stream tuple, using one bit for each particular instantaneous event. Note that multiple bits may be set at each location; e.g., the vessel may have just taken a sudden turn and also changed its speed above the respective thresholds, hence two distinct bits must be set to 1.

By buffering these instantaneous events within the window, we then can detect spatiotemporal phenomena of some duration. Examination of such long-lasting trajectory events is carried out in the following order. Note that if a certain long-lasting event has just been detected at a location, then checking if it also qualifies for another event is skipped altogether.

• 1. Gap in reporting is examined first. This event is spotted when a vessel has not emitted a message for a time period ΔT, e.g., over the past 10 minutes. This may occur when the vessel sails in an area with no AIS receiving station nearby, or because the transmission power of its transponder allows broadcasting in a shorter range. Then, its course is unknown during this period, as it occurs between the two red bullets in Fig. 3c. Reporting that contact was lost is important not only for online monitoring, but also for safety reasons, e.g., a suspicious move near maritime boundaries, or a potential intrusion of a tanker into a marine park. A pair of critical points signify when contact was lost (gapStart annotates the previously reported location) and when it was restored (gapEnd for current location).

• 2. Checking for a long-term stop is only fired if the vessel is noticed to move (v _{n o w} >v _{m i n} ) just after a pause. If current location is preceded by at least m consecutive instantaneous pause or turn events in the buffer, and they are all within a predefined radius r (e.g., 250 meters), then a long-term stop is identified. In Fig. 3d, the red points inside the circle succeed one another and indicate such immobility, so they are collectively approximated by a single critical point (their centroid) annotated as stopped with their total duration.

• 3. Slow motion means that a vessel consistently moves at very low speed (≤v _{m i n} ) over its m most recent messages, as in Fig. 3e. If those buffered positions have not already qualified as a long-term stop by the previous rule (because they did not fall inside a small circle), then they probably succeed each other slowly along a path. The first and the last of these positions are both reported as critical, respectively annotated as lowSpeedStart and lowSpeedEnd.

• 4. Smooth turns are examined last. Due to their large size and maritime regulations, vessels normally report a series of locations when they change course. By checking whether the cumulative change in heading over buffered previous positions exceeds a given angle Δ𝜃, a series of such critical turning points may be emitted, as illustrated with the red points in Fig. 3f.

Thus, critical points are emitted from each detected long-lasting trajectory event, and this relies heavily on efficient noise reduction (cf. Section 3.1). For instance, an outlier breaking the subsequence of instantaneous pause events could prevent characterization of a long-term stop, and instead yield two successive such stops very close to each other. Moreover, in case that no long-lasting trajectory event was identified at this location, we check its associated bitmap with these additional rules:

• 5. If the bit for ‘turn’ is set, we check whether the current heading in $\overrightarrow {v}_{now}$ also deviates more than Δ𝜃 from mean velocity $\overrightarrow {v}_{m}$ of the vessel. If true, we emit a critical turning point. Note that this could possibly affect only raw AIS locations that are not qualified as erroneous. In fact, noisy positions as those in Fig. 2c have already been discarded by the Noise Reduction module.

• 6. If the bit for ‘speed change’ is set (Fig. 3b) and current speed v _{n o w} also deviates by more than α % from the mean speed v _m of this vessel, then a critical point must be emitted and annotated as speedChange. It signifies that this instantaneous event was not caused by fluctuations in the measured speed due to delayed messages, but that such change in speed is probably valid.

Clearly, this detection process can only lead to a single annotation for each critical point. For instance, if a vessel disappeared for long and is suddenly found anchored somewhere, this event will be spotted either as a gap or a stop, but not both. We have deliberately chosen such a ‘crisp’ classification allowing a single characterization per detected point, as our goal is to achieve a concise trajectory representation, by dropping superfluous locations. In future work, we plan to introduce a fuzzy, probabilistic scheme of multiple annotations per critical point at diverse confidence margins.

Each critical point is issued along with a velocity vector (comprising instantaneous speed and heading), as an indicator of the short-term course of that particular vessel. This measurement may be useful for further analysis, e.g., in order to identify complex maritime events as explained in Section 4.

The example trajectory in Fig. 4 illustrates the data compression gains achieved when retaining critical points only. Obviously, such filtering greatly depends on proper choice of parameter values, which is a trade-off between reduction efficiency and approximation accuracy. For a suitable calibration of these parameters, apart from consulting maritime domain experts (our partners in the AMINESS project), we have also conducted several exploratory tests on randomly chosen vessels from AIS data in the Aegean Sea. For instance, setting Δ𝜃=5^o instead of Δ𝜃=15^o may even double the amount of critical points, because more raw AIS locations would qualify as turning points due to sea drift and discrepancies in GPS signals. Since our analysis is mostly geared towards data reduction, for our empirical study (Section 5.1) we have chosen an aggressive parametrization (values listed in bold in Table 4), which yields quite tolerable accuracy. With more relaxed parameter values, additional movement events can be detected, capturing slighter changes along each trajectory.

Fig. 4

Critical points identified along a vessel trajectory (raw AIS positions are shown as blue dots)

The complexity for detecting instantaneous events and communication gaps is O(1) per incoming positional tuple, since only the two latest locations are examined per vessel. The cost for the remaining long-lasting events is O(b), where b is the number of buffered positions that need inspection by each such rule. This may involve just a few points in case of smooth turns, but b may be higher (sometimes, a few hundred) if a series of positions qualify for a stop or slow motion. However, we stress that checks for stop of slow motion are fired rather infrequently, only once a vessel starts moving after a certain period of idleness. Thus, the overall cost is more than affordable and detection is near real-time, as we empirically verify in Section 5.1.

By taking advantage of those online annotations at critical points along trajectories, lightweight, succinct synopses can be retained per vessel over the recent past. Then, the compressor module simply evicts point locations that have not been detected as critical. Instead of resorting to a costly simplification algorithm, we opt to reconstruct vessel traces approximately from already available critical points. Such summarization depends on the annotation of detected trajectory events (stop, turn, gap, etc.), so as to refresh each trajectory accordingly. This main-memory process affects trajectory portions currently within the sliding window. Of course, resulting synopses may be also archived via the Trajectory Exporter module for offline use as files (e.g., KML, CSV) or in a database by incrementally emitting “delta” batches of critical points as they get identified at each slide of the window.

The aforementioned rules for detecting trajectory events are suitably defined in the mobility tracker, which allows fast, in-memory maintenance of movement features. Note that additional events can be detected by simply enhancing the mobility tracker with extra conditions. In future work, we plan to complement this methodology so as to capture more features, such as traveled distance from a given origin (e.g., a port). Nonetheless, even with this set of filters, we can figure out the mutability in each trajectory and distinctly characterize its course across time. Most importantly, these spatiotemporal features can serve as a basis to recognize more complex maritime events, as we discuss next.

4 Complex event recognition

The trajectory detection module compresses a vessel position stream to a stream of critical events, including the instantaneous events g a p S t a r t and g a p E n d, indicating communication gaps, l o w S p e e d S t a r t, l o w S p e e d E n d, s p e e d C h a n g e and t u r n, and the durative event s t o p p e d. Each such event is accompanied by the coordinates and velocity (speed and heading) of the corresponding vessel. This data stream, hereafter Movement Event (ME) stream, is transmitted to the complex event (CE) recognition module, which combines it with the locations of ports and protected areas, in order to recognize potentially suspicious or dangerous maritime situations, for the benefit of marine authorities.

The CE recognition module is based on the ‘Event Calculus for Run-Time reasoning’ (RTEC) [4]. The Event Calculus [22] is a logic programming action language. RTEC has a formal, declarative semantics—CE patterns in RTEC are (locally) stratified logic programs [36]. In contrast, almost all complex event processing languages, including [1, 6, 26], and several data stream processing languages, such as ESL [5] that extends CQL [3], lack a rigorous, formal semantics [9]. Reliance on informal semantics constitutes a serious limitation for maritime monitoring, where validation and traceability of the effects of events are crucial. Moreover, the semantics of event query languages and production rule languages often have an algebraic and less declarative flavor [14, 32]. In the following sections we present RTEC and illustrate its use for maritime monitoring.

4.1 Event calculus for run-time reasoning

RTEC has a linear temporal model including integer time-points. Following Prolog’s convention, variables start with an upper-case letter, while predicates and constants start with a lower-case letter. For a fluent F—a property that is allowed to have different values at different points in time—the term F = V denotes that fluent F has value V. holdsFor (F = V, I) denotes that I is the list of the maximal intervals for which F = V holds continuously. holdsAt (F = V, T) represents that fluent F has value V at some time-point T. holdsAt and holdsFor are defined in such a way that, for any fluent F, holdsAt (F = V, T) if and only if T belongs to one of the maximal intervals of I for which holdsFor (F = V, I).

An event description in RTEC includes rules that define the event instances with the use of the happensAt predicate, the effects of events with the use of the initiatedAt and terminatedAt predicates, and the fluent values with the use of the holdsAt and holdsFor predicates, as well as other, possibly atemporal, constraints. Table 2 presents a fragment of the predicates available to the event description developer.

Table 2 RTEC Predicates

Fluents in RTEC are of two kinds: simple and statically determined. For a simple fluent F, F = V holds at a particular time-point T if F = V has been initiated by an event that has occurred at some time-point earlier than T, and has not been terminated at some other time-point in the meantime. This is an implementation of the law of inertia. To compute the intervals I for which F = V, i.e. holdsFor(F = V, I), we find all time-points T _s at which F = V is initiated, and then, for each T _s , we compute the first time-point T _f after T _s at which F = V is terminated. As an example, consider the formulation below:

$$ \begin{array}{l} \textsf{initiatedAt}\mathit{(gap(Vessel)=\textsf{true},\ T) \leftarrow} \\ \qquad \textsf{happensAt}\mathit{(gapStart(Vessel),\ T),} \\ \qquad \textsf{holdsAt}\mathit{(coord(Vessel)=(Lon,Lat),\ T),} \\ \qquad \textsf{not} \mathit{nearPorts(Lon,Lat)}\\ \textsf{terminatedAt}\mathit{(gap(Vessel)=\textsf{true},\ T) \leftarrow} \\ \qquad \textsf{happensAt}\mathit{(gapEnd(Vessel),\ T)} \end{array} $$

(1)

g a p ( V e s s e l ) is a Boolean simple fluent denoting a communication gap for some V e s s e l, i.e. the V e s s e l stops transmitting AIS messages. In some cases, the absence of AIS messages is suspicious and thus we need to record it. g a p S t a r t ( V e s s e l ) and g a p E n d ( V e s s e l ) are instantaneous MEs indicating, respectively, the time-points in which a V e s s e l stops and resumes sending AIS messages. c o o r d is a fluent reporting the coordinates of a vessel. Like MEs, this type of information is provided by the trajectory detection module. n e a r P o r t s ( L o n , L a t ) is an atemporal predicate that becomes true when the point ( L o n , L a t ) is close to a port. ‘not’ is negation-by-failure [8]. Rule-set (1) states that g a p ( V e s s e l ) =true is initiated if the trajectory detection module reports a g a p S t a r t ME for the V e s s e l, and the V e s s e l is far from the ports of the area under surveillance. Furthermore, g a p ( V e s s e l ) =true is terminated when the V e s s e l resumes communications. Given rule-set (1), RTEC computes the list of maximal intervals during which g a p ( V e s s e l ) =true holds continuously.

4.2 Spatial indexing

CE recognition for maritime surveillance requires various types of spatial operation [16, 24]. For instance, we need to determine whether a point—a vessel’s location—lies inside a polygon indicating an area of interest, such as a protected area, or whether it is near another point, such as a port. Moreover, we need to detect the vessels that are in close proximity (heading towards each other). In our approach to CE recognition, the availability of the full power of logic programming is one of the main attractions of employing RTEC as the temporal formalism. It allows CE patterns to include not only temporal constraints but also (complex) atemporal constraints. Recall e.g. the use of the atemporal predicate n e a r P o r t s in the specification of communication g a p in rule-set (1). This is in contrast to various state-of-the-art CE recognition approaches, such as [9, 12, 23, 42], which support very limited atemporal reasoning, thus being unsuitable for maritime monitoring.

For efficient spatial reasoning, we adopt a grid partitioning scheme which divides the surveillance area into equally sized cells (see Fig. 5). Each area of interest and port is assigned only to those cells with which it overlaps. This assignment is performed off-line and provided as background knowledge to RTEC. The use of a grid enables us to quickly determine, through a simple calculation on the coordinates, the cell inside which a vessel is located. The task of determining each vessel’s cell is performed before each CE recognition query. This way, we can efficiently compute the number of vessels in close proximity and check whether a vessel is inside an area of interest, by performing calculations (e.g. using the ray crossings algorithm [30] for determining whether a point lies inside a polygon) only for those vessels/areas in the same or adjacent cells.

Fig. 5

Grid partitioning: different polygon types indicate different types of (overlapping) area of interest

4.3 Specifying complex maritime events

Given the critical ME stream produced by the trajectory detection module, and a set of protected areas, RTEC recognizes a set of CEs for the benefit of maritime authorities. The choice of CEs and their patterns were specified in collaboration with the domain experts of the AMINESS project. Below we present a fragment of our CE patterns. The complete list may be found in [2].

Suspicious vessel delay

Some vessels, such as those passing through protected areas in order to minimize trip length and fuel consumption, switch off their transmitters and stop sending position signals. But sailing through a protected area is not the only reason for switching off an AIS transmitter. To investigate the behavior of vessels during a communication gap, we formulated the CE below:

$$ \begin{array}{l} \textsf{holdsFor}\mathit{(suspiciousDelay(Vessel)=\textsf{true},\ I)} \leftarrow \\ \qquad \textsf{holdsFor}\mathit{(gap(Vessel)=\textsf{true},\ I_{gap}),}\\ \qquad \mathit{extendedDelays(Vessel,\ I_{gap},\ I)} \end{array} $$

(2)

Recall that I in holdsFor(F = V, I) is the list of the maximal intervals for which F = V holds continuously (see Table 2). I _{g a p} in holdsFor ( g a p ( V e s s e l ) =true, I _{g a p} ), therefore, is the list of maximal intervals during which a V e s s e l stops transmitting AIS signals while at open sea (see rule-set (1) for the g a p fluent). e x t e n d e d D e l a y s ( V e s s e l , I ^′ , I ) selects the maximal intervals I of the list I ^′ for which the highest possible speed of the V e s s e l is below a threshold. We estimate the highest possible speed of a vessel in a simplified way: we assume that the vessel moved along a straight line from the point of g a p S t a r t to that of g a p E n d. Under this assumption, its speed cannot have been greater than the one determined by dividing this shortest path by the time spent to travel it. Rule (2) thus states that a very low vessel speed combined with a communication gap occurring at open sea is to be treated as a suspicious delay.

The s u s p i c i o u s D e l a y fluent is defined by a domain-specific holdsFor rule. We call fluents defined by such rules statically determined. For some fluents, it is much more concise to use domain-specific holdsFor rules defining the value of a fluent in terms of the values of other fluents, as opposed to the traditional style of Event Calculus representation, i.e. identifying the various conditions under which the fluent is initiated and terminated so that maximal intervals can then be computed using the domain-independent holdsFor.

Vessel rendezvous

‘Suspicious delay’ allows us to define additional types of suspicious activity; consider the rule below:

$$ \begin{array}{l} \textsf{holdsFor}\mathit{(possibleRendezvous(Vessel_{1},Vessel_{2})=\textsf{true},\ I)} \leftarrow \\ \qquad \textsf{holdsFor}\mathit{(in(Vessel_{1}, Cell)=\textsf{true},\ I_{1}),}\\ \qquad \textsf{holdsFor}\mathit{(in(Vessel_{2}, Cell)=\textsf{true},\ I_{2}),}\\ \qquad \textsf{holdsFor}\mathit{(suspiciousDelay(Vessel_{1})=\textsf{true},\ I_{3}),}\\ \qquad \textsf{holdsFor}\mathit{(suspiciousDelay(Vessel_{2})=\textsf{true},\ I_{4}),}\\ \qquad \textsf{intersectall}\mathit{([I_{1},I_{2},I_{3},I_{4}],\ I)} \end{array} $$

(3)

i n ( V e s s e l , C e l l ) is a statically determined fluent indicating the C e l l of the grid in which the V e s s e l is located. The value of this fluent is calculated according to the reported vessel coordinates and is set prior to each CE recognition query, as described in Section 4.2. intersectall is a built-in RTEC predicate which calculates the intersection of a list of lists of maximal intervals (see Table 2). According to rule (3), if two vessels simultaneously exhibit a s u s p i c i o u s D e l a y and are located in the same area, then this could indicate that they had arranged for a rendezvous. Note that, since we do not have information about the vessels’ locations during communication gaps, the above rule cannot capture the precise place and time of the rendezvous, if any.

Figure 6 illustrates the definition of p o s s i b l e R e n d e z v o u s. During the rendezvous, there would be no i n ( V e s s e l , C e l l ) fluents available. These fluents would become available only when a vessel re-appears, i.e. at the end of a communication g a p. To detect instances of p o s s i b l e R e n d e z v o u s, we make the assumption that a V e s s e l remains in the same C e l l for an interval extending 60 seconds before and after the timestamp of the reported vessel coordinates (see Fig. 6). Therefore, the intersection of the two i n and the two s u s p i c i o u s D e l a y intervals is not necessarily empty. We reserve for future work a more refined specification of this CE.

Fig. 6

Example of vessel rendezvous. V e s s e l ₁ re-appears at time T ₁ while V e s s e l ₂ re-appears at time T ₂. The interval of p o s s i b l e R e n d e z v o u s is the intersection of the intervals displayed above it

Maritime activities form hierarchies, in the sense that the formulation of one activity is also used to define other, higher-level activities. For example, vessel rendezvous is specified in terms of suspicious vessel delay. In contrast to many state-of-the-art CE recognition systems, such as Esper⁵ and SASE⁶, RTEC can naturally express hierarchical knowledge by means of well-structured specifications.

Fast approach

Another dangerous situation may arise when a vessel is rapidly moving towards some other vessel(s). Such a behavior could indicate a vessel pursuit or even imminent collision. Consider the formalization below:

$$ \begin{array}{l} \textsf{happensAt}\mathit{(fastApproach(Vessel),\ T)} \leftarrow \\ \qquad \textsf{happensAt}(\mathit{speedChange(Vessel),\ T),}\\ \qquad \textsf{holdsAt}\mathit{(velocity(Vessel)= Speed,\ T),} \\ \qquad \mathit{Speed > 20\ knots},\\ \qquad \textsf{holdsAt}\mathit{(coord(Vessel)= (Lon,Lat),\ T),} \\ \qquad \textsf{not} \mathit{nearPorts(Lon,Lat),}\\ \qquad \textsf{holdsAt}\mathit{(headingToVessels(Vessel)=\textsf{true},\ T)} \end{array} $$

(4)

f a s t A p p r o a c h ( V e s s e l ) and s p e e d C h a n g e ( V e s s e l ) are instantaneous CE and ME respectively. v e l o c i t y is a fluent indicating the speed of a vessel. This information, as well as a vessel’s heading, is provided by the trajectory detection module and accompanies every detected ME. h e a d i n g T o V e s s e l s ( V e s s e l ) is a fluent that becomes true whenever a V e s s e l’s direction of movement is towards at least one nearby vessel. According to rule (4), a ‘fast approach’ is recognized when a V e s s e l changes its speed at open sea, the new speed is above 20 knots, and there is at least one other nearby vessel towards which it is heading. The value of 20 knots was chosen by domain experts.

Package picking

Another possible interaction between two vessels is when one of them drops a package at some area and another vessel appears later in order to pick it up. One way of formulating this type of interaction is the following:

$$ \begin{array}{l} \textsf{happensAt}\mathit{(possiblePicking(Vessel_{1},Vessel_{2}),\ T_{pick})} \leftarrow \\ \quad \textsf{happensAt}\mathit{(\textsf{end}(stopped(Vessel_{1})=\textsf{true}), T_{drop}),}\\ \quad \textsf{holdsAt}\mathit{(in(Vessel_{1})= Cell,\ T_{drop}),}\\ \quad \textsf{happensAt}\mathit{(\textsf{start}(stopped(Vessel_{2})=\textsf{true}), T_{pick}),}\\ \quad \textsf{holdsAt}\mathit{(in(Vessel_{2})= Cell,\ T_{pick}),}\\ \quad \mathit{T_{pick} - T_{drop} < 1 \ hour,}\\ \quad \textsf{holdsAt}\mathit{(coord(Vessel_{1})=(Lon_{1},Lat_{1}),\ T_{drop}),}\\ \quad \textsf{holdsAt}\mathit{(coord(Vessel_{2})=(Lon_{2},Lat_{2}),\ T_{pick}),}\\ \quad \mathit{distance((Lon_{1},Lat_{1}),(Lon_{2},Lat_{2}),\ Dist),}\\ \quad \mathit{Dist < 0.5 \ km} \end{array} $$

(5)

s t o p p e d ( V e s s e l ) is a Boolean simple fluent indicating that a V e s s e l has stopped at open sea. The definition of this fluent is based on the information provided by the trajectory detection module, which reports the list of maximal intervals during which a vessel has stopped. From this list, we keep only those intervals where the vessel is not in any port. start(F = V) (respectively end(F = V)) is a built-in RTEC event taking place at the starting (ending) point of each maximal interval for which fluent F has value V continuously. For instance, start( s t o p p e d ( V e s s e l ) =true) takes place at the starting point of each maximal interval for which the V e s s e l has stopped at at open sea. Rule (5) describes a scenario where a vessel had stopped at some area and started moving at time T _{d r o p} , then, after no more than an hour, another vessel arrived and stopped at the same area, and the Haversine distance between the two stop locations, as calculated by the d i s t a n c e predicate, was no more than half a kilometer.

4.4 Recognizing complex maritime events

Listing 1 shows the pseudo-code of the main loop of RTEC. CE recognition is performed by means of continuous query processing, and concerns the computation of the maximal intervals of simple fluents (e.g. g a p as defined by rule-set (1)) and statically determined fluents (such as p o s s i b l e R e n d e z v o u s defined by rule (3)), as well as the time-points in which events occur (e.g. f a s t A p p r o a c h as defined by rule (4)). At each query time Q _i , the MEs that fall within a specified sliding window ω are taken into consideration. All MEs that took place before or at Q _i −ω are discarded/‘forgotten’ (see line 1 of Listing 1). At Q _i , the CE intervals computed by RTEC are those that can be derived from MEs that occurred in the interval (Q _i −ω, Q _i ], as recorded at time Q _i . When the range ω is longer than the slide step β, it is possible that an ME occurs in the interval (Q _i −ω, Q _i−1] but arrives at RTEC only after Q _i−1; its effects are taken into account at query time Q _i .

After ‘forgetting’ MEs, RTEC determines the cell inside which a vessel is located (see line 2 of Listing 1 and Section 4.2). Then, RTEC computes and stores the intervals of each CE of interest. RTEC restricts attention to hierarchical CE patterns, those where it is possible to define a function level that maps all fluents and all events to the non-negative integers as follows. Events and statically determined fluents of level 0 are those whose happensAt and holdsFor definitions do not depend on any other events or fluents. These are the input MEs. There are no simple fluents in level 0. Events and simple fluents of level n are defined in terms of at least one event or fluent of level n − 1 and a possibly empty set of events and fluents from levels lower than n−1. Statically determined fluents of level n are defined in terms of at least one fluent of level n − 1 and a possibly empty set of fluents from levels lower than n − 1.

RTEC adopts a caching technique where the fluents and events of the CE hierarchy are processed in a bottom-up manner; this way, the intervals (resp. time-points) of the fluents (events) that are required for the processing of a fluent (event) of level n will simply be fetched from the cache without the need for re-computation. This technique is illustrated in the outer for-loop of Listing 1 (see lines 3–13) where fluent (event) processing starts at level 1 of the CE hierarchy and proceeds towards the top (k) level. The fluents (events) of the same level may be processed in any order. For illustration purposes, in Listing 1 the following order is adopted: statically determined fluents (lines 4–6), simple fluents (lines 7–9) and events (lines 10–12).

Listing 2 shows the pseudo-code of recogniseSDFluent, the procedure for computing and storing the intervals of statically determined fluents. First, RTEC determines the index of the given fluent S D F. The index is set by the user and allows for the fast retrieval of stored intervals for a given fluent even in the presence of very large numbers of fluents. Then, RTEC retrieves from the sdFList predicate the maximal intervals of S D F computed at the previous query time Q _i−1 and checks if there is such an interval that overlaps Q _i −ω (lines 2–8). O l d I represents the intervals of S D F computed at Q _i−1. These intervals are temporally sorted and start in (Q _i−1−ω, Q _i−1]. O l d P E stores the interval, if any, ending at Q _i−1−ω. RTEC amalgamates O l d P E with the intervals in O l d I, producing O l d L i s t (line 3). If there is an interval [ S t a r t , E n d ) in O l d L i s t that overlaps Q _i −ω, then the sub-interval [ S t a r t , Q _i − ω + 1 ) is retained. See P E in Listing 2. All S D F intervals in O l d L i s t after Q _i −ω are discarded.

Subsequently, RTEC evaluates holdsFor rules to compute the S D F intervals from MEs recorded as occurring in (Q _i −ω, Q _i ] (line 9). The computed list of intervals I of S D F, along with P E, are stored in sdFList (line 10), replacing the intervals computed at Q _i−1. When the user queries the maximal intervals of a fluent, RTEC amalgamates P E with the intervals in I.

Details about simple fluent and event processing, as well as a complexity analysis of RTEC, may be found at [4].

5 Empirical evaluation

Our maritime surveillance system has a modular design with loosely coupled components. The mobility tracker for online trajectory detection⁷ is developed in GNU C++ and runs entirely on main memory for efficiently coping with volatile, asynchronously updated, streaming locations. RTEC⁸, the complex event (CE) recognition component, is implemented in Prolog⁹.

We conducted experiments against a real AIS dataset containing 23GB of AIS messages spanning from 1 June 2009 to 31 August 2009 for N= 6,425 vessels in the Aegean, the Ionian, and part of the Mediterranean Sea. Not all vessels were actually on the move at all times, since a considerable part (chiefly cargo ships) were just passing by, and thus tracked for a limited period (days or even hours). But most vessels were frequently sailing, e.g., passenger ships or ferries to the islands. When decoded and cleaned from corrupt messages, the dataset yielded 168,240,595 raw timestamped positions¹⁰.

We simulated a streaming behavior by consuming this positional data little by little, i.e., reading small chunks periodically according to window specifications. We examine sliding windows with varying ranges ω and slide steps β based on timestamps from the original AIS messages. Thus, we replay this stream and the window keeps in pace with the reported timestamps and not the actual time of each simulation. The arrival rate of positions is fluctuating throughout this 3-month period and varies widely among vessels; none of them reports at a fixed frequency, whereas there are ships inactive for large intervals. If we only consider the activity period of each vessel (i.e., when it actually relays positions, either moving or not), then it reports every two minutes on average, which translates into a mean arrival rate ρ≈50 positions/sec from the entire fleet. For consistency with the real-world scenario, we consume the original stream “as is” in some simulations, even though this is a very low rate for a streaming application. We performed additional experiments at artificially increased rates so as to stress test our system and verify its efficiency and robustness. For the CE recognition component, artificially enlarged datasets include 1,2M vessels and 3,2B MEs. The simulation settings are listed in Table 3, whereas the calibrated settings for online mobility tracking are given in Table 4; default values are shown in bold.

Table 3 Experimental settings

Table 4 Mobility tracking parameters

In addition to this centralized approach, we have also examined the case of parallelizing the monitoring process for advanced efficiency against scalable data volumes. As a proof-of-concept, due to the different tasks of the two components, we employed different data partitioning schemes. First, concerning the trajectory detection component, the mobility tracker updates and maintains each trajectory in isolation from the rest. This process has been parallelized by using a varying number of concurrent POSIX threads in C++: each one is responsible to monitor a distinct subset of vessels. The resulting synopses get merged into a single derived stream of critical points (MEs) that is subsequently consumed by RTEC. With respect to the complex event recognition component, we employed multiple processors on which RTEC operated in parallel. We divided the grid covering the surveillance area into multiple sub-grids (groups of adjacent cells) whose number was equal to that of the processors used in parallel. Each processor was responsible for the areas and ports located in, and the vessels passing through its assigned sub-grid. We used three distributed settings: performing CE recognition on two, four and twelve processors. We made an attempt to evenly distribute the load of MEs among the different processors, by exhaustively searching for the best configuration. The different sub-grids had to be compact rectangles without dispersed cells. As a result, we did not take into account solutions with sub-grids of arbitrary shapes and the load distribution was thus not the best possible. Note that this partitioning is an off-line process and takes place only once.

Next, we report indicative results from these experiments. The trajectory event detection component operated on a server running Debian Linux “Wheezy” 7.5 amd64 with 48GB of RAM and two Intel Xeon X5675 processors at 3.07GHz. The CE recognition component RTEC operated on a computer with Intel Xeon CPU E5-2630 v2@2.60GHz ×12 processors and 256GB RAM, running Ubuntu Linux 14.04 and SWI Prolog 7.2.1.

5.1 Assessment of trajectory detection

5.1.1 Timeliness of online mobility tracking

First, we examine performance of online detection concerning trajectory movement events using simulations at the original arrival rate. These experiments have been performed employing window specifications with varying ranges ω and slide steps β, and we measure the total time it takes to update a window with a fresh batch of raw AIS locations, evict expired ones, detect trajectory events, and report critical points. Then, we calculate averages of these time values over the total count of window instantiations, hence obtaining the per slide cost for window maintenance and identification of any trajectory events therein. Figure 7 plots this average execution cost per window for monitoring the entire fleet.

Fig. 7

Online mobility tracking cost per window slide

From Fig. 7a it turns out that our mobility tracker provides results instantly for smaller ω up to 2 hours. In the worst case, it takes less than 150ms to track down any critical points per incoming batch of raw positional tuples. Quite expectedly, the cost grows linearly with an increasing slide β, as the window slides forward less often and thus each batch contains more input locations (illustrated with bars in this plot) directly proportional to the sliding step β.

For larger windows with range ω up to 24 hours shown in Fig. 7b, the cost is greater. Increased by almost an order of magnitude compared to the execution times in Fig. 7a, the cost still remains linear with the size of wider sliding steps. Again, this is due to the larger amount of accumulated raw locations per batch (depicted with the bar plots). For the larger window tested (ω=24 hours and β=4 hours), critical points can be reported in less than 2 seconds per batch, even though the mobility tracker has to validate almost 30,000 fresh raw positions each time. This clearly testifies the robustness and timeliness of the online tracking process.

We should also stress that these execution costs are drastically reduced compared to our previous performance study in [33]. Apart from better memory management in the implementation of the method, this improvement should be also attributed to the extra module for noise reduction. Since each position qualified as noise is filtered out without further processing, this incurs no more checks against the rest of the positions reported per vessel. Moreover, it reduces the size of the trajectory synopsis (i.e., critical points retained out of the raw positions per vessel), since such erroneous deviations from the known course are suppressed. Figure 8 plots the average amount of critical points retained per window state for several window ranges ω. It is no wonder that the number of critical points in window are proportional to its range, as this is actually the memory footprint of the maintained trajectory synopses. Space consumption is provably lightweight, since the trajectories of all vessels within the latest ω=24 hours can be approximately reconstructed from the almost 52,000 critical point locations maintained (on average) in the respective window state.

Fig. 8

Window states for varying ranges

5.1.2 Scalability under varying arrival rates

Admittedly, such swift processing of raw positions is largely due to the low arrival rate of the original AIS stream (on average ρ≈50 positions/sec). Hence, for a more stringent assessment of the online mobility tracking module, we performed some extra simulations, by admitting bigger chunks of data for processing at considerably increased arrival rates up to ρ=10,000 positions/sec. Then, given the fleet size N, every ship appears as reporting almost twice per second; although quite improbable in practice, this makes sense as a stress test for scalability.

As timeliness is also an objective, the window for the simulations in Fig. 9 was set with range ω=10 minutes and slide β=1 minute. We first discuss performance when employing a single thread to tackle the entire trajectory detection process. Observe that critical points are still issued promptly for ρ=1,000 positions/sec, but the latency grows with increasing rates. Note that this cost includes reporting time for the resulting critical points (i.e., after detection), and this adds a significant overhead at higher arrival rates, as greater chunks of AIS updates inevitably generate more critical points. In the worst case tested with ρ=10,000 positions/sec, the online mobility tracker accepts 600,000 fresh raw positions every minute; yet, it can output results in less than 13 seconds, well before the next window slide.

Fig. 9

Trajectory detection at various stream rates

The fact that the mobility tracker updates and maintains each trajectory in isolation from the rest, offers great opportunities for more advanced scalability. For the trajectory detection process, we also employed a varying number of concurrent threads, each one monitoring a distinct subset of vessels. Each thread consumes a substream of the incoming raw positions that correspond to the particular vessels it has been assigned to monitor. For simplicity, this subdivision is based on simple hashing over the MMSI identifier of the vessel, such that its positions are always propagated to the same thread to establish consistency in trajectory maintenance. The system load may not be evenly balanced among the threads and cannot account to fluctuations in the arrival rate, but still the burden of processing can be shared and thus boost performance. In this case, the overall tracking cost per window is considered the maximum of costs incurred among the concurrent threads in order to emit results. Obviously, this cost differs depending on the size of the incoming batch consumed by a thread in each window instantiation. Figure 9 plots the average tracking cost per window slide when multiple threads are used (due to hashing, a prime number of threads was specified). There are significant savings even when employing two threads only; the original stream is halved into two substreams, but the cost drops by almost two thirds as each thread exploits better the available system resources. With more threads the cost still drops, although at a lower pace due to the overhead from context switching and contention for system resources. Overall, even this simplified approach confirms that the trajectory detection process is capable of handling scalable volumes of streaming vessel positions and has great potential for parallelization and advanced load balancing, as we plan to study in future work.

5.1.3 Compression efficiency

In this experiment, we examine the efficiency of our prototype in keeping only major trajectory characteristics as critical points and discard the rest. In order to measure the compression ratio accomplished by online trajectory tracking, we compared the amount of discarded points against the originally relayed locations per vessel. A compression ratio close to 1 signifies stronger data reduction, as the vast majority of original locations are dropped. The red line plot in Fig. 10 depicts measurements of this ratio with varying tolerance angles for detecting changes in heading. With a lower Δ𝜃, even slight deviations in vessel direction can be spotted, and thus extra critical points get reported. Bar charts in Fig. 10 illustrate the amount of critical points in each class (gap, low speed, speed change, stop, turn) retained from the entire dataset. Clearly, every further increase in threshold Δ𝜃 suppresses more and more turning points and only marginally affects the share of other classes, incurring extra reduction in the total amount of emitted critical points. Hence, relaxing this parameter value leads to a more intense compression. Most importantly, compression ratio always remains above 92 %, and with a more relaxed Δ𝜃 it reaches as much as 98 %. In this latter case, only 2 % of the original locations survive as critical, mostly by eliminating local manoeuvres of little impact on vessel’s course. Eliminating noise also plays an important role in data reduction, as erroneous deviations are dropped and no points need be retained.

Fig. 10

Compression for varying Δ𝜃

A similar pattern regarding reduction efficiency can be observed in Fig. 11 with respect to varying periods ΔT for detecting gaps in communication. Not surprisingly, it is the amount of critical points marking those gap periods that gets reduced with increasing thresholds ΔT. This time, reduction ratio is never below 96%, even though many more points are required to keep track that contact was lost even for 5 minutes. In a streaming context, such high compression ratios may lead to reduced system load in subsequent stages of the analysis, without sacrificing quality, as discussed next.

Fig. 11

Compression for varying period ΔT

5.1.4 Approximation error

Preserving only critical points incurs a lossy approximation in trajectory representations. To assess the quality of those compressed trajectories, we estimated their deviation from the original ones (i.e., without discarding any raw positions except for those qualified as noise). Deviation can be computed from the pairwise distance between synchronized locations from the original and the compressed trajectory. If an original AIS point p _i at time t _i has been evicted as non-critical, then its corresponding time-aligned p i′ in the compressed trace can be estimated using linear interpolation along the path that connects the two critical points before and after t _i . For each vessel that has reported M raw positions, we estimated the root mean square error (R M S E) between the original and synchronized sequences of its locations as:

$$\mathit{RMSE} = \sqrt{\frac{1}{M} \cdot \sum\limits_{i=1}^{M} (H(p_{i}, p^{\prime}_{i}))^{2} } $$

which returns one RMSE estimate (in meters) per vessel trajectory and employs Haversine distance H between geographic coordinates. Figure 12 illustrates the number of vessel trajectories for certain intervals of these RMSE estimates. For example, RMSE is between 10 and 25 meters for trajectories of 3093 vessels (almost half of the fleet), whereas RMSE less than 10 meters occurs for another 1428 vessels. In contrast, only 3 vessels were found with RMSE above 100 meters. Although parametrization of the mobility tracker is common for all vessels, this result proves that it can offer a correct (or at least fairly trustful) approximation in almost all cases.

Fig. 12

Breakdown of RMSE for Δ𝜃=15^o

Figure 13 plots the average and maximum R M S E over the entire fleet for several values of turn threshold Δ𝜃, which is used to recognize significant changes in heading. As discussed in Section 3.2, the degree of trajectory approximation is mostly sensitive to parameter Δ𝜃 compared to the rest in Table 4 and this is reflected on the plot. Both error estimates escalate as this angle tolerance gets more relaxed. In the worst case for Δ𝜃=20^o, average RMSE is only 22 meters and the maximum R M S E ever observed is 133 meters, which are negligible compared to the much larger size of open-sea vessels, and also considering the discrepancies inherent in GPS positioning and AIS transmissions. In practice, a moderate threshold of 10^o or 15^o may be adequate for balancing compression efficiency without losing important details in vessel mobility. Therefore, the suggested method can provide quite acceptable accuracy and can capture most, if not all, critical changes along each vessel’s course.

Fig. 13

Trajectory approximation quality

5.1.5 Quality of synopses

As raw AIS locations pass through the trajectory detection module in successive window instantiations, they get characterized according to their significance on vessel mobility. Figure 14 illustrates a breakdown of the resulting classifications after the input stream was exhausted and all critical points were detected for the entire 3-month period. More than half of the relayed raw positions indicate a “normal” course, i.e., a vessel moves according to its known velocity vector with a steady speed and heading. Thus, apart from notifying on the current position of each vessel, such points practically do not alter its trajectory and can be safely discarded without any further consideration. In addition, almost one out of five original positions is classified as noise for reasons explained in Section 3.1. It must be stressed that the vast majority of such points are not really “off-course” positions from the reporting vessel, but they actually fall along its route. However, due to their delayed arrival, these locations falsely indicate the vessel as moving back and forth in an agitating manner with no obvious reason, hence they should be purged altogether.

Fig. 14

Classified raw locations of all vessels

But it is the remaining vessel locations, after eliminating redundancy and noise, which get actually classified as critical points and can be used in trajectory summarization. As Fig. 14 testifies, there are relatively very few cases (about 0.1 % of the raw data) in which vessels either move at low speed or they change their speed considerably. This is to be expected, since vessels usually follow their planned course and they typically manoeuvre when arriving to or departing from ports. Gaps in communication account for about 0.8 % of the raw data. Although we observed that this phenomenon is rather frequent in practice, we note that at most two points are used to delimit this period and thus indicate the loss of contact with the respective vessel. Locations indicating turns are very important and must be certainly considered in trajectory representation. In fact, these points are roughly 1.5 % of the total, since only significant deviations (over 15^o) from the known course qualify for a turn, even though possibly emitting a series of such critical points in case of smooth turns as depicted in Fig. 3b. Finally, about 27 % of the raw positions are emitted when vessels are idle, most usually when anchored in a port. As discussed in Section 3, instead of keeping all these points, we collect successive “pause” events occurring within a small distance and merge them into a collective “stop” event located at their centroid. This incurs huge savings in the resulting synopses, leading into much more concise trajectory representations that can be highly usable in subsequent query processing and offline analytics.

This dramatic effect on summarization is much more evident in Fig. 15, which plots a breakdown of the accumulated critical points after processing the entire dataset. The resulting trajectories mainly consist of turning points between stops with some occasional changes in speed, but rather frequent communication gaps. Indeed, 60 % of critical points are turning points, which are only 1.5 % of the original AIS locations (Fig. 14). Points indicating gap periods are almost 32 % of the critical points, testifying the frequent loss of contact with vessels on the move. In contrast, long-term stops comprise a meagre 4.5 % in the resulting trajectory synopses, since locations that belong to the same stop event are compressed into a single centroid that suffices to designate that the vessel is idle during this period. Apart from redundant “normal” points and eliminating the inherent noise, condensing these stops really adds much to the reduction efficacy of the trajectory detection module, offering a valuable semantic interpretation of the motion features.

Fig. 15

Characterization of critical points

As an offline, post-processing step, we have reconstructed trajectories from the entire sequence of critical points accumulated per vessel. In effect, the long motion history of a ship can be broken up into shorter “trips” between identified stop points, which usually indicate anchorage at ports. Table 5 lists representative statistics from these approximate trajectories, and offers insight on a possible offline usage of the results from trajectory summarization. It turns out that a typical trip spanning several hours over a long distance (more than 131km) can be approximated with 48 points only; once more, this confirms the strong reduction effect of the method. Note that almost 5 % of the detected critical points belong to “open-ended” trips, as certain vessels were only spotted while traversing the Aegean without anchoring there.

Table 5 Statistics from post-processing of compressed trajectories

5.2 Assessment of complex event recognition

The trajectory detection module compresses a vessel position stream to a stream of critical movement events (ME)s. Each such event is represented by predicates expressing the activity of the vessel, its coordinates and its velocity (see Section 4). This way, the ME stream given to RTEC includes 15,884,253 predicates spanning over the 3-month period. In addition to this stream, RTEC makes use of real data consisting of protected areas, such as NATURA areas, represented as polygons, and ports, represented as points, across the Greek seas. The dataset has 3,966 protected areas with a total of 78,418 edges, and 64 ports. The size of the grid is 720 ×900 km². Given this combination of event stream and static geographical information, RTEC recognizes the following CEs: illegal shipping, suspicious vessel delay, vessel rendezvous, suspicious areas, vessel pursuit, and package picking (see Table 1).

5.2.1 Grid partitioning

Figure 16 shows the results from a first set of experiments in which we attempted to determine the optimal grid granularity/cell size. Starting with a grid having 5×5=25 cells (with a cell size of 138×170 km²), we increased the number of cells along each dimension, up to 90×90= 8,100 cells (each cell being 9×11 km² wide). Figure 16a shows the average CE recognition times in CPU seconds for each different grid. Both the window ω and the slide β are set to 1 hour. The worst grid configuration (90×90) is almost two times slower than the best (10×10), but in all cases the average time is within the same order of magnitude, and less than 3 seconds. Figure 16b shows the average number of recognized CEs for each different grid as a stack plot. The number of recognized CEs shows a decreasing trend initially, with a tendency to stabilize after grid configuration 30×30. The reason for the difference in the number of detected CEs lies in the way the respective patterns are defined. Most of the CE patterns are grid-independent. Therefore, the number of recognized CEs remains stable across all grid configurations. On the other hand, p o s s i b l e R e n d e z v o u s, as defined by rule (3), depends on the size of the grid cells. Recall that the place of vessel rendezvous cannot be determined precisely, since vessels stop transmitting AIS signals during the time of the meeting. Therefore, we can only define p o s s i b l e R e n d e z v o u s in terms of the cells in which the vessels in question stopped (respectively resumed) transmitting AIS signals. As a result, when the size of the cells increases, more p o s s i b l e R e n d e z v o u s CEs are being recognized. For this reason, instead of choosing the 10×10 grid for the remaining experiments, we opted for the 30×30 one, which has comparable time performance and a stable number of detected CEs.

Fig. 16

CE recognition for different grid cell sizes

5.2.2 Timeliness of complex event recognition

Next, we proceed with a more thorough analysis of the performance of RTEC. Figure 17 shows the results of experiments under various window sizes and distributed configurations. First, we used a single processor to perform CE recognition for all 6,425 vessels, 3,966 areas and 64 ports. We subsequently employed multiple processors in three different settings, with two, four and twelve processors.

Fig. 17

CE recognition under varying window sizes and distributed configurations

Figure 17a shows the average CE recognition times, including the time taken for spatial indexing (see Section 4.2). The slide β is 1 hour while the window ω ranges from 1 hour to 24 hours. Figure 17b shows the average number of MEs for each setting. In the case of a single processor, the window ranges from ≈7,200 MEs (1 hour) to 175,000 MEs (24 hours). In the distributed settings—two, four and twelve processors for CE recognition— the input MEs are forwarded to the appropriate processor according to vessel location. For instance, when twelve processors are used in parallel, each one of them processes ≈700 MEs for the 1 hour window, and 17,000 MEs for the 24 hour window. Figure 17c shows the average number of CEs for each setting. This number also depends on the window size. In the case of a single processor, e.g., for 1 hour windows approximately 150 CEs are recognized, while for 24 hour windows RTEC recognizes around 2,900 CEs. We do not show memory consumption figures because memory usage is negligible and stable.

Figure 17a shows that we can achieve a significant performance gain by running RTEC in parallel. As the window size increases, the gain becomes more pronounced. Furthermore, Figure 17a shows that RTEC supports real-time CE recognition. E.g. for a window of 6 hours, RTEC recognizes all CEs in 14 sec when a single processor is used, and in 0.4 sec when twelve processors are used in parallel.

5.2.3 Scalability of complex event recognition

Since RTEC can comfortably handle the initial dataset, we tested its performance with artificially enlarged datasets in order to determine its limits in terms of scalability. We created enlarged data streams by inserting extra critical MEs to the real dataset. For each vessel, we replicated its trajectories by a specified number of times (increase factor). The replicated trajectories were assigned to new vessels which do not exist in the original dataset, thus adding more vessels as well. An increase factor X implies that we have exactly X times as many critical MEs and X times as many vessels, compared to the original dataset of ≈16,000,000 MEs and ≈6,500 vessels. We varied the increase factor from 20, producing datasets of ≈128,000 vessels and 320,000,000 MEs, to 200, creating data of ≈1,280,000 vessels and 3,200,000,000 MEs. To the best of our knowledge, this is the most comprehensive evaluation of CE recognition techniques in the maritime domain. Compared to e.g. [40], our surveillance area, number of vessels and data volume are substantially larger. Moreover, CE recognition needs to consider (a large number of) protected areas.

Figure 18 displays the experimental results. Twelve processors are used in parallel, the slide β is set to 1 min, and the window sizes ω are 60 min (1 hour) and 10 min. We set two ‘response limits’ to 10 sec and 60 sec—we stopped performing tests once the response limit of 60 sec was exceeded.

Fig. 18

CE recognition for approximately 128K–1,28M vessels and 320M–3,2B MEs. Response limits are indicated with lines in Fig. 18a and with points in Figs. 18b–d

Figure 18a shows the average CE recognition times while Fig. 18b the average memory usage. As expected, a smaller window produces both lower recognition times and lower memory usage. Figures 18c and d display respectively the average number of MEs and CEs. We also show how RTEC performs with respect to the two response limits of 10 and 60 sec. Assume, for instance, that we want to guarantee that RTEC responds within 60 sec. In this case, for a window of 60 min, RTEC can handle data streams that are ≈70 times larger (≈450,000 vessels) than the original one (see Fig. 18a). This means that a window may include up to approximately 400,000 MEs, while recognizing around 105,000 CEs (see the 60 sec response limit markers on the 60 min window lines in Figs. 18c and d respectively). Memory consumption is 4,9 GB (see the 60 sec response limit marker on the 60 min window line in Fig. 18b). Similarly, for a window of 10 min, RTEC is guaranteed to respond within 60 sec even in data streams that are 160 times larger than the original (≈1,000,000 vessels).

Comparing the 60 min window/80 increase factor setting against the 10 min window/200 increase factor setting, we see that the latter has fewer MEs and CEs (see the right-most marks of the window lines in Figs. 18c and d). However, both the CE recognition times and memory usage are higher (see the right-most marks of the window lines in Figs. 18a and 18b). One reason for this behavior is that the complexity of the recognition task is higher in the 10 min window/200 increase factor setting. A simple measure of complexity in CE recognition is the ratio of CEs to MEs. This ratio is depicted in Fig. 18e.

As a further step towards understanding RTEC’s behavior, we investigated how it stores some of its internal structures. During CE recognition, RTEC maintains several lists of time intervals for different types of event and fluent. In Fig. 18f, we plot the average number of instances of these lists. The results show that these lists are mostly responsible for the increased recognition times and memory usage, as the increase factor grows. More specifically, the lists concerning p o s s i b l e R e n d e z v o u s and p o s s i b l e P i c k i n g event (see rules (3) and (5) respectively), require that all combinations of vessels within some area are checked. Therefore, when the number of vessels increases, as is the case with replicated trajectories, the number of possible combinations is increased by the square of the number of vessels, hence the parabolic lines in Fig. 18f. On the other hand, a window increase does not result in many more vessels being considered. Many of the added MEs may refer to extra messages transmitted by the same vessel over the longer duration of a larger window. Note that this is a different kind of complexity than the one reflected in the ratio of CEs to MEs. In the case where we have more combinations to check, this does not necessarily imply that proportionally more CEs will be recognized, since their definitions might not be satisfied. RTEC has to check all possible combinations though, thus incurring a higher latency and memory consumption.

6 System deployment

In order to verify its operational capabilities, we have set up our system to monitor live AIS feeds from vessels across the Aegean Sea. Fresh positions are periodically fetched from a database (maintained by the University of the Aegean) that receives any transmitted AIS messages. Each retrieved record only includes vessel identification, geographic position, and a timestamp. Currently, fresh input is fetched every hour (the sliding step β of the window employed in this instance), although a different period may be chosen. Typically, we observed that up to 40,000 fresh records can be fetched per hour, which is a rather moderate amount of geostreaming data compared with the arrival rates simulated in our empirical validation (cf. Section 5).

Once each batch of fresh data arrives, it is being consumed by the online mobility tracker in order to identify any critical points in each vessel’s course. The resulting points with their annotations (turn, stop, etc.) are then archived into a PostgreSQL database. But the Trajectory Exporter module also converts them into KML files for map visualization in a web application, as illustrated in Fig. 19. Critical points may be exported upon detection, but in order to avoid duplication of data across the modules, we opt to export them once they get evicted from the sliding window (currently set to a range of ω=6 hours). Hence, exported results currently have a lag of 6 hours from the current time, but this is only a configuration parameter.

Fig. 19

Monitoring real-time AIS positions and vessel trajectories in the Aegean

This deployment against real-time AIS messages collected across the Aegean has been activated since April 2015. This confirms that our system can integrate with a precious source of online data, offering to marine experts and authorities the means to instantly locate, recognize, and correlate events from real-time vessel traces.

7 Summary & future work

In this paper, we introduced a system that monitors activity of thousands of vessels and can instantly recognize events with a potentially serious impact on the environment and on safe navigation at sea. The system can sustain streaming messages from vessels and can filter out noise and redundant positions along their course. Hence, it can retain only succinct synopses of vessel trajectories, drastically reducing the original path into few critical points that convey major motion features. As empirically validated, with a proper parametrization our suggested trajectory summarization may incur a compression ratio of almost 98 %, with tolerable error in the resulting approximation. Moreover, trajectory detection is highly scalable and can be easily parallelized in order to sustain very high arrival rates in the input stream. Furthermore, this reduced information may be readily analyzed online for Complex Event (CE) recognition. Equipped with efficient pattern matching algorithms, this module correlates critical trajectory positions with static geographical data, and detects suspicious or dangerous situations, such as illegal shipping, suspicious vessel delay, vessel rendezvous, suspicious area, vessel pursuit and package picking. We showed that the CE recognition module performs in real-time using real data as well as synthetically enlarged datasets that include up to 1,28M vessels and 3,2B critical positions.

We plan further extensions and improvements in the existing implementation. First, since trajectory detection may be sensitive to parameters, we intend to study advanced methods for adaptive, auto-calibrated parameterization depending on the size, the type, and the motion patterns of vessels. Also, creating CE patterns manually is painstaking and error-prone. To facilitate the process of CE pattern construction, we plan to employ a recent framework for incremental structure learning that takes advantage of Big Data in order to construct Event Calculus programs [20]. Besides, maritime surveillance exhibits various types of uncertainty [39]. AIS messages are often corrupt, with incorrect or missing fields. Furthermore, maritime CE patterns do not account for all possible situations. To deal with these issues, we have been developing an Event Calculus dialect for Markov Logic Networks [38]. This way, we can use weight learning techniques [13] for estimating the confidence values of CE patterns, and subsequently perform probabilistic inference. Maritime surveillance may also benefit from combining multiple data sources. For example, the use of heterogeneous data sources, as in [40], can help in constructing more refined CE patterns. We aim to increase our data sources in order to improve monitoring quality and possibly recognize additional events. Last, but not least, it would be challenging to apply ideas from our methodology against other sources of big geostreaming mobility data, e.g., traces of aircrafts or vehicles. Although the particular definitions of events may differ, as well as their configurations, we expect that our methodology may still be valid.