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

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

TL;DR

Researchers have developed "Dropout K-Means" and "Dropout K-Median" algorithms to optimize the placement of marine buoys for detecting illegal fishing vessels. By accounting for the high probability of buoy failure (due to weather or vandalism), these new methods increase ship detection probability from 38% to 52% compared to standard clustering techniques.

What Problem Does This Paper Address?

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.

Standard placement strategies use k-means clustering, which places 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.

Methods

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

  1. The Objective Shift: Instead of minimizing the distance between a ship and its closest buoy (as in classic k-means), the authors minimize the expected distance to the closest surviving buoy.
  2. Dropout K-Means & K-Median: They propose two variations. K-means minimizes squared distances (L2 norm), while K-median minimizes absolute distances (L1 norm).
  3. Computational Efficiency: A naive approach to "dropout" would require checking all $2^K$ possible combinations of buoy failures, which is computationally impossible 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.
  4. Iterative Updates: They use a modified version of the Weiszfeld algorithm for the dropout k-median variant to find the geometric median of ship clusters.

Datasets

The study used real-world maritime data to simulate ship traffic:

  • AIS Dataset: Historical Automatic Identification System (AIS) tracks were downloaded from the Global Fishing Watch repository.
  • Geographic Focus: The evaluation focused on the Gabonese Exclusive Economic Zone (EEZ) near West Africa, a region highly susceptible to IUU fishing.
  • Scale: The researchers used 55 distinct ship tracks consisting of 313,390 individual location reports to determine where traffic is most concentrated.

Key Insights and Ideas

  • The "Aha" Moment on Norms: The researchers found that Dropout K-Median outperformed Dropout K-Means. This is because the L1 distance (used in k-median) provides a "tighter upper bound" on the probability of missing a ship compared to the squared L2 distance (used in k-means). In simpler terms, k-median is less sensitive to outliers and creates a more reliable "safety net."
  • Deterministic vs. Stochastic: Unlike previous "stochastic dropout" attempts that relied on random sampling during training (which can be unstable), 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 slightly closer together or into more strategic "backup" positions than classic k-means, specifically to cover the gaps left by potential failures.

Key Results

The researchers simulated the deployment of 5 buoys with a 30% failure rate (matching real-world NOAA data). The ship detection probabilities ($P_d$) were:

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

By simply changing the math behind where the buoys were dropped, they achieved a 14% absolute increase in detection probability over the standard industry approach. Furthermore, the dropout-aware algorithms converged faster and with less variance than previous stochastic methods.

Limitations and Future Work

  • Uniform Failure Rates: The model assumes every buoy has the same 30% chance of failing. In reality, buoys in high-traffic or high-vandalism areas might have a higher failure rate than those in open water.
  • Static Placement: The current model assumes buoys are stationary. Future work could explore how these algorithms apply to drifting buoys or mobile autonomous surface vehicles.
  • Detection Radius: The study assumes a fixed 10km detection radius for all buoys. Varying sensor capabilities (e.g., different cameras or radar ranges) were not accounted for in this specific formulation.

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},
}

Loading related content...

Figure