⚡ electrical engineering

Data-Driven Trajectory Imputation for Vessel Mobility Analysis

This paper introduces HABIT, a lightweight, data-driven framework that leverages historical AIS data and H3 aggregation to accurately and efficiently impute missing vessel trajectory segments by accounting for unique maritime motion patterns, thereby outperforming existing methods in latency while maintaining comparable accuracy.

Original authors: Giannis Spiliopoulos, Alexandros Troupiotis-Kapeliaris, Kostas Patroumpas, Nikolaos Liapis, Dimitrios Skoutas, Dimitris Zissis, Nikos Bikakis

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Giannis Spiliopoulos, Alexandros Troupiotis-Kapeliaris, Kostas Patroumpas, Nikolaos Liapis, Dimitrios Skoutas, Dimitris Zissis, Nikos Bikakis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the ocean as a giant, invisible highway. Just like cars on a road, ships leave behind a digital trail of where they've been. This trail is called AIS data (Automatic Identification System). It's how we know where a ship is, how fast it's going, and where it's heading.

But here's the problem: sometimes the ship's "GPS" goes offline. Maybe the signal gets blocked by a storm, the battery dies, or the captain decides to turn it off to hide their location. When this happens, the digital trail has gaps. It's like looking at a movie where someone ripped out a whole reel of film. You see the ship at Point A, and then suddenly, hours later, it's at Point B. You have no idea what happened in between. Did it go straight? Did it take a scenic route? Did it stop at a secret island?

This paper introduces a smart solution called HABIT to fill in those missing movie reels.

The Problem: Why Can't We Just Draw a Straight Line?

If you were trying to guess where a car went between two points on a map, you might just draw a straight line. But ships aren't cars.

Cars are stuck on roads. They can't drive through buildings or fields.
Ships can go almost anywhere on the water, but they can't drive through islands, coastlines, or shallow reefs. They also can't make sharp 90-degree turns like a Formula 1 car; big ships turn slowly and smoothly, like a massive cruise ship trying to park.

If you just draw a straight line between two ship locations, you might accidentally draw a path that goes right through a mountain or a tiny island. That's not helpful.

The Solution: HABIT (The "Crowdsourced Map" Approach)

The authors created a framework called HABIT. Think of HABIT not as a single detective, but as a giant, smart librarian who has read every single ship log from the past.

Here is how HABIT works, step-by-step, using a simple analogy:

1. The Honeycomb Map (H3 Grid)

Instead of trying to track every single inch of the ocean (which is too much data), HABIT divides the ocean into a giant honeycomb grid (like a beehive). Each hexagon is a "cell."

Analogy: Imagine the ocean is a giant floor covered in hexagonal tiles. HABIT doesn't care exactly where the ship is inside the tile; it just cares that the ship moved from "Tile A" to "Tile B."

2. Learning the Patterns (The "Commute" Logic)

HABIT looks at millions of historical trips. It notices patterns.

Analogy: Imagine you live in a city. You know that most people who leave "Tile A" in the morning usually go to "Tile B" to get to work, not "Tile C" which is a park.
HABIT builds a map of probabilities. It learns: "Hey, 90% of the time, when a ship leaves this hexagon, it goes to this specific neighbor hexagon." It creates a "traffic flow" map based on real history, not just math.

3. Filling the Gap (The Detective Work)

When a ship's signal goes missing, HABIT looks at where the ship was before the gap and where it was after.

It asks its "librarian" database: "What is the most common path ships take between these two hexagons?"
It finds the most popular route (the "shortest path" through the honeycomb) and fills in the missing dots.
Crucial Step: It doesn't just pick the center of the hexagon. It looks at the exact spots where real ships usually pass through that hexagon. If the "center" of the hexagon is deep water, but real ships usually hug the edge to avoid a reef, HABIT picks the edge.

4. Smoothing the Ride (The "Steering Wheel" Check)

The path HABIT draws might look a bit jagged because it's hopping from hexagon to hexagon.

Analogy: Imagine walking from room to room in a house. You don't walk in a jagged zig-zag; you walk in a smooth curve.
HABIT uses a smoothing algorithm to make the path look natural, ensuring it doesn't have sharp, impossible turns that a real ship couldn't make.

Why is HABIT Better than Other Methods?

The paper compares HABIT to other high-tech methods (like complex AI models).

Speed: HABIT is incredibly fast. It's like using a well-organized index card system vs. asking a supercomputer to re-simulate the entire ocean every time you ask a question. It fills gaps in less than a second.
Memory: It takes up very little computer memory. Other methods are like trying to store the entire internet on a USB stick; HABIT is like storing just the map you need.
Accuracy: It's just as good at guessing the right path as the complex methods, but it's much lighter and faster.

The Big Picture

Why does this matter?

Safety: If a ship goes missing, we can guess where it likely went to help search and rescue.
Traffic Control: We can see where ships usually go, helping ports manage traffic better.
Environment: We can track if ships are taking routes that avoid sensitive marine areas.

In short: HABIT is a smart, fast, and efficient way to guess where a ship went when its GPS went silent, by learning from the habits of millions of other ships that traveled the same waters before. It turns a broken, jagged line into a smooth, realistic story of a journey.

1. Problem Statement

The Automatic Identification System (AIS) is the primary source for monitoring global maritime traffic, generating massive datasets used for logistics, safety, and environmental analysis. However, AIS data suffers from significant gaps due to:

Coverage limitations: Signal loss from terrestrial or satellite receivers.
Irregular reporting: Variable sampling rates.
Intentional interruptions: Devices switched off or spoofing.

