Near-optimal irrevocable sample selection for periodic data streams with applications to marine robotics

Genevieve Flaspohler, Nicholas Roy, Yogesh Girdhar

TL;DR

This paper introduces the periodic secretary algorithm, a novel approach for real-time, irrevocable sample selection in structured data streams. By leveraging the periodic nature of environmental phenomena, the algorithm achieves near-optimal performance for submodular utility functions, overcoming the limitations of traditional secretary algorithms that fail when data is spatiotemporally correlated.

What Problem Does This Paper Address?

In many robotics and environmental monitoring tasks, an agent (like an Autonomous Underwater Vehicle, or AUV) must decide in real-time whether to collect a physical sample. These decisions are often irrevocable: once a location is passed, the agent cannot return, and once a sample container is used, it cannot be emptied.

This is a classic "secretary problem." However, standard theoretical solutions assume that data arrives in a random order. In the real world, environmental data is highly structured—temperature, salinity, and biological activity are correlated in space and time. If you apply a random-order algorithm to a structured stream, it performs poorly. The authors specifically target periodic data streams (e.g., daily or annual cycles), which are ubiquitous in nature but violate the assumptions of existing streaming selection methods.

Streaming irrevocable sample selection: An AUV must decide which water samples are most informative along a fixed trajectory.

Methods

The authors propose a two-stage periodic secretary algorithm designed to maximize a monotone submodular utility function (specifically, the entropy criterion).

  1. Observation Phase: The algorithm observes the data stream for one full period ($T$) without taking any samples. This builds a "reference set" ($U_R$) that represents the range of possible observations.
  2. Sampling Phase: For the remainder of the mission, the algorithm compares the utility of the current observation to the maximum utility found in the reference set.
  3. Noise-Aware Thresholding: To handle noise, they introduce a parameter $\lambda$. A sample is collected if its utility is within $\lambda$ of the maximum reference utility.
  4. Dynamic Updating: Because the utility function is submodular (meaning there are diminishing returns), the reference set's utility values are updated every time a new sample is collected.

The researchers use Gaussian Processes (GPs) to model the data. A key advantage of GPs is that the uncertainty (entropy) at a new location depends only on the locations of previous samples, not the values measured. This allows the AUV to calculate the information gain of a potential sample in real-time, even if the actual quantity of interest (like plankton concentration) requires slow, offline lab analysis.

The algorithm assumes data is approximately periodic with Gaussian noise.

Datasets

  • Synthetic Periodic Data: A noisy sine-wave-based stream used to theoretically validate the algorithm and demonstrate how to tune the $\lambda$ parameter.
  • MVCO Dataset: A massive seven-year environmental dataset (2009–2016) from the Martha’s Vineyard Coastal Observatory. It includes water temperature and counts of the phytoplankton species Guinardia flaccida. This real-world data exhibits strong annual periodicity.
The MVCO dataset showing annual cycles in temperature and plankton counts.

Key Insights and Ideas

  • Structure as an Asset: Instead of trying to "de-correlate" the data, the algorithm uses periodicity as a "preview." The first period acts as a representative sample of what the agent is likely to see later.
  • The $\lambda$ Trade-off: Tuning $\lambda$ is critical. If $\lambda$ is too small, the algorithm is too picky and might reach the end of the mission without filling its sample containers. If $\lambda$ is too large, it samples too early and misses higher-quality opportunities later.
  • Submodularity is Key: By using submodular functions, the authors can provide provable lower bounds on performance, ensuring the selected set is "near-optimal" compared to an offline algorithm that could see the whole dataset at once.
Visualizing how the threshold $\lambda$ affects the sampling process over multiple periods.

Key Results

  • Near-Optimal Performance: On the MVCO dataset, the periodic secretary algorithm (with a well-tuned $\lambda$) achieved entropy reduction nearly identical to the offline greedy algorithm, which is the gold standard but impossible to run in real-time.
  • Outperforming the State-of-the-Art: It significantly outperformed the "submodular secretary algorithm," which is the current standard for streaming submodular maximization but fails on non-random data.
  • Better Science: When the selected samples were used to predict plankton concentrations at unsampled locations, the periodic secretary method resulted in the lowest Mean Squared Error (MSE) among all streaming baselines.
Quantitative results showing the periodic algorithm achieving higher utility and lower prediction error than baselines.

Limitations and Future Work

  • Known Periodicity: The algorithm currently assumes the period $T$ is known or can be estimated accurately. While many natural cycles are predictable, others might be more complex.
  • Parameter Tuning: While the authors provide a way to tune $\lambda$ through simulation, they note that finding a closed-form solution for the optimal $\lambda$ based on noise characteristics is an open question.
  • Broader Spatiotemporal Structures: The current work focuses on periodicity. The authors suggest that similar techniques could be developed for other types of structured data, such as streams with linear trends or evolving correlations.

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