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 non-trivial 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 complex 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 which 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 to do streaming, irrevocable sample selection.
Streaming, irrevocable-choice algorithms have been applied to select samples in environmental monitoring and robotics applications, even when the data streams in question violate random arrival order assumptions. @cite_18 apply the submodular secretary algorithm on-board an AUV to select @math water samples with the highest concentration of a harmful phytoplankton and use a GP model to predict these concentrations. However, they directly apply the submodular secretary algorithm, despite their data being spatially correlated, which could lead to arbitrarily poor sampling performance. @cite_0 also deploy a modified multiple-choice secretary algorithm on an AUV to choose the most informative images to send back to a ground station. However, this approach is incompatible with the use of information-theoretic utility functions, requires that data arrive in random order, and does not account for spatiotemporal structure in an image stream.
@cite_0 @cite_18
2161331788 1938668859
In this paper we focus on the task of summarizing observations made by a mobile robot on a trajectory. A navigation summary is the synopsis of these observations. We pose the problem of generating navigation summaries as a sampling problem. The goal is to select a few samples from the set of all observations, which are characteristic of the environment, and capture its mean properties and surprises. We define the surprise score of an observation as its distance to the closest sample in the summary. Hence, an ideal summary is defined to have a low mean and a low max surprise score, measured over all the observations. We present three different strategies for solving this sampling problem. Of these, we show that the kCover sampling algorithm produces summaries with low mean and max surprise scores; even in the presence of noise. These results are demonstrated on datasets acquired in different robotics context. Robotic sampling is attractive in many field robotics applications that require persistent collection of physical samples for ex-situ analysis. Examples abound in the earth sciences in studies involving the collection of rock, soil, and water samples for laboratory analysis. In our test domain, marine ecosystem monitoring, detailed understanding of plankton ecology requires laboratory analysis of water samples, but predictions using physical and chemical properties measured in real-time by sensors aboard an autonomous underwater vehicle AUV can guide sample collection decisions. In this paper, we present a data-driven and opportunistic sampling strategy to minimize cumulative regret for batches of plankton samples acquired by an AUV over multiple surveys. Samples are labeled at the end of each survey, and used to update a probabilistic model that guides sampling during subsequent surveys. During a survey, the AUV makes irrevocable sample collection decisions online for a sequential stream of candidates, with no knowledge of the quality of future samples. In addition to extensive simulations using historical field data, we present results from a one-day field trial where beginning with a prior model learned from data collected and labeled in an earlier campaign, the AUV collected water samples with a high abundance of a pre-specified planktonic target. This is the first time such a field experiment has been carried out in its entirety in a data-driven fashion, in effect ?closing the loop? on a significant and relevant ecosystem monitoring problem while allowing domain experts marine ecologists to specify the mission at a relatively high level.