Abstract
In marine robotics and environmental monitoring, agents must often make real-time, irrevocable decisions regarding sample collection from continuous data streams. While the classic "secretary problem" provides a theoretical basis for optimal selection, its assumption of random arrival orders is frequently violated by the inherent periodicity of natural systems. This paper presents the Periodic Secretary Algorithm, a novel approach designed to exploit spatiotemporal structures like seasonal or daily cycles. By utilizing an initial observation period to establish a reference set of environmental utility, the algorithm sets adaptive thresholds for subsequent sampling. Evaluated on the seven-year Martha’s Vineyard Coastal Observatory (MVCO) dataset, the algorithm demonstrates near-optimal performance, achieving entropy reduction levels comparable to offline greedy baselines and significantly outperforming standard random or scheduled sampling strategies.
Introduction
Environmental monitoring using autonomous underwater vehicles (AUVs) presents a unique challenge in sequential decision-making. Equipped with a limited number of physical sample containers, an AUV must decide whether to collect a sample at its current location without the ability to revisit past sites or discard previously collected samples. This scenario is a practical manifestation of the "secretary problem," where the goal is to select the best $k$ items from a sequence of $N$ observations.
Traditional solutions to the secretary problem assume that observations arrive in a random order. However, environmental variables such as temperature, salinity, and biological concentrations are heavily structured by periodic cycles (e.g., tidal, diurnal, or annual). Applying random-order algorithms to such structured streams often leads to sub-optimal outcomes, such as exhausting sampling capacity during the first peak of a cycle and missing more informative opportunities later in the mission.
The Periodic Secretary Algorithm
The proposed method addresses these limitations by incorporating periodicity into the selection logic. The algorithm operates in two distinct phases:
- Observation Phase: For a duration equal to one full period ($T$), the agent observes the environment without collecting any samples. This phase allows the agent to build a "reference set" that captures the typical range of environmental variability and informativeness.
- Sampling Phase: Following the observation phase, the agent evaluates each new observation against the reference set. A sample is collected if its calculated utility exceeds the maximum utility observed during the first phase, adjusted by a threshold parameter $\lambda$.
Utility is defined using an information-theoretic criterion: entropy reduction. By modeling the environment with a Gaussian Process (GP), the agent can estimate the informativeness of a potential sample based on easily observable covariates (e.g., temperature) even before the sample is processed.
The parameter $\lambda$ serves as a critical tuning mechanism. A small $\lambda$ enforces strict selectivity, ensuring high-quality samples but risking under-utilization of capacity. Conversely, a larger $\lambda$ encourages more frequent sampling, ensuring all bottles are filled but potentially at the cost of lower average sample utility.
Experimental Evaluation
The algorithm was validated using both synthetic periodic data and the Martha’s Vineyard Coastal Observatory (MVCO) dataset. The MVCO dataset spans seven years (2009–2016) and includes high-resolution measurements of water temperature and time-of-year, alongside ground-truth counts of the phytoplankton species Guinardia flaccida. This dataset provides a rigorous testbed for evaluating how well the algorithm can predict complex biological variables from periodic environmental covariates.
Results and Discussion
The Periodic Secretary Algorithm demonstrated significant improvements over baseline methods, including random sampling, fixed-interval scheduling, and the submodular secretary algorithm.
Key findings include:
- Near-Optimality: The algorithm achieved cumulative entropy reduction nearly identical to an offline greedy algorithm, which represents the theoretical upper bound by having access to the entire dataset a priori.
- Predictive Accuracy: Samples selected via the periodic secretary method led to lower mean-squared error (MSE) when predicting phytoplankton concentrations in unsampled regions compared to all other online methods.
- Robust Coverage: The method ensured a more uniform and dense coverage of the environmental state space, preventing the "clustering" of samples that often plagues scheduled or random approaches in periodic environments.
Conclusion
By treating environmental structure as a feature rather than a nuisance, the Periodic Secretary Algorithm provides a robust framework for real-time sample selection in marine robotics. Future work will focus on automating the tuning of the threshold parameter $\lambda$ and extending the approach to non-periodic spatiotemporal structures such as oceanic fronts or gradients. This research bridges the gap between sequential decision theory and the practical requirements of autonomous environmental science.
Summary updated