Near-optimal Irrevocable Sample Selection for Periodic Data Streams with Applications to Marine Robotics

Genevieve Flaspohler, Nicholas Roy, Yogesh Girdhar

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:

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

Two-phase sampling strategy based on periodic observation.

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.

Performance comparison of sampling algorithms on the MVCO dataset.

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

Abstract

We consider the task of monitoring spatiotemporal phenomena in real-time by deploying limited sampling resources at locations of interest irrevocably and without knowledge of future observations. This task can be modeled as an instance of the classical secretary problem. Although this problem has been studied extensively in theoretical domains, existing algorithms require that data arrive in random order to provide performance guarantees. These algorithms will perform arbitrarily poorly on data streams such as those encountered in robotics and environmental monitoring domains, which tend to have spatiotemporal structure. We focus on the problem of selecting representative samples from phenomena with periodic structure and introduce a novel sample selection algorithm that recovers a near-optimal sample set according to any monotone submodular utility function. We evaluate our algorithm on a seven-year environmental dataset collected at the Martha's Vineyard Coastal Observatory and show that it selects phytoplankton sample locations that are nearly optimal in an information-theoretic sense for predicting phytoplankton concentrations in locations that were not directly sampled. The proposed periodic secretary algorithm can be used with theoretical performance guarantees in many real-time sensing and robotics applications for streaming, irrevocable sample selection from periodic data streams.
BibTeX
@inproceedings{flaspohler2018near,
  author = {Genevieve Flaspohler and Nicholas Roy and Yogesh Girdhar},
  title = {{Near-optimal Irrevocable Sample Selection for Periodic Data Streams with Applications to Marine Robotics}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2018},
  doi = {10.1109/icra.2018.8460709},
}
Figure