Geometry-Informed Maritime Anomaly Detection Using Probabilistic Roadmaps

Technical Summary: Geometry-Informed Maritime Anomaly Detection Using Probabilistic Roadmaps

Problem Statement
Maritime anomaly detection is critical for navigational safety and the protection of underwater infrastructure, particularly in complex environments like the Baltic Sea, which features dense traffic, archipelagos, and critical submarine cables. While recent data-driven approaches utilizing Automatic Identification System (AIS) data have advanced through unsupervised clustering, deep generative models, and hybrid graph-based methods, a significant limitation persists: most existing methods rely on latent behavior modeling or learned feature embeddings without explicitly encoding navigational feasibility constraints. Consequently, geometric consistency is often inferred implicitly rather than structurally embedded, potentially overlooking deviations that violate physical or regulatory navigational norms.

Methodology
The authors propose a geometry-informed supervised framework that integrates Probabilistic Roadmaps (PRMs)—originally developed for robotic motion planning—with supervised machine learning to detect anomalous vessel trajectories.

1. Probabilistic Roadmap (PRM) Construction:

   • A weighted undirected graph $G=(V, E)$ is constructed over the navigable Baltic Sea domain.
   • Nodes ($V$): Generated from the departure/arrival points of 858 real AIS voyages (1,716 points) and uniformly sampled points within the Baltic Sea bounding box. Nodes are filtered using a land-water mask derived from Sentinel-2 satellite imagery (reflectance threshold $\approx 0.18$) to ensure they lie on water. The final set comprises 2,284 valid nodes.
   • Edges ($E$): Nodes are connected to their $k$-nearest neighbors ($k=25$) if the straight segment between them lies entirely within navigable water. Edges intersecting coastlines (extracted from OpenStreetMap) are discarded.
   • Function: The PRM serves as a structural prior encoding feasible maritime corridors. The shortest-path distance $d_G(v_i, v_j)$ on this graph defines the "nominal" maritime distance between points.

2. Dataset and Synthetic Anomaly Generation:

   • Data: 858 real general cargo vessel trajectories from the Baltic Sea (Jan 2017–Jan 2019) were cleaned, resampled to 5-minute intervals, and projected into the EPSG:3035 coordinate system.
   • Synthetic Anomalies: Due to the scarcity of labeled real anomalies, 858 synthetic anomalies were generated to create a balanced dataset (1,716 total trajectories). These were created via four mechanisms to ensure diversity:
     • Sinusoidal Deviation: Periodic lateral perturbations with added Gaussian noise.
     • Markov-Based Perturbations: Stochastic directional deviations using a 3x3 probability kernel.
     • Autoencoder-Based Distortions: Nonlinear distortions introduced by injecting noise into a trained autoencoder's latent space.
     • Speed Anomalies Near Cables: Artificial speed increases (1.8x–2.2x) for segments intersecting a 500m buffer around submarine cables.

3. Feature Extraction:
   Trajectories are projected onto the PRM nodes to extract three categories of voyage-level descriptors:

   • PRM Conformity: Metrics quantifying deviation from the graph, including the ratio of actual trajectory length to PRM shortest-path length ($L_{AIS}/L_{PRM}$), absolute length difference, maximum and average Euclidean deviation from the nearest PRM node, and PRM coverage.
   • Kinematics: Variability in speed and heading, and maximum absolute acceleration.
   • Contextual Interaction: Minimum distance to coastlines and metrics regarding interaction with submarine cables (time spent near cables and average speed while near them).

4. Classification:
   A Random Forest (RF) classifier is trained on the extracted feature set. The model uses bootstrap sampling and random feature subsets to handle heterogeneous, non-linear interactions. Hyperparameters are tuned via a two-stage search (random search followed by grid refinement) using 10-fold cross-validation.

Key Contributions

• Structural Priors: The paper reinterprets PRMs not for control input generation, but as structural priors that explicitly encode navigational feasibility constraints (geography, coastlines, restricted areas) into the anomaly detection process.
• Interpretability: By projecting trajectories onto a navigability graph, the framework extracts interpretable features (e.g., route efficiency, geometric deviation) rather than relying solely on opaque latent embeddings.
• Infrastructure Awareness: The methodology explicitly integrates submarine cable data, allowing for the detection of anomalies specifically related to critical underwater infrastructure.
• Balanced Synthetic Dataset: The generation of diverse synthetic anomalies allows for supervised training in a domain where labeled anomalies are otherwise unavailable.

Experimental Results
The framework was evaluated on a held-out test set (20% of the data) with the following results:

• Performance: The model achieved a test ROC AUC of 0.837, with a test accuracy of 74.6%, precision of 76.2%, and recall of 71.3%.
• Generalization: The test AUC (0.837) remained close to the validation AUC (0.819), indicating stable generalization despite the use of synthetic data. The training AUC was higher (0.949), suggesting moderate overfitting, which the authors attribute to the heterogeneous and high-dimensional nature of the feature space.
• Discrimination: The ROC curve demonstrated clear separation from the random baseline, and the distribution of predicted probabilities showed distinct clustering for anomalous versus normal trajectories.

Significance and Claims
The authors claim that embedding navigational feasibility constraints via PRMs yields a "structurally meaningful representation" of maritime behavior. This approach provides an interpretable and operationally relevant framework for infrastructure-aware monitoring in geometrically complex environments.

The paper modestly acknowledges its limitations:

• The results rely on synthetic anomalies; independent real-world anomaly data is required for external validation.
• The study lacks ablation studies comparing the PRM-based approach against kinematic-only or non-PRM geometric baselines to isolate the specific contribution of the roadmap.
• The current PRM is static; future work is suggested to incorporate temporal dynamics (seasonal patterns) and environmental factors (weather, currents) to evolve the graph into a time-aware model.

Ultimately, the work establishes a structured, graph-based foundation for maritime anomaly detection, offering a structured alternative to purely latent trajectory representations.