Robust Marine Buoy Placement for Ship Detection Using Dropout K-Means

Yuting Ng, João M. Pereira, Denis Garagic, Vahid Tarokh

Abstract

Marine buoys aid in the battle against Illegal, Unreported and Unregulated (IUU) fishing by detecting fishing vessels in their vicinity. Marine buoys, however, may be disrupted by natural causes and buoy vandalism. In this paper, we formulate marine buoy placement as a clustering problem, and propose dropout k-means and dropout k-median to improve placement robustness to buoy disruption. We simulated the passage of ships in the Gabonese waters near West Africa using historical Automatic Identification System (AIS) data, then compared the ship detection probability of dropout k-means to classic k-means and dropout k-median to classic k-median. With 5 buoys, the buoy arrangement computed by classic k-means, dropout k-means, classic k-median and dropout k-median have ship detection probabilities of 38%, 45%, 48% and 52%.

Introduction

Illegal, Unreported, and Unregulated (IUU) fishing is a multi-billion dollar global threat that devastates marine ecosystems and food security. While networks of camera-equipped marine buoys are effective at catching illegal vessels, the ocean is a harsh environment. Data shows that at any given time, only about 70% of deployed buoys are actually reporting data; they are frequently taken offline by harsh weather, corrosion, or intentional vandalism by the very fishers they are meant to track.

Global distribution of marine buoys, where failures (red) can create significant gaps in surveillance networks.

Standard placement strategies typically use k-means clustering, which positions buoys at the "centers" of historical ship traffic. However, k-means assumes every buoy will always be functional. If a central buoy fails, a massive gap opens in the surveillance network. This paper addresses the need for "robust" placement—positioning buoys so that the network remains effective even when some nodes inevitably drop out.

Methodology

The authors reformulate buoy placement as a clustering problem that incorporates a dropout probability.

The Objective Shift

Instead of minimizing the distance between a ship and its closest buoy (as in classic k-means), the proposed methods minimize the expected distance to the closest surviving buoy.

Dropout K-Means & K-Median

Two variations are proposed:

  • Dropout K-Means: Minimizes squared distances (L2 norm).
  • Dropout K-Median: Minimizes absolute distances (L1 norm).

Computational Efficiency

A naive approach to "dropout" would require checking all $2^K$ possible combinations of buoy failures, which is computationally prohibitive for large networks. The authors derived a mathematical shortcut: by sorting buoys by their proximity to each ship location, they can calculate the dropout probabilities in polynomial time ($NK \log K$), making the algorithm nearly as fast as standard k-means. For the dropout k-median variant, a modified version of the Weiszfeld algorithm is used to find the geometric median of ship clusters.

Experimental Setup

The study used real-world maritime data to simulate ship traffic in the Gabonese Exclusive Economic Zone (EEZ) near West Africa, a region highly susceptible to IUU fishing.

  • AIS Dataset: Historical Automatic Identification System (AIS) tracks from Global Fishing Watch.
  • Scale: The researchers used 55 distinct ship tracks consisting of 313,390 individual location reports to determine traffic concentration.

Results and Discussion

The researchers simulated the deployment of 5 buoys with a 30% failure rate, matching real-world NOAA data.

Comparison of performance metrics across different clustering algorithms, showing the superior detection probability (Pd) of dropout-aware methods.

As shown in the table above, the dropout-aware algorithms significantly outperformed their classic counterparts. The ship detection probabilities ($P_d$) were:

  • Classic K-Means: 38%
  • Dropout K-Means: 45%
  • Classic K-Median: 48%
  • Dropout K-Median: 52%

Key Insights

  • Norm Selection: Dropout K-Median outperformed Dropout K-Means because the L1 distance provides a "tighter upper bound" on the probability of missing a ship. K-median is less sensitive to outliers and creates a more reliable "safety net."
  • Deterministic Solution: Unlike previous stochastic dropout attempts that relied on random sampling, this paper provides a deterministic closed-form solution that considers all possible failure outcomes simultaneously.
  • Redundancy by Design: The dropout-aware algorithms naturally push buoys into strategic "backup" positions to cover the gaps left by potential failures.

Conclusion

By simply changing the mathematical formulation of buoy placement, researchers achieved a 14% absolute increase in detection probability over standard industry approaches. Furthermore, the dropout-aware algorithms converged faster and with less variance than previous stochastic methods. Future work will explore non-uniform failure rates, drifting buoys, and varying sensor detection radii.

Summary updated

Abstract

Marine buoys aid in the battle against Illegal, Unreported and Unregulated (IUU) fishing by detecting fishing vessels in their vicinity. Marine buoys, however, may be disrupted by natural causes and buoy vandalism. In this paper, we formulate marine buoy placement as a clustering problem, and propose dropout k-means and dropout k-median to improve placement robustness to buoy disruption. We simulated the passage of ships in the Gabonese waters near West Africa using historical Automatic Identification System (AIS) data, then compared the ship detection probability of dropout k-means to classic k-means and dropout k-median to classic k-median. With 5 buoys, the buoy arrangement computed by classic k-means, dropout k-means, classic k-median and dropout k-median have ship detection probabilities of 38%, 45%, 48% and 52%.
BibTeX
@inproceedings{ng2020robust,
  author = {Yuting Ng and João M. Pereira and Denis Garagic and Vahid Tarokh},
  title = {{Robust Marine Buoy Placement for Ship Detection Using Dropout K-Means}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=Zq8G28897N8},
}
Figure