These gaps result in sparse, discontinuous trajectories that degrade the quality of analysis. While trajectory imputation (filling gaps) is well-studied for land vehicles using road networks, maritime trajectories present unique challenges:

No fixed network: Ships do not follow fixed roads; routes vary based on weather, traffic, and port constraints.
Motion patterns: Vessels exhibit smooth turns, complex maneuvering near ports, and specific behaviors based on size/draught, which differ significantly from cars.
Existing limitations: State-of-the-art methods (e.g., network-based or deep learning models like Transformers) are often computationally expensive, rely on road networks, or fail to produce navigable paths (e.g., crossing land) when applied to open sea data.

2. Methodology: The HABIT Framework

The authors propose HABIT (H3 Aggregation-Based Imputation Trajectory), a lightweight, data-driven framework designed specifically for maritime gaps. It relies on H3 (Uber's hierarchical hexagonal geospatial indexing system) to aggregate historical AIS data into a graph structure.

The framework operates in four distinct phases:

Phase 1: Data Preprocessing & Trip Segmentation

Cleaning: Filters noise (duplicate positions, invalid coordinates, delayed messages).
Segmentation: Splits continuous vessel tracks into "trips" based on stops (speed < 0.5 knots) or communication gaps (> 30 minutes).
Annotation: Identifies mobility events (turning points, speed changes) to ensure only relevant movement data is used.

Phase 2: Graph Generation

H3 Indexing: Raw AIS positions are projected onto H3 hexagonal cells at a specific resolution ( $r$ ).
Statistical Aggregation: Using DuckDB (an in-memory analytical database), the system computes statistics for each cell and transitions between cells:
- Cell stats: Median longitude/latitude, median speed/course, distinct vessel counts.
- Transition stats: Number of transitions between cell pairs ( $lag\_cl \to cl$ ).
Graph Construction: A weighted directed graph is built where:
- Nodes = H3 cells (attributes: median coordinates, vessel counts).
- Edges = Transitions between cells (weight = frequency of transitions).
- This creates a "data-driven maritime network" reflecting actual traffic flow rather than a theoretical grid.

Phase 3: Trajectory Imputation

Gap Mapping: The start and end points of a gap are mapped to the nearest H3 cells in the graph.
Pathfinding: An A search algorithm* identifies the shortest path (minimum transitions) between the start and end nodes, effectively finding the most historically frequent route.
Inverse Projection: The sequence of H3 cells is converted back to real-world coordinates.
- Innovation: Instead of using the geometric center of the hexagon (which may fall on land or in open water), HABIT uses the median coordinates of historical AIS points within that cell. This ensures the imputed path remains grounded in actual navigable areas.

Phase 4: Trajectory Simplification

Smoothing: Grid-based paths often contain "zigzags." To ensure navigability (smooth turns suitable for large ships), the Ramer-Douglas-Peucker (RDP) algorithm is applied.
Tolerance ( $t$ ): A parameter controls the trade-off between path smoothness and fidelity to the original grid sequence.

3. Key Contributions

Domain-Specific Framework: HABIT is the first lightweight framework explicitly designed for maritime trajectory imputation, addressing the lack of fixed networks and unique vessel motion patterns.
Data-Driven Navigation: By using median coordinates instead of geometric centers and aggregating historical transitions, HABIT generates paths that are statistically probable and physically navigable (avoiding land/obstacles).
Efficiency & Scalability: Unlike heavy deep learning models (e.g., BERT, Transformers) or complex graph diffusion models, HABIT utilizes DuckDB and NetworkX for in-memory processing, resulting in a significantly smaller memory footprint and faster query latency.
Configurability: The framework allows tuning of H3 resolution ( $r$ ) and simplification tolerance ( $t$ ) to balance accuracy, smoothness, and computational cost.

4. Experimental Results

The authors evaluated HABIT using real-world AIS data from two regions:

DAN/KIEL: Passenger ferry routes (Denmark/Germany/Sweden).
SAR: Mixed vessel traffic in the Saronic Gulf (Greece).

Key Findings:

Accuracy:
- HABIT achieves accuracy comparable to GTI (a state-of-the-art network-agnostic method) in terms of Dynamic Time Warping (DTW) error.
- In complex, multi-route scenarios (SAR dataset), HABIT outperformed GTI, which tended to select outlier paths or fail to converge.
- HABIT significantly outperformed Simple Linear Interpolation (SLI), which often created non-navigable straight lines across land.
Performance & Latency:
- Query Latency: HABIT operates in sub-second latency (avg ~0.02s - 0.14s), whereas GTI took significantly longer (0.26s - 1.2s).
- Memory Footprint: HABIT models are orders of magnitude smaller (e.g., < 60 MB for SAR) compared to GTI models (up to 4.8 GB), making HABIT highly scalable.
Robustness: The method remained stable even with larger gap durations (up to 4 hours), though error naturally increased with gap size.

5. Significance

This paper addresses a critical bottleneck in maritime data analytics: the inability to reliably reconstruct vessel paths from sparse AIS data.

Practical Impact: HABIT enables the generation of high-quality, dense trajectory maps essential for traffic monitoring, anomaly detection (e.g., smuggling, illegal fishing), and emergency response planning.
Technical Advancement: It demonstrates that lightweight, statistical graph approaches can rival or exceed complex machine learning models in specific domains where data sparsity and physical constraints (navigability) are paramount.
Future Directions: The authors plan to integrate vessel-specific attributes (draught, type) and environmental context (weather) to further refine the imputation logic, potentially moving toward unified pipelines for maritime analytics.