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.
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.
